ulearn/systems

topics / data-caching

Bloom Filter

A HashSet of every key won't fit in RAM, and asking the disk costs a seek every time, even for keys that aren't there. A Bloom filter answers “definitely not” from a few bits of memory, so the disk only hears about keys that might exist.

SimulateStudyGlossary
New here? Hover any underlined word for a quick definition, orstart with Study →
0%bit saturation
0items inserted (n)
0%theoretical FP rate
0disk seeks prevented
0false positives
0 msdisk time wasted
1 · KEY → k HASHES (IN MEMORY)key—Each hash turns the key into one bit index.2 · BIT ARRAY — m = 128, 0 set (0%)016324864809611200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000RESULTWaiting for a keyInsert sets k bits to 1.Check reads the same k bits.3 · DATABASE ON DISK — only reached when the filter says “maybe”SSTable 1sorted, on diskSSTable 2sorted, on diskSSTable 3sorted, on diskSSTable 4sorted, on diskread headLAST CHECK LATENCY—no checks yetbit = 1bit = 0probed by hᵢ0 bit → definitely absentcleared by deleteneeded disk readwasted disk seek

Event log

Waiting for traffic…

Keys

Leave the box blank and Insert adds a random user:NNNNN, while Check asks about one that was never inserted. Click a recent key to check it again.

Filter shape

128
3

Changing either one rebuilds the filter from the stored keys — a real Bloom filter can't be resized in place.

Stress it

Every one of these is a negative lookup. Count how many the filter turns away before they reach the disk.

Keeps inserting until 90% of the bits are 1. Then query absent keys again and watch false positives leak through.

Try to delete

Clears the key's k bits back to 0. With the box blank, it picks the stored key that shares the most bits with others. Any key that relied on one of those bits now gets a false negative.