IntersectMBO / IntersectMBO/lsm-tree
[FEATURE] Implement Monkey-style bloom filter allocation
- Dominant language
- Haskell
- Stars
- 53
- Forks
- 17
- Avg merge
- 2d 3h
- Merged PRs (30d)
- 4
Description
That is, a style of bloom filter allocation based on Niv Dayan, Manos Athanassoulis, and Stratos Idreos. 2017. "Monkey: Optimal Navigable Key-Value Store." [doi:10.1145/3035918.3064054](https://doi.org/10.1145/3035918.3064054)
We used to have a version of this Monkey allocation, but it was removed in https://github.com/IntersectMBO/lsm-tree/pull/617 because it did not work very well and there were some bugs.
Implementing the Monkey allocation strategy is a little complex. For example, it's hard to compute the allocation dynamically as a table grows -- the algorithm requires some static information like the workload and table size. Moreover, our implementation of the merge schedule is somewhat atypical and changes the complexity analysis from the paper.
Having a fixed allocation number, like a requested FPR or requested BPE, is arguably simpler. However, if one really wanted to optimise their bloom filter allocation strategy, then it would be worth looking into re-implementing the Monkey strategy
Contributor guide
Assessment
This issue has not been assessed yet.