In the Optimal Bloom FIlters and Adapative Merging for LSM-Trees paper, section 4, the authors observe that the lookup cost for an LSM-Tree is proportional to the sum of false positive rates of all the bloom filters. The authors provide equations/algorithms to determine the optimal FPR for each level, which we can use to initialise bloom filters.
We will implement this "Monkey"-style allocation of bits to bloom filters. Note that:
There is a difference between the analysis for zero result lookups and non-zero-result lookups. However, we can assume that for the UTxO case, all lookups will be non-zero-result lookups.
It would be good if the algorithm is adaptive in the sense that it accounts for new levels being added over time, which changes the optimal allocation.
Appendix B provides an algorithm for (re-)allocating bits to bloom filters based on the actual number of entries per run, which can vary, but not greatly in our implementation: there is a bound on the number of entries in a run
In general, I think the algorithm should be parameterised with: (i) the total memory budget for bloom filters, and (ii) the current levels. It's not clear to me that the paper provides an algorithm of this shape (maybe appendix B?), but you'd probably be able to rearrange the existing equations/algorithms to fit our needs.
In the Optimal Bloom FIlters and Adapative Merging for LSM-Trees paper, section 4, the authors observe that the lookup cost for an LSM-Tree is proportional to the sum of false positive rates of all the bloom filters. The authors provide equations/algorithms to determine the optimal FPR for each level, which we can use to initialise bloom filters.
We will implement this "Monkey"-style allocation of bits to bloom filters. Note that:
In general, I think the algorithm should be parameterised with: (i) the total memory budget for bloom filters, and (ii) the current levels. It's not clear to me that the paper provides an algorithm of this shape (maybe appendix B?), but you'd probably be able to rearrange the existing equations/algorithms to fit our needs.
Previous discussion, might be interesting to look at: https://github.com/IntersectMBO/lsm-tree/pull/210#discussion_r1598660727. Not everything I've mentioned there is relevant or correct, but it shows a dump of thoughts we had before on the topic.