Putting It All Together

You have built a Bloom filter from its bits up: sizing, hashing, the variants, the byte format, and the monitoring. This capstone uses all of it in the pattern that real systems use most: a Bloom filter in front of a cache. After it, your program serves reads from a cache, skips the cache entirely for keys the filter has never seen, tolerates invalidations, and rebuilds the filter when stale bits pile up.

What you built

The pattern

A read first asks the filter about the key. Only a MAYBE proceeds to the cache.

• Filter says NO: reply BLOOM_MISS. The key was never stored, so skip the cache lookup. This is where the filter earns its memory.
• Filter says MAYBE and the key is in the cache: reply HIT <value>.
• Filter says MAYBE and the key is not in the cache: reply MISS_BLOOM_FP. The filter was wrong, or the key was removed and the filter cannot forget. Either way one cache lookup was spent.

PUT_CACHE writes to both the cache and the filter. INVALIDATE removes the key from the cache only, because a plain Bloom filter cannot delete: its bits may belong to other keys. So an invalidated key keeps answering MAYBE, and every GET of it costs a wasted lookup (MISS_BLOOM_FP).

Paying the debt: rebuild

Stale bits accumulate, and FILL rises even though the live key count does not. The cure is a rebuild: clear the bit array and set the bits again for every key that is still in the cache. REBUILD does exactly that, keeping the same m and k. Afterwards invalidated keys read NO again and FILL falls to what the live keys justify.

Here is a trace with m and k from INIT 20 0.05. Watch the invalidated key user:2 stay MAYBE until the rebuild:

command                reply            filter
PUT_CACHE user:1 ada   OK               fill 0.0320
PUT_CACHE user:2 bob   OK               fill 0.0640
PUT_CACHE user:3 eve   OK               fill 0.0960
GET user:2             HIT bob          fill 0.0960
GET user:9             BLOOM_MISS       fill 0.0960
INVALIDATE user:2      OK               fill 0.0960
GET user:2             MISS_BLOOM_FP    fill 0.0960
REBUILD                OK rebuilt=2     fill 0.0640
GET user:2             BLOOM_MISS       fill 0.0640
GET user:3             HIT eve          fill 0.0640

Counters

hits counts HIT replies. bloom_misses counts BLOOM_MISS replies, which never reach the cache and so are not in misses. misses counts cache lookups that found nothing, so it equals bloom_fp in this design. INIT resets all four, the cache and the filter.

Choosing a structure

• Plain Bloom: add and test only, smallest and simplest.
• Counting Bloom or Cuckoo: you must delete. Cuckoo is smaller and has bounded lookups, but inserts can fail.
• Scalable Bloom: the number of keys is unknown.
• A hash set instead: small sets, or whenever a false positive is harmful. Below a few hundred keys a set is smaller and exact.
• HyperLogLog is a different tool. It estimates how many distinct keys exist; it cannot say whether one particular key was seen.

Common mistakes

• Counting BLOOM_MISS as a miss. The cache was never consulted.
• Forgetting that a replaced PUT_CACHE value must be overwritten, not duplicated.
• Rebuilding from the old filter instead of from the cache's current keys.
• Splitting the value on spaces: everything after the key and one space is the value.
• Not resetting the cache and counters on INIT.

Your exercise

The starter sizes the filter and provides the cache. You write PUT_CACHE, GET, INVALIDATE, REBUILD, FILL and STATS.