cockroachdb / cockroachdb/pebble
prototype modular bloom filters
- Dominant language
- Go
- Stars
- 6k
- Forks
- 584
- Avg merge
- 16h 35m
- Merged PRs (30d)
- 5
Description
[LSM-Trees Under (Memory) Pressure](https://www.adms-conf.org/2022-camera-ready/ADMS22_mun.pdf) 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
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.