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

Implement Blocked Bloom Filters #78

Open
marvin-j97 opened this issue Nov 17, 2024 · 0 comments
Open

Implement Blocked Bloom Filters #78

marvin-j97 opened this issue Nov 17, 2024 · 0 comments
Labels
enhancement New feature or request good first issue Good for newcomers help wanted Extra attention is needed performance

Comments

@marvin-j97
Copy link
Contributor

marvin-j97 commented Nov 17, 2024

Implement Blocked Bloom Filters as an alternative to the current "standard" bloom filters and benchmark its impact on point reads and FPR.

Add a benchmark to https://github.com/fjall-rs/lsm-tree/blob/be649abf47554f98c41056681b8edb1b34ff3a57/benches/bloom.rs.

There is a "filter type" byte in the filter section of the Segment so we can variably switch out different filter types without breaking change:

assert_eq!(0, filter_type, "Invalid filter type");

0 = Standard bloom filter

The Segment "load from file" procedure needs to be adjusted to load the correct filter by matching on filter type byte, then we can use enum_dispatch as the top-level filter type

let filter = match filter_type {
  0 => Filter::StandardBloomFilter(load_bloom_filter(...)?),
  1 => Filter::BlockedBloomFilter(load_blocked_bloom_filter(...)?),
};

FilterType should also become an enum with conversion into a u8 (encode/decode trait).

@marvin-j97 marvin-j97 added enhancement New feature or request good first issue Good for newcomers help wanted Extra attention is needed performance labels Nov 17, 2024
marvin-j97 added a commit that referenced this issue Nov 17, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request good first issue Good for newcomers help wanted Extra attention is needed performance
Projects
None yet
Development

No branches or pull requests

1 participant