IntersectMBO / IntersectMBO/lsm-tree

[FEATURE] Implement Monkey-style bloom filter allocation

Open
#626 0 comments 0 reactions 0 assignees View on GitHub
enhancement lsm-tree priority: low
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.