Answers Without Memory: Bloom Filters, HyperLogLog, and the Art of Calculated Error

The Hook: The Question That Costs You a Data Center

Picture a question so mundane that it gets asked in thirty seconds in any product meeting and goes unsolved in any architecture for thirty days: "How many distinct users visited our platform last month?"

Not "how many page views" — that is a counter, an addition, trivial. But: how many distinct ones. Set theory calls this cardinality. And cardinality is the most expensive question in data processing, because it demands a memory.

To know exactly how many distinct users there were, you have to retain every user you have already seen. You need a set, a HashSet, an index — something that can look up, for each new element: "do I already know you?" With 500 million unique user IDs at 16 bytes each, that is 8 gigabytes of raw payload, and in practice, with hash overhead and pointers, more like 30 to 50 gigabytes of RAM. For one number. Per time window. Per dimension you want to break it down by — country, device, campaign, plan. The combinatorics eat you alive long before the data does.

And now comes the punchline, which is nearly fifty years old and still reaches most architects only once their cluster is on fire: you do not need the memory at all. You can answer the same question with 12 kilobytes — not gigabytes, kilobytes — with a typical error below one percent. The saving is not a factor of ten. It is a factor of several million.

The price is a single, precisely defined concession: you give up certainty and get an error bound in return. Not "somewhat inaccurate," but mathematically described, provably bounded, configurable in advance.

This class of tools is called probabilistic data structures, or, in the jargon, sketches. They are the reason APPROX_COUNT_DISTINCT in BigQuery answers in seconds where COUNT(DISTINCT …) takes minutes. They are the reason Cassandra and RocksDB do not torture the disk on every read. And they are, I would argue in this article, the most elegant lesson in systems design there is: that you can design an error instead of suffering one.

Part 1: The Core Principle — Trading Certainty for an Error Bound

The Streaming Model

All the sketches we will discuss live in a shared computational model: the data stream model. Its assumptions are strict, and that strictness is precisely what makes the results so strong:

• Elements pass by once, in arbitrary order (one pass).
• The available memory is sublinear in the data volume, typically logarithmic or constant.
• Processing per element is O(1) or close to it.
• There is no rewinding. Whatever you did not write into your sketch is gone forever.

In this model, exactly counting distinct elements is provably impossible without memory proportional to the cardinality. That is not an implementation problem, it is an information-theoretic lower bound. Whoever wants to answer exactly must be able to remember.

So you relax the requirement — and not vaguely, but deliberately.

The Three Dimensions of the Concession

There are exactly three things a sketch can sacrifice. Which of them it sacrifices is what defines it:

1. Accuracy of the value (ε): The answer is not the truth, but with high probability it lies close to it. Example: HyperLogLog delivers a cardinality with roughly 1% relative standard error.
2. Reliability of the statement (δ): In a small fraction of cases, the answer falls outside the error bound. Example: the Count-Min Sketch guarantees its bound "with probability 1 − δ."
3. Direction of the error: This is the most underrated dimension. A sketch can be built so that it errs in only one direction. A Bloom filter never says "I don't know this" about an element it does know. A Count-Min Sketch never underestimates a frequency.

That third dimension is the real lever for architects. A one-sided error is a fundamentally different thing from a two-sided error, because you can build it into a system without losing the correctness of the system as a whole. We will see how shortly: the Bloom filter becomes a tool that never produces a wrong answer — only, sometimes, unnecessary work.

Part 2: The Bloom Filter — Membership Without a Membership List

1970: An Idea in Five Pages

In 1970, Burton H. Bloom published a short paper in Communications of the ACM under the programmatic title "Space/Time Trade-offs in Hash Coding with Allowable Errors" (CACM 13(7), 422–426, DOI 10.1145/362686.362692). The core of his argument is already in the abstract: if you allow a small number of test messages to be falsely identified as members of the given set, a much smaller hash area can be used without increasing reject time.

Bloom's use case was very concrete at the time: a program for automatic hyphenation. The vast majority of English words follow simple hyphenation rules; only a minority require a dictionary lookup. The filter was to decide in advance which words needed the (slow, disk-resident) exception list consulted at all.

That shape of problem — "do I even need to make the expensive access?" — has not gone out of fashion since. It is the pattern.

The Mechanics

A Bloom filter consists of two things:

• a bit array of length m, initially all zeros,
• k independent hash functions, each mapping an element to a position in [0, m).

Insert element x: compute h₁(x) … h_k(x), set all k bits to 1.

Query element y: compute h₁(y) … h_k(y), check all k bits.

• If at least one bit is 0 → y is definitely not in the set.
• If all bits are 1 → y is probably in the set.

And here lies the whole beauty. The first answer is a certainty. Had y been inserted, all of its bits would be set; an unset bit proves absence. The second answer is only an indication: the k bits could also have been set by other, coincidentally overlapping elements.

So:

• False negatives: impossible. Never. Structurally excluded.
• False positives: possible, at a calculable rate.

The Formula Worth Knowing

With n inserted elements, m bits, and k hash functions, the false-positive rate is approximately

p ≈ (1 − e^(−kn/m))^k

This formula is not merely theory, it is a sizing tool. Two consequences are worth carrying in your head:

1. There is an optimal k. For given m and n,

k_opt = (m/n) · ln 2 ≈ 0.693 · (m/n)

minimizes the error rate. More hash functions are not better — past the optimum they merely fill the array with ones faster.

2. Memory per element is independent of element size. With optimal k you need

m/n ≈ −1.44 · log₂(p) bits per element

In numbers:

Read that table slowly, because it contains the most important number in this article: each order of magnitude less error costs a constant ~4.8 bits per element. The relationship is logarithmic, not linear. Which means: very low error rates are dirt cheap. And it also means: whether your element is a 16-byte UUID or a 2-kilobyte URL, ten bits remain ten bits. The Bloom filter is blind to element size, and that is the source of the absurd compression factors.

What the Bloom Filter Cannot Do

Three limitations that regularly hurt in practice:

No deletion. You cannot simply reset a bit to 0, because another element might share it — resetting would create a false negative and thereby destroy the structure's only guarantee. The classic answer is the Counting Bloom Filter, introduced by Li Fan, Pei Cao, Jussara Almeida, and Andrei Broder in "Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol" (IEEE/ACM Transactions on Networking 8(3), 2000): instead of bits you store small counters (typically 4 bits), incremented on insert and decremented on delete. Price: four to eight times the memory.

No element recovery. A Bloom filter cannot tell you what is inside it. It is a one-way street. That is, incidentally, an underrated privacy advantage, which I will come back to.

No flexibility in size. Sizing happens in advance for an expected n. Exceed it and the error rate explodes — more on that in Part 7.

The Modern Successor: Cuckoo Filters

In 2014, Bin Fan, David G. Andersen, Michael Kaminsky, and Michael D. Mitzenmacher presented the cuckoo filter at CoNEXT'14, under the gloriously self-confident title "Cuckoo Filter: Practically Better Than Bloom." It stores not bits but short fingerprints of elements in a cuckoo hash table. The authors state two advantages in their abstract: for applications that store many items and target moderately low false-positive rates, cuckoo filters have lower space overhead than space-optimized Bloom filters — and they support adding and removing items dynamically, at even higher performance.

The caveat worth knowing: a cuckoo filter can fail on insert when it gets too full (the cuckoo eviction chain gives up). So it trades the Bloom filter's rigidity for a different rigidity — but one that announces itself explicitly instead of silently degrading the error rate. I am of the opinion that in production systems this is almost always the better property: an error that fails loudly beats an error that degrades quietly.

Part 3: Counting Without Remembering — From Flajolet-Martin to HyperLogLog

Now back to the opening question: how many distinct? Here the idea gets more radical still, because here you no longer store even traces of the elements, only a statistic over their hash values.

The Intuition: The Longest Coin Run

Imagine watching someone flip a fair coin, and you record only one piece of information: the longest observed run of heads.

If the longest run was 3, the person probably made about eight flips — because "three heads in a row" occurs with probability 1/8. If the longest run was 10, it was probably around 1024 flips. You have reconstructed the number of flips without counting a single one, purely from extreme-value statistics.

That is exactly the trick. You hash each element to a (pseudo-)random bit string. Hashing serves a double function here, and both parts are essential:

1. It randomizes: user IDs become uniformly distributed bit patterns.
2. It idempotizes: the same element always yields the same hash. This is why an element that appears a million times counts exactly once — duplicates are automatically neutralized. That is the reason these methods measure cardinality and not volume.

You then observe an extremum — say, the maximum number of leading zeros across all hash values — and infer the number of distinct elements from it.

Flajolet and Martin, 1985

Philippe Flajolet and G. Nigel Martin formalized this in "Probabilistic Counting Algorithms for Data Base Applications" (Journal of Computer and System Sciences 31(2), 1985, 182–209). Their method achieved a relative standard error of 0.78/√m for m observation positions.

The central technique they introduced is stochastic averaging: a single extremum fluctuates wildly — it is one trial with exponential variance. So you partition the hash space by its leading bits into m subsets ("registers," "buckets"), observe each subset's own extremum, and average across all m. Variance falls with √m. More registers, more accuracy — at the price of m times a few bits.

LogLog, 2003

Marianne Durand and Philippe Flajolet improved the method in "Loglog Counting of Large Cardinalities" (ESA 2003, LNCS 2832, 605–617). The observation that gives it its name: each register only needs to store the position of the first one — a number on the order of log log N. Five bits per register suffice for cardinalities into the billions. The standard error was 1.30/√m — worse per register than Flajolet-Martin, but dramatically cheaper per register, and therefore better per byte.

HyperLogLog, 2007: The Harmonic Mean

The breakthrough came with "HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm" by Philippe Flajolet, Éric Fusy, Olivier Gandouët, and Frédéric Meunier (2007 Conference on Analysis of Algorithms, AofA'07; DMTCS proc. AH, 2007, 137–156).

The decisive change is a single line of mathematics: instead of the arithmetic or geometric mean of register values, HyperLogLog uses the harmonic mean. The reason is statistically elegant — the harmonic mean strongly dampens large outliers. And large outliers are exactly the problem here: a single register that happened to see a very long run of zeros would otherwise drag the estimate upward.

The result, quoted from the paper's abstract: the relative accuracy (the standard error) is typically about 1.04/√m. More precisely, Theorem 1 of the paper gives the constants β_m: β₁₆ ≈ 1.106, β₃₂ ≈ 1.070, β₆₄ ≈ 1.054, β₁₂₈ ≈ 1.046, and in the limit β_∞ = √(3 ln 2 − 1) ≈ 1.03896.

And then comes the sentence that changed the data world: "For instance, the new algorithm makes it possible to estimate cardinalities well beyond 10⁹ with a typical accuracy of 2% while using a memory of only 1.5 kilobytes." Cardinalities beyond a billion, 2% accuracy, 1.5 kilobytes.

The authors also put the direct comparison in their overview table: Probabilistic Counting 0.78/√m, MINCOUNT 1.00/√m, LOGLOG 1.30/√m, HYPERLOGLOG 1.04/√m. HyperLogLog matches LogLog's accuracy while consuming only 64% of the memory.

The practical reference point you have probably already used: Redis implements HyperLogLog with m = 16384 registers. 1.04/√16384 = 1.04/128 ≈ 0.81% standard error — at roughly 12 kilobytes per sketch. That is the number from the hook.

HyperLogLog++, 2013: What Google Changed in Practice

Stefan Heule, Marc Nunkesser, and Alex Hall described, in "HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm" (Proceedings of the EDBT 2013 Conference, ACM, Genoa), a series of improvements that remain the basis of production implementations (BigQuery, Presto, Druid, and others) to this day:

• 64-bit hashes instead of 32-bit. With 32 bits, hash collisions occur in material numbers at cardinalities around 10⁹, and the estimate saturates. 64 bits push that limit out of reach of practical data volumes.
• Empirical bias correction in the small-cardinality range, where the asymptotic formula is systematically off. Instead of the switch to "linear counting" proposed by Flajolet et al., they use measured bias tables.
• Sparse representation. At small cardinalities almost all registers are empty. Instead of m registers full of zeros, you store a compact list of the ones actually occupied — and switch to the dense representation only when needed. This drastically reduces memory for the (in practice extremely common) case of small sets.

In the abstract the authors state the purpose concisely: a series of improvements that reduce memory requirements and significantly increase accuracy for an important range of cardinalities.

The Property That Changes Everything: Unions Are Free

Here comes the architecturally most important point in the whole article, and tutorials often omit it.

Two HyperLogLog sketches over two disjoint or overlapping data sets can be merged exactly and losslessly: take the register-wise maximum. The result is bit-for-bit the same sketch you would have obtained had you processed both streams together from the start.

Mathematically: HyperLogLog sketches, under the register-wise maximum, form a commutative, associative, idempotent monoid — a join semilattice. Anyone who read the article on Agreement Without a Vote: CRDTs and the Art of Conflict-Free Replication will recognize the structure instantly: that is exactly the algebraic property that makes conflict-free replication possible. An HLL sketch is a CRDT.

The practical consequences are enormous:

• Precomputation per dimension. You store one sketch per hour, per country, per campaign. Any arbitrary aggregation — "distinct users in Q3 across the DACH region" — is then a union of precomputed sketches, not a recomputation over raw data.
• Arbitrary parallelization. Map-Reduce, Spark, Flink: each worker builds a local sketch, the reducer merges them. No shuffle over user IDs. That is the difference between a query that scales and one that does not.
• Raw data becomes dispensable. After aggregation you can delete the IDs. More on that in Part 7.

The warning that goes with it — and it matters: for intersections this does not hold. There is no corresponding operation. You can compute via inclusion-exclusion (|A ∩ B| = |A| + |B| − |A ∪ B|), but the absolute errors of the three estimates add up. If A and B are large and their intersection is small, the result is noise — the error can considerably exceed the estimated size. Anyone who wants to measure overlap needs a different tool (MinHash or Theta sketches, for instance). This one asymmetry is the most frequent serious misapplication of HyperLogLog I know of.

Part 4: Count-Min Sketch — Not Whether, But How Often

Bloom filters answer "is x in there?" HyperLogLog answers "how many distinct?" The third great question is: "How often did x occur?"

Graham Cormode and S. Muthukrishnan described the Count-Min Sketch for this in "An improved data stream summary: The count-min sketch and its applications" (Journal of Algorithms 55(1), 2005, 58–75, DOI 10.1016/j.jalgor.2003.12.001).

The Mechanics

The sketch is a matrix of d rows and w columns, initially zero, with one hash function per row.

Insert element x with weight 1: in each row i, increment cell [i, h_i(x)] by 1.

Query the frequency of x: read cell [i, h_i(x)] in each row and take the minimum across all d rows.

The logic of the minimum is the same asymmetry as in the Bloom filter, only in numbers rather than bits: each cell holds the sum of x's true frequency plus the contributions of all colliding elements. Each cell is therefore an overestimate. The minimum is the least contaminated estimate.

So again, a one-sided error:

• Underestimation: impossible.
• Overestimation: possible, bounded by the sizing.

The Sizing

If you want an absolute error of at most ε·N (N = sum of all weights) with probability 1 − δ, you choose

w = ⌈e/ε⌉ and d = ⌈ln(1/δ)⌉

That is the line that matters: width controls accuracy, depth controls reliability. And memory grows with 1/ε, not 1/ε². In the abstract the authors note that their bounds significantly improve on those previously known — "typically from 1/ε² to 1/ε in factor." That sounds technical, but it is the difference between practical and impractical: for ε = 0.1%, 1/ε means roughly 2,700 columns; 1/ε² means roughly 2.7 million.

What You Need It For

The classic use case is heavy hitters — the question "which elements make up more than x% of the stream?" In practice, that is surprisingly often the actual question:

• Which IP addresses are dominating traffic right now? (DDoS detection, rate limiting)
• Which search queries are trending in the last five minutes?
• Which API keys are causing the load?
• Which product IDs are hot keys and belong in the cache?

For all of these, the long tail is irrelevant — and that is precisely where the Count-Min Sketch is inaccurate. The error is absolute (proportional to N), not relative. For frequent elements it is therefore negligible; for rare elements it can constitute the whole estimate. The sketch is precise exactly where you need it and useless exactly where you do not care. That is not an accident, that is design.

Part 5: A Map of the Errors

Here is the framework I would pin to the wall:

Two things stand out when you look at this table.

First: three of the five structures have a one-sided error. That is why they are so useful architecturally. A one-sided error can be eliminated entirely by a downstream exact check — and that is exactly the dominant usage pattern.

Second: mergeability is a property of the structure, not of the implementation. Where it is absent (cuckoo filter), it is absent in principle. Anyone planning distributed aggregation should read that column first.

(Historical footnote on the last row: in 1978, Robert Morris described the approximate counter in "Counting large numbers of events in small registers," CACM 21(10), 840–842 — probably the first probabilistic data structure built on this logic. The idea: instead of N you store roughly log N, and increment only with probability 2^(−counter value).)

Part 6: Where This Is Already Running in Your Systems

What is fascinating about these structures is how invisibly ubiquitous they are.

Storage Engines: The Expensive Disk Access

This is the most important and cleanest use case. In a Log-Structured Merge-Tree, data is spread across many unsorted generations of SSTables (see Write First, Sort Later – Log-Structured Merge-Trees and the Inversion of the Database). A read request for a key that does not exist would, in the worst case, have to check every SSTable on disk — expensive, and when the key is absent, entirely wasted.

Solution: each SSTable carries a Bloom filter over its keys in RAM. Before each disk access the question is asked: "could the key be here?" On "definitely not," the access is skipped. On "probably yes," you read — and in the false-positive case find nothing.

Now notice what happens here: the overall system still always answers correctly. A false positive causes only an unnecessary disk access, i.e. latency, never a wrong result. The approximate part is fully encapsulated in a performance path, while correctness stays with the exact store. This is the pattern to carry into every design: sketch as pre-filter, exact source as authority.

In production you find this in RocksDB and LevelDB, in Apache Cassandra and HBase, in Google's Bigtable — that is, underneath a considerable share of the world's data.

Analytics: The Cardinality Question

• APPROX_COUNT_DISTINCT in BigQuery, Presto/Trino, Snowflake, Spark SQL — HyperLogLog or variants of it.
• PFADD / PFCOUNT / PFMERGE in Redis — HyperLogLog at 12 kB and 0.81% standard error.
• Apache Druid, ClickHouse, Elasticsearch's cardinality aggregation — the same principle.

What is decisive here is not the compute saving on a single query, but precomputability: because sketches are mergeable, you can materialize them as column values in aggregate tables and regroup them arbitrarily after the fact.

Networks, Caches, and Routing

The counting Bloom filter arose, as mentioned, in the context of cooperating web caches: proxies exchange compact summaries of their contents instead of querying one another. The same idea — "tell me approximately what you have" — appears today in service discovery, in set-reconciliation protocols, and in distributed deduplication systems. The kinship with the efficient comparison methods of The Tree That Condenses Truth: Merkle Trees and the Art of Efficient Integrity Verification is obvious here: both are about comparing sets without transferring them.

Count-Min Sketches sit in network telemetry and DDoS defense, because they find heavy hitters at line rate and in constant memory.

An Instructive Warning: Bitcoin's BIP37

In 2012, Bitcoin introduced Bloom filters with BIP37 so that lightweight clients ("SPV wallets") could request from full nodes only the transactions relevant to them, without revealing their exact addresses. The false-positive rate was meant to act as a privacy buffer: the node would see a noisy interest profile, not the real addresses.

In practice it did not work. Analyses showed that a node could reconstruct the addresses with high reliability through multiple filters from the same client, through correlation across connections, and through the structure of the filter itself. BIP37 is today regarded as a privacy failure and was replaced by BIP157/158 (compact block filters, client-side filtering).

The lesson is general and important: a probabilistic error rate is not cryptographic protection. Noise that protects against chance does not protect against an adversary allowed to correlate many observations. Anyone wanting to use sketches as a privacy mechanism needs a formal model — differential privacy, for instance — not a gut feeling about fuzziness.

Part 7: The Pitfalls That Hurt in Production

1. Saturation: The Filter That Quietly Rots

A Bloom filter is sized for an expected n. Fill it with 5n or 10n elements and the false-positive rate does not rise linearly, it collapses: at m/n ≈ 9.6 and k = 7 you are at 1%; with five times the element count practically all bits are set, and the filter answers "probably yes" to everything. It is not broken then — it is merely entirely useless, and without any error message.

That is the most dangerous property of this whole family: silent degradation. The operational consequence: fill rate (the fraction of set bits) must be a monitored metric, with an alert. For sets of unknown growth, scalable variants (scalable Bloom filters, layering several filters) or periodic resizing belong in the design.

2. The Error Is Deterministic, Not Random

This is the subtlest misconception, and I have seen it often. "1% false-positive rate" sounds like a die rolled afresh on each query. That is wrong. For a fixed filter content, a false positive is a property of the element: if element y is a false positive, it is one on every query, always, until the filter content changes.

Practically, this means:

• Retrying does not help. There is no "second attempt."
• The 1% refers to a random selection of non-elements. If your access pattern happens to hammer a false-positive element, you pay its cost on every single request.
• With non-cryptographic hashes, an attacker who knows the hash function and its seed can construct false positives deliberately and render the pre-filter worthless — an algorithmic complexity attack. Countermeasure: secret, per-instance random seeds; for exposed interfaces, keyed hashes (SipHash, for example).

3. Cardinality Is Not Intersection

Worth repeating, because it is the most common mistake: HyperLogLog unions exactly and intersects miserably. Dashboards that compute "users who did A and B" from HLL sketches via inclusion-exclusion produce, for small overlaps and large sets, numbers statistically indistinguishable from noise.

4. Compliance: Where "Approximately" Is Forbidden

Here things get interesting for consulting contexts, because the decision is not technical but regulatory.

Where approximation is inadmissible: anything subject to a duty of evidence or serving as the basis of a legal consequence. Billing and revenue determination. Financial reporting. Audit trails and the logging of security-relevant events. Access control — a Bloom filter must never decide an authorization on its own, because a false positive there is an unauthorized grant. The regulatorily required completeness of reporting chains (incident notifications, for instance) also tolerates no estimate.

Where approximation is not merely admissible but preferable: monitoring, capacity planning, product analytics, trend detection, pre-screening of A/B tests, anomaly detection. Here a number with 1% error available in seconds beats an exact number available in twenty minutes — because the decision it supports does not hinge on one percent.

And one point often overlooked in data protection discussions: sketches can actively support data minimization. A HyperLogLog register contains maxima of zero runs — no IDs, no hashes of complete identifiers, no recoverable elements. If all you must answer is "how many distinct visitors," you can keep the sketch and delete the raw data after a short retention period. That is purpose limitation and storage limitation under Art. 5(1)(b) and (e) GDPR, technically implemented rather than merely asserted in a policy.

With two caveats that must be stated honestly: first, this holds only for the cardinality question — a Bloom filter over user IDs very much permits membership tests ("was this person here?") and is thus by no means anonymous. Second, BIP37 shows that fuzziness alone is not anonymization. I am of the opinion that sketches are a powerful data-minimization tool, but only where the question being asked is itself aggregate — not as retroactive obfuscation of an individual lookup.

Part 8: The Deeper Lesson — Error as Design Material

I consider these structures to be more than a collection of tricks. They make visible a figure of thought that reaches far beyond data structures.

In classical computer science, correctness is binary: an algorithm is correct or defective. An error is a flaw, something to be removed. Probabilistic data structures introduce a third category: the specified, bounded, intended error. It is not a lack of quality but a dimension of the design space you turn — like latency or memory.

And once you have seen it, you see it everywhere: in lossy compression, in Monte Carlo methods, in caching with TTL (every stale answer is a calculated error traded for latency), in eventual consistency, in sampling-based tracing, in randomized algorithms, in differential privacy, where the noise is the protection. It is the same figure of thought as in The Promise Nobody Can Keep: Two-Phase Commit, Sagas and the End of the Distributed Transaction: you give up a strong guarantee you cannot afford and receive a weaker but precisely described one in exchange — which you then work with deliberately.

The difference between a good and a bad system is therefore rarely whether it has errors. It is whether the errors are named, bounded, and placed in the right spot. A Bloom filter in front of a database is a built-in error that harms no one, because it only causes work, never wrong answers. An authorization check on a Bloom filter would be the same error in the wrong spot — and a security incident.

The question is never "error-free or defective?" It is: "Which error can I afford here, in which direction, and where is the authority that catches it?"

The Central Takeaway

1. Exactness is a requirement, not a law of nature. Whether you need it is a decision with a price tag — and for cardinality, membership, and frequency, that price runs from thousands to millions of times the memory.
2. The direction of the error matters more than its magnitude. One-sided errors (Bloom: false positives only; Count-Min: overestimation only) can be encapsulated in architectures without touching the correctness of the whole. The pattern: sketch as pre-filter, exact source as authority.
3. Mergeability decides scalability. HyperLogLog's lossless union (register-wise maximum) makes it a CRDT and therefore the ideal building block of distributed, precomputed aggregation. Intersections, by contrast, are a trap.
4. Silent degradation is the operational risk. A saturated Bloom filter keeps working and is useless. Fill rates belong in monitoring.
5. Fuzziness is not privacy (BIP37), but sketches are a powerful data-minimization tool when the question itself is aggregate.

A concrete next step for this week: take the slowest query or the most expensive job in a system you look after, and ask exactly one question: "Does any decision that rests on this number depend on the last 1% of accuracy?"

For billing, audit, or authorization, the answer is no — and then you have documented a boundary, which is gain enough. For a monitoring dashboard, a capacity plan, or a product metric, it is almost always yes, estimation is allowed — and then a one-line APPROX_COUNT_DISTINCT instead of COUNT(DISTINCT …) may well be the cheapest performance improvement you ship this quarter. Test it on a real query and compare both results: the measured gap between estimate and truth is the most persuasive argument you can bring to the next architecture discussion.

Reflection question: If a deliberately built-in, bounded error can make a system better by orders of magnitude — where in your own architecture are you currently paying a high price for an exactness nobody ever requested, but which nobody has ever questioned either?

Cross-References in the Vault

• Write First, Sort Later – Log-Structured Merge-Trees and the Inversion of the Database – the most prominent production use of Bloom filters: avoiding unnecessary SSTable accesses.
• Agreement Without a Vote: CRDTs and the Art of Conflict-Free Replication – HyperLogLog sketches form a join semilattice under the register-wise maximum and are therefore a CRDT.
• The Tree That Condenses Truth: Merkle Trees and the Art of Efficient Integrity Verification – the exact answer to the same basic question: comparing sets without transferring them.
• The Needle in a Billion Haystacks: Approximate Nearest Neighbor Search, HNSW, and the Architecture of Vector Databases – the same trade in similarity search: recall for speed instead of exactness for memory.
• The Promise Nobody Can Keep: Two-Phase Commit, Sagas and the End of the Distributed Transaction – the same figure of thought at the transaction level: trading a strong guarantee for a weaker but affordable one.
• The Ring That Shares the Load: Consistent Hashing and the Art of Moving Gracefully – hashing as the structuring principle of distributed systems; here as a source of randomization, there as an assignment function.

Sources and Further Reading

• Burton H. Bloom – Space/Time Trade-offs in Hash Coding with Allowable Errors, Communications of the ACM 13(7), 1970, 422–426, DOI 10.1145/362686.362692: https://cacm.acm.org/research/space-time-trade-offs-in-hash-coding-with-allowable-errors
• Philippe Flajolet, Éric Fusy, Olivier Gandouët, Frédéric Meunier – HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm, AofA'07, DMTCS proc. AH, 2007, 137–156: https://dmtcs.episciences.org/3545/pdf
• Philippe Flajolet, G. Nigel Martin – Probabilistic Counting Algorithms for Data Base Applications, Journal of Computer and System Sciences 31(2), 1985, 182–209: https://www.gwern.net/doc/cs/algorithm/1985-flajolet.pdf
• Stefan Heule, Marc Nunkesser, Alex Hall – HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm, Proceedings of the EDBT 2013 Conference, ACM, Genoa, 2013: https://research.google/pubs/hyperloglog-in-practice-algorithmic-engineering-of-a-state-of-the-art-cardinality-estimation-algorithm/
• Graham Cormode, S. Muthukrishnan – An improved data stream summary: The count-min sketch and its applications, Journal of Algorithms 55(1), 2005, 58–75, DOI 10.1016/j.jalgor.2003.12.001: https://www.cs.ox.ac.uk/people/graham.cormode/pubs/html/CormodeMuthukrishnan04CMJalg.html
• Bin Fan, David G. Andersen, Michael Kaminsky, Michael D. Mitzenmacher – Cuckoo Filter: Practically Better Than Bloom, Proceedings of CoNEXT'14, December 2014: https://pdl.cmu.edu/PDL-FTP/FS/cuckoo-conext2014_abs.shtml
• Marianne Durand, Philippe Flajolet – Loglog Counting of Large Cardinalities, ESA 2003, LNCS 2832, 605–617, DOI 10.1007/978-3-540-39658-1_55: https://doi.org/10.1007/978-3-540-39658-1_55

Created as part of the daily learning workflow. Area of interest: Software Architecture. Estimated reading time: ~30 minutes.

← All articles