Skip to content

[FEATURE] Implement Monkey-style bloom filter allocation #626

@jorisdral

Description

@jorisdral

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

We used to have a version of this Monkey allocation, but it was removed in #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

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementNew feature or request

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions