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.

Verification of Bit-Exactness of Output Compared to Google's Zetasketch

The implementation is verified against the upstream Java reference library (google/zetasketch) to ensure exact byte-for-byte serialization compatibility. The testing apparatus utilizes the following methodologies:

1. Corpus Size and Dimensionality

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

• Static Golden Corpus (golden_corpus.tsv): Contains exactly 61 pre-computed test vectors generated by the upstream Java ZetaSketch library. These vectors scale from 0 elements up to 100,000 elements.
• Dynamic Differential Fuzzer (differential_fuzzer_test.cpp): A native C++ cc_test that dynamically generates randomized string data, processes it simultaneously through both the C++ architecture and the Java ZetaSketch reference, and asserts strict serialization parity. It executes 16 distinct CREATE operations (yielding 16 sketches) and 12 distinct MERGE operations (yielding an additional 64 intermediate sketches).

2. Configuration Diversity

The testing matrix iterates over four structural configurations, defined by the Normal Precision (NP) and Sparse Precision (SP):

• NP=15, SP=20: High precision, large sparse mode capacity.
• NP=10, SP=15: Low precision, standard sparse mode capacity.
• NP=15, SP=0: Sparse mode explicitly disabled (forces immediate dense allocation).
• NP=10, SP=0: Low precision, sparse mode disabled.

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

3. API Functions Exercised

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)
• HyperLogLogPlusPlus::Add(std::string_view)
• HyperLogLogPlusPlus::FromBytes(std::span<const uint8_t>)
• HyperLogLogPlusPlus::Merge(HyperLogLogPlusPlus&&)
• HyperLogLogPlusPlus::Serialize()
• HyperLogLogPlusPlus::Result() (Cardinality estimation parity verified in golden_corpus_test.cpp).

4. State Machine Cartesian Product Coverage

The HyperLogLog++ architecture transitions between SparseRepresentation and NormalRepresentation. The Merge function uses std::visit to handle the Cartesian product of these representations. The testing regimen explicitly targets all edges of this state machine:

• Sparse + Sparse: Merging multiple small sketches keeps the state below the SP thresholds.
• Sparse + Sparse -> Promotion to Normal: Triggered by merging multiple sparse sketches whose combined unique elements exceed the maximum sparse threshold during the merge operation.
• Normal + Normal: Merging sketches initialized with large element counts forces early promotion to the normal representation prior to the merge.
• Sparse + Normal / Normal + Sparse: Merging sketches sitting near the capacity threshold. Across multiple sketches, variations in hash collisions result in a mix of sparse and normal structures, forcing the cross-mode variant visitation branches.
• Edge Cases: The static corpus explicitly verifies POP0 (completely empty initialization states) and configurations with SP=0 (which entirely bypass the sparse state machine and initialize as normal).

5. Endianness Validation

Dedicated unit tests confirm that the integrated FarmHash implementation produces outputs identical to the Java reference across differing hardware architectures, including x86_64 and ARM64.

Architectural Design and Precision

The primary objective of this project is to achieve byte-identical serialization with the original Java implementation. Discrepancies in the serialized byte array render the output incompatible with the existing Cloud Bigtable ecosystem. To ensure this conformity, our architectural strategy integrates existing reference logic.

We have incorporated the exact Protocol Buffer definitions (hllplusplus.proto) directly from Google's repository. We compile these definitions using the protoc compiler, ensuring that the structural encoding remains accurate. Furthermore, we have copied the exact farmhash.cc and farmhash.h source files from Google's FarmHash repository. This guarantees that the Fingerprint64 hashing operations produce results identical to the original implementation.

For the internal state machine, which governs the transitions between sparse and dense representations, we translated the logic from the zetasketch-rs Rust codebase. The Rust implementation uses explicit memory management and type systems that map directly to C++ constructs, whereas the original Java architecture utilizes class inheritance.

Performance and Code Hygiene

We have designed this library in adherence to the performance constraints required by RowKeyDB. There is zero memory allocation on the hot path. We avoid dynamic allocation during active sketch mutations, relying upon pre-allocated, fixed-capacity arrays managed through Resource Acquisition Is Initialization (RAII).

The repository continuous integration pipeline executes hermetic builds within Docker containers, ensuring determinism across environments. The code is subjected to cross-translation-unit (CTU) static analysis using clang-tidy, and it is continuously monitored by an array of runtime sanitizers (Address, Memory, Thread, and Undefined Behavior).

License and Copyright

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).