Randomness and Probabilistic Structures

Sometimes the cheapest correct algorithm flips coins, and sometimes the cheapest useful structure is allowed to be wrong in a known, bounded way. A random pivot keeps quicksort fast on every input. A 1.8-megabyte Bloom filter tells Lantern that a term is definitely not among its 1.5 million index terms. A HyperLogLog counts billions of distinct visitors in 12 kilobytes with a typical error under 1%.

Small, fast and almost right, on purpose. The engineering is in the "almost": knowing which side the error falls on, how large it is, and what happens downstream when it strikes. A probabilistic structure with a cheap fallback is one of the best trades in computing; one without a fallback is a bug with good performance numbers.

Randomness Against Bad Inputs

Any fixed rule has a worst-case input, and real data or an attacker will find it. Quicksort with a first-element pivot, from Chapter 7, degrades to n² on sorted input. A hash table with a fixed hash function, from Chapter 5, degrades to a list when an attacker sends keys that collide. Choosing at random, a random pivot or a random hash seed per process, means no single input is bad every time, so the expected cost holds for every input rather than for an average one.

That guarantee holds only while the attacker cannot predict the random choices. A general-purpose generator seeded predictably does not provide that. Python's random module is documented as unsuitable for security purposes and points to the secrets module instead; the hash randomization Chapter 5 describes draws its seed from the operating system for the same reason.

Two Kinds of Randomized Algorithm

Some randomized algorithms are always right and random only in their running time. Quicksort with a random pivot returns exactly the same sorted list every time; only how long it takes varies, and a slow run becomes vanishingly unlikely as n grows.

Others are always fast and wrong with a small probability that the caller controls. The Miller–Rabin primality test declares a composite number "probably prime" with probability at most one in four per round, and the rounds are independent, so 40 rounds leave at most one chance in 2 to the 80th. That is how key generation finds primes hundreds of digits long quickly: it tests random candidates and accepts an error it has chosen to be negligible.

The Bloom Filter

A Bloom filter is a bit array plus k hash functions. Adding an item sets the k bits its hashes point to. Asking about an item checks the same k bits. If any of them is 0, the item was definitely never added, because adding it would have set that bit. If all of them are 1, the item is probably present, and "probably" is the catch: those bits may have been set by other items.

The figure uses 16 bits and three hash functions, computed from real hashes of each word. Adding "dispossessed" sets bits 3, 8 and 14. Adding "earthsea" sets bits 4, 2 and 9. Asking about "lathe" checks bits 13, 1 and 8. Bit 8 is set, by "dispossessed", but bits 13 and 1 are 0, so "lathe" was never added. The filter never stores the words themselves, only bits, which is where its size advantage comes from.

The error is one-sided. An item that was added is never reported absent, as long as nothing is removed. And nothing can be removed from a plain Bloom filter: clearing an item's bits could clear bits that other items share, which would make the filter lie in the one direction it promised never to.

Sizing the Error

The standard formulas, from the survey by Broder and Mitzenmacher, fix the size from two numbers: how many items the filter will hold and what false-positive rate is acceptable. About 9.6 bits per item with 7 hash functions gives a 1% rate. Each further 4.8 bits per item cuts the rate tenfold, so 0.1% costs about 14.4 bits per item.

import math

n, p = 1_500_000, 0.01                        # Lantern's terms, target rate
bits = -n * math.log(p) / math.log(2) ** 2
k = round(bits / n * math.log(2))
print(f"{bits / n:.1f} bits per term, {k} hashes, {bits / 8 / 1e6:.1f} MB")
print(f"at twice the terms: {(1 - math.exp(-k * 2 * n / bits)) ** k:.1%}")

# 9.6 bits per term, 7 hashes, 1.8 MB
# at twice the terms: 15.7%

The calculation above takes Lantern's 1.5 million index terms and a 1% target. The first formula gives the total number of bits, the second the number of hash functions, and the last line predicts the rate if the filter receives twice the terms it was sized for. Run on CPython 3.15, it prints 9.6 bits per term, 7 hashes and 1.8 megabytes, and a rate of 15.7% at twice the terms.

So for Lantern, 1% costs 1.8 megabytes, about a thousandth of the 1.8-gigabyte index it protects. The chart shows the other half of the bargain. The rate is 1% at the design count of 1.5 million and climbs steeply past it, to about 16% at 3 million. Nothing fails or warns along the way; the filter quietly gets less useful.

Lantern's "Definitely Not in the Catalogue"

Before reading a term's postings list from the on-disk index, Lantern asks the filter. A "no" skips the read entirely and sends the term straight to typo matching, the edit-distance search of the Dynamic Programming topic. A "maybe" pays for the read. A term that is not in the index still gets a "maybe" about once in a hundred times, and then the read finds nothing, which costs one wasted lookup and nothing else. The false positive is cheap because the fallback is the normal path.

Storage engines built on log-structured files use filters the same way. RocksDB, for example, when configured with a filter policy, embeds a Bloom filter in each data file it writes, so a lookup can skip every file that cannot hold the key without reading it.

HyperLogLog and What "Almost" Costs

Counting distinct items exactly means remembering every item seen. A set of a billion 8-byte visitor ids takes 8 gigabytes before any overhead. HyperLogLog counts them approximately in a fixed, tiny space. It hashes each item and looks at the run of leading zero bits in the hash. A run of 20 zeros happens about once in a million random hashes, so seeing one suggests about a million distinct items have gone by. One such observation is noisy, so the structure splits the hashes into many buckets by their first few bits and keeps, per bucket, the longest run seen, then averages across buckets.

The figure runs a toy version with four buckets on eight visitor ids, two of them repeated. The first two bits of each hash choose the bucket, and the register keeps the largest count of leading zeros plus one. Repeated ids hash identically and never change a register, which is why the structure counts distinct items rather than events. Redis's implementation uses 16,384 buckets of 6 bits, 12 kilobytes at most, and documents a standard error of 0.81%; the memory stays the same whether the count is a thousand or a billion.

The price in both structures is an error bar that has to travel with the number, and a fallback that makes a wrong answer cheap. "About 1.2 million unique visitors, plus or minus 0.81%" is a fact. The same figure without the bar invites a decision the data cannot support.