⏱️ Reading time: 10 min
Apache DataSketches documents that its CPC Sketch saves between 30% and 40% of memory compared to HyperLogLog at the same accuracy, when both sketches are serialized for storage or network transfer (source). ScopeDB, a database engine, migrated its distinct value counting to that sketch earlier this year, and finishing that Rust port meant reconstructing, with artificial intelligence, a table generator that Apache DataSketches had lost years earlier.
📑 En este artículo
- What a Probabilistic Sketch Is and What It Trades Off for Memory
- How HyperLogLog Counts Without Storing a Single Value
- CPC Sketch: The Matrix That Rescued the Original FM85 Process
- Why ScopeDB Didn’t Settle for the First Rust Crate It Found
- The Missing Code: Magic Tables Without a Generator
- HyperLogLog, CPC Sketch, or the Cloudflare Crate: How to Choose
- When Not to Use a Probabilistic Sketch
- Frequently Asked Questions About HyperLogLog and CPC Sketch
- References
What a Probabilistic Sketch Is and What It Trades Off for Memory
A probabilistic sketch is a data structure updated element by element through a hash function, answering an aggregate question (how many distinct values exist, what is the frequency of one of them) within a bounded error margin. The difference from storing the full data is radical: a HashSet grows with every new value, while a sketch like HyperLogLog or CPC occupies a fixed size, decided in advance, regardless of whether the stream carries a thousand or a billion values.
ScopeDB ran into this problem for a concrete reason: it needed to implement approx_count_distinct, the function that estimates how many unique values exist in a column without materializing all of them in memory (source). That need (counting distinct values in large-scale analytical queries) is the same one faced by any engine that reports active users or distinct queries per hour.
How HyperLogLog Counts Without Storing a Single Value
HyperLogLog’s mechanism is the one almost every textbook teaches first. Each element gets hashed, and that hash decides two things: which of the K buckets it falls into, and how many leading zeros it has (the “leading zero count”). Each bucket stores only the maximum leading-zero count it has seen so far, typically in 4 to 6 bits; any other hash that lands in that same bucket, if it does not exceed that maximum, gets discarded without leaving a trace (source). Once the sketch enters dense mode, each bucket keeps a fixed-width register, so the total size stops depending on how many distinct elements were processed.
That design is elegant, but it carries a statistical cost: by keeping only the maximum per bucket, HyperLogLog discards the rest of the information that passed through it. That exact discard is what Kevin J. Lang, a researcher at Yahoo! Research, decided to question in 2017.
CPC Sketch: The Matrix That Rescued the Original FM85 Process
In his paper Back to the Future: an Even More Nearly Optimal Cardinality Estimation Algorithm (2017), Lang proposed going back to an older idea: instead of keeping only the maximum per bucket, store the full K×64-bit matrix of the original FM85 process, the same coupon collector that this family of algorithms descends from (source). Every time row r sees a hash with c leading zeros, the sketch sets bit (r, c) to 1, without discarding anything.
Having that full matrix, instead of a single maximum, lets CPC combine a HIP estimator (which runs in real time as data arrives) with an ICON estimator designed to be mergeable without reprocessing the original data; the combination is statistically more efficient than HyperLogLog’s simple maximum (source). The cost shows up when storing or transmitting the sketch: for that matrix to not take up more space than an equivalent HyperLogLog, CPC adapts its format to data density. With few unique values it uses a sparse table of (row, column) pairs; with medium and high cardinalities it combines an 8-bit sliding window, length-limited Huffman encoding and column permutations to approach the theoretical entropy limit. According to Apache DataSketches documentation, that compressed format takes up between 30% and 40% less space than HyperLogLog at the same accuracy (source).
Why ScopeDB Didn’t Settle for the First Rust Crate It Found
Before reaching Apache DataSketches, the ScopeDB team already had a working HyperLogLog implementation: the open source crate cardinality-estimator, from Cloudflare. They dropped it as a direct dependency because the Rust HLL ecosystem was, at the time, uneven: that crate leaned heavily on unsafe code and manual bit-packing tricks, so to keep something auditable and under their own control they ended up forking it and maintaining an internal copy inside ScopeDB (source). It is a detail the original post mentions in passing, before getting to its main topic, but it sums up the state of the sketching ecosystem in Rust just over a year ago: mature in Java and C++, unstable in Rust.
The way out was porting Apache DataSketches, which already had a production-proven HllSketch plus the more efficient CpcSketch, but only in Java and C++. The Apache DataSketches community itself wanted an official Rust port; the author teamed up with other Rust developers specialized in sketching algorithms to build datasketches-rust, starting with HllSketch, and ScopeDB switched its distinct-value counting to that implementation shortly after (source). CpcSketch arrived later, in late January, via PR-75, and has been running in production at ScopeDB ever since, for more than six months now (source).
What this means for you if you write Rust and your service needs to count unique values at scale (telemetry, analytics, event deduplication): before depending on a crate that solves HLL through brute-force unsafe code, check whether datasketches-rust already covers your case. HllSketch has spent more time in production; CpcSketch is newer, but if your bottleneck is the sketch’s serialized size (because you store it per partition or send it over the network between nodes), the 30-40% savings over HLL can matter more than maturity. For a team running analytics on Rust on its own Kubernetes cluster or a PaaS, the question is not theoretical: it decides how much RAM to reserve for counting unique users per hour.
The Missing Code: Magic Tables Without a Generator
Porting CpcSketch from the original C++ and Java implementations brought a different problem than coding the algorithm itself: several lookup tables shipped with values hardcoded into the source, with no trace of how they had been computed. In total there were four families of tables, split between compression_data.rs and estimator.rs: 23 static Huffman encoding tables, 16 column permutations for the sliding window, 23 sets of coefficients for a degree-19 polynomial used for statistical correction, and 4 empirical quantile tables for confidence intervals (source).
The author’s usual practice when porting a table like this is to derive the values from scratch inside a unit test and compare them, element by element, against the original static array; that is what he did with the kxp_byte_lookup table, recalculating each of its 256 values from the bit logic that generates them (source). But for the CompressionData tables and the ICON estimator, no generator code existed in any of the Apache DataSketches repositories. The only trace left was a legacy comment with two OCaml build commands, which ran files called columnProbabilities.ml and generateHuffmanCodes.ml to produce a table in C (source). Those .ml files never showed up in any of the project’s public repositories.
With no generator in sight, the author opened issue ISSUE-720 on datasketches-java asking where that source code lived (source). Lee Rhodes, the project’s maintainer, replied on the thread: he said Kevin did most of his simulations and mathematical modeling in OCaml, that the code lived only on his personal computer, and that computer no longer exists; to Rhodes, his personal code died with him, and even if someone kept a copy of that machine, it would be like looking for a needle in a haystack. Kevin Lang died in April 2019 (source). With the original generator considered lost for good, the reconstruction ended up being solved with an AI agent system, Gemini 4 Carbon Orchestrator combined with a “Swarm” of agents, which recreated the logic of those four generators (source). Validation, once again, followed the same discipline the author already used for tables with a known generator: comparing, table by table and value by value, the reconstructed output against the static arrays already running in production in Java and C++.
flowchart TD
A["Legacy comment: 2 ocamlopt commands"] --> B["Search for columnProbabilities.ml and generateHuffmanCodes.ml"]
B --> C{"Files found"}
C -- "No, in any repo" --> D["ISSUE-720 on datasketches-java"]
D --> E["Reconstruct with Gemini 4 Carbon Orchestrator + Swarm"]
E --> F["Validate each table against the static arrays in Java and C++"]
HyperLogLog, CPC Sketch, or the Cloudflare Crate: How to Choose
For a team starting a Rust project today that needs to count unique values, the three options in this story solve the same problem with different trade-offs.
| Option | What it stores | Strength | Weakness |
|---|---|---|---|
| HyperLogLog (classic design) | A maximum leading-zero count per bucket | Simple to implement and reason about; decades of production use across languages | Discards useful statistical information; takes up more space when serialized than CPC at the same accuracy |
| CPC Sketch (Apache DataSketches) | The full K×64 matrix of the FM85 process | Saves 30-40% of serialized memory compared to HyperLogLog (source) | Complex compression format (Huffman, permutations, correction tables); its Rust port is newer |
| cardinality-estimator (Cloudflare crate) | A HyperLogLog variant implemented directly in Rust | Available before an official DataSketches port existed | Relies on unsafe code and manual bit-packing, hard to audit |
When Not to Use a Probabilistic Sketch
A probabilistic sketch never gives an exact number: if your use case is billing, regulatory compliance, or any count that has to match down to the last digit, a HyperLogLog or a CPC sketch do not replace a HashSet or an exact COUNT DISTINCT over a small table.
The CpcSketch port to Rust, moreover, is young compared with the Java and C++ implementations Apache DataSketches has spent years testing: it has been in production at ScopeDB for a bit more than six months, not decades. A team with strict stability requirements may prefer to wait until the port accumulates more real-world use, or stay on Java/C++ if that stack is already in place.
And there’s a more specific risk unique to this story: the CPC compression tables that had no public generator were reconstructed with an AI system and then validated manually against the reference values (source). Anyone taking that code for their own fork should repeat that validation, table by table, rather than assuming the reconstruction is correct just because it is already in a public repository; it is worth checking the project’s official documentation (Apache DataSketches) before trusting a third-party implementation.
Frequently Asked Questions About HyperLogLog and CPC Sketch
Does CPC Sketch Always Beat HyperLogLog on Memory?
Only when serialized: the 30-40% advantage Apache DataSketches documents applies to the size stored on disk or sent over the network, thanks to its Huffman encoding and column permutations (source). While the sketch lives only in memory, without being serialized, the practical difference is smaller.
Can Sketches Computed on Different Nodes Be Combined?
Yes: HyperLogLog shares that property through the same mechanism already described, merging two sketches is simply keeping, bucket by bucket, the maximum of the maximums. CPC carries that same idea into its ICON estimator, designed to be mergeable without reprocessing the original data (source), which allows adding up partial counts from different partitions of an analytical query.
References
- Reverse-Engineering Kevin J. Lang’s Lost OCaml Code in Apache DataSketches: primary source for the facts, figures and timeline in this article.
- PR-75 on apache/datasketches-rust: the pull request that added CpcSketch to the official Rust port.
- Apache DataSketches: official documentation for the project and its various sketches.
- Hacker News thread: community discussion of the CPC Sketch table reconstruction.
Featured image: Foto de Logan Voss en Unsplash
How each article is made (sources, testing and editorial criteria): How we work.
Did it work for you? Got a different error? Say so below: questions get answered and help the next reader.
Leave a comment
0 Comments