google / google/leveldb

A little confused about the bloom filter

Open
#1,257 2 comments 0 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
39.4k
Forks
8.2k
PR merge metrics
No merged PRs in 30d

Description

In the code of bloom.cc, I found that the following code to create bloom filter:

```c++
// Compute bloom filter size (in both bits and bytes)
size_t bits = n * bits_per_key_;

// For small n, we can see a very high false positive rate. Fix it
// by enforcing a minimum bloom filter length.
if (bits < 64) bits = 64;

size_t bytes = (bits + 7) / 8;
bits = bytes * 8;
const size_t init_size = dst->size();
dst->resize(init_size + bytes, 0);
dst->push_back(static_cast(k_)); // Remember # of probes in filter
```

This means that the bloom filter should be at least has a size of 9.
But in the later code in `bool KeyMayMatch(const Slice& key, const Slice& bloom_filter) const override`, I found the following code:

```c++
const size_t len = bloom_filter.size();
if (len < 2) return false;
```

I guess that these are used to test the **completeness** of the bloom filter. But I wonder that should the length be 9? Or maybe I mistakenly understood them?

I am eager for an answer! And I am appreciate if you can help me! Thanks!

Contributor guide

Open the contributing guide

Research direction

Start in bloom.cc by reading the filter-construction code alongside KeyMayMatch and tracing how the stored byte length and probe count are interpreted. Compare the minimum-size check with the construction path, then document the relationship and clarify the issue if the existing comments do not make it clear.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp
Domain
database
Issue type
Documentation
Difficulty
2/5
Estimated time
1-3 hours
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
30/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.