This is an automated email from the ASF dual-hosted git repository. leerho pushed a commit to branch count-min-v2 in repository https://gitbox.apache.org/repos/asf/datasketches-java.git
commit 1963d150adbc906ad246f37cc2764965220414db Author: Lee Rhodes <[email protected]> AuthorDate: Tue Nov 10 16:45:34 2026 -0800 Count-Min: write serialization version 2, keep reading version 1 New sketches use the cross-language Count-Min format, version 2, defined in the TCK (docs/count-min-format.md): - row seeds: rowSeed[i] = XXH64(LE64(i), seed) - items hashed with XxHash64: longs as 8 little-endian bytes, strings as UTF-8, byte arrays as given - bucket = (hash >>> 1) % numBuckets - serial version byte 2; the byte layout is unchanged A sketch read from a version 1 image keeps the version 1 hashing (Random seeds, MurmurHash3, floorMod) and is written back as version 1. Merging version 1 with version 2 throws, and other serial versions are rejected. A null byte array is now ignored, like an empty one. Tests check every test vector in the spec (XXH64, row seeds, buckets and both images), and the version 1 path against an independent computation of the legacy hashing. Co-Authored-By: Claude Opus 5.5 <[email protected]> --- .../apache/datasketches/count/CountMinSketch.java | 112 +++++++++--- .../datasketches/count/CountMinSketchTest.java | 187 +++++++++++++++++++++ 2 files changed, 277 insertions(+), 22 deletions(-) diff --git a/src/main/java/org/apache/datasketches/count/CountMinSketch.java b/src/main/java/org/apache/datasketches/count/CountMinSketch.java index 5354eb702..f5840673e 100644 --- a/src/main/java/org/apache/datasketches/count/CountMinSketch.java +++ b/src/main/java/org/apache/datasketches/count/CountMinSketch.java @@ -21,6 +21,8 @@ package org.apache.datasketches.count; import static java.lang.foreign.ValueLayout.JAVA_BYTE; import static java.lang.foreign.ValueLayout.JAVA_LONG_UNALIGNED; +import static org.apache.datasketches.hash.XxHash64.hash; +import static org.apache.datasketches.hash.XxHash64.hashBytes; import java.lang.foreign.MemorySegment; import java.nio.charset.StandardCharsets; @@ -42,8 +44,19 @@ import org.apache.datasketches.hash.MurmurHash3; * providing approximate counts with configurable error bounds. * * Reference: http://dimacs.rutgers.edu/~graham/pubs/papers/cm-full.pdf + * + * <p>New sketches are written in serialization version 2, the cross-language format defined in + * <a href="https://github.com/apache/datasketches-tck/blob/main/docs/count-min-format.md"> + * the DataSketches TCK</a>. Version 2 hashes items with XxHash64, so its images give the same results + * in every language. A sketch read from a version 1 image keeps the version 1 hashing, which used + * MurmurHash3 and seeds from {@link Random}, and is written back as version 1. + * Version 1 and version 2 sketches can't be merged.</p> */ public class CountMinSketch { + static final byte SERIAL_VERSION_1 = 1; + static final byte SERIAL_VERSION_2 = 2; + + private final byte serialVersion_; private final byte numHashes_; private final int numBuckets_; private final long seed_; @@ -65,13 +78,25 @@ public class CountMinSketch { /** * Creates a CountMin sketch with given number of hash functions and buckets, - * and a user-specified seed. + * and a user-specified seed. The sketch uses serialization version 2. * * @param numHashes The number of hash functions to apply to items * @param numBuckets Array size for each of the hashing function * @param seed The base hash seed */ CountMinSketch(final byte numHashes, final int numBuckets, final long seed) { + this(numHashes, numBuckets, seed, SERIAL_VERSION_2); + } + + /** + * Creates a CountMin sketch that hashes items as the given serialization version does. + * + * @param numHashes The number of hash functions to apply to items + * @param numBuckets Array size for each of the hashing function + * @param seed The base hash seed + * @param serialVersion 1 for the legacy hashing, 2 for the cross-language hashing + */ + private CountMinSketch(final byte numHashes, final int numBuckets, final long seed, final byte serialVersion) { // Validate numHashes if (numHashes <= 0) { throw new SketchesArgumentException("Number of hash functions must be positive, got: " + numHashes); @@ -102,6 +127,7 @@ public class CountMinSketch { + "Consider reducing numHashes or numBuckets."); } + serialVersion_ = serialVersion; numHashes_ = numHashes; numBuckets_ = numBuckets; seed_ = seed; @@ -109,9 +135,16 @@ public class CountMinSketch { sketchArray_ = new long[(int) totalSize]; totalWeight_ = 0; - final Random rand = new Random(seed); - for (int i = 0; i < numHashes; i++) { - hashSeeds_[i] = rand.nextLong(); + if (serialVersion == SERIAL_VERSION_1) { + final Random rand = new Random(seed); + for (int i = 0; i < numHashes; i++) { + hashSeeds_[i] = rand.nextLong(); + } + } else { + // rowSeed[i] = XXH64(LE64(i), seed): XxHash64.hash(long, seed) hashes the 8 little-endian bytes of i + for (int i = 0; i < numHashes; i++) { + hashSeeds_[i] = hash(i, seed); + } } } @@ -128,13 +161,42 @@ public class CountMinSketch { final long[] updateLocations = new long[numHashes_]; for (int i = 0; i < numHashes_; i++) { - final long[] index = MurmurHash3.hash(item, hashSeeds_[i]); - updateLocations[i] = (i * (long)numBuckets_) + Math.floorMod(index[0], numBuckets_); + updateLocations[i] = (i * (long) numBuckets_) + bucket(item, hashSeeds_[i]); } return updateLocations; } + private long[] getHashes(final long item) { + if (serialVersion_ == SERIAL_VERSION_1) { + return getHashes(longToBytes(item)); + } + final long[] updateLocations = new long[numHashes_]; + for (int i = 0; i < numHashes_; i++) { + // XxHash64.hash(long, seed) hashes the 8 little-endian bytes of the item, as version 2 requires + final long h = hash(item, hashSeeds_[i]); + updateLocations[i] = (i * (long) numBuckets_) + ((h >>> 1) % numBuckets_); + } + return updateLocations; + } + + private long bucket(final byte[] item, final long rowSeed) { + if (serialVersion_ == SERIAL_VERSION_1) { + return Math.floorMod(MurmurHash3.hash(item, rowSeed)[0], numBuckets_); + } + final long h = hashBytes(item, 0, item.length, rowSeed); + return (h >>> 1) % numBuckets_; + } + + /** + * Returns the serialization version this sketch hashes and serializes with: + * 2 for new sketches, or 1 for a sketch read from a version 1 image. + * @return the serialization version + */ + byte getSerialVersion() { + return serialVersion_; + } + /** * Checks if the CountMinSketch has processed any items. * @return True if the sketch is empty, otherwise false. @@ -214,7 +276,7 @@ public class CountMinSketch { * @param weight The weight of the item. */ public void update(final long item, final long weight) { - update(longToBytes(item), weight); + updateLocations(getHashes(item), weight); } /** @@ -236,12 +298,14 @@ public class CountMinSketch { * @param weight The weight of the item. */ public void update(final byte[] item, final long weight) { - if (item.length == 0) { + if ((item == null) || (item.length == 0)) { return; } + updateLocations(getHashes(item), weight); + } + private void updateLocations(final long[] hashLocations, final long weight) { totalWeight_ += weight > 0 ? weight : -weight; - final long[] hashLocations = getHashes(item); for (final long h : hashLocations) { sketchArray_[(int) h] += weight; } @@ -253,7 +317,7 @@ public class CountMinSketch { * @return Estimated frequency. */ public long getEstimate(final long item) { - return getEstimate(longToBytes(item)); + return estimateAt(getHashes(item)); } /** @@ -276,11 +340,13 @@ public class CountMinSketch { * @return Estimated frequency. */ public long getEstimate(final byte[] item) { - if (item.length == 0) { + if ((item == null) || (item.length == 0)) { return 0; } + return estimateAt(getHashes(item)); + } - final long[] hashLocations = getHashes(item); + private long estimateAt(final long[] hashLocations) { long res = sketchArray_[(int) hashLocations[0]]; // Start from index 1 to avoid processing first element twice for (int i = 1; i < hashLocations.length; i++) { @@ -296,7 +362,7 @@ public class CountMinSketch { * @return Upper bound of estimated frequency. */ public long getUpperBound(final long item) { - return getUpperBound(longToBytes(item)); + return getEstimate(item) + (long) (getRelativeError() * getTotalWeight_()); } /** @@ -319,7 +385,7 @@ public class CountMinSketch { * @return Upper bound of estimated frequency. */ public long getUpperBound(final byte[] item) { - if (item.length == 0) { + if ((item == null) || (item.length == 0)) { return 0; } @@ -332,7 +398,7 @@ public class CountMinSketch { * @return Lower bound of estimated frequency. */ public long getLowerBound(final long item) { - return getLowerBound(longToBytes(item)); + return getEstimate(item); } /** @@ -373,6 +439,10 @@ public class CountMinSketch { if (!acceptableConfig) { throw new SketchesException("Incompatible sketch configuration."); } + if (serialVersion_ != other.serialVersion_) { + throw new SketchesException("Cannot merge sketches with different serialization versions: " + + serialVersion_ + " and " + other.serialVersion_); + } for (int i = 0; i < sketchArray_.length; i++) { sketchArray_[i] += other.sketchArray_[i]; @@ -404,8 +474,7 @@ public class CountMinSketch { // Long 0 final int preambleLongs = Family.COUNTMIN.getMinPreLongs(); posSeg.setByte((byte) preambleLongs); - final int serialVersion = 1; - posSeg.setByte((byte) serialVersion); + posSeg.setByte(serialVersion_); final int familyId = Family.COUNTMIN.getID(); posSeg.setByte((byte) familyId); final int flagsByte = isEmpty() ? Flag.IS_EMPTY.mask() : 0; @@ -457,10 +526,9 @@ public class CountMinSketch { throw new SketchesArgumentException("Preamble longs mismatch: expected " + expectedPreambleLongs + ", actual " + preambleLongs); } - final int expectedSerialVersion = 1; - if (serialVersion != expectedSerialVersion) { - throw new SketchesArgumentException("Serial version mismatch: expected " + expectedSerialVersion - + ", actual " + serialVersion); + if ((serialVersion != SERIAL_VERSION_1) && (serialVersion != SERIAL_VERSION_2)) { + throw new SketchesArgumentException("Serial version mismatch: expected " + SERIAL_VERSION_1 + + " or " + SERIAL_VERSION_2 + ", actual " + serialVersion); } final int expectedFamilyId = Family.COUNTMIN.getID(); if (familyId != expectedFamilyId) { @@ -483,7 +551,7 @@ public class CountMinSketch { final long arrayBytes = (long) numHashes * numBuckets * Long.BYTES; Util.checkBounds(preambleBytes, Long.BYTES + Math.max(arrayBytes, 0), b.length); } - final CountMinSketch cms = new CountMinSketch(numHashes, numBuckets, seed); + final CountMinSketch cms = new CountMinSketch(numHashes, numBuckets, seed, serialVersion); if (empty) { return cms; } diff --git a/src/test/java/org/apache/datasketches/count/CountMinSketchTest.java b/src/test/java/org/apache/datasketches/count/CountMinSketchTest.java index 59590d9a6..e5adb8ddd 100644 --- a/src/test/java/org/apache/datasketches/count/CountMinSketchTest.java +++ b/src/test/java/org/apache/datasketches/count/CountMinSketchTest.java @@ -24,10 +24,16 @@ import static org.testng.Assert.assertFalse; import static org.testng.Assert.assertThrows; import static org.testng.Assert.assertTrue; +import java.nio.charset.StandardCharsets; +import java.util.HexFormat; +import java.util.Random; + import org.apache.datasketches.common.AllocationTracker; import org.apache.datasketches.common.ByteArrayUtil; import org.apache.datasketches.common.SketchesArgumentException; import org.apache.datasketches.common.SketchesException; +import org.apache.datasketches.hash.MurmurHash3; +import org.apache.datasketches.hash.XxHash64; import org.testng.annotations.Test; public class CountMinSketchTest { @@ -271,4 +277,185 @@ public class CountMinSketchTest { assertThrows(SketchesArgumentException.class, () -> CountMinSketch.deserialize(shortBytes, seed)); } + // ---- Serialization version 2: test vectors from the TCK spec docs/count-min-format.md, section 7 ---- + + private static final long SPEC_SEED = 9001L; + + // 7.1 XXH64 and 7.2 row seeds + @Test + public void v2XxHashAndRowSeedVectors() { + final byte[] empty = new byte[0]; + assertEquals(XxHash64.hashBytes(empty, 0, 0, 0), 0xEF46DB3751D8E999L); + assertEquals(XxHash64.hashBytes(utf8("a"), 0, 1, 0), 0xD24EC4F1A98C6E5BL); + assertEquals(XxHash64.hashBytes(utf8("abc"), 0, 3, 0), 0x44BC2CF5AD770999L); + + final long[] seeds9001 = { 0xD71D64972584A288L, 0xEFE8454A6499F311L, 0x23819BE21B1B1D9EL }; + final long[] seeds42 = { 0xB71B47EBDA15746CL, 0x9ED50FD59358D232L, 0xD19FE30002B9A3CDL }; + for (int i = 0; i < 3; i++) { + assertEquals(XxHash64.hash(i, 9001L), seeds9001[i]); + assertEquals(XxHash64.hash(i, 42L), seeds42[i]); + } + } + + // 7.3 item buckets, observed through the counters a single update sets + @Test + public void v2BucketVectors() { + assertBuckets(SPEC_SEED, 1L, 185, 898, 4); + assertBuckets(SPEC_SEED, 9L, 490, 217, 440); + assertBuckets(SPEC_SEED, -1L, 256, 641, 308); + assertBuckets(SPEC_SEED, Long.MIN_VALUE, 951, 0, 298); + assertBuckets(SPEC_SEED, "apple", 130, 747, 144); + assertBuckets(SPEC_SEED, "\u00e9t\u00e9", 806, 491, 163); + assertBuckets(42L, 1L, 468, 459, 696); + assertBuckets(42L, 9L, 841, 428, 322); + } + + // 7.4 images + @Test + public void v2ImageVectors() { + final CountMinSketch empty = new CountMinSketch((byte) 2, 9, SPEC_SEED); + assertEquals(empty.getSerialVersion(), CountMinSketch.SERIAL_VERSION_2); + assertEquals(empty.toByteArray(), hex("02021201000000000900000002cc9300")); + + final CountMinSketch cms = new CountMinSketch((byte) 2, 9, SPEC_SEED); + cms.update(1L, 10); + cms.update(9L, 810); + cms.update("apple", 5); + final byte[] expected = new byte[168]; + System.arraycopy(hex("02021200000000000900000002cc9300"), 0, expected, 0, 16); + ByteArrayUtil.putLongLE(expected, 16, 825); + ByteArrayUtil.putLongLE(expected, 24 + (8 * 0), 810); // row 0, bucket 0 + ByteArrayUtil.putLongLE(expected, 24 + (8 * 4), 5); // row 0, bucket 4 + ByteArrayUtil.putLongLE(expected, 24 + (8 * 6), 10); // row 0, bucket 6 + ByteArrayUtil.putLongLE(expected, 24 + (8 * 10), 5); // row 1, bucket 1 + ByteArrayUtil.putLongLE(expected, 24 + (8 * 11), 810); // row 1, bucket 2 + ByteArrayUtil.putLongLE(expected, 24 + (8 * 16), 10); // row 1, bucket 7 + assertEquals(cms.toByteArray(), expected); + + final CountMinSketch read = CountMinSketch.deserialize(expected, SPEC_SEED); + assertEquals(read.getSerialVersion(), CountMinSketch.SERIAL_VERSION_2); + assertEquals(read.getEstimate(1L), 10); + assertEquals(read.getEstimate(9L), 810); + assertEquals(read.getEstimate("apple"), 5); + assertEquals(read.toByteArray(), expected); + } + + // The long overloads hash the 8 little-endian bytes of the item, like the byte[] overloads + @Test + public void v2LongMatchesLittleEndianBytes() { + final CountMinSketch a = new CountMinSketch((byte) 4, 101, SPEC_SEED); + final CountMinSketch b = new CountMinSketch((byte) 4, 101, SPEC_SEED); + final long[] items = { 0L, 1L, -1L, Long.MIN_VALUE, Long.MAX_VALUE, 0x0123456789ABCDEFL }; + for (final long item : items) { + final byte[] le = new byte[Long.BYTES]; + ByteArrayUtil.putLongLE(le, 0, item); + a.update(item, 3); + b.update(le, 3); + } + assertEquals(a.toByteArray(), b.toByteArray()); + } + + // Version 1 images keep the legacy hashing and are written back as version 1 + @Test + public void v1ImageKeepsLegacyHashing() { + final long seed = 1234L; + final byte numHashes = 3; + final int numBuckets = 17; + final byte[] emptyV1 = new CountMinSketch(numHashes, numBuckets, seed).toByteArray(); + emptyV1[1] = CountMinSketch.SERIAL_VERSION_1; + + final CountMinSketch v1 = CountMinSketch.deserialize(emptyV1, seed); + assertEquals(v1.getSerialVersion(), CountMinSketch.SERIAL_VERSION_1); + v1.update(7L, 11); + v1.update("legacy", 13); + + final byte[] image = v1.toByteArray(); + assertEquals(image[1], CountMinSketch.SERIAL_VERSION_1); + + // Independent version 1 computation: seeds from Random(seed), MurmurHash3, floorMod, native byte order + final Random rand = new Random(seed); + final long[] rowSeeds = new long[numHashes]; + for (int i = 0; i < numHashes; i++) { rowSeeds[i] = rand.nextLong(); } + final byte[] item7 = java.nio.ByteBuffer.allocate(8).order(java.nio.ByteOrder.nativeOrder()).putLong(7L).array(); + final long[] expected = new long[numHashes * numBuckets]; + for (int i = 0; i < numHashes; i++) { + expected[(i * numBuckets) + Math.floorMod(MurmurHash3.hash(item7, rowSeeds[i])[0], numBuckets)] += 11; + expected[(i * numBuckets) + Math.floorMod(MurmurHash3.hash(utf8("legacy"), rowSeeds[i])[0], numBuckets)] += 13; + } + for (int k = 0; k < expected.length; k++) { + assertEquals(ByteArrayUtil.getLongLE(image, 24 + (8 * k)), expected[k], "counter " + k); + } + + final CountMinSketch reread = CountMinSketch.deserialize(image, seed); + assertEquals(reread.getSerialVersion(), CountMinSketch.SERIAL_VERSION_1); + assertEquals(reread.getEstimate(7L), v1.getEstimate(7L)); + assertEquals(reread.getEstimate("legacy"), v1.getEstimate("legacy")); + } + + @Test + public void mergeAcrossVersionsThrows() { + final long seed = 1234L; + final byte[] emptyV1 = new CountMinSketch((byte) 3, 17, seed).toByteArray(); + emptyV1[1] = CountMinSketch.SERIAL_VERSION_1; + final CountMinSketch v1 = CountMinSketch.deserialize(emptyV1, seed); + final CountMinSketch v2 = new CountMinSketch((byte) 3, 17, seed); + assertThrows(SketchesException.class, () -> v1.merge(v2)); + assertThrows(SketchesException.class, () -> v2.merge(v1)); + } + + @Test + public void unknownSerialVersionThrows() { + final long seed = 1234L; + final byte[] image = new CountMinSketch((byte) 3, 17, seed).toByteArray(); + image[1] = 3; + assertThrows(SketchesArgumentException.class, () -> CountMinSketch.deserialize(image, seed)); + image[1] = 0; + assertThrows(SketchesArgumentException.class, () -> CountMinSketch.deserialize(image, seed)); + } + + @Test + public void nullAndEmptyItemsAreIgnored() { + final CountMinSketch cms = new CountMinSketch((byte) 3, 17, SPEC_SEED); + cms.update((byte[]) null, 5); + cms.update(new byte[0], 5); + cms.update((String) null, 5); + cms.update("", 5); + assertTrue(cms.isEmpty()); + assertEquals(cms.getEstimate((byte[]) null), 0); + assertEquals(cms.getEstimate(new byte[0]), 0); + assertEquals(cms.getEstimate((String) null), 0); + assertEquals(cms.getEstimate(""), 0); + assertEquals(cms.getUpperBound((byte[]) null), 0); + } + + private static void assertBuckets(final long seed, final long item, final int... buckets) { + final CountMinSketch cms = new CountMinSketch((byte) 3, 1000, seed); + cms.update(item, 1); + assertCounters(cms, buckets); + } + + private static void assertBuckets(final long seed, final String item, final int... buckets) { + final CountMinSketch cms = new CountMinSketch((byte) 3, 1000, seed); + cms.update(item, 1); + assertCounters(cms, buckets); + } + + private static void assertCounters(final CountMinSketch cms, final int... buckets) { + final byte[] image = cms.toByteArray(); + for (int row = 0; row < buckets.length; row++) { + for (int b = 0; b < 1000; b++) { + final long counter = ByteArrayUtil.getLongLE(image, 24 + (8 * ((row * 1000) + b))); + assertEquals(counter, b == buckets[row] ? 1 : 0, "row " + row + ", bucket " + b); + } + } + } + + private static byte[] utf8(final String s) { + return s.getBytes(StandardCharsets.UTF_8); + } + + private static byte[] hex(final String s) { + return HexFormat.of().parseHex(s); + } + } --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
