Repository navigation
Replies: 1 comment
|
Timeline (lazy consensus). I will be traveling until Oct 25, so this discussion stays open until Sunday, October 25, 2026. If there are no objections by then, we will start implementing the recommended options (6(a)–(e), with 6(d)(ii) and 7.3(b)) and reference this Discussion in the PRs. If there are objections, we'll resolve them here first. |
0 replies
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Uh oh!
There was an error while loading. Please reload this page.
While updating the cross-language snapshots in 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.skinserts the itemsi = 0..9with weights10·i², using the default seed. We generated it from the same commit (datasketches-cpp16d4ea6) on macOS and on Linux, then deserialized both files on macOS and queried each item: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:
std::default_random_engine(seed)withstd::uniform_int_distribution<uint64_t>, plusseedcount_min_impl.hpp:53-58new java.util.Random(seed).nextLong()CountMinSketch.java:112-114rand.New(rand.NewSource(seed)).Int(), plusseedcount_min_sketch.go:54-57C++: 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:
For example, libc++ defines
std::default_random_engineasminstd_rand(multiplier 48271), while libstdc++ defines it asminstd_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:
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 maph1to a bucket differently:h1 % numBucketson an unsigned 64-bit valuecount_min_sketch.go:98Math.floorMod(h1, numBuckets)on the signed valueCountMinSketch.java:132The two agree only when
h1's sign bit is clear ornumBucketsis 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.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:
hash[0] >>> 1h1 >> 1h1 >> 1((h0 + i*h1) >>> 1) % numBitsCount-Min should follow the same convention:
This gives the same result in every language, whether its 64-bit integers are signed or unsigned.
4. Item encoding
A
longis 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:
(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) % numBucketsin 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:
floorModbucket mapping for version 1 images.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
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.)
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.)
Until fixed versions are released, should we:
(Removing the sketches is pretty drastic and eliminates even within language and std-lib use)
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.
(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)).)
All reactions