Bloom filters and checksums

Distributed storage constantly asks two cheap-sounding questions. "Might this key exist in that file on disk?" and "Is this block of data still exactly what we wrote?" Answering the first by reading the file wastes a disk read when the answer is no. Answering the second by trusting the disk is dangerous, because disks and networks corrupt data silently. Two small patterns solve these: the Bloom filter and the checksum.

A Bloom filter is a compact structure that tells you either "this item is definitely not in the set" or "it might be". It never gives a false negative. It can give a false positive, which is acceptable whenever a wrong "maybe" only costs a little extra work.

It is a bit array of m bits, all starting at 0, and k independent hash functions.

• Add an item: compute its k hash values, each giving a position in the array, and set those k bits to 1.
• Check an item: compute the same k positions. If any bit is 0, the item was never added, so answer "definitely not". If all are 1, answer "maybe".

A false positive happens when other items have, by chance, set all k bits of a new item. As more items are added, more bits are set, so the false positive rate rises.

With m bits, n items and k hash functions, the false positive probability is about (1 - e^(-kn/m))^k. The best k is (m/n) x ln 2. Solving for size, you need about:

• 9.6 bits per item for a 1 percent false positive rate, with k about 7.
• 14.4 bits per item for 0.1 percent, with k about 10.

For 1 billion items at 1 percent, that is about 9.6 Gbit, or 1.2 GB. Storing the items themselves would take tens of gigabytes. A Bloom filter trades a small error for a huge saving in space.

• No deletion: clearing a bit could erase other items. A counting Bloom filter uses small counters instead of bits to allow removal, at several times the space.
• No listing: you cannot get the items back out.
• Fixed capacity: a filter sized for n items degrades if you add far more. Scalable filters chain new filters as they fill.

• Cassandra and Bigtable keep one per SSTable, so a read skips files that definitely lack the key, avoiding most disk reads.
• Web crawlers use one to test whether a URL was already visited.
• Caches use one to avoid searching for keys that do not exist, which would otherwise always miss and hit the database.

A checksum is a short fixed-size value computed from data by a function. Store it with the data. When reading, recompute it and compare. If they differ, the data changed, so it is corrupt.

• CRC (cyclic redundancy check) is very fast and catches accidental errors such as flipped bits. It is the common choice for storage and networks, often 32 bits.
• Cryptographic hashes such as SHA-256 are slower but make deliberate tampering infeasible.

Systems apply this everywhere. GFS stores a checksum for every 64 KB block and verifies it on every read. Kafka records a CRC on each message. A node that finds a bad block fetches a good copy from another replica and repairs it.

A checksum detects errors but cannot correct them. Correction needs redundancy, such as replicas, error-correcting codes or erasure coding. A plain checksum also does not defend against an attacker, who can change the data and recompute it. For that, use a keyed signature. Finally, verify end to end: check the checksum where the data is finally used, since corruption can happen in any layer between.

• Bloom filter: tiny, fast, no false negatives, some false positives, no deletes.
• Checksum: tiny, fast, detects corruption, does not fix it.
• Both spend a little computation to avoid a much larger cost: a wasted disk read, or a silently wrong answer.