I can take this one. @criccomini what did you intend the placeholder label to mean? Is it supposed to be work that is relatively large or undefined in scope and needs further breakdown?

My intent here is to implement something basic that should work reasonably well for most cases. I'm thinking:

maintain a single filter per SST. Alternatively, we could maintain per-block filters but I don't see the benefit there other than keeping the in-memory state required to build the filter constrained. But even with really large SSTs I don't expect it to be a problem (e.g. for a 10GB SST and 128 byte entrires you'd need ~100MB of memory to maintain the filter). And there are drawbacks to small SSTs (small filters and having to read the index to use the filter, e.g. see https://github.com/facebook/rocksdb/wiki/RocksDB-Bloom-Filter).
The filter will be a bloom filter (we can support more specialized filters later if we want). I'm still deciding whether to write my own or use one of the crates that are out there. I'll probably start with something that exists, but we'll probably want to move to our own implementation sooner than later to optimize building the filter (for example, to maintain key hashes instead of keys as we go along, which the crates I've found don't support).
I'll allow the user to configure the filter bits per key and the false positive percentage, and we can compute the required number of hashes.

Uh oh!

Add bloom filtering to SST fetches #11

Description

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions