GitHub user leerho created a discussion: Count-Min sketch is not compatible across languages, or across C++ standard libraries
While updating the cross-language snapshots in [datasketches-tck](https://github.com/apache/datasketches-tck), we found that the Count-Min sketch cannot be shared between languages, and in C++ not even between builds that use different standard libraries. A deserialized sketch silently returns wrong estimates. Count-Min's main guarantee, that it never underestimates, does not hold for these sketches. We should agree on a fix strategy before anyone changes code. ## 1. What happens The C++ test that generates `count_min_non_empty_cpp.sk` inserts the items `i = 0..9` with weights `10·i²`, using the default seed. We generated it from the same commit ([datasketches-cpp `16d4ea6`](https://github.com/apache/datasketches-cpp/commit/16d4ea6f2013f7fb005eb53ea2b88bf5da937652)) on macOS and on Linux, then deserialized both files on macOS and queried each item: | Item | Inserted | Estimate from macOS file | Estimate from Linux file | |---:|---:|---:|---:| | 1 | 10 | 10 | **0** | | 2 | 40 | 40 | **0** | | 5 | 250 | 250 | **0** | | 9 | 810 | 810 | **0** | All 9 non-zero items behave the same way. Both files report `total_weight = 2850`, and neither raises an error. The Linux-built sketch is useless when read on macOS, and vice versa. ## 2. Cause: each implementation derives its per-row hash seeds differently Each row of a Count-Min sketch hashes an item with its own row seed. The serialized image stores only the base seed (as a 16-bit seed hash). Every implementation re-derives the row seeds from the base seed with a pseudo-random number generator (PRNG), and each uses a different one: | Language | Row seed derivation | Source | |---|---|---| | C++ | `std::default_random_engine(seed)` with `std::uniform_int_distribution<uint64_t>`, plus `seed` | [`count_min_impl.hpp:53-58`](https://github.com/apache/datasketches-cpp/blob/16d4ea6f2013f7fb005eb53ea2b88bf5da937652/count/include/count_min_impl.hpp#L53-L58) | | Java | `new java.util.Random(seed).nextLong()` | [`CountMinSketch.java:112-114`](https://github.com/apache/datasketches-java/blob/059b5a9ccf15f4036a50624cc910128e6b015636/src/main/java/org/apache/datasketches/count/CountMinSketch.java#L112-L114) | | Go | `rand.New(rand.NewSource(seed)).Int()`, plus `seed` | [`count_min_sketch.go:54-57`](https://github.com/apache/datasketches-go/blob/fdcffae6c0c42be7576012a772ec287e242b1887/count/count_min_sketch.go#L54-L57) | - **C++:** the standard leaves both the default engine and the distribution's algorithm to each standard library. The difference comes from the standard library the code is built against, not the compiler: - libc++, the LLVM project's library and the default on macOS - libstdc++, GNU's library and the default on Linux, even with Clang - the MSVC STL on Windows For example, libc++ defines `std::default_random_engine` as `minstd_rand` (multiplier 48271), while libstdc++ defines it as `minstd_rand0` (multiplier 16807). So row seeds, and therefore bucket positions, differ between standard libraries even within C++. That's what the table above shows. - **Java and Go:** each is internally portable, because their PRNG algorithms are fixed. But the two derivations differ from each other and from C++. So a Count-Min sketch built in one language gives wrong answers in any other language. ### Affected releases Count-Min has already shipped in these implementations, all with the derivations above: | Implementation | Releases with Count-Min | |---|---| | C++ | since 4.1.0 (Apr 2023); current 5.2.0, and 5.3.0-rc1 | | Python (wraps C++) | 5.1.1 and 5.2.0 | | Java | 9.0.0 (Dec 2025) | | Go | v0.1.0 (Feb 2026) and v0.2.0 | Python is probably where users are most likely to hit the C++ problem. Its wheels are built per OS: Linux wheels use libstdc++, macOS wheels libc++, and Windows wheels the MSVC STL. A sketch serialized by Python on a Linux server and read by Python on a Mac returns wrong estimates. Within one language, and in C++ within one standard library, version 1 images work correctly today. Users who stay within one language and standard library are not affected. ## 3. A separate bug: mapping a hash to a bucket This bug is independent of the row seeds. It would break cross-language use even if all three implementations derived identical row seeds. All three implementations hash items with MurmurHash3_x64_128 and take `h1`. Then they map `h1` to a bucket differently: | Language | Mapping | Source | |---|---|---| | C++, Go | `h1 % numBuckets` on an **unsigned** 64-bit value | [`count_min_sketch.go:98`](https://github.com/apache/datasketches-go/blob/fdcffae6c0c42be7576012a772ec287e242b1887/count/count_min_sketch.go#L98) | | Java | `Math.floorMod(h1, numBuckets)` on the **signed** value | [`CountMinSketch.java:132`](https://github.com/apache/datasketches-java/blob/059b5a9ccf15f4036a50624cc910128e6b015636/src/main/java/org/apache/datasketches/count/CountMinSketch.java#L132) | The two agree only when `h1`'s sign bit is clear or `numBuckets` is a power of two. The suggested bucket count, `ceil(e / relativeError)`, usually isn't a power of two, so about half of all items land in a different bucket. > Example: `h1 = -7`, `numBuckets = 1000` gives **993** in Java and **609** in > C++/Go. We solved the same problem early on in the count-unique sketches: an unsigned right shift by one clears the sign bit and leaves 63 bits, which are plenty. Theta and tuple do this in every language, and so does the Bloom filter: - Java theta: [`hash[0] >>> 1`](https://github.com/apache/datasketches-java/blob/059b5a9ccf15f4036a50624cc910128e6b015636/src/main/java/org/apache/datasketches/theta/UpdatableThetaSketch.java#L353) - C++ theta: [`h1 >> 1`](https://github.com/apache/datasketches-cpp/blob/16d4ea6f2013f7fb005eb53ea2b88bf5da937652/theta/include/theta_update_sketch_base.hpp#L183) - Go theta: [`h1 >> 1`](https://github.com/apache/datasketches-go/blob/fdcffae6c0c42be7576012a772ec287e242b1887/theta/hashtable.go#L108) - Bloom filter: [`((h0 + i*h1) >>> 1) % numBits`](https://github.com/apache/datasketches-java/blob/059b5a9ccf15f4036a50624cc910128e6b015636/src/main/java/org/apache/datasketches/filters/bloomfilter/BloomFilter.java#L375) Count-Min should follow the same convention: ``` bucket = (h1 >>> 1) % numBuckets // h1 >> 1 on an unsigned 64-bit value ``` > Example: `h1 = -7`, `numBuckets = 1000` gives **804** in every language. This gives the same result in every language, whether its 64-bit integers are signed or unsigned. ## 4. Item encoding A `long` is hashed as 8 bytes in native byte order in Java (`JAVA_LONG_UNALIGNED`) and C++, and explicitly little-endian in Go. Strings are hashed as UTF-8 in all three. These agree today on little-endian hardware, but the spec should say little-endian for numbers and UTF-8 for strings, so that a big-endian platform can't diverge. ## 5. Why our tests didn't catch it Only C++ produces Count-Min snapshots in the TCK, and no cross-language test reads them. The TCK's cross-language binary (CLB) tests currently cover only theta and HLL. Each language's round-trip tests pass because they serialize and deserialize on the same platform, in the same language. ## 6. Proposal **a) Deterministic row seeds.** Replace the PRNG with a specified, portable hash of the base seed and the row index, for example: ``` rowSeed[i] = h1 of MurmurHash3_x64_128(8-byte little-endian i, seed = baseSeed) ``` (or XXHash64; MurmurHash3 is already used by Count-Min in all three implementations). The exact formula should be agreed here and written into the format spec with test vectors. **b) Fix the hash-to-bucket mapping** (section 3) with the project's existing convention: `bucket = (h1 >>> 1) % numBuckets` in every language. **c) Specify item encoding** (section 4): integers as 8-byte little-endian; strings as UTF-8 bytes; empty items ignored, as today. **d) Bump the serial version** (preamble byte 1, 0-based) from 1 to 2. Every current reader rejects any version other than 1, so released versions fail loudly on new sketches instead of returning wrong counts. A version 1 image doesn't record which derivation produced its row seeds, so new readers have two options: | Option | Behavior | Trade-off | |---|---|---| | **(i) Reject version 1** | Readers accept only version 2. | Simple and safe. But users who stay in one language, whose sketches work today, would have to rebuild them from source data. | | **(ii) Accept version 1 with each language's legacy derivation** | Readers use the old PRNG and, in Java, the old `floorMod` bucket mapping for version 1 images. | Images written by the same language (and, in C++, the same standard library) keep working. Cross-language use of version 1 images stays unsupported, which is no worse than today. The cost is keeping the legacy code path in each implementation. | Either way, the release notes must explain the change. **e) Add Count-Min to the TCK cross-language tests:** snapshots from every language, plus a CLB byte comparison. Once (a)–(c) are fixed, identical inputs should produce byte-identical images in every language. ## 7. Questions for the community 1. Do we agree on deterministic row seeds, and on which hash and formula to use: MurmurHash3_x64_128 or XxHash64, and how to combine the base seed with the row index? *(I would recommend XxHash64. We only need 64 bits and it is 2x faster than MurmurHash3_64_128, and already in our library.)* 2. Do we agree on the unsigned shift by one before the modulo, as theta, tuple and the Bloom filter already do, and on the item encoding in 6(c)? *(I recommend the unsigned shift, which is already our convention.)* 3. Until fixed versions are released, should we: - (a) remove Count-Min from the implementations <br> *(Removing the sketches is pretty drastic and eliminates even within language and std-lib use)* - (b) keep it, but document in each implementation that its serialized form is not portable across languages (or, for C++, across standard libraries), until we have a fix? *(I would recommend this)* 4. Any objection to the serial version bump to 2? For version 1 images, should new readers reject them (6(d)(i)), or keep reading them with each language's legacy derivation (6(d)(ii))? Option (ii) protects users who stay within one language, which is probably most of them, at the cost of keeping legacy code in each implementation.<br> *(We already have cases where we have kept legacy code in the library for backward compatibility, which is a minor cost. I would recommend (6(d)(ii)).)* GitHub link: https://github.com/apache/datasketches-tck/discussions/18 ---- This is an automatically sent email for [email protected]. To unsubscribe, please send an email to: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
