This is an automated email from the ASF dual-hosted git repository.
tisonkun pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/datasketches-rust.git
The following commit(s) were added to refs/heads/main by this push:
new 6856e45 fix(countmin): use version 2 hashing for new sketches (#299)
6856e45 is described below
commit 6856e45a89a07522b7faafaff83f64d9155dd37b
Author: tison <[email protected]>
AuthorDate: Sun Nov 8 17:23:03 2026 +0800
fix(countmin): use version 2 hashing for new sketches (#299)
---
CHANGELOG.md | 1 +
datasketches/src/countmin/mod.rs | 14 +-
datasketches/src/countmin/serialization.rs | 21 --
datasketches/src/countmin/sketch.rs | 274 +++++++++++++++---------
datasketches/src/hash/mod.rs | 6 +-
datasketches/src/hash/value/mod.rs | 2 +-
datasketches/src/hash/value/natural_extend.rs | 3 +-
datasketches/src/lib.rs | 2 +-
tests-integration/tests/countmin_test/sketch.rs | 36 +++-
tests-integration/tests/serde_tests/countmin.rs | 228 +++++++++++++++++++-
10 files changed, 448 insertions(+), 139 deletions(-)
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 545914c..9f68d7e 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -6,6 +6,7 @@ All significant changes to this project will be documented in
this file.
### New features
+* Use serial version 2 for new `CountMinSketch` instances, enabling
cross-language interchange with the documented input encodings. New sketches
support `1..=127` rows and require a version 2 reader. Existing version 1 data
remains readable and updatable, but must be rebuilt from source items to merge
with new sketches.
* Add `CpcUnion::serialize`, which produces the same bytes as
`to_sketch().serialize()` and can be faster.
* Add `HllUnion::serialize` to serialize union results directly.
* Add `XorFilter` and `XorFilterBuilder` behind the `xor` feature for
immutable membership queries on values or precomputed hashes. Filters support
8-, 16-, and 32-bit fingerprints and can be serialized for later queries.
diff --git a/datasketches/src/countmin/mod.rs b/datasketches/src/countmin/mod.rs
index d8e4f5d..03c9283 100644
--- a/datasketches/src/countmin/mod.rs
+++ b/datasketches/src/countmin/mod.rs
@@ -20,15 +20,19 @@
//! The CountMin sketch provides approximate frequency counts for streaming
data
//! with configurable relative error and confidence bounds.
//!
+//! Serial version 2 sketches with `i64` counters support cross-language
binary interchange when
+//! items use compatible hashing; see [`CountMinSketch`] and
[`hash::value`](crate::hash::value).
+//!
//! # Usage
//!
//! ```
//! use datasketches::countmin::CountMinSketch;
+//! use datasketches::hash::value::raw_bytes;
//!
//! let mut sketch = CountMinSketch::<i64>::new(5, 256).unwrap();
-//! sketch.update("apple");
-//! sketch.update_with_weight("banana", 3);
-//! assert!(sketch.estimate("banana") >= 3);
+//! sketch.update(raw_bytes::from_str("apple"));
+//! sketch.update_with_weight(raw_bytes::from_str("banana"), 3);
+//! assert!(sketch.estimate(raw_bytes::from_str("banana")) >= 3);
//! ```
//!
//! # Configuration Helpers
@@ -39,11 +43,9 @@
//! let buckets = CountMinSketch::<i64>::suggest_num_buckets(0.01).unwrap();
//! let hashes = CountMinSketch::<i64>::suggest_num_hashes(0.99).unwrap();
//! let sketch = CountMinSketch::<i64>::new(hashes, buckets).unwrap();
-//! assert_eq!(sketch.estimate("apple"), 0);
+//! assert_eq!(sketch.estimate(1i64), 0);
//! ```
-mod serialization;
-
mod sketch;
pub use self::sketch::CountMinSketch;
diff --git a/datasketches/src/countmin/serialization.rs
b/datasketches/src/countmin/serialization.rs
deleted file mode 100644
index 7a930e0..0000000
--- a/datasketches/src/countmin/serialization.rs
+++ /dev/null
@@ -1,21 +0,0 @@
-// Licensed to the Apache Software Foundation (ASF) under one
-// or more contributor license agreements. See the NOTICE file
-// distributed with this work for additional information
-// regarding copyright ownership. The ASF licenses this file
-// to you under the Apache License, Version 2.0 (the
-// "License"); you may not use this file except in compliance
-// with the License. You may obtain a copy of the License at
-//
-// http://www.apache.org/licenses/LICENSE-2.0
-//
-// Unless required by applicable law or agreed to in writing,
-// software distributed under the License is distributed on an
-// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
-// KIND, either express or implied. See the License for the
-// specific language governing permissions and limitations
-// under the License.
-
-pub const PREAMBLE_LONGS_SHORT: u8 = 2;
-pub const SERIAL_VERSION: u8 = 1;
-pub const FLAGS_IS_EMPTY: u8 = 1 << 0;
-pub const LONG_SIZE_BYTES: usize = 8;
diff --git a/datasketches/src/countmin/sketch.rs
b/datasketches/src/countmin/sketch.rs
index b81576f..f36b2fe 100644
--- a/datasketches/src/countmin/sketch.rs
+++ b/datasketches/src/countmin/sketch.rs
@@ -21,34 +21,45 @@ use std::hash::Hasher;
use crate::codec::SketchBytes;
use crate::codec::SketchSlice;
use crate::codec::assert::ensure_preamble_longs_in;
-use crate::codec::assert::ensure_serial_version_is;
use crate::codec::assert::insufficient_data;
use crate::codec::family::Family;
use crate::countmin::CountMinValue;
use crate::countmin::UnsignedCountMinValue;
-use crate::countmin::serialization::FLAGS_IS_EMPTY;
-use crate::countmin::serialization::LONG_SIZE_BYTES;
-use crate::countmin::serialization::PREAMBLE_LONGS_SHORT;
-use crate::countmin::serialization::SERIAL_VERSION;
use crate::error::Error;
use crate::error::ErrorKind;
use crate::hash::DEFAULT_UPDATE_SEED;
use crate::hash::MurmurHash3X64128;
+use crate::hash::XxHash64;
use crate::hash::check_seed_hash;
use crate::hash::compute_seed_hash;
+const PREAMBLE_LONGS_SHORT: u8 = 2;
+const SERIAL_VERSION_1: u8 = 1;
+const SERIAL_VERSION_2: u8 = 2;
+const FLAGS_IS_EMPTY: u8 = 1 << 0;
+const LONG_SIZE_BYTES: usize = 8;
const MAX_TABLE_ENTRIES: usize = 1 << 30;
/// CountMin sketch for estimating item frequencies.
///
/// The sketch provides upper and lower bounds on estimated item frequencies
/// with configurable relative error and confidence.
+///
+/// New sketches use serial version 2. Deserialized version 1 sketches retain
their legacy
+/// hashing and serialization format, and sketches of different versions
cannot be merged.
+///
+/// For cross-language version 2 interchange, use `i64` counters and encode
inputs consistently:
+/// * `i64` and `u64` values are hashed as eight little-endian bytes; use
+/// [`crate::hash::value::natural_extend`] for narrower integers.
+/// * Use [`crate::hash::value::raw_bytes`] for UTF-8 strings and byte slices,
and skip empty inputs
+/// when interoperating with implementations that ignore them.
#[derive(Debug, Clone, PartialEq)]
pub struct CountMinSketch<T: CountMinValue> {
num_hashes: u8,
buckets: BucketCount,
seed: u64,
seed_hash: u16,
+ serial_version: SerialVersion,
// Every bucket satisfies |count| <= total_weight, so a checked total also
bounds bucket
// additions during update/merge: |a + b| <= |a| + |b|. Deserialization
validates this
// invariant; unsigned halving and decay preserve it.
@@ -57,6 +68,91 @@ pub struct CountMinSketch<T: CountMinValue> {
hash_seeds: Vec<u64>,
}
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
+#[repr(u8)]
+enum SerialVersion {
+ V1 = SERIAL_VERSION_1,
+ V2 = SERIAL_VERSION_2,
+}
+
+impl SerialVersion {
+ fn from_u8(byte: u8) -> Result<Self, Error> {
+ match byte {
+ SERIAL_VERSION_1 => Ok(Self::V1),
+ SERIAL_VERSION_2 => Ok(Self::V2),
+ _ => Err(Error::deserial(format!(
+ "unsupported serial version: expected {SERIAL_VERSION_1} or
{SERIAL_VERSION_2}, got {byte}"
+ ))),
+ }
+ }
+
+ fn max_hashes(self) -> u8 {
+ match self {
+ Self::V1 => u8::MAX,
+ Self::V2 => 127,
+ }
+ }
+
+ fn entries_for_config(
+ self,
+ num_hashes: u8,
+ num_buckets: u32,
+ kind: ErrorKind,
+ ) -> Result<usize, Error> {
+ if !(1..=self.max_hashes()).contains(&num_hashes) {
+ return Err(Error::new(
+ kind,
+ match self {
+ Self::V1 => "num_hashes must be at least 1",
+ Self::V2 => "num_hashes must be within 1..=127",
+ },
+ ));
+ }
+ if num_buckets < 3 {
+ return Err(Error::new(kind, "num_buckets must be at least 3"));
+ }
+ let entries = (num_hashes as usize)
+ .checked_mul(num_buckets as usize)
+ .ok_or_else(|| Error::new(kind, "num_hashes * num_buckets
overflows usize"))?;
+ if entries >= MAX_TABLE_ENTRIES {
+ return Err(Error::new(
+ kind,
+ format!("num_hashes * num_buckets must be <
{MAX_TABLE_ENTRIES}"),
+ ));
+ }
+ Ok(entries)
+ }
+
+ fn make_hash_seeds(self, seed: u64, num_hashes: u8) -> Vec<u64> {
+ (0..num_hashes)
+ .map(|i| match self {
+ Self::V1 => {
+ let mut hasher = MurmurHash3X64128::with_seed(seed);
+ hasher.write(&u64::from(i).to_le_bytes());
+ hasher.finish128().0
+ }
+ Self::V2 => XxHash64::hash_u64(u64::from(i), seed),
+ })
+ .collect()
+ }
+
+ #[inline]
+ fn hash_item<I: Hash>(self, item: &I, seed: u64) -> u64 {
+ match self {
+ Self::V1 => {
+ let mut hasher = MurmurHash3X64128::with_seed(seed);
+ item.hash(&mut hasher);
+ hasher.finish128().0
+ }
+ Self::V2 => {
+ let mut hasher = XxHash64::with_seed(seed);
+ item.hash(&mut hasher);
+ hasher.finish64() >> 1
+ }
+ }
+ }
+}
+
#[derive(Debug, Clone, PartialEq)]
struct BucketCount {
count: u32,
@@ -101,8 +197,8 @@ impl<T: CountMinValue> CountMinSketch<T> {
///
/// # Errors
///
- /// Returns an error if `num_hashes` is `0`, `num_buckets` is less than
`3`, or the total table
- /// size exceeds the supported limit.
+ /// Returns an error if `num_hashes` is outside `1..=127`, `num_buckets`
is less than `3`, or
+ /// the total table size exceeds the supported limit.
///
/// # Examples
///
@@ -121,7 +217,7 @@ impl<T: CountMinValue> CountMinSketch<T> {
/// # Errors
///
/// Returns an error if any of:
- /// * `num_hashes` is `0`.
+ /// * `num_hashes` is outside `1..=127`.
/// * `num_buckets` is less than `3`.
/// * The total table size exceeds the supported limit.
/// * The computed seed hash is zero.
@@ -135,13 +231,18 @@ impl<T: CountMinValue> CountMinSketch<T> {
/// assert_eq!(sketch.seed(), 42);
/// ```
pub fn with_seed(num_hashes: u8, num_buckets: u32, seed: u64) ->
Result<Self, Error> {
- let entries = entries_for_config(num_hashes, num_buckets)?;
+ let entries = SerialVersion::V2.entries_for_config(
+ num_hashes,
+ num_buckets,
+ ErrorKind::InvalidArgument,
+ )?;
let seed_hash = compute_seed_hash(seed, ErrorKind::InvalidArgument)?;
Ok(Self::make(
num_hashes,
num_buckets,
seed,
seed_hash,
+ SerialVersion::V2,
entries,
))
}
@@ -219,6 +320,9 @@ impl<T: CountMinValue> CountMinSketch<T> {
/// Updates the sketch with a single occurrence of the item.
///
+ /// Use [`hash::value`](crate::hash::value) wrappers to select an input
encoding for
+ /// cross-language hashing.
+ ///
/// # Panics
///
/// Panics without modifying the sketch if the total absolute weight would
exceed `T::MAX`.
@@ -229,8 +333,8 @@ impl<T: CountMinValue> CountMinSketch<T> {
/// use datasketches::countmin::CountMinSketch;
///
/// let mut sketch = CountMinSketch::<i64>::new(4, 128).unwrap();
- /// sketch.update("apple");
- /// assert!(sketch.estimate("apple") >= 1);
+ /// sketch.update(1i64);
+ /// assert!(sketch.estimate(1i64) >= 1);
/// ```
pub fn update<I: Hash>(&mut self, item: I) {
self.update_with_weight(item, T::ONE);
@@ -238,6 +342,9 @@ impl<T: CountMinValue> CountMinSketch<T> {
/// Updates the sketch with the given item and weight.
///
+ /// Use [`hash::value`](crate::hash::value) wrappers to select an input
encoding for
+ /// cross-language hashing.
+ ///
/// # Panics
///
/// Panics without modifying the sketch if the absolute weight or the
total absolute weight
@@ -249,8 +356,8 @@ impl<T: CountMinValue> CountMinSketch<T> {
/// use datasketches::countmin::CountMinSketch;
///
/// let mut sketch = CountMinSketch::<i64>::new(4, 128).unwrap();
- /// sketch.update_with_weight("banana", 3);
- /// assert!(sketch.estimate("banana") >= 3);
+ /// sketch.update_with_weight(2i64, 3);
+ /// assert!(sketch.estimate(2i64) >= 3);
/// ```
pub fn update_with_weight<I: Hash>(&mut self, item: I, weight: T) {
if weight == T::ZERO {
@@ -276,19 +383,15 @@ impl<T: CountMinValue> CountMinSketch<T> {
/// use datasketches::countmin::CountMinSketch;
///
/// let mut sketch = CountMinSketch::<i64>::new(4, 128).unwrap();
- /// sketch.update_with_weight("pear", 2);
- /// assert!(sketch.estimate("pear") >= 2);
+ /// sketch.update_with_weight(3i64, 2);
+ /// assert!(sketch.estimate(3i64) >= 2);
/// ```
pub fn estimate<I: Hash>(&self, item: I) -> T {
let num_buckets = self.buckets.count as usize;
let mut min = T::MAX;
for (row, seed) in self.hash_seeds.iter().enumerate() {
let bucket = self.bucket_index(&item, *seed);
- let index = row * num_buckets + bucket;
- let value = self.counts[index];
- if value < min {
- min = value;
- }
+ min = min.min(self.counts[row * num_buckets + bucket]);
}
min
}
@@ -310,7 +413,8 @@ impl<T: CountMinValue> CountMinSketch<T> {
/// # Errors
///
/// Returns an error without modifying the sketch if the sketches have
different numbers of
- /// hashes, bucket counts, or seeds, or their combined total absolute
weight exceeds `T::MAX`.
+ /// hashes, bucket counts, seeds, or serial versions, or their combined
total absolute weight
+ /// exceeds `T::MAX`.
///
/// # Examples
///
@@ -320,19 +424,20 @@ impl<T: CountMinValue> CountMinSketch<T> {
/// let mut left = CountMinSketch::<i64>::new(4, 128).unwrap();
/// let mut right = CountMinSketch::<i64>::new(4, 128).unwrap();
///
- /// left.update("apple");
- /// right.update_with_weight("banana", 2);
+ /// left.update(1i64);
+ /// right.update_with_weight(2i64, 2);
///
/// left.merge(&right).unwrap();
- /// assert!(left.estimate("banana") >= 2);
+ /// assert!(left.estimate(2i64) >= 2);
/// ```
pub fn merge(&mut self, other: &CountMinSketch<T>) -> Result<(), Error> {
if self.num_hashes != other.num_hashes
|| self.buckets.count != other.buckets.count
|| self.seed != other.seed
+ || self.serial_version != other.serial_version
{
return Err(Error::invalid_argument(
- "Count-Min sketches must have matching numbers of hashes,
bucket counts, and seeds",
+ "Count-Min sketches must have matching numbers of hashes,
bucket counts, seeds, and serial versions",
));
}
self.total_weight = self
@@ -347,8 +452,11 @@ impl<T: CountMinValue> CountMinSketch<T> {
/// Serializes this sketch into the Count-Min binary format.
///
- /// DataSketches C++ can read the serialized data, but item queries and
updates there are
- /// unreliable because the two implementations map items to counters
differently.
+ /// New sketches are written as version 2. A sketch deserialized from a
version 1 image
+ /// retains its legacy hashing for queries and updates and is written back
as version 1.
+ ///
+ /// Version 1 images are not portable across implementations. Version 2
supports cross-language
+ /// interchange with `i64` counters and the input encodings documented on
[`CountMinSketch`].
///
/// # Examples
///
@@ -356,10 +464,10 @@ impl<T: CountMinValue> CountMinSketch<T> {
/// use datasketches::countmin::CountMinSketch;
///
/// let mut sketch = CountMinSketch::<i64>::new(4, 128).unwrap();
- /// sketch.update("apple");
+ /// sketch.update(1i64);
/// let bytes = sketch.serialize();
/// let decoded = CountMinSketch::<i64>::deserialize(&bytes).unwrap();
- /// assert!(decoded.estimate("apple") >= 1);
+ /// assert!(decoded.estimate(1i64) >= 1);
/// ```
pub fn serialize(&self) -> Vec<u8> {
let header_size = PREAMBLE_LONGS_SHORT as usize * LONG_SIZE_BYTES;
@@ -372,7 +480,7 @@ impl<T: CountMinValue> CountMinSketch<T> {
let mut bytes = SketchBytes::with_capacity(header_size + payload_size);
bytes.write_u8(PREAMBLE_LONGS_SHORT);
- bytes.write_u8(SERIAL_VERSION);
+ bytes.write_u8(self.serial_version as u8);
bytes.write_u8(Family::COUNTMIN.id);
bytes.write_u8(if self.is_empty() { FLAGS_IS_EMPTY } else { 0 });
bytes.write_u32_le(0); // unused
@@ -399,9 +507,8 @@ impl<T: CountMinValue> CountMinSketch<T> {
/// Deserializes a sketch from bytes using the default seed.
///
- /// Can read sketches serialized by DataSketches C++.
- /// Item queries and updates on those sketches are unreliable because the
two
- /// implementations map items to counters differently.
+ /// Accepts versions 1 and 2, preserving the image's hashing and
serialization version.
+ /// Counter values must fit `T`. See [`CountMinSketch`] for input
encodings and compatibility.
///
/// # Errors
///
@@ -414,10 +521,10 @@ impl<T: CountMinValue> CountMinSketch<T> {
/// use datasketches::countmin::CountMinSketch;
///
/// let mut sketch = CountMinSketch::<i64>::new(4, 64).unwrap();
- /// sketch.update("apple");
+ /// sketch.update(1i64);
/// let bytes = sketch.serialize();
/// let decoded = CountMinSketch::<i64>::deserialize(&bytes).unwrap();
- /// assert!(decoded.estimate("apple") >= 1);
+ /// assert!(decoded.estimate(1i64) >= 1);
/// ```
pub fn deserialize(bytes: &[u8]) -> Result<Self, Error> {
Self::deserialize_with_seed(bytes, DEFAULT_UPDATE_SEED)
@@ -425,9 +532,8 @@ impl<T: CountMinValue> CountMinSketch<T> {
/// Deserializes a sketch from bytes using the provided seed.
///
- /// Can read sketches serialized by DataSketches C++.
- /// Item queries and updates on those sketches are unreliable because the
two
- /// implementations map items to counters differently.
+ /// Accepts versions 1 and 2, preserving the image's hashing and
serialization version.
+ /// Counter values must fit `T`. See [`CountMinSketch`] for input
encodings and compatibility.
///
/// # Errors
///
@@ -440,10 +546,10 @@ impl<T: CountMinValue> CountMinSketch<T> {
/// use datasketches::countmin::CountMinSketch;
///
/// let mut sketch = CountMinSketch::<i64>::with_seed(4, 64, 7).unwrap();
- /// sketch.update("apple");
+ /// sketch.update(1i64);
/// let bytes = sketch.serialize();
/// let decoded = CountMinSketch::<i64>::deserialize_with_seed(&bytes,
7).unwrap();
- /// assert!(decoded.estimate("apple") >= 1);
+ /// assert!(decoded.estimate(1i64) >= 1);
/// ```
pub fn deserialize_with_seed(bytes: &[u8], seed: u64) -> Result<Self,
Error> {
fn read_value<T: CountMinValue>(
@@ -469,7 +575,7 @@ impl<T: CountMinValue> CountMinSketch<T> {
.map_err(insufficient_data("<unused>"))?;
Family::COUNTMIN.validate_id(family_id)?;
- ensure_serial_version_is(SERIAL_VERSION, serial_version)?;
+ let serial_version = SerialVersion::from_u8(serial_version)?;
ensure_preamble_longs_in(&[PREAMBLE_LONGS_SHORT], preamble_longs)?;
let num_buckets = cursor
@@ -489,7 +595,8 @@ impl<T: CountMinValue> CountMinSketch<T> {
ErrorKind::InvalidData,
)?;
- let entries = entries_for_config_checked(num_hashes, num_buckets)?;
+ let entries =
+ serial_version.entries_for_config(num_hashes, num_buckets,
ErrorKind::InvalidData)?;
let is_empty = (flags & FLAGS_IS_EMPTY) != 0;
if !is_empty {
let payload_values = entries
@@ -507,7 +614,14 @@ impl<T: CountMinValue> CountMinSketch<T> {
}
}
- let mut sketch = Self::make(num_hashes, num_buckets, seed,
expected_seed_hash, entries);
+ let mut sketch = Self::make(
+ num_hashes,
+ num_buckets,
+ seed,
+ expected_seed_hash,
+ serial_version,
+ entries,
+ );
if is_empty {
return Ok(sketch);
}
@@ -537,14 +651,22 @@ impl<T: CountMinValue> CountMinSketch<T> {
self.counts.capacity() * size_of::<T>() + self.hash_seeds.capacity() *
size_of::<u64>()
}
- fn make(num_hashes: u8, num_buckets: u32, seed: u64, seed_hash: u16,
entries: usize) -> Self {
+ fn make(
+ num_hashes: u8,
+ num_buckets: u32,
+ seed: u64,
+ seed_hash: u16,
+ serial_version: SerialVersion,
+ entries: usize,
+ ) -> Self {
let counts = vec![T::ZERO; entries];
- let hash_seeds = make_hash_seeds(seed, num_hashes);
+ let hash_seeds = serial_version.make_hash_seeds(seed, num_hashes);
CountMinSketch {
num_hashes,
buckets: BucketCount::new(num_buckets),
seed,
seed_hash,
+ serial_version,
total_weight: T::ZERO,
counts,
hash_seeds,
@@ -552,10 +674,8 @@ impl<T: CountMinValue> CountMinSketch<T> {
}
fn bucket_index<I: Hash>(&self, item: &I, seed: u64) -> usize {
- let mut hasher = MurmurHash3X64128::with_seed(seed);
- item.hash(&mut hasher);
- let (h1, _) = hasher.finish128();
- self.buckets.index(h1)
+ self.buckets
+ .index(self.serial_version.hash_item(item, seed))
}
}
@@ -568,9 +688,9 @@ impl<T: UnsignedCountMinValue> CountMinSketch<T> {
/// use datasketches::countmin::CountMinSketch;
///
/// let mut sketch = CountMinSketch::<u64>::new(4, 128).unwrap();
- /// sketch.update_with_weight("apple", 3);
+ /// sketch.update_with_weight(1i64, 3);
/// sketch.halve();
- /// assert!(sketch.estimate("apple") >= 1);
+ /// assert!(sketch.estimate(1i64) >= 1);
/// ```
pub fn halve(&mut self) {
for c in &mut self.counts {
@@ -596,9 +716,9 @@ impl<T: UnsignedCountMinValue> CountMinSketch<T> {
/// use datasketches::countmin::CountMinSketch;
///
/// let mut sketch = CountMinSketch::<u64>::new(4, 128).unwrap();
- /// sketch.update_with_weight("apple", 3);
+ /// sketch.update_with_weight(1i64, 3);
/// sketch.decay(0.5);
- /// assert!(sketch.estimate("apple") >= 1);
+ /// assert!(sketch.estimate(1i64) >= 1);
/// ```
pub fn decay(&mut self, decay: f64) {
assert!(decay > 0.0 && decay <= 1.0, "decay must be within (0, 1]");
@@ -616,54 +736,6 @@ impl<T: UnsignedCountMinValue> CountMinSketch<T> {
}
}
-fn entries_for_config(num_hashes: u8, num_buckets: u32) -> Result<usize,
Error> {
- if num_hashes == 0 {
- return Err(Error::invalid_argument("num_hashes must be at least 1"));
- }
- if num_buckets < 3 {
- return Err(Error::invalid_argument("num_buckets must be at least 3"));
- }
- let entries = (num_hashes as usize)
- .checked_mul(num_buckets as usize)
- .ok_or_else(|| Error::invalid_argument("num_hashes * num_buckets
overflows usize"))?;
- if entries >= MAX_TABLE_ENTRIES {
- return Err(Error::invalid_argument(format!(
- "num_hashes * num_buckets must be < {MAX_TABLE_ENTRIES}"
- )));
- }
- Ok(entries)
-}
-
-fn entries_for_config_checked(num_hashes: u8, num_buckets: u32) ->
Result<usize, Error> {
- if num_hashes == 0 {
- return Err(Error::deserial("num_hashes must be at least 1"));
- }
- if num_buckets < 3 {
- return Err(Error::deserial("num_buckets must be at least 3"));
- }
- let entries = (num_hashes as usize)
- .checked_mul(num_buckets as usize)
- .ok_or_else(|| Error::deserial("num_hashes * num_buckets overflows
usize"))?;
- if entries >= MAX_TABLE_ENTRIES {
- return Err(Error::deserial(format!(
- "num_hashes * num_buckets must be < {MAX_TABLE_ENTRIES}",
- )));
- }
- Ok(entries)
-}
-
-fn make_hash_seeds(seed: u64, num_hashes: u8) -> Vec<u64> {
- let mut seeds = Vec::with_capacity(num_hashes as usize);
- for i in 0..num_hashes {
- // Derive per-row hash seeds deterministically from the sketch seed.
- let mut hasher = MurmurHash3X64128::with_seed(seed);
- hasher.write(&u64::from(i).to_le_bytes());
- let (h1, _) = hasher.finish128();
- seeds.push(h1);
- }
- seeds
-}
-
#[cfg(test)]
mod tests {
use super::*;
diff --git a/datasketches/src/hash/mod.rs b/datasketches/src/hash/mod.rs
index f2dde4f..69fff2e 100644
--- a/datasketches/src/hash/mod.rs
+++ b/datasketches/src/hash/mod.rs
@@ -38,9 +38,9 @@ mod murmurhash;
))]
pub(crate) use self::murmurhash::*;
-#[cfg(any(feature = "bloom", feature = "xor"))]
+#[cfg(any(feature = "bloom", feature = "countmin", feature = "xor"))]
mod xxhash;
-#[cfg(any(feature = "bloom", feature = "xor"))]
+#[cfg(any(feature = "bloom", feature = "countmin", feature = "xor"))]
pub(crate) use self::xxhash::*;
#[cfg(any(
@@ -82,7 +82,7 @@ pub(crate) use self::seed::*;
))]
pub(crate) const DEFAULT_UPDATE_SEED: u64 = 9001;
-#[cfg(any(feature = "bloom", feature = "xor"))]
+#[cfg(any(feature = "bloom", feature = "countmin", feature = "xor"))]
#[inline(always)]
fn read_u32_le(bytes: &[u8]) -> u32 {
u32::from_le_bytes(bytes.try_into().expect("four-byte hash input"))
diff --git a/datasketches/src/hash/value/mod.rs
b/datasketches/src/hash/value/mod.rs
index a4867a3..803aba5 100644
--- a/datasketches/src/hash/value/mod.rs
+++ b/datasketches/src/hash/value/mod.rs
@@ -48,7 +48,7 @@
//!
//! [`natural_extend::NaturalExtend`] first widens signed values to `i64` and
unsigned values to
//! `u64`, and then hashes the resulting integers. Use this encoding to match
short-integer hashing
-//! in DataSketches C++'s Bloom filters.
+//! in DataSketches C++'s Bloom filters and Count-Min sketches.
//!
//! The concrete wrapper documentation provides more details and examples.
//!
diff --git a/datasketches/src/hash/value/natural_extend.rs
b/datasketches/src/hash/value/natural_extend.rs
index 29d7fcf..780116f 100644
--- a/datasketches/src/hash/value/natural_extend.rs
+++ b/datasketches/src/hash/value/natural_extend.rs
@@ -20,7 +20,8 @@
//! [`NaturalExtend`] first widens signed values to `i64` and unsigned values
to `u64`, and then
//! hashes the resulting integers.
//!
-//! Use this encoding to match short-integer hashing in DataSketches C++'s
Bloom filters.
+//! Use this encoding to match short-integer hashing in DataSketches C++'s
Bloom filters and
+//! Count-Min sketches.
use std::hash::Hash;
use std::hash::Hasher;
diff --git a/datasketches/src/lib.rs b/datasketches/src/lib.rs
index 18cd2bc..bc77ea8 100644
--- a/datasketches/src/lib.rs
+++ b/datasketches/src/lib.rs
@@ -54,7 +54,7 @@
//! * `raw_bytes` for byte and string contents;
//! * `canonical_float` for floating-point values;
//! * `sign_extend` for short integers used with HLL and CPC;
-//! * `natural_extend` for short integers used with Bloom filters.
+//! * `natural_extend` for short integers used with Bloom filters and
Count-Min sketches.
//!
//! When interoperating with an implementation that skips empty strings, check
for empty input
//! before updating here as well.
diff --git a/tests-integration/tests/countmin_test/sketch.rs
b/tests-integration/tests/countmin_test/sketch.rs
index 8508bee..3437293 100644
--- a/tests-integration/tests/countmin_test/sketch.rs
+++ b/tests-integration/tests/countmin_test/sketch.rs
@@ -15,12 +15,15 @@
// specific language governing permissions and limitations
// under the License.
+use std::hash::Hash;
use std::panic::AssertUnwindSafe;
use std::panic::catch_unwind;
use datasketches::countmin::CountMinSketch;
use datasketches::countmin::UnsignedCountMinValue;
use datasketches::error::ErrorKind;
+use datasketches::hash::value::natural_extend;
+use datasketches::hash::value::raw_bytes;
use googletest::assert_that;
use googletest::prelude::ge;
use googletest::prelude::le;
@@ -415,8 +418,11 @@ fn
test_truncated_non_empty_payload_is_rejected_before_table_allocation() {
#[test]
fn test_invalid_hashes_return_error() {
- let error = CountMinSketch::<i64>::new(0, 5).unwrap_err();
- assert_eq!(error.kind(), ErrorKind::InvalidArgument);
+ for rows in [0, 128, 255] {
+ let error = CountMinSketch::<i64>::new(rows, 5).unwrap_err();
+ assert_eq!(error.kind(), ErrorKind::InvalidArgument);
+ }
+ assert!(CountMinSketch::<i64>::new(127, 5).is_ok());
}
#[test]
@@ -432,3 +438,29 @@ fn test_merge_incompatible() {
let error = left.merge(&right).unwrap_err();
assert_eq!(error.kind(), ErrorKind::InvalidArgument);
}
+
+#[test]
+fn value_wrappers_match_portable_item_encodings() {
+ fn assert_same_item<I: Hash, J: Hash>(left: I, right: J) {
+ let mut a = CountMinSketch::<i64>::new(3, 1000).unwrap();
+ let mut b = a.clone();
+ a.update_with_weight(&left, 7);
+ b.update_with_weight(&right, 7);
+ assert_eq!(a, b);
+ }
+
+ assert_same_item(natural_extend::from_i8(-2), -2i64);
+ assert_same_item(natural_extend::from_i16(-2), -2i64);
+ assert_same_item(natural_extend::from_i32(-2), -2i64);
+ assert_same_item(natural_extend::from_u8(u8::MAX), u64::from(u8::MAX));
+ assert_same_item(natural_extend::from_u16(u16::MAX), u64::from(u16::MAX));
+ assert_same_item(natural_extend::from_u32(u32::MAX), u64::from(u32::MAX));
+ assert_same_item(
+ -2i64,
+ raw_bytes::from_slice(&[0xfe, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
0xff]),
+ );
+ assert_same_item(
+ 0x0102_0304_0506_0708u64,
+ raw_bytes::from_slice(&[8, 7, 6, 5, 4, 3, 2, 1]),
+ );
+}
diff --git a/tests-integration/tests/serde_tests/countmin.rs
b/tests-integration/tests/serde_tests/countmin.rs
index 4a62faa..a0a019d 100644
--- a/tests-integration/tests/serde_tests/countmin.rs
+++ b/tests-integration/tests/serde_tests/countmin.rs
@@ -16,15 +16,237 @@
// under the License.
use std::fs;
+use std::hash::Hash;
use datasketches::countmin::CountMinSketch;
use datasketches::error::ErrorKind;
+use datasketches::hash::value::natural_extend;
+use datasketches::hash::value::raw_bytes;
use googletest::assert_that;
use googletest::prelude::contains_substring;
use tests_integration::ZERO_HASH_SEED;
use crate::serialization_test_data;
+fn words_to_bytes<const N: usize>(words: [u64; N]) -> Vec<u8> {
+ words.into_iter().flat_map(u64::to_le_bytes).collect()
+}
+
+#[test]
+fn v2_reads_and_writes_the_published_image() {
+ // TCK discussion #18, section 7.4: update(1, 10), update(9, 810),
update("apple", 5).
+ let bytes = words_to_bytes([
+ 0x0000_0000_0012_0202,
+ 0x0093_cc02_0000_0009,
+ 825,
+ 810,
+ 0,
+ 0,
+ 0,
+ 5,
+ 0,
+ 10,
+ 0,
+ 0,
+ 0,
+ 5,
+ 810,
+ 0,
+ 0,
+ 0,
+ 0,
+ 10,
+ 0,
+ ]);
+ let mut sketch = CountMinSketch::<i64>::new(2, 9).unwrap();
+ let mut empty = bytes[..16].to_vec();
+ empty[3] = 1;
+ assert_eq!(sketch.serialize(), empty);
+ assert_eq!(CountMinSketch::<i64>::deserialize(&empty).unwrap(), sketch);
+
+ sketch.update_with_weight(1i64, 10);
+ sketch.update_with_weight(9i64, 810);
+ sketch.update_with_weight(raw_bytes::from_str("apple"), 5);
+ assert_eq!(sketch.serialize(), bytes);
+
+ let mut restored = CountMinSketch::<i64>::deserialize(&bytes).unwrap();
+ assert_eq!(restored, sketch);
+ assert_eq!(restored.estimate(1u64), 10);
+ assert_eq!(restored.estimate(natural_extend::from_i8(9)), 810);
+ assert_eq!(restored.estimate(raw_bytes::from_str("apple")), 5);
+ restored.update_with_weight(raw_bytes::from_str("apple"), -2);
+ assert_eq!(restored.estimate(raw_bytes::from_str("apple")), 3);
+ assert_eq!(restored.total_weight(), 827);
+ sketch.merge(&restored).unwrap();
+ assert_eq!(sketch.estimate(raw_bytes::from_str("apple")), 8);
+ assert_eq!(sketch.total_weight(), 1652);
+}
+
+#[test]
+fn v2_matches_known_bucket_vectors() {
+ fn check<I: Hash>(item: I, seed: u64, expected: [usize; 3]) {
+ let mut sketch = CountMinSketch::<i64>::with_seed(3, 1000,
seed).unwrap();
+ sketch.update_with_weight(&item, 7);
+ let bytes = sketch.serialize();
+ for (row, bucket) in expected.into_iter().enumerate() {
+ let row_start = 24 + row * 1000 * 8;
+ let counts: Vec<(usize, i64)> = bytes[row_start..row_start + 1000
* 8]
+ .chunks_exact(8)
+ .map(|bytes| i64::from_le_bytes(bytes.try_into().unwrap()))
+ .enumerate()
+ .filter(|(_, count)| *count != 0)
+ .collect();
+ assert_eq!(counts, [(bucket, 7)], "seed {seed}, row {row}");
+ }
+ }
+
+ // Java XxHash64 vectors from TCK discussion #18, section 7.3.
+ check(-1i64, 9001, [256, 641, 308]);
+ check(natural_extend::from_i8(-1), 9001, [256, 641, 308]);
+ check(i64::MIN, 9001, [951, 0, 298]);
+ check(raw_bytes::from_str("apple"), 9001, [130, 747, 144]);
+ check(
+ raw_bytes::from_slice("été".as_bytes()),
+ 9001,
+ [806, 491, 163],
+ );
+
+ // Independently computed with XXH64 over little-endian u64 inputs.
+ check(1u64, 9001, [185, 898, 4]);
+ check(9u64, 9001, [490, 217, 440]);
+ check(natural_extend::from_u16(9), 9001, [490, 217, 440]);
+ check(1u64, 42, [468, 459, 696]);
+ check(9u64, 42, [841, 428, 322]);
+}
+
+#[test]
+fn legacy_image_preserves_wrappers_and_custom_hash_inputs() {
+ #[derive(Hash)]
+ struct Key(u64);
+
+ // Generated by Rust v0.6.0: raw_bytes("apple", 5), natural_extend(-1i8,
7),
+ // Key(42, 11), and raw_bytes("", 13), with two rows and nine buckets.
+ let bytes = words_to_bytes([
+ 0x0000_0000_0012_0102,
+ 0x0093_cc02_0000_0009,
+ 36,
+ 7,
+ 0,
+ 16,
+ 0,
+ 13,
+ 0,
+ 0,
+ 0,
+ 0,
+ 11,
+ 0,
+ 12,
+ 0,
+ 0,
+ 0,
+ 13,
+ 0,
+ 0,
+ ]);
+ let mut sketch = CountMinSketch::<i64>::deserialize(&bytes).unwrap();
+ assert_eq!(sketch.serialize(), bytes);
+
+ let restored = CountMinSketch::<i64>::deserialize(&bytes).unwrap();
+ assert_eq!(restored.estimate(raw_bytes::from_str("apple")), 12);
+ assert_eq!(restored.estimate(natural_extend::from_i8(-1)), 7);
+ assert_eq!(restored.estimate(Key(42)), 11);
+ assert_eq!(restored.estimate(raw_bytes::from_str("")), 13);
+
+ sketch.merge(&restored).unwrap();
+ sketch.update(Key(42));
+ assert_eq!(sketch.estimate(Key(42)), 23);
+ assert_eq!(sketch.total_weight(), 73);
+ assert_eq!(sketch.serialize()[1], 1);
+ assert_eq!(
+ CountMinSketch::<i64>::deserialize(&sketch.serialize()).unwrap(),
+ sketch
+ );
+}
+
+#[test]
+fn v2_row_limit_does_not_reject_legacy_images() {
+ for rows in [128, 255] {
+ let mut bytes = CountMinSketch::<i64>::new(1, 3).unwrap().serialize();
+ bytes[12] = rows;
+ assert_eq!(
+ CountMinSketch::<i64>::deserialize(&bytes)
+ .unwrap_err()
+ .kind(),
+ ErrorKind::InvalidData
+ );
+ bytes[1] = 1;
+ let legacy = CountMinSketch::<i64>::deserialize(&bytes).unwrap();
+ assert_eq!(legacy.num_hashes(), rows);
+ assert_eq!(legacy.serialize(), bytes);
+ }
+}
+
+// Generated by CountMinSketch v0.5.0 with one row, five buckets, seed 123,
and key 1 at weight 10.
+fn rust_v1_custom_seed_image() -> Vec<u8> {
+ words_to_bytes([
+ 0x0000_0000_0012_0102,
+ 0x0005_b601_0000_0005,
+ 10,
+ 0,
+ 0,
+ 0,
+ 0,
+ 10,
+ ])
+}
+
+#[test]
+fn legacy_rust_v1_image_preserves_queries_updates_and_merges() {
+ let image = rust_v1_custom_seed_image();
+ let mut sketch = CountMinSketch::<u64>::deserialize_with_seed(&image,
123).unwrap();
+ assert_eq!(sketch.total_weight(), 10);
+ assert_eq!(sketch.estimate(1u64), 10);
+ assert_eq!(sketch.serialize(), image);
+
+ sketch.update_with_weight(1u64, 5);
+ assert_eq!(sketch.total_weight(), 15);
+ assert_eq!(sketch.estimate(1u64), 15);
+ assert_eq!(sketch.serialize()[1], 1);
+
+ let mut merged = CountMinSketch::<u64>::deserialize_with_seed(&image,
123).unwrap();
+ merged.merge(&sketch).unwrap();
+ assert_eq!(merged.total_weight(), 25);
+ assert_eq!(merged.estimate(1u64), 25);
+}
+
+#[test]
+fn rejects_merge_across_serial_versions() {
+ let legacy =
+
CountMinSketch::<u64>::deserialize_with_seed(&rust_v1_custom_seed_image(),
123).unwrap();
+ let mut current = CountMinSketch::<u64>::with_seed(1, 5, 123).unwrap();
+ current.update_with_weight(1u64, 10);
+ let before = current.clone();
+
+ assert_eq!(
+ current.merge(&legacy).unwrap_err().kind(),
+ ErrorKind::InvalidArgument
+ );
+ assert_eq!(current, before);
+}
+
+#[test]
+fn rejects_unknown_serial_version() {
+ let mut bytes = CountMinSketch::<u64>::new(1, 5).unwrap().serialize();
+ bytes[1] = 3;
+ let error = CountMinSketch::<u64>::deserialize(&bytes).unwrap_err();
+ assert_eq!(error.kind(), ErrorKind::InvalidData);
+ assert_that!(
+ error.message(),
+ contains_substring("expected 1 or 2, got 3")
+ );
+}
+
#[test]
fn rejects_weights_that_cannot_bound_counter_arithmetic() {
let mut sketch = CountMinSketch::<i8>::new(2, 8).unwrap();
@@ -43,9 +265,9 @@ fn rejects_weights_that_cannot_bound_counter_arithmetic() {
}
}
-// This test validates binary format compatibility (deserialize + byte
round-trip) for
-// datasketches-cpp CountMin snapshots. It intentionally does not assert
estimate equivalence
-// against original input keys because per-row hash seed derivation differs
across implementations.
+// This helper validates binary format compatibility (deserialize + byte
round-trip) for
+// version 1 datasketches-cpp CountMin snapshots. It intentionally does not
assert estimate
+// equivalence because version 1 row-seed derivation differs across
implementations.
fn assert_cpp_snapshot(
filename: &str,
seed: u64,
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]