LRU Trusts Recency; a Bloom Filter Is Only Sure About 'No'

In one line

A cache is a bet on guessing "what will be used again soon," and LRU bets on "what was just used will be used again soon." A Bloom filter does the opposite: it promises only "definitely not present," and in exchange it carries a set in very few bits. You have to know what each structure trusts before you use it, or the numbers will not come out as you expect.

Why this was needed

The moment you put a fast store in front of a slow one, two questions appear. What do you throw away when space runs out? And do you really have to go all the way to the slow side to look for something that was never there in the first place?

The textbook answer to the first question is LRU (least recently used). The functools.lru_cache documentation says an LRU cache works best "when the most recent calls are the best predictors of upcoming calls," and gives as an example the popular articles of a news server that change every day. Conversely, for access patterns that break that assumption, such as a batch or backfill that scans every key once, LRU honors keys that will never come again as the "most recent," and pushes out the keys that are actually used often. The Cache replacement policies entry calls this cache pollution.

The second question is where the Bloom filter comes in. For lookups where the answer is mostly "not present," such as checking whether someone has signed up, filtering out already-seen URLs, or bot requests hammering keys that do not exist, even if you put the negative results into the cache, they get pushed out quickly when the key space is large. The survey by Broder and Mitzenmacher, Network Applications of Bloom Filters: A Survey (Internet Mathematics, vol. 1, no. 4), summarizes this as the "Bloom filter principle": whenever you use a list or set, space is precious, and you can reduce the impact of false positives, consider a Bloom filter.

How it works

LRU in O(1). Three operations are needed: look up by key, mark something as "just used," and discard the least recently used. A hash table does the first, and a doubly linked list does the other two in constant time (detach a node and attach it at the end, and detach the front). In Python, OrderedDict already has this combination. The documentation says OrderedDict is designed to be good at reordering operations and is well suited to building various kinds of LRU caches, and it provides move_to_end(key) (KeyError if the key is missing) and popitem(last=False) (pops in FIFO order).

Operation	LRU	FIFO
get hit	Move it to the end (most recent)	Leave it as is
put on an existing key	Update the value and move to the end	Update only the value
On overflow	Remove the front (least recently used)	Remove the front (first to enter)

That one first row of the table is almost the whole difference between the two policies. So an LRU that forgets to update recency in get is a FIFO in name only, and its hit count quietly goes down. If you manage the order with a list, remove is O(n), so it gets slower as the capacity grows, which does not show up in a small test.

Real caches are not exact LRU either. The Redis eviction documentation explains that Redis uses an approximation that picks a few keys at random and discards the least recently used among them, because true LRU needs more memory (the sample size is maxmemory-samples).

The Bloom filter. It consists of an m-bit array and k hashes. When adding, you turn on k positions to 1, and when querying, if all k positions are 1 the answer is "maybe present," and if even one is 0 it is "definitely not present." Bits that were turned on are never turned off, so there are no false negatives for keys that were added. By the calculation in section 2.1 of the survey, the false positive rate after adding n keys is about (1 − e^(−kn/m))^k, and once m and n are fixed, it is smallest at k = (m/n)·ln 2. Section 2.2 gives the bits needed for a target false positive rate p as m ≈ n·log2(1/p) / ln 2. As an example, with n = 1,000 and p = 1%, m is about 9,586 bits (a little over 1.2KB) and k is 7.

You also do not need to compute k independent hashes separately. Less Hashing, Same Performance by Kirsch and Mitzenmacher (2008) showed that building g_i(x) = h1(x) + i·h2(x) from two hashes h1 and h2 does not worsen the asymptotic false positive rate. This lab extracts h1 and h2 from the sha256 digest (32 bytes) of hashlib. The reason it does not use the built-in hash() is that, as the PYTHONHASHSEED documentation says, the seed for string hashes is random by default, so a filter built by another process cannot be read with the same rule.

When you measure the false positive rate, the denominator is the number of queries for keys that are truly absent. If you divide by all queries, the value shrinks by the fraction of present keys and the filter looks better than it really is.

What it looks like in the field

Among ClickHouse's skip indexes, bloom_filter takes a single tolerated false positive rate as an argument (default 0.025), and the documentation says a false positive only means reading a few unnecessary blocks, so it is not a big problem. The "ClickHouse — A Columnar Analytics Database from the Inside" course shows that scene with actual granule counts. The choice of expiry and eviction policy and cache-aside are covered by the "Redis and Caching" course, and how the same locality logic shows up in the CPU cache hierarchy is covered by the "Computer Architecture" course. This module is the place where you build the data structures underneath them yourself and confirm them with numbers.

What you will do in the next lab

You will measure the hit counts of LRU and FIFO by capacity on a skewed access trace, and count how many hot keys a one-pass scan pushes out. Then you will choose m and k with the formula, build a Bloom filter with a pinned hash rule and measure its false positive rate, and then calculate how many DB lookups are saved when the filter is placed in front of the LRU.