Bloom Filter, Reservoir Sampling, HyperLogLog: Three Probabilistic Answers to Three Different Questions

Same family, different jobs

Bloom filters, reservoir sampling and HyperLogLog tend to get filed in the same mental drawer. All three are probabilistic. All three give up something to save memory. All three let you process a stream without keeping everything you've seen. If you've only met them in a "data structures you should know" listicle, they blur together into one category: clever hashing tricks that are approximately right.

But they aren't interchangeable, and the difference isn't one of accuracy or sophistication. Each one answers a different question. Pick the wrong one and you don't get a slightly worse answer. You get a confident answer to a question you didn't ask.

Here's the setup for the whole post. SupraScan indexes a continuous stream of blockchain transactions. Every transaction has a sender wallet. Millions of transactions arrive, wallets come and go, and every analytics feature competes with the indexer itself for memory. Against that one stream, we keep asking three questions:

• "Have we seen wallet X before?" That's a Bloom filter.
• "Give me 1,000 random transactions from today's stream." That's reservoir sampling.
• "How many distinct wallets transacted today?" That's HyperLogLog.

Three questions, three structures, three different definitions of a useful answer. The rest of this post is about why you can't swap them, plus a fourth question that none of them answers.

Three questions, three structures

The last column surprises people the most. None of these structures lets you "undo" a wallet cheaply, because none of them remembers which wallet set which bits.

Bloom filter: "Have we seen this wallet?"

A Bloom filter is a bit array of size m and k hash functions. To add a wallet, hash it k times and set those k bits. To check a wallet, hash it the same way and look at those k bits. If any of them is 0, the wallet was never added. If all of them are 1, it might have been added, or other wallets might have set those bits between them.

That gives the one-sided error every Bloom filter guarantee rests on:

• "No" means no. No false negatives, as long as you never clear bits.
• "Yes" means maybe. False positives happen at a rate you choose up front.

The analogy I use is a bouncer with a fuzzy guest list. He never turns away someone who's on the list. Occasionally he waves in a stranger who looks enough like a guest.

Here's a small implementation, written to show the mechanics rather than to replace a library. It derives all k positions from one SHA-256 digest using double hashing (h1 + i * h2), a well-known shortcut that performs close to k independent hash functions in practice without being literally equivalent to them. The same helper drives the Count-Min sketch later in the post:

import { createHash } from 'node:crypto';
 
// Runs once per constructor; trial division over odd numbers is plenty here
function nextPrime(n) {
  if (n <= 2) return 2;
  for (n += n % 2 === 0 ? 1 : 0; ; n += 2) {
    let prime = true;
    for (let d = 3; d * d <= n && prime; d += 2) prime = n % d !== 0;
    if (prime) return n;
  }
}
 
// Two 32-bit hashes from one digest. size must be prime: then any step in
// [1, size - 1] is coprime to it, so the first `size` positions h1 + i * h2
// are all distinct and an item's k positions never land on the same slot.
// 32-bit hashes can't address more than 2^32 slots, hence the upper limit.
function twoHashes(item, size) {
  if (size < 2 || size > 2 ** 32) throw new RangeError('size must be a prime in [2, 2^32]');
  const digest = createHash('sha256').update(item).digest();
  const h1 = digest.readUInt32BE(0) % size;
  const h2 = 1 + (digest.readUInt32BE(4) % (size - 1));
  return [h1, h2];
}
 
class BloomFilter {
  constructor(expectedItems, falsePositiveRate) {
    if (!Number.isInteger(expectedItems) || expectedItems <= 0) {
      throw new RangeError('expectedItems must be a positive integer');
    }
    if (!(falsePositiveRate > 0 && falsePositiveRate < 1)) {
      throw new RangeError('falsePositiveRate must be between 0 and 1');
    }
    // Optimal sizing for a target false-positive rate, rounded up to a prime
    this.m = nextPrime(Math.ceil(-(expectedItems * Math.log(falsePositiveRate)) / Math.LN2 ** 2));
    this.k = Math.max(1, Math.round((this.m / expectedItems) * Math.LN2));
    this.bits = new Uint8Array(Math.ceil(this.m / 8));
  }
 
  #positions(item) {
    const [h1, h2] = twoHashes(item, this.m);
    return Array.from({ length: this.k }, (_, i) => (h1 + i * h2) % this.m);
  }
 
  add(item) {
    for (const p of this.#positions(item)) this.bits[p >> 3] |= 1 << (p & 7);
  }
 
  mightContain(item) {
    return this.#positions(item).every((p) => this.bits[p >> 3] & (1 << (p & 7)));
  }
}

Sized for 1 million wallets at a 1% false-positive rate, this picks m = 9,585,061 bits (the optimal 9,585,059, rounded up to the next prime, which is about 1.2 MB of bit array) and k = 7. I loaded it with 1 million synthetic wallet IDs, checked every one of them, then probed it with five separate sets of 1 million IDs that were guaranteed never to have been inserted (a different prefix):

false negatives:                 0 of 1,000,000
false positive rate, 5 probes:   1.007%  1.003%  1.020%  1.017%  0.984%
bit array:                       1.2 MB (ceil(m / 8) bytes, excluding object overhead)

The false-positive rate is empirical, so it wobbles a little from probe set to probe set, but it sits on the 1% it was sized for.

Compare that with storing the addresses themselves. A Supra or Aptos address is 32 bytes, so 1 million of them is 32 MB of raw address bytes alone. A real set adds hash-table overhead on top, and JavaScript strings of hex addresses cost several times more again. The filter costs about 9.6 bits per wallet no matter how long the addresses are.

Where it earns its keep

Skipping disk reads in LSM-trees. Cassandra, RocksDB and friends keep a Bloom filter per SSTable. A point lookup checks the filter first and skips every SSTable that definitely doesn't contain the key. This is why LSM reads aren't as bad as "check every file on disk" sounds (the B-Trees vs LSM-Trees module walks through the read path, and the Postgres vs Cassandra storage engines post covers why the two databases chose differently).

Guarding against cache penetration. If attackers or buggy clients request wallets that don't exist, every request misses the cache and hits the database. A filter of known wallets lets you reject those cheaply. Be precise about what this buys you: it only works if "in the filter" means exactly what the lookup needs ("this wallet exists in our index"), and if the filter is updated whenever a new wallet is indexed. A filter that lags the index will reject real, brand-new wallets. That's not a false negative of the filter. It's a false negative of your synchronization. (Penetration's two siblings, stampede and avalanche, need different fixes; the cache stampede, avalanche and penetration module covers all three.)

What it can't do

You can't delete. Clearing a wallet's bits would also clear bits that other wallets rely on, and those wallets would start returning "definitely not present", which breaks the one guarantee the filter has. Counting Bloom filters (small counters instead of bits) and cuckoo filters support deletion, at the cost of more memory per item and their own failure modes.

You also can't list what's inside or ask how many times a wallet appeared. The filter only knows "these bits are on".

Reservoir sampling: "Give me 1,000 random transactions"

Different problem. You're debugging a fee-calculation issue and want a random sample of today's transactions to inspect by hand. You don't know how many transactions today will have. You can't store all of them and sample at midnight, because that defeats the point.

The obvious shortcuts are both wrong:

• Keep the first 1,000. That's a sample of the first few seconds after midnight, not of the day.
• Keep every Nth transaction. You don't know N until the day ends, and any periodic pattern in the stream (a bot firing every 1,000 blocks) aliases straight into your sample.

Reservoir sampling (Algorithm R) keeps a uniform random sample of size k from a stream of unknown length, in a single pass, with O(k) memory:

1. Put the first k items into the reservoir.
2. For the n-th item (n > k), pick a random integer j in [0, n).
3. If j < k, replace reservoir slot j with the new item. Otherwise drop it.

function reservoirSample(stream, k) {
  if (!Number.isInteger(k) || k < 0) {
    throw new RangeError('k must be a non-negative integer');
  }
  const reservoir = [];
  if (k === 0) return reservoir;
  let n = 0;
  for (const item of stream) {
    n++;
    if (reservoir.length < k) {
      reservoir.push(item);
      continue;
    }
    const j = Math.floor(Math.random() * n);
    if (j < k) reservoir[j] = item;
  }
  return reservoir;
}

Why every transaction gets a fair chance

Take item number n in a stream that ends up N items long. Three steps:

1. It gets in with probability k/n (that's j < k when j is uniform over n values).
2. At each later step i, it gets evicted only if the new item gets in (probability k/i) and lands on its particular slot (probability 1/k). That's (k/i) × (1/k) = 1/i, so it survives step i with probability (i-1)/i.
3. Surviving every step from n+1 to N multiplies those odds, and the product telescopes:

P(survive)  = (n / (n+1)) × ((n+1) / (n+2)) × ... × ((N-1) / N)  =  n / N
 
P(in final sample)  = P(gets in) × P(survive)  =  (k / n) × (n / N)  =  k / N

Every item, early or late, ends up with the same k/N chance. You can check this empirically: sample 3 items from a stream of 10, repeat 100,000 times, and count how often each item shows up. You expect about 30,000 each:

item:    0      1      2      3      4      5      6      7      8      9
count:   30034  30025  29961  29947  30130  29787  29798  30079  30081  30158

The analogy: a raffle where tickets keep arriving all night, and at any moment the drum holds a fair draw of everything that arrived so far.

The caveats that matter in production

Uniform is not the same as representative. Each transaction has an equal chance, so a chain or a transaction type that makes up 0.1% of traffic will contribute about one item to a 1,000-item sample, often zero. If you need coverage per chain, per hour or per transaction type, keep a separate reservoir per group (stratified sampling).

Merging needs the stream lengths. If two indexer workers each keep a reservoir of 1,000, concatenating them doesn't give a uniform sample of the combined stream when one worker saw 10 million transactions and the other saw 100,000. A correct merge draws from each reservoir in proportion to its stream length, so each worker has to report n along with its sample.

The randomness is part of the correctness. Math.random() is fine for debugging samples. If a sample feeds anything adversarial (audits, rewards, anything a user could game by timing their transactions), use a proper source of randomness.

HyperLogLog: "How many distinct wallets?"

I've covered this one in depth elsewhere: the HyperLogLog, Bitmaps, and Geospatial module of the Redis course explains the internals, the Redis HyperLogLog introduction covers PFADD, PFCOUNT and PFMERGE, and the wallet-uniqueness case study covers what went wrong running it under concurrent production writes. So here's only what this comparison needs.

HyperLogLog hashes each wallet and looks at the run of leading zeros in the hash. A long run is rare, so seeing one is evidence that many distinct values went by. Splitting hashes across many registers and averaging their evidence turns a noisy signal into a stable estimate. Redis uses 16,384 registers in 12 KB, with a standard error of about 0.81%.

Two precise points worth stating:

• It's an estimate. 0.81% is a standard error, a statistical property of the estimator, not a promise that every count lands within 0.81% of the truth. Most counts land well inside that. Some land outside it.
• Duplicates are free. A wallet that sends 50,000 transactions sets the same register the same way every time. That's exactly the property sampling lacks, as the next section shows.

What HyperLogLog can't do: tell you whether wallet X is in the set, list the wallets, or tell you how often any wallet appeared. It only knows "about this many distinct things went past".

Why you can't substitute one for another

So far, each structure has answered its own question. The interesting part starts when you try to reuse an answer you already have for a different purpose, which is exactly where the "they're all basically the same" intuition breaks. Each structure throws away the information the others depend on.

A sample can't count distinct wallets

This is the substitution people actually try: "we already keep a 1,000-transaction sample, just count the distinct wallets in it and scale up."

Here are two synthetic streams of 1 million transactions each, both shuffled:

• Stream A: 500 bot wallets send 900,000 transactions between them, and 100,000 real users send 1 transaction each. True distinct wallets: 100,500.
• Stream B: 20,000 wallets send exactly 50 transactions each. True distinct wallets: 20,000.

I ran the reservoirSample function above on each with k = 1000, then repeated the whole thing 100 times, reshuffling both streams every time, so the result doesn't hinge on one lucky run:

stream   true distinct   distinct in sample (100 runs)    naive estimate (median x1000)
                         min    median   max
A        100,500         494    518      544              518,000
B        20,000          964    976      983              976,000
 
Stream A's sample showed fewer distinct wallets than B's in 100 of 100 runs.

The sample doesn't just get the numbers wrong. It ranks the streams backwards, every time. Stream A has five times as many wallets, but its sample shows about half as many distinct ones, because roughly 90% of the draws land on the same 500 bots. The 100,000 one-time users, who are most of the answer, show up about 100 times in the sample and look like a rounding error.

Scaling the sample up doesn't fix this, because the sample can't tell a long tail of one-time wallets from no tail at all. Very different streams can produce very similar samples. Charikar, Chaudhuri, Motwani and Narasayya made this precise for one specific setting in "Towards Estimation Error Guarantees for Distinct Values" (PODS 2000): when an estimator sees only a uniform random sample of r rows from a table of n rows, then for any such estimator there exist tables where its ratio error is large, on the order of sqrt(n/r), with non-trivial probability. That's a statement about worst-case inputs in that sampling model, not a claim that every sample-based estimate is bad on every distribution. But blockchain traffic, with a few very loud wallets and a long tail of quiet ones, looks a lot like the hard cases. HyperLogLog sits outside that model entirely: it sees every item, it just doesn't keep them.

And yet that same sample is good at its own job. Questions about transactions are what it's built for. Across the 100 runs, the share of sampled transactions that came from bots ranged from 87.5% to 92.2%, with a median of 90%, against a true value of exactly 90%. That's ordinary sampling variation around the right answer. The sample is good for questions about transactions and bad for questions about distinct wallets. That's the whole lesson in one sentence.

HyperLogLog can't answer "have we seen X?"

It keeps one small number per register: the longest run of leading zeros seen so far. Wallet X's hash may have set a register, or a different wallet may have set it higher already. There's nothing left to check X against. A cardinality sketch answers questions about the whole set and nothing about any single member.

A Bloom filter can count, until it can't

This is the interesting near-miss. If you know m and k, the fraction of bits that are set tells you roughly how many distinct items went in. With X bits set:

n ≈ -(m / k) × ln(1 - X / m)

On the 1-million-wallet filter above, 4,966,293 of the 9,585,061 bits are set (51.8%), and the formula gives 999,691. That is an estimate under the usual Bloom-filter model (well-spread hashes, no deletions), not an exact count. Duplicates are free here too, since re-adding a wallet sets bits that are already on. So why not just use it?

Because it only works while the filter is sized for the count. A Bloom filter's memory grows linearly with the number of items you plan to hold, about 9.6 bits per wallet at 1%. As the filter fills up, X / m approaches 1, the logarithm blows up, and the estimate falls apart. HyperLogLog stays at 12 KB whether you count a thousand wallets or a billion. The Bloom filter can answer the counting question, but at a price that grows with the answer, and only up to the capacity you guessed in advance.

A Bloom filter can't give you a sample

It doesn't store transactions, only bits derived from them. There's nothing to inspect.

The fourth question: "How often does this wallet transact?"

None of the three answers this. A Bloom filter says "seen". HyperLogLog says "how many distinct". A reservoir says "here are some transactions". None of them says "wallet X sent 1,831 transactions today".

The exact answer is a counter per wallet, a hash map or a Redis INCR key each (the atomic counters and rate limiters module covers that pattern), which is just as big as storing every wallet. The probabilistic answer is a Count-Min sketch: d rows of w counters, one hash function per row. To add a wallet, increment one counter in each row. To estimate a wallet's count, read its counter in each row and take the minimum.

Like the Bloom filter above, this is an illustration of the algorithm, reusing the same twoHashes helper, not a production sketch library:

class CountMinSketch {
  constructor(epsilon, delta) {
    if (!(epsilon > 0 && epsilon < 1) || !(delta > 0 && delta < 1)) {
      throw new RangeError('epsilon and delta must be between 0 and 1');
    }
    this.width = nextPrime(Math.ceil(Math.E / epsilon));
    this.depth = Math.ceil(Math.log(1 / delta));
    // Float64 counters stay exact up to 2^53, far past where Uint32 would wrap
    this.table = Array.from({ length: this.depth }, () => new Float64Array(this.width));
  }
 
  #columns(item) {
    const [h1, h2] = twoHashes(item, this.width);
    return Array.from({ length: this.depth }, (_, row) => (h1 + row * h2) % this.width);
  }
 
  add(item, count = 1) {
    this.#columns(item).forEach((col, row) => { this.table[row][col] += count; });
  }
 
  estimate(item) {
    return Math.min(...this.#columns(item).map((col, row) => this.table[row][col]));
  }
}

Every counter a wallet touches also holds counts from other wallets that collided there, so each row overestimates. Taking the minimum picks the row with the least collision noise. In the standard insertion-only form, the estimate never underestimates. Two claims are worth keeping apart here:

• The theoretical guarantee. This is the standard additive-error bound for the usual construction: width e / epsilon, depth ln(1 / delta), and each row's hash drawn independently from a pairwise-independent family. Under those conditions, any single query overestimates by more than epsilon × N with probability at most delta, where N is the total number of transactions.
• What this code does. It derives every row's column from one SHA-256 digest, which is a practical construction, not a proof that those independence assumptions hold. What it can show is how this implementation behaves on a real workload.

With epsilon = 0.001 and delta = 0.01, that's 5 rows of 2,719 counters, about 109 KB with 8-byte counters. On Stream A from earlier (N = 1 million, so the bound is 1,000):

wallet                   true count   estimate
bot7                     1,800        1,831
user42                   1            35
never-seen wallet        0            28
 
all 100,000 one-time users:  mean overcount 31,  worst 1,837
estimates above the 1,000 bound:  22 of 100,000  (0.022%)

The worst case is worth a look. Some estimates overshot the bound, and that doesn't contradict the theory: the guarantee caps the probability for each query, it doesn't promise that every query in a batch of 100,000 stays inside. Empirically, this implementation on this workload exceeded the bound on 22 of 100,000 queries, a rate comfortably below delta. That's evidence the construction behaves well here, not a proof that it meets the formal guarantee.

That table shows exactly what it's good for. In this run, the typical overestimate was around 30 transactions. That's negligible for a wallet with thousands of transactions and overwhelming for a wallet that appeared once. Count-Min is for finding the loud wallets, not for auditing the quiet ones.

In practice that means flagging wallets whose estimated volume crosses a threshold, then checking them exactly. If you want the top 100 wallets rather than everyone over a threshold, pair the sketch with a size-100 min-heap of the current leaders, the same "k largest" pattern from the heap applications module. A high count isn't evidence of abuse. Exchanges, bridges and market makers are loud by design. The sketch tells you where to look, not what you'll find.

If you're on Redis, the RedisBloom module (bundled with Redis Stack, and part of Redis 8) ships Bloom filters, cuckoo filters, Count-Min sketches and Top-K as native commands, so you rarely need to build these yourself.

When the question involves two sets

Distinct counting has a follow-up problem. Sooner or later someone asks a question about two sets:

• How many wallets were active on both mainnet and testnet?
• How many wallets transacted this week but not last week?

HyperLogLog handles unions natively: merge the two sketches and count. For intersections, the usual workaround is inclusion-exclusion, |A ∩ B| = |A| + |B| - |A ∪ B|. The identity is exact. The trouble is that you're feeding it three estimates and subtracting large numbers to get a small one.

Suppose each chain has 5 million wallets and only 10,000 are on both. The union is 9,990,000. At 0.81% standard error, the union estimate alone typically misses by tens of thousands of wallets (0.81% of 9.99 million is about 81,000), and |A| and |B| each carry their own error of around 40,000. Those errors are partly correlated, since the union sketch is built from the same registers, so you can't simply add them up. But whichever way they combine, they're measured in tens of thousands, and the answer you want is 10,000.

Rather than argue about the exact error formula, I simulated it. I didn't run Redis itself. This is a Redis-parameterized HLL: 16,384 registers, a 64-bit hash split into a 14-bit register index and a 50-bit rank, register-wise max for the union, and the classic HLL estimator with the small-range correction (Redis uses a newer estimator, which mainly differs at small counts, far below these). The setup: 5 million wallets per chain, an overlap of exactly 10,000, and 30 runs with different hash seeds. In these 30 runs, the union estimates stayed within about 0.8% of the true count. The intersection estimates did not:

true intersection:              10,000
estimates (30 runs):            -128,271 to 125,076
negative:                       13 of 30
more than double the truth:     13 of 30
within 50% of the truth:         4 of 30

Thirty runs illustrate the problem rather than map its full error distribution, but the mechanism doesn't depend on the simulation: healthy sketches, a correct identity, and an answer that is mostly noise. The subtraction takes errors that are small relative to 10 million and makes them enormous relative to 10,000.

Theta sketches, also in Apache DataSketches, are built for this. They keep a sample of hash values, not register maxima, which lets them do union, intersection and difference directly. (HyperLogLog can only reach A-not-B through the same inclusion-exclusion arithmetic, |A ∪ B| - |B|, with the same error problem.) They cost more memory than HyperLogLog for the same accuracy, and intersections of very small overlaps are still hard for any sketch. But when the product question is "how many wallets did X and Y", it's the right family to start from. DataSketches also offers HLL with a choice of 4-, 6- or 8-bit registers, trading memory for update speed, which matters once you keep thousands of sketches (one per time bucket, per chain).

The decision cheat sheet

Start from the question, not the data structure:

That last row matters. All of these structures are good because they're comfortable being slightly wrong. When being slightly wrong costs money or breaks an audit, the right data structure is a database table and an honest COUNT(DISTINCT).

So yes, these three are close. They're close the way a thermometer, a barometer and a rain gauge are close: same weather station, same sky, three instruments that each measure exactly one thing. Before you pick one, write down the question you're asking.