Bloom filters

01Represent possible membership with shared bits

A storage service receives many requests for keys that do not exist. Before an expensive disk lookup, it can use a small bit array to rule out some definite misses. This structure is a Bloom filter; it does not store the full records.

Build a toy filter with twelve positions numbered 0 through 11:

1. Start every bit at zero. A bit holds either zero or one.
2. Run repeatable hash calculations on cat. Suppose they choose positions 2 and 7. Insert cat by setting those bits to one.
3. Insert dog at its positions 7 and 10. The set positions are now 2, 7, and 10; bit 7 is shared.
4. To test a key, calculate its positions using the same key bytes and hash settings.
5. If any required bit is zero, that key was not successfully inserted into this filter.
6. If every required bit is one, the key is only possibly present. Another key may have set those bits.

For example, fox chooses positions 2 and 10. Both are one although fox was never inserted. This is a false positive. owl chooses 1 and 9; the zero at 1 rules out its insertion into this filter.

An intact ordinary insert-only filter does not reject a successfully inserted key after insertion completes: all its required bits remain one. This no-false-negative property assumes unchanged hashes and key encoding, no damaged bits, and no unsafe deletion. It does not prove every current database record has already reached the filter.

02Use it as a gate, not an exact authority

Use the filter as a preliminary check, followed by an exact store when needed:

1. A positive means “possibly present.” Ask the exact store for the record or final decision.
2. A negative can avoid that lookup only if all relevant committed keys are already covered by the filter or another checked complete set.
3. If coverage is uncertain, query the exact source instead of hiding a potentially real record.

Estimate the benefit separately from the guarantee:

1. Assume 10,000 lookups for keys actually absent from the exact store.
2. At a 1% false-positive rate, about 10000 × 0.01 = 100 still require exact lookups.
3. About 9,900 avoid those expensive misses under complete coverage. Present keys also pass and still need the record when its contents or authoritative decision matters.

Size the filter for expected insertions. More bits per key generally reduce false positives; inserting too many keys into a fixed array raises them as more positions become one.

A standard approximate model uses:

• m: the number of bits.
• n: the number of inserted keys.
• k: the number of hash positions per key.
• False-positive probability: (1−e^(−kn/m))^k, where e is the natural exponential constant.
• A useful hash count near (m/n) × ln(2), with ln(2) ≈ 0.693.

For one million keys and about 1% false positives, the model suggests roughly 9.6 million bits. Divide by eight for 1.2 million bytes, or 1.2 MB of bit-array storage, and use about seven hash positions. Extra structures add overhead. These estimates depend on the hash-distribution assumptions; they are not guarantees for arbitrary inputs.

03Keep coverage and deletion safe

A database saves a new document at 12:00:01, but the filter refreshes only once a minute. A 12:00:02 lookup may test negative because the new key was never inserted into that filter. Skipping the database now can hide a real document.

Protect coverage explicitly:

1. The simplest fallback queries the exact database whenever coverage is uncertain.
2. One concrete alternative saves the document and a recent-key row in the same database transaction. After a filter negative, check that small recent-key table with a read that can see completed inserts. A key found there requires the ordinary exact document lookup.
3. Build a replacement filter from a database snapshot and record which committed inserts it includes. Switch readers to that build before removing the recent-key rows it includes. Keep those rows while any reader can still use an older filter, and keep newer rows until a later build includes them. If the service cannot establish which build readers use, do the full database lookup instead.
4. If the recent-key check or rebuild coverage cannot be established, use the full database lookup. This alternative adds a recent-table lookup to negative requests; compare that cost with the expensive source probes it saves.

Deletion has a different hazard:

1. Cat and dog both use bit 7 in the example.
2. Clearing bit 7 to delete dog makes cat test negative even though cat was inserted.
3. Ordinary shared bits therefore cannot be cleared safely for individual deletion.

Counting Bloom filters store counters instead of single bits. Deleting dog reduces its position counters while preserving counts contributed by cat. This requires correct insertion/deletion bookkeeping and overflow handling; deleting an uninserted key can also damage the counts. Rebuilding from the exact source is another option.

Separate consequences:

• A deleted key that still tests positive usually costs an extra exact lookup, which returns absent.
• A committed new key missing from the filter can cause a wrong absence if negatives bypass the source.
• A positive never proves username uniqueness, permission, or a completed payment. Use the exact authoritative operation, including its concurrency rules.

Monitor insert count, observed false positives, and rebuild coverage. A good miss-saving estimate does not replace a complete view of which keys the filter represents.