Repository navigation
Array-of-strings tuple sketch: key hashing is incompatible with Java (UTF-8 vs UTF-16) #533
Description
@proost, while checking cross-language binary compatibility of the tuple sketches against the snapshots in datasketches-tck, we found that the C++ array-of-strings (AoS) tuple sketch hashes keys differently from Java. For the same keys, C++ and Java produce completely different hashes, so their sketches cannot be meaningfully combined.
Evidence
Comparing the TCK snapshots aos_*_cpp.sk and aos_*_java.sk, generated from the same keys:
| Case | Retained (Java / C++) | Hashes in common |
|---|---|---|
aos_1_n10 |
10 / 10 | 0 |
aos_1_n1000 |
1000 / 1000 | 0 |
aos_multikey_n1000 |
1000 / 1000 | 0 |
aos_unicode |
3 / 3 | 0 |
Each language reads the other's files without error, so nothing fails visibly. But a union of a Java sketch and a C++ sketch built from the same keys double-counts every key, and an intersection comes out empty.
Cause
The seed (0x7A3CCA71) and the , separator match Java, but the bytes that get hashed don't:
- Java (
tuple/Util.stringArrHash) hashes the joined key as UTF-16 code units:final String s = stringConcat(strArray); // joined with ',' return hashCharArr(s.toCharArray(), 0, s.length(), PRIME);
XxHash.hashCharArrhashes eachcharas 2 bytes, little-endian. - C++ (
hash_array_of_strings_keyintuple/include/array_of_strings_sketch_impl.hpp) hashes the UTF-8 bytes of each string.
Why C++ and Go should change, not Java
All three implementations need to agree. The cost of changing each one differs a lot:
- Java has shipped its AoS sketch for years. Changing its hashing would make every AoS sketch Java users have already saved incompatible with new ones. It would also break Java's compatibility with itself across versions. Java also hashes UTF-16 deliberately: that is how Java stores strings, so it can hash them without first converting them.
- C++ has never released its AoS sketch (feat: AoS tuple sketch #476). Changing it now affects no users.
- Go released its AoS sketch only recently, in v0.2.0. As a pre-1.0 library, it can make breaking changes between minor versions, provided the release notes call them out.
So Java is the reference, and C++ and Go should match it.
Why this issue wasn't caught earlier
Our current cross-language tests only check that the .sk files can be read, not that the hashes match. We discovered this only recently, when we began Cross-Language Binary (CLB) testing.
Proposed fix
- In
hash_array_of_strings_key, convert each key string from UTF-8 to UTF-16 code units, using surrogate pairs for code points above U+FFFF. Hash the code units as little-endian bytes, with,as2c 00between strings. Invalid UTF-8 should throwstd::invalid_argument. - Add a test that builds sketches in C++ from the same keys as the Java generators (
AosSketchCrossLanguageTest) and requires the hash sets to equal those in the Java.skfiles, includingaos_unicode. - Update the header comment, which currently says the hashing matches Java.
We have verified this approach: with UTF-8 to UTF-16LE conversion, C++ reproduces the hashes in every Java AoS snapshot exactly. That includes aos_unicode, whose keys contain Korean, Cyrillic and emoji outside the BMP (🔑, 🗝️), and the multikey and 1,000,000-item cases. Apart from the hashing, the format already matches: every multi-entry Java AoS snapshot round-trips through C++ byte for byte.
Optional, while in this code: compact_array_of_strings_tuple_sketch::serialize() has no default serde, unlike deserialize(). Calling it without passing default_array_of_strings_serde<>() compiles but fails at link time with an undefined serde<array<std::string>> symbol.
Timing
The C++ AoS sketch (#476) has not been released yet. We'd like to fix this before 5.3.0, which we plan to release very soon, so that the first release is compatible with Java. Otherwise, fixing it later would invalidate C++ users' saved sketches.
Could you take this on in the next few days? If you're short on time, let us know and we can prepare the PR for your review.
Go has the same issue; see apache/datasketches-go#191.
Activity
proost commentedon Oct 1, 2026
I have short time about two weeks.
What i think:
Because of this two reasons, i suggest revert my AoS sketch PR.
Releasing 5.3.0 is more important than introducing AoS sketch.
I will rewrite completely binary compatible AoS sketch.
leerho commentedon Oct 1, 2026
Two additions to include in the fix:
Hash input, precisely: the UTF-16 code units of the joined key, as little-endian bytes with no byte-order mark (UTF-16LE). This is what Java's
XxHash.hashCharArr(s.toCharArray(), ...)hashes. Note that a generic "UTF-16" converter is not the same thing: Java's ownStandardCharsets.UTF_16, for example, writes aFE FFbyte-order mark followed by big-endian bytes.Document the key-join behavior. Key elements are joined with
","without escaping, so different keys that join to the same string hash the same and are treated as one key, for example{"a,b"}and{"a", "b"}, or an empty array and{""}. We can't change this without breaking compatibility with Java, so all implementations must keep this behavior. Please note it in the API documentation, along these lines:We'll add the same note to the Java documentation.
leerho commentedon Oct 2, 2026
@proost ,
Your proposal makes sense. We should revert C++ AoS for 5.3.0. It removes the release blocker today, and the C++ AoS sketch never ships with incompatible hashing.
I will open a disscussion on dev@ WRT the earlier UTF-8 validation discussion[1]. what we missed before was the already released Java AoS that used UTF-16, no BOM, which has been out for years. This discussion should not be rushed.
Claude helped me determine that the revert can be done cleanly: no later commits touch the 8 affected files, five can be deleted outright, and only two CMakeLists.txt files plus 39 lines in array_tuple_sketch.hpp need edits, with no downstream Python bindings at risk. Claude can test the revert locally without pushing to check if anything later depends on those 39 lines. If you are short on time I can have Claude do the revert for you. With your permission I can push the revert and open the PR for you to approve quickly, which will allow us to move forward on 5.3.0.
There are some ripple effects for the revert:
As for the rewrite, we don't need a 3rd party library to do a conversion from UTF-8 to UTF-16E: it is about 30 lines of code with no dependencies and reproduces Java's encoding exactly (what you also suggested in February). I could have Claude help with the rewrite also, but we need the result of the discussion for that and your go-ahead.
[1]: [DISCUSS] UTF-8 validation for string SerDe across sketches", 14 messages from Feb 14 to Mar 12, 2026.
https://lists.apache.org/thread/8p36zbmjp57fcjq7tlss69zy67459jv1
leerho commentedon Oct 2, 2026
The discussion on dev@ is open. https://lists.apache.org/thread/5vlbnodmw8h5s0oc1988f4pdhkjnv8qw
proost commentedon Oct 3, 2026
Thanks! Could you revert my merged PR?
No reverting feature in the mobile github app.
Sorry for late response.
Revert "Merge pull request #476 from proost/feat-aos-tuple-sketch"
leerho commentedon Oct 4, 2026
Closing: the unreleased C++ array-of-strings sketch was reverted in #537, so 5.3.0 will not ship it with UTF-8 key hashing. The choice of hash encoding (UTF-16LE to match Java, or UTF-8 everywhere) is being discussed on dev@: https://lists.apache.org/thread/5vlbnodmw8h5s0oc1988f4pdhkjnv8qw. The AoS sketch will be rewritten once that is decided. The Go side is tracked in apache/datasketches-go#191.