cockroachdb / cockroachdb/pebble

prototype modular bloom filters

Open
#3,734 2 comments 0 reactions 0 assignees View on GitHub
A-storage C-performance E-starter T-storage
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.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.