Probabilistic Structures: Bloom Filters, Count-Min, HyperLogLog, Sampling and Consistent Hashing

#Why Approximate: Memory Against Exactness

Suppose you must answer "have I seen this item before?" for a billion items. A Python set answers exactly, but it stores every item whole. A set of a billion long strings will not fit in the memory of an ordinary machine. An exact answer to this question needs memory that grows with the number of items, because the structure must be able to tell any two different sets of items apart.

A count-min sketch may count too high, never too low. If you know which way the error goes, you can build a safe system around it.

Each tool answers one question. Membership: a Bloom filter. How often: a count-min sketch. How many different: HyperLogLog. A fair small sample: reservoir sampling. Which machine holds this key: consistent hashing, which is exact but uses the same hashing ideas at the same scale. In every case, time per operation is small and fixed, space is set by the error you accept, and the error is a formula you can read before you build anything.

#A Hash We Can Replay

import bisect
import hashlib
import math


def h(item, seed):
    """A seeded 64-bit hash. The same item and seed always give the same number."""
    data = f"{seed}:{item}".encode()
    return int.from_bytes(hashlib.sha256(data).digest()[:8], "big")


print(h("cat", 0))
print([h("cat", s) % 16 for s in range(3)], [h("dog", s) % 16 for s in range(3)])
print(h("cat", 0) == h("cat", 0), h("cat", 0) == h("cat", 1))
# Output:
# 17068036285650775687
# [7, 12, 3] [9, 3, 6]
# True False

The first line is the 64-bit number for cat with seed 0. The second line shows how three seeds give three different slots for the same item, taken modulo 16. Seeds 0, 1 and 2 act like three independent hash functions. Each call costs O(1) time, because it hashes a short string.

Every formula below assumes these hashes behave like fair dice: each output equally likely, and different seeds independent. Real hashes are only close to that.

#Bloom Filter: Bits and k Hashes

Here is a small filter traced by hand before any code: m is 16 and k is 2. We ran the two seeded hashes for each word. Adding cat sets bits 7 and 12. Adding dog sets 9 and 3. Adding emu sets 14 and 14, because both of its hashes landed on the same bit, which is allowed.

Now the code. We spend one byte per bit to keep it readable. A real filter packs eight bits to the byte, so it is eight times smaller.

class Bloom:
    """m bits and k hashes. add and might_contain cost O(k) time. The space is m bits."""

    def __init__(self, m, k):
        self.m, self.k = m, k
        self.bits = bytearray(m)             # one byte per bit, for readability

    def positions(self, item):
        return [h(item, seed) % self.m for seed in range(self.k)]

    def add(self, item):
        for p in self.positions(item):
            self.bits[p] = 1

    def might_contain(self, item):
        return all(self.bits[p] for p in self.positions(item))


b = Bloom(16, 2)
for w in ["cat", "dog", "emu"]:
    print("add", w, b.positions(w))
    b.add(w)
print("".join(map(str, b.bits)))
for w in ["cat", "ant", "bee"]:
    print(w, b.positions(w), b.might_contain(w))
# Output:
# add cat [7, 12]
# add dog [9, 3]
# add emu [14, 14]
# 0001000101001010
# cat [7, 12] True
# ant [0, 7] False
# bee [14, 7] True

The code matches the hand trace. Both operations touch k bits and nothing else, so each costs O(k) time however many items are stored. The size never changes. What changes is how full the card is, and that decides the error.

#How Often Does a Bloom Filter Lie

The filter lies only when an absent item finds all k of its bits already on. How likely is that? Count the bits.

Adding n items throws k times n darts at m bits. A single dart misses a given bit with probability 1 minus 1/m. After all the darts, a given bit is still off with probability (1 - 1/m) to the power kn, which is close to e^(-kn/m) when m is large.

So the fraction of bits that are on is about 1 - e^(-kn/m). An absent item reads k bits, each on with that probability, and all k must be on:

false-positive rate  p  ~  (1 - e^(-kn/m)) ^ k

The formula treats the k bits as independent, which is only approximately true. The real rate is a little higher, most visibly in small filters. Before measuring, commit to a guess.

Now measure it. The function below builds a filter, checks that every added item is found, and then queries 10,000 items that were never added.

def measure(n, m, k, trials=10000):
    """Build a filter with n items, then test items that were never added."""
    b = Bloom(m, k)
    for i in range(n):
        b.add(f"in{i}")
    missed = sum(not b.might_contain(f"in{i}") for i in range(n))
    false_pos = sum(b.might_contain(f"out{i}") for i in range(trials))
    return missed, false_pos / trials


def predicted(n, m, k):
    return (1 - math.exp(-k * n / m)) ** k


for m, k in [(10000, 1), (10000, 3), (10000, 7), (10000, 12), (5000, 3)]:
    missed, rate = measure(1000, m, k)
    print(m, k, missed, rate, round(predicted(1000, m, k), 4))
# Output:
# 10000 1 0 0.1011 0.0952
# 10000 3 0 0.0179 0.0174
# 10000 7 0 0.0081 0.0082
# 10000 12 0 0.0161 0.0136
# 5000 3 0 0.0897 0.0918

The columns are m, k, missed items, the measured rate, and the formula. The missed column is 0 in every row, the no-false-negatives guarantee seen in practice. The measured rate tracks the formula. Halving the bits (last row) raises the rate fivefold. And more hashes is not always better: k = 12 is worse than k = 7 for the same m. The next section explains why.

#Sizing a Bloom Filter

Each extra hash gives a query one more chance to hit an off bit and say "no". But it also turns on one more bit for every item, which fills the card faster. These two forces balance when about half of the bits are on. Setting the fraction of ones to one half in the formula gives the best k:

best k  =  (m / n) * ln 2          (about 0.69 bits per item, per hash)
p       =  (1/2) ^ k  =  0.6185 ^ (m / n)
m       =  -n * ln(p) / (ln 2) ^ 2     (about 1.44 * n * log2(1 / p) bits)

Read the last line as a recipe. To hold n items at a false-positive rate p, you need m bits, and m grows in step with n. The memory per item depends only on p, not on how big the items are. A million long URLs and a million short words need the same filter.

def size_for(n, p):
    """Bits m and hash count k for n items at false-positive rate p."""
    m = math.ceil(-n * math.log(p) / math.log(2) ** 2)
    k = max(1, round(m / n * math.log(2)))
    return m, k


for n, p in [(1000, 0.1), (1000, 0.01), (1000, 0.001), (1000000, 0.01)]:
    m, k = size_for(n, p)
    print(n, p, m, k, round(m / n, 2), round(predicted(n, m, k), 4))
print(measure(1000, *size_for(1000, 0.01)))
# Output:
# 1000 0.1 4793 3 4.79 0.1007
# 1000 0.01 9586 7 9.59 0.01
# 1000 0.001 14378 10 14.38 0.001
# 1000000 0.01 9585059 7 9.59 0.01
# (0, 0.011)

A million items at 1 percent need 9,585,059 bits, about 1.2 megabytes. The columns show 4.8 bits per item for 10 percent, 9.6 for 1 percent and 14.4 for 0.1 percent, so each tenfold drop in error costs about 4.8 more bits per item. The measured rate for the 1000-item filter was 0.011, close to the target.

How good is that? A counting argument gives a known lower bound: any structure with no false negatives and false-positive rate p needs at least about n times log2(1/p) bits. A Bloom filter uses 1.44 times that, so it is within 44 percent of the best possible, using only a bit array and a few hashes. Cuckoo filters and similar designs add deletion and can use less space at low error rates, but they are more complex.

The formula has limits. It assumes you know n in advance. If you add more than the planned n, the card fills and the rate climbs with no warning, so a filter that must grow needs a rebuild or a stack of filters. And the rate describes a random absent item. An attacker who knows your hash can pick items that collide, so hostile input needs a secret seed.

#Deletion and Counting Bloom Filters

A plain Bloom filter has no delete. Two different items can have the same bit on, and the filter does not record who turned it on. Try a naive delete before reading on.

b = Bloom(16, 2)
for w in ["cat", "dog", "emu", "bee"]:
    b.add(w)
for p in b.positions("cat"):
    b.bits[p] = 0                       # a naive delete of cat
print([(w, b.might_contain(w)) for w in ["cat", "dog", "emu", "bee"]])
# Output:
# [('cat', False), ('dog', True), ('emu', True), ('bee', False)]

class CountingBloom:
    """Counters in place of bits. Same O(k) time, but the space is m counters."""

    def __init__(self, m, k):
        self.m, self.k, self.cells = m, k, [0] * m

    def positions(self, item):
        return [h(item, seed) % self.m for seed in range(self.k)]

    def add(self, item):
        for p in self.positions(item):
            self.cells[p] += 1

    def remove(self, item):                  # only safe for an item that was added
        for p in self.positions(item):
            self.cells[p] -= 1

    def might_contain(self, item):
        return all(self.cells[p] > 0 for p in self.positions(item))


c = CountingBloom(16, 2)
for w in ["cat", "dog", "emu", "bee"]:
    c.add(w)
c.remove("cat")
print(c.cells)
print([(w, c.might_contain(w)) for w in ["cat", "dog", "emu", "bee"]])
# Output:
# [0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 3, 0]
# [('cat', False), ('dog', True), ('emu', True), ('bee', True)]

Cell 7 dropped from 2 to 1 and still holds bee. Cell 14 shows 3: emu counted it twice and bee once. The price is memory. Counters of a few bits each make the filter several times larger than the plain bit version. Two traps remain.

A counter that overflows its width breaks the guarantee, so real designs make counters wide enough or stop them at a maximum. And removing an item that was never added corrupts the counts, so the caller must know the item is really in the set.

#Count-Min Sketch: Counting With a Small Table

class CountMin:
    """d rows of w counters. add and estimate cost O(d) time. The space is O(w * d) counters."""

    def __init__(self, width, depth):
        self.w, self.d = width, depth
        self.rows = [[0] * width for _ in range(depth)]

    def add(self, item, count=1):
        for r in range(self.d):
            self.rows[r][h(item, r) % self.w] += count

    def estimate(self, item):
        return min(self.rows[r][h(item, r) % self.w] for r in range(self.d))


stream = []
for i in range(20):
    stream += [f"w{i}"] * (40 // (i + 1))        # w0 appears 40 times, w1 20, w2 13, ...
true = {}
for x in stream:
    true[x] = true.get(x, 0) + 1
print(len(stream), len(true))
for w, d in [(1, 1), (16, 1), (16, 4), (40, 4)]:
    cm = CountMin(w, d)
    for x in stream:
        cm.add(x)
    assert all(cm.estimate(x) >= true[x] for x in true)      # never an undercount
    worst = max(cm.estimate(x) - true[x] for x in true)
    print(w, d, worst, [cm.estimate(x) for x in ("w0", "w5", "w19")])
print([true[x] for x in ("w0", "w5", "w19")])
# Output:
# 138 20
# 1 1 136 [138, 138, 138]
# 16 1 22 [40, 9, 24]
# 16 4 4 [40, 6, 2]
# 40 4 0 [40, 6, 2]
# [40, 6, 2]

The stream has 138 events over 20 distinct words. The last line gives the true counts. With one cell (first row), everything collides and every estimate is the whole stream, 138. With 16 columns and one row, some rare words land in a busy word's cell: w19 is truly 2 but reads 24.

Adding three more rows brings the worst error from 22 down to 4, because a rare word must collide in all four rows to be fooled. The assert confirms that no estimate was ever below the truth.

The guarantee, with a short proof

Choose an error size ε (epsilon, for example 0.05) and a failure chance δ (delta, for example 0.01). Use width w = ceil(e / ε) and depth d = ceil(ln(1/δ)). Let N be the total number of events in the stream. Then with probability at least 1 - δ, the estimate is at most the true count plus ε times N.

The reason is short. In one row, the extra count in an item's cell is the sum of the counts of other items that share the cell. Each other item lands there with chance 1/w, so the expected extra is at most N/w, which is at most εN/e.

By Markov's inequality (a value is rarely much above its average), the extra exceeds εN with probability at most 1/e. All d rows must fail together, and the rows are independent, so the chance is at most e^(-d), which is at most δ.

eps, delta = 0.05, 0.01
print(math.ceil(math.e / eps), math.ceil(math.log(1 / delta)))
# Output:
# 55 5

So 55 columns and 5 rows (275 counters) promise an overcount of at most 0.05 times N, with 99 percent probability, however many distinct items there are. For our stream, 0.05 times 138 is 6.9, and the 16 by 4 table above already stayed under it with fewer counters. The cost is O(d) time per operation and O(w·d) space, which is O((1/ε) log(1/δ)) and does not depend on the number of distinct items.

#HyperLogLog: Counting Distinct Items by Luck

Hash each item to a 64-bit number and look at the bits as coin flips. The chance that a hash starts with z zeros in a row is 1 in 2^z. If the longest run of leading zeros you have seen is z, then you have probably looked at about 2^z different items, since you would need roughly that many tries to meet such a run.

Duplicates do not help: the same item gives the same hash, so it cannot produce a new run.

def leading_zeros(x):
    return 64 - x.bit_length()


for n in [10, 1000, 100000]:
    print(n, max(leading_zeros(h(f"item{i}", 0)) for i in range(n)), round(math.log2(n), 1))
# Output:
# 10 2 3.3
# 1000 11 10.0
# 100000 15 16.6

The columns are n, the longest zero run found, and log2 of n. The run follows log2(n) loosely, but one lucky hash can double the estimate, so a single maximum is too noisy.

class HyperLogLog:
    """m = 2^p registers. add costs O(1) time. The space is m small integers."""

    def __init__(self, p=10):
        self.p, self.m = p, 1 << p
        self.reg = [0] * self.m

    def add(self, item):
        x = h(item, 99)
        idx = x >> (64 - self.p)                          # first p bits pick the register
        rest = x & ((1 << (64 - self.p)) - 1)             # the other bits are the coin flips
        rank = (64 - self.p) - rest.bit_length() + 1      # leading zeros plus one
        if rank > self.reg[idx]:
            self.reg[idx] = rank

    def count(self):
        m = self.m
        alpha = 0.7213 / (1 + 1.079 / m)                  # constant from the HyperLogLog paper
        est = alpha * m * m / sum(2.0 ** -r for r in self.reg)
        zeros = self.reg.count(0)
        if est <= 2.5 * m and zeros:                      # small counts: use linear counting
            est = m * math.log(m / zeros)
        return est

    def merge(self, other):
        self.reg = [max(a, b) for a, b in zip(self.reg, other.reg)]


for n in [10, 100, 1000, 10000, 100000]:
    s = HyperLogLog(10)
    for i in range(n):
        s.add(f"user{i}")
    print(n, round(s.count()), f"{(s.count() - n) / n * 100:+.1f}%")
# Output:
# 10 10 +0.5%
# 100 100 -0.3%
# 1000 999 -0.1%
# 10000 10409 +4.1%
# 100000 102519 +2.5%

With 1024 registers the estimates stay within a few percent from 10 users to 100,000. The usual relative error is about 1.04 divided by the square root of m, which is 3.25 percent here, and one run can land a little outside it, as the 4.1 percent row shows. Doubling the accuracy costs four times the registers. Each register needs only about 6 bits, since a rank never exceeds 64.

a, b = HyperLogLog(10), HyperLogLog(10)
for i in range(6000):
    a.add(f"user{i}")
for i in range(4000, 10000):
    b.add(f"user{i}")
a.merge(b)
print(round(a.count()))
s = HyperLogLog(10)
for i in range(5000):
    s.add(f"user{i % 50}")
print(round(s.count()))
# Output:
# 10409
# 50

Two groups of 6000 users with 2000 in common merge to an estimate for 10,000 distinct users, the shared ones counted once. The second test sends 5000 events from only 50 users and gets 50. Time is O(1) per item and O(m) per merge, and the space is O(m). The memory does not depend on n at all.

#Reservoir Sampling: A Fair Sample From a Stream

The rule: keep the first k items. Then for the item at 1-based position i (with i greater than k), draw a random whole number j from 1 to i. If j is at most k, the new item replaces slot j. Otherwise drop it. The code uses 0-based numbering and our replayable hash for the dice.

The claim is that after any prefix of length i, every item seen so far sits in the reservoir with probability exactly k/i. Check it by induction (small steps that build on each other). After k items, each is in with probability 1 = k/k. Now suppose it holds after i items. The new item, number i + 1, enters with probability k/(i+1).

An older item is in with probability k/i, and it is removed only if the new item enters (chance k/(i+1)) and lands on its slot (chance 1/k), so it survives with probability 1 - 1/(i+1) = i/(i+1). Its chance becomes k/i times i/(i+1) = k/(i+1). The claim holds for every item.

def reservoir(stream, k, seed):
    """One pass, O(n) time, O(k) extra space. Returns the sample and the replacement count."""
    sample, replaced = [], 0
    for i, x in enumerate(stream):             # i items came before x
        if i < k:
            sample.append(x)
        else:
            j = h(i, seed) % (i + 1)           # a fair number from 0 to i
            if j < k:
                sample[j] = x
                replaced += 1
    return sample, replaced


print(reservoir(range(100), 5, 1))
print(reservoir(range(3), 5, 1), reservoir([], 5, 1))
counts = [0] * 10
for seed in range(3000):
    for x in reservoir(range(10), 3, seed)[0]:
        counts[x] += 1
print(counts, 3000 * 3 / 10)
# Output:
# ([77, 81, 98, 93, 55], 13)
# ([0, 1, 2], 0) ([], 0)
# [911, 862, 893, 905, 909, 883, 903, 933, 893, 908] 900.0

The first line is a sample of 5 from 100 values. The second shows the edge cases: a short stream returns everything and an empty stream returns nothing. The third is the fairness test: sampling 3 of 10 items with 3000 seeds, each item should appear about 900 times. The counts run from 862 to 933, the spread chance gives.

How often does the reservoir change? Item i replaces something with probability k/i, so the expected number of replacements over n items is about k times ln(n/k), a slow growth.

print(sum(reservoir(range(2000), 10, s)[1] for s in range(100)) / 100, round(10 * math.log(2000 / 10), 2))
# Output:
# 51.98
# 52.98

#Consistent Hashing: Moving Few Keys

That server owns the key. When a new server joins, its point cuts out a stretch of the ring from the next server around. Only the keys in that stretch move, and all of them move to the new server.

def build_ring(servers, vnodes):
    """Sorted ring points and their owners. O(S * v log(S * v)) time, O(S * v) space."""
    pairs = sorted((h(f"{s}#{v}", 7), s) for s in servers for v in range(vnodes))
    return [p for p, _ in pairs], [s for _, s in pairs]


def owner(ring, key):
    """Binary search for the next point clockwise. O(log(S * v)) time."""
    points, owners = ring
    i = bisect.bisect_right(points, h(key, 7))
    return owners[i % len(points)]             # past the last point, wrap around to the first


keys = [f"key{i}" for i in range(10000)]
servers = ["A", "B", "C", "D"]
for v in (1, 10, 100):
    ring = build_ring(servers, v)
    load = {s: 0 for s in servers}
    for k in keys:
        load[owner(ring, k)] += 1
    print(v, load)
old, new = build_ring(servers, 100), build_ring(servers + ["E"], 100)
moves = [k for k in keys if owner(old, k) != owner(new, k)]
print(len(moves), all(owner(new, k) == "E" for k in moves))
print(sum(h(k, 7) % 4 != h(k, 7) % 5 for k in keys))
# Output:
# 1 {'A': 5148, 'B': 2320, 'C': 959, 'D': 1573}
# 10 {'A': 1937, 'B': 2961, 'C': 2627, 'D': 2475}
# 100 {'A': 2643, 'B': 2434, 'C': 2159, 'D': 2764}
# 1936 True
# 7959

With one point per server the loads range from 959 to 5,148. With 100 points each they range from 2,159 to 2,764. Adding a fifth server moved 1,936 keys, close to the fair share of 10,000 divided by 5, and every one of them moved to the new server E. The modulo rule moved 7,959. An old server never loses a key to another old server.

A lookup is a binary search, O(log(S·v)) time, and the ring needs O(S·v) space. Adding or removing a server edits that sorted list, up to O(S·v) in a Python list. In expectation, adding a server to S servers moves K/(S+1) of K keys, and more virtual nodes bring real runs closer to that average.

The viewer below draws a ring with its own points and presets, not our SHA hashes, but the idea is the same. Try the presets that add and remove a node.

#Choosing One and Where It Is Used

Match the question to the tool and know which way each one errs.

When not to use them

If the data fits comfortably in memory, use a set or a dict. They are exact and simpler. Avoid a Bloom filter when you must list the members, delete freely, or cannot afford a wrong "yes". Avoid count-min for rare items. Avoid HyperLogLog when you need an exact figure, such as a bill. Every tool here loses information on purpose, and you cannot get it back.

Where they show up

These are examples, not a survey. Storage engines built on log-structured merge trees, such as LevelDB and RocksDB, can keep a Bloom filter per file so a lookup for a missing key skips most disk reads. Redis offers HyperLogLog commands for counting distinct items. The Dynamo paper describes consistent hashing with virtual nodes for spreading data across machines, and Cassandra uses virtual nodes. Stream-processing systems use count-min style sketches to track frequent items.

In machine learning pipelines, a Bloom filter can cheaply skip records already seen during data cleaning, and reservoir sampling keeps a fair training sample from a stream, as in a replay buffer of fixed size.

#Common Mistakes

#Try It: Five Problems

Work up the ladder. Problem 1 is a Bloom filter with a read counter, so you can see that absent items often stop early. Problem 2 is the sizing formula, with edge cases. Problem 3 is a count-min sketch with a cell counter, tested with width 1 as the worst case.

Problem 4 is reservoir sampling, with a short stream, an empty stream and k = 0 as edge cases. Problem 5 is a consistent hash ring with an empty ring and a single point per server as the adversarial inputs.

#Recap

A probabilistic structure trades a small, predictable error for a large saving in memory. A Bloom filter answers membership in O(k) time with fixed space, errs only with false positives at rate about (1 - e^(-kn/m))^k, and cannot delete. A counting filter adds deletion with counters.

A count-min sketch overcounts by at most εN with probability 1 - δ. HyperLogLog counts distinct items with relative error about 1.04/√m. Reservoir sampling keeps k items fairly in one pass, because each survives with probability k/i. Consistent hashing with virtual nodes moves only about 1/(S+1) of the keys when a server joins.