Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

prototype modular bloom filters #3734

Open
RaduBerinde opened this issue Jul 5, 2024 · 0 comments
Open

prototype modular bloom filters #3734

RaduBerinde opened this issue Jul 5, 2024 · 0 comments

Comments

@RaduBerinde
Copy link
Member

RaduBerinde commented Jul 5, 2024

LSM-Trees Under (Memory) Pressure introduces the idea of Modular Bloom filters.

The TL;DR is that instead of having a bloom filter with 10 bits per key, you can have (for example) two bloom filters, a smaller one with 2 bits per key and a larger one with 8 bits per key. When both are consulted, the false positive rate is the same as a single filter. But you have the flexibility to use just the small one.

We currently don't use bloom filters at all in L6 because they are two big. We could improve on this a lot by using just the small one in L6.

This is a possible intern project - it's interesting and fairly well contained.

Jira issue: PEBBLE-32

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
Status: Backlog
Development

No branches or pull requests

2 participants