tisonkun opened a new issue, #297: URL: https://github.com/apache/datasketches-rust/issues/297
Count-Min sketches can be deserialized across implementations without an error while producing incorrect frequency estimates. The binary layout and global seed hash agree, but the per-row hash seeds do not. This is a semantic interoperability bug, beyond a difference in serialized bytes. This was investigated while clarifying the documentation in #296. That PR documents the current limitation; this issue tracks a separate compatibility fix. ## Reproduction and observed behavior The existing TCK fixture `count_min_non_empty_cpp.sk` uses 3 rows, 1,024 buckets, and seed 9001. Its [C++ generator](https://github.com/apache/datasketches-cpp/blob/16d4ea6f2013f7fb005eb53ea2b88bf5da937652/count/test/count_min_test.cpp#L232-L247) inserts unsigned 64-bit keys `i = 0..9` with weights `10 * i * i`. The total weight is 2,850. After running `cargo x prepare-testdata cpp`, this Rust example, run from the repository root, exposes the problem: ```rust use datasketches::countmin::CountMinSketch; let bytes = std::fs::read( "tests-integration/tests/serde_tests/cpp_generated_files/count_min_non_empty_cpp.sk", ).unwrap(); let mut sketch = CountMinSketch::<u64>::deserialize(&bytes).unwrap(); assert_eq!(sketch.total_weight(), 2850); assert_eq!(sketch.serialize(), bytes); // Expected estimates for this fixture: 10 and 810. assert_eq!(sketch.estimate(1u64), 0); assert_eq!(sketch.estimate(9u64), 0); sketch.update_with_weight(1u64, 5); // The existing weight 10 is effectively lost to this query. assert_eq!(sketch.estimate(1u64), 5); // Expected 15. ``` I also generated the same input independently in Rust, C++ with libstdc++, C++ with libc++, and Go, then loaded each image into every implementation. The table shows `estimate(1), estimate(9)` after deserialization: | Reader / writer | Rust | C++ / libstdc++ | C++ / libc++ | Go | | --- | --- | --- | --- | --- | | Rust | 10, 810 | 0, 0 | 0, 0 | 0, 0 | | C++ / libstdc++ | 0, 0 | 10, 810 | 0, 0 | 0, 0 | | C++ / libc++ | 0, 0 | 0, 0 | 10, 810 | 0, 0 | | Go | 0, 0 | 0, 0 | 0, 0 | 10, 810 | All readers accepted all four images and reported total weight 2,850. Rust and Go reproduced each imported image byte for byte. Updating key 1 by 5 yielded 15 for a matching writer/reader and 5 for every mismatching pair in this example. These zero estimates are not ordinary Count-Min approximation error: the input contains only positive weights, yet the previously inserted weights are missed. Reproduction versions: - Rust: `74c60477a5d801642f094b266812e5828b04de6b`. The same row-seed derivation is present in v0.5.0. - C++: `16d4ea6f2013f7fb005eb53ea2b88bf5da937652`, the revision selected by the Rust repository's [pinned TCK configuration](https://github.com/apache/datasketches-tck/blob/8193bab45ca5da3b513ea43fb5793e7e5b4da548/config.toml). - C++ toolchains: GCC 14.2.0 / libstdc++ on Linux and Apple Clang 21.0.0 / libc++ on macOS. The libstdc++ output exactly matched the existing TCK fixture. - Go: `327fd976228ccfce4794318db3db500a8310d073`, tested with Go 1.27.1 on darwin/arm64. - The experiments used 64-bit integer keys and nonnegative integer weights that fit in both `u64` and `i64`, avoiding string framing and counter representation differences. ## Cause and history The implementations derive row seeds differently: | Implementation | Row-seed derivation | | --- | --- | | [Rust](https://github.com/apache/datasketches-rust/blob/74c60477a5d801642f094b266812e5828b04de6b/datasketches/src/countmin/sketch.rs) | For each row index, hash its 8-byte little-endian representation with MurmurHash3 x64 128 using the global seed, then take the first 64-bit result. | | [C++](https://github.com/apache/datasketches-cpp/blob/16d4ea6f2013f7fb005eb53ea2b88bf5da937652/count/include/count_min_impl.hpp) | Seed `std::default_random_engine` with the global seed; draw from `std::uniform_int_distribution<uint64_t>(0, UINT64_MAX)`; add the global seed. | | [Go](https://github.com/apache/datasketches-go/blob/327fd976228ccfce4794318db3db500a8310d073/count/count_min_sketch.go) | Use `rand.New(rand.NewSource(seed))`, then `int64(rng.Int()) + seed` for each row. | Rust has used this derivation since the initial implementation in #38; `git log -L :make_hash_seeds:datasketches/src/countmin/sketch.rs` shows no subsequent algorithm change. The original comment states that the seeds are derived deterministically, but the inspected PR discussion does not explain the choice relative to C++. The C++ serialization tests added in #92 explicitly limit their checks to metadata and byte round-tripping because row-seed derivation differs. The [current test helper](https://github.com/apache/datasketches-rust/blob/74c60477a5d801642f094b266812e5828b04de6b/tests-integration/tests/serde_tests/countmin.rs) retains that limitation, so those passing tests do not establish query compatibility. The version-1 image stores the global seed hash, dimensions, total weight, and counters. It stores neither the row seeds nor an identifier for their derivation. Deserialization reconstructs the row seeds using the reader's algorithm. Matching the global seed hash therefore does not establish that the counters represent the same item-to-bucket mapping. Merging an imported sketch with a native one is also unsafe: the current compatibility check only compares dimensions and the global seed. ## Go and C++ portability DataSketches Go already implements Count-Min in its `count` package, including integer/string updates, estimates, merging, serialization, and deserialization. It has the same interoperability problem with Rust and the two tested C++ builds; it is not a ready-made compatible reference for Rust to copy. There is also no single portable sequence implied by the current C++ source. The C++ standard leaves both [`default_random_engine`](https://eel.is/c++draft/rand.predef#10) and [distribution algorithms](https://eel.is/c++draft/rand.dist.general#3) implementation-defined. In the tested builds, libstdc++ uses `minstd_rand0`, whereas libc++ uses `minstd_rand`. Merely selecting a fixed engine would still leave the distribution algorithm unspecified. The C++-to-C++ failures above demonstrate the practical consequence. ## Follow-up design and acceptance criteria 1. Agree with the C++ and Go implementations on a fully specified row-seed algorithm, including integer widths, overflow, and any random-output mapping. If the immediate target is the existing C++ TCK fixtures, reproduce the specific libstdc++ engine **and** distribution algorithm explicitly; document that this does not cover legacy libc++ or Go images. 2. Decide how to identify and read legacy images before changing Rust's default. The current Rust algorithm has shipped, and silently replacing it would misinterpret existing Rust images. A versioned format or an explicit legacy-algorithm selection is needed; the current header cannot distinguish these mappings. Existing counter arrays cannot generally be remapped to a new hash scheme without the original input. 3. Add shared row-seed vectors and cross-language tests that assert estimates, updates after deserialization, and compatible merges against known input. Cover default and custom seeds and the relevant C++ standard libraries. Byte round-tripping alone is insufficient. 4. Keep the limitation explicit in the public serialization/deserialization documentation until interoperable behavior is implemented. No hashing or serialization behavior is changed by #296. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
