ZetaSketch C++

The purpose of this repository is to provide a standalone C++ implementation of Google's ZetaSketch format. This format is the serialization schema used for HyperLogLog++ aggregate mutations within Cloud Bigtable and BigQuery.

Google utilizes C++ internally for these operations; however, the open-source community is provided with a Java implementation. The absence of a native C++ library requires developers to utilize cross-language bindings. This project provides an implementation written in C++23.

The implementation is verified against the upstream Java reference library (google/zetasketch) to ensure exact byte-for-byte serialization compatibility. The reference is built from source at revision d098c49, pinned by commit hash in MODULE.bazel, rather than taken from Maven Central: the only artifact ever published there is 0.1.0 from 2019, which predates changes to the accepted range of precisions and so cannot establish compatibility with the library as it now stands. The testing apparatus utilizes the following methodologies:

The validation regimen consists of two components: a static golden corpus and a dynamic differential fuzzer.

• Static Golden Corpus (golden_corpus.tsv): Contains 84 sketch vectors, 5 merge vectors and 98 integer vectors generated by the upstream Java ZetaSketch library. These vectors scale from 0 elements up to 100,000 elements, and span normal precisions from 4 to 20. The integer vectors are rebuilt from the integers they name rather than only read back, so the integer hash is covered by a build that does not run Java.
• Dynamic Differential Fuzzer (differential_fuzzer_test.cpp): A native C++ cc_test that generates a fixed, deterministic series of string and integer values, processes it through both the C++ implementation and the Java ZetaSketch reference, and asserts strict serialization parity. The values are not random, so any failure reproduces exactly. It also holds the bounded guarantee described below: an exhaustive space of short operation sequences and a seeded random space. On the text path it executes 72 distinct CREATE operations and 54 distinct MERGE operations, yielding a further 288 intermediate sketches; on the integer path a further 49 CREATE operations, one of them built from the boundary values of the type, and 21 MERGE operations over 112 operand sketches. It additionally compares the cardinality estimate against the reference at every population from one upward across the point at which the estimator changes, and compares the bias correction against the reference at every tabulated mean and at the points between them, at every precision. It drives 120 parse shapes through the reference and compares both the verdict and the bytes written back, then carries each shape the reference reads through an addition, a merge and an estimate and compares those too, and it compares the verdict and the bytes for all 1,260 combinations of the aggregator's own fields.

The testing matrix iterates over twenty structural configurations, defined by the Normal Precision (NP) and Sparse Precision (SP). The text path runs eighteen of them:

• NP=15, SP=20: High precision, large sparse mode capacity.
• NP=10, SP=15: Low precision, standard sparse mode capacity.
• NP=15, SP=0 and NP=10, SP=0: Sparse mode explicitly disabled (forces immediate dense allocation).
• NP=4, SP=0, NP=4, SP=9 and NP=9, SP=14: The lowest normal precisions the reference accepts.
• NP=4, SP=4: The sparse precision equal to the normal precision, where every value takes the flagged encoding.
• NP=15, SP=25 and NP=24, SP=25: Both extremes of the accepted range.
• NP=5, SP=0, NP=5, SP=10, NP=6, SP=0, NP=7, SP=0, NP=7, SP=12, NP=8, SP=0, NP=8, SP=13 and NP=9, SP=0: The remaining newly accepted precisions, each compared byte for byte with sparse mode disabled and with it enabled.

The integer path runs seven: NP=15, SP=20, NP=10, SP=15, NP=24, SP=25, NP=15, SP=0 and NP=10, SP=0 from the list above, and two of its own:

• NP=15, SP=15: The sparse precision equal to the normal precision at the default normal precision.
• NP=10, SP=25: The widest gap between the two precisions.

The element populations injected into these configurations are [10, 100, 1000, 5000] on the text path and [0, 1, 10, 100, 1000, 5000] on the integer path, with the golden corpus extending to 10000 and 100000.

The testing framework explicitly invokes and asserts the results of the following C++ API methods against the Java equivalents:

• HyperLogLogPlusPlus::Create(normal_precision, sparse_precision, value_type), over the whole product of normal precisions at and around both limits against sparse precisions that are disabled, below the normal precision, equal to it, above it, at the maximum and past it, with the accepted set and the refusal messages confirmed against the reference.
• HyperLogLogPlusPlus::Create(normal_precision, value_type), which takes the sparse precision the reference's builder chooses, five above the normal precision and capped at the maximum: compared with the reference's default-built aggregator at every normal precision from one below the minimum to one above the maximum, for each of the three value types it builds for, empty and after additions.
• HyperLogLogPlusPlus::Add(std::string_view)
• HyperLogLogPlusPlus::Add(int64_t)
• HyperLogLogPlusPlus::FromBytes(std::span<const uint8_t>)
• HyperLogLogPlusPlus::Validate(), the walk of a sparse sketch's stream that reading stops short of. Every sketch the reference writes in the golden corpus and in the differential runs passes it; each defect it refuses (a stream that does not decode, does not increase, or disagrees with the recorded sparse size) is constructed and refused in error_handling_test.cpp. It checks nothing about the values themselves, because the reference writes values encoded at an old, higher sparse precision after an in-memory downgrade, which are out of range, repeat indices and promote to registers above the hash bound, and so does this library; that case is built at every pair of sparse precisions and passed in the same file.
• HyperLogLogPlusPlus::Merge(HyperLogLogPlusPlus&&), including the kinds of value the two sketches admit. The reference intersects the two admitted sets and refuses an empty intersection; every pair of the eleven admitted-set states this library can reach (untyped, each of the three value types built and read from bytes, and each narrowed by a first addition) is merged both ways, then given each kind of addition in both orders, and the verdicts, messages, bytes and estimates compared with the reference's, at six pairings of configuration that put each side in each representation, at differing precisions, and past the promotion threshold. Every merge across sparse precisions at normal precisions 4 to 12, with populations that leave values unflushed on either side, is then performed by both libraries, written and estimated after the merge and after three more additions, and compared line for line: the bytes, the estimates, and the stage at which either refuses. This is the shape that lowers a receiver to its operand's precision and carries the receiver's unflushed values across as they are, so the bytes depend on which values were still unflushed; the unflushed values are held as the reference holds them, as a set of distinct values, because the flush falls at a count of distinct values.
• HyperLogLogPlusPlus::Serialize()
• HyperLogLogPlusPlus::Result() (Cardinality estimation parity verified in golden_corpus_test.cpp).

Two implementations cannot be proved equal by testing; what is stated is a bound, and it is checked on every run. Over the operations add one value, add m/4 + 1 values, add 2m values (m being 2^p of the sketch added to; the second count is one more than the buffer holds before it flushes, and flushes it except where two of the values share an encoding, which can happen at a sparse precision within one of the normal precision; the third promotes the sketch to its dense form at every configuration below, which a test checks), merge, write, and estimate, with the values all strings or all longs, every sequence of one to three operations is performed by both libraries and compared at every write, every estimate and every refusal. The receiver is at normal precision 4, 5 or 6 with sparse mode disabled, at the normal precision, one above it, or at 25; the operand at the same or the next normal precision, with sparse mode disabled, at its own normal precision, or at 25, holding nothing, one value, m/4

• 1 values or 2m values. That is 63,048 sequences. Every addition is its own step, so a refusal is located to the very addition it happened at; the wording of a refusal is not compared. It is the same in both libraries for the incompatible-precision refusals, and differs in the 44 carried-value refusals, where the reference reports an index out of bounds, naming the index in four of them and nothing in the rest. Every write is also read back, and the sketch read must pass the walk, estimate as the writer does, and write the same bytes again. Compared are the bytes of every write and the estimate of every estimate and, where the reference throws, that this library refuses at the same step. The reference throws in 1,358 of the sequences, every one of a shape it is known to throw in: a pair of sparse configurations it declares incompatible, one higher in normal precision and lower in sparse precision, checked only while the receiver is sparse (1,314 of them, all at the merge); or unflushed values carried across a lowering to a lower sparse precision (44, at the merge or at an addition after it). Nothing after a refusal is compared, on either side. After an incompatible-precision or cross-kind refusal both libraries leave the receiver as it was, which is tested in error_handling_test.cpp; after a throw that interrupts a merge part way, the reference's state is not defined. This library's remaining steps are still performed, and must not fault; the receiver of a refused merge is left as it was moved out of, so its later writes are not read back.

On top of that, every continuous-integration test job draws a seed from the clock and compares 600 random sequences of up to twelve operations over normal precisions 4 to 12, with additions of one, three, m/4 + 1 or 2m values; 2m values promoted the sketch in every case measured: at every precision and sparse precision from the first 300 starting values, at every reachable starting value at precisions 4 to 8, and at sampled ones at 9 to 12. One sequence in four is drawn to allow the kinds of value to cross, and about one in five does, which both libraries refuse; the two sides' sparse precisions are drawn independently; so about a quarter of the sequences meet a refusal before their last step and are compared up to it. The seed and a digest of the sequences it produced are printed into the job's log, so a failure replays exactly with --test_arg=--seed=<value> and the replay can be seen to be the same sample. Every job of a run, and every re-run, draws its own seed; the CI script passes it as a test argument, which also keeps Bazel from serving a cached verdict. Locally, Bazel returns a cached result for unchanged inputs; a new sample needs a new seed or --nocache_test_results. Every sample that ever failed is replayed by its seed on every run, from a fixed list in the test, so a divergence once found cannot return unnoticed.

What may be claimed from these tests, in full:

For every sequence of one to three operations drawn from add one value, add m/4 + 1 values, add 2m values, merge, write and estimate, with the values all strings or all longs, at the receiver and operand configurations named above, this library and Google's Java ZetaSketch give the same bytes at every write and the same estimates at every estimate, up to the first refusal, and where the reference throws, this library refuses at the same step; the wording of a refusal is not compared. There are 63,048 such sequences; every continuous-integration test job compares all of them, and every one has agreed in every job, on x86_64, and on arm64 up to commit 0eead28. Nothing after a refusal is compared.

Beyond that set, every continuous-integration test job draws a seed from the clock, prints it in its log with a digest of the sample, and compares 600 further random sequences of up to twelve operations at normal precisions 4 to 12. A disagreement at any compared step fails the run, and the seed replays the sample exactly. Each green job therefore records in its log a seed and a digest from which its 600 draws, a few of which may repeat, replay exactly, and on which every compared step agreed; about a quarter of them are compared only up to a refusal both libraries make. What grows with every job is the number of sequences on which agreement has been observed. Nothing is claimed about sequences that have not been compared, and no probability of agreement on them is claimed.

One shape is left out of both spaces: an operand at a lower normal precision than the receiver, in either representation. The reason is the dense receiver: that merge lowers the reference's state but not its own encoding of it, so its later additions index outside the register array and throw, or land in the wrong register and miscount, and a sketch written after those additions carries the miscount. The merge itself writes correctly. This library lowers both together and continues correctly, which is tested in error_handling_test.cpp; the sparse receiver's case is the ordinary lowering, compared elsewhere in the differential tests as a single merge.

A sketch begins sparse and becomes dense when its stream reaches three quarters of the register array. At normal precision 10 with sparse precision 15, and with 25, for strings and for longs, every value from the first to well past the promotion point is followed by a write and an estimate on both sides, and every line is compared; the step of promotion, read from the bytes, must exist and agree. Every write compacts the buffer, so the walk holds the promotion check at every step; the flush of a full buffer and a promotion at an addition are exercised by the two spaces above. The two other roads into the dense form are compared at the same configurations: a sketch written one value short of promotion, read back, and given the value; and two sparse sketches each holding six tenths of the promoting count, merged in both orders.

• Inputs: strings (hashed as UTF-8 text, or as raw bytes through the byte channel), and 64-bit integers, at encoding version 2. The reference's 32-bit integer mode is not implemented: sketches typed for it are read, written back, merged and estimated by the tests only while empty, since this library offers no 32-bit addition and no test adds one through the reference.
• Reference: the Java library built from source at revision d098c49, on x86_64, and on arm64 up to commit 0eead28, under the release build and under the address, undefined-behaviour, thread and memory sanitizers.
• Precisions: normal precisions 4 to 24 and sparse precisions from the normal precision to 25 or disabled are accepted, as the reference accepts them; sketches holding values are compared at every normal precision from 4 to 12 and at 15, 20 and 24. - Every error code this library defines is produced through a public call in error_handling_test.cpp, except the one for a message that fails to serialize, which no input reaches. The branches no public call reaches are listed by name in that file, beside the tests that cover the rest, and the coverage workflow measures the remainder.

The primary objective of this project is byte-identical serialization with the Java implementation. Discrepancies in the serialized bytes render the output incompatible with the Cloud Bigtable ecosystem. To that end the exact Protocol Buffer definitions (hllplusplus.proto) are compiled from Google's repository, and the exact farmhash.cc and farmhash.h sources are copied from Google's FarmHash repository, so that Fingerprint64 hashes as the original does. The sparse and dense representations were first translated from the zetasketch-rs Rust codebase and have since been read and corrected function by function against the Java source: the flush, the merge, the lowering of precisions, the rho computations and the intake of sparse values into the dense form.

The library is built to the constraints of RowKeyDB. An addition to a dense sketch allocates nothing; the register array is allocated once. An addition to a sparse sketch allocates when the buffer grows, which happens a logarithmic number of times, and when a full buffer is flushed into the stream, which allocates the new stream. A write allocates: the state is copied out of the representation, the data into the message, and the message into the output; a caller that keeps its output vector between writes saves the last of those. A refused operation allocates for its message.

The continuous integration pipeline builds on the infrastructure shared with RowKeyDB (rowkeydb-com/rowkeydb-build-infra): Bazel runs in that repository's image, named by digest, on GitHub's machines, and BuildBuddy executes every action in the same image; a pull request from a fork, which GitHub gives no secret, is built on GitHub's machine alone. The code passes clang-tidy with the checks named in .clang-tidy, and every test runs under the address, undefined behaviour, thread and memory sanitizers on x86_64. Up to commit 0eead28 they also ran on arm64; that returns when the shared infrastructure provides an arm64 image.

This project is licensed under the Apache License, Version 2.0 (APL). The code that has been copied directly from Google (such as the FarmHash implementation and the Protocol Buffer definitions) retains its original licensing and copyright notices. The logic that has been ported from the zetasketch-rs project includes all necessary credits and attributions to its original authors. All other modifications and original code within this repository are Copyright RowKeyDB (2026).