This is an automated email from the ASF dual-hosted git repository. tisonkun pushed a commit to branch codex/xor-filter in repository https://gitbox.apache.org/repos/asf/datasketches-rust.git
commit 1baf4d3d2db85cc21a002543139f2180edf23e8a Author: tison <[email protected]> AuthorDate: Mon Aug 24 04:05:27 2026 +0800 feat: add xor filter --- CHANGELOG.md | 4 + README.md | 1 + datasketches/Cargo.toml | 6 + datasketches/src/codec/family.rs | 9 + datasketches/src/codec/mod.rs | 2 + datasketches/src/hash/mod.rs | 5 +- datasketches/src/lib.rs | 2 + datasketches/src/xor/filter.rs | 535 +++++++++++++++++++++ datasketches/src/xor/mod.rs | 62 +++ datasketches/src/xor/serialization.rs | 183 +++++++ datasketches/tests/serde_tests.rs | 4 + datasketches/tests/serde_tests/xor.rs | 154 ++++++ datasketches/tests/xor_test/filter.rs | 142 ++++++ .../{src/codec/mod.rs => tests/xor_test/main.rs} | 32 +- 14 files changed, 1108 insertions(+), 33 deletions(-) diff --git a/CHANGELOG.md b/CHANGELOG.md index ad6104c..65a3f65 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -4,6 +4,10 @@ All significant changes to this project will be documented in this file. ## Unreleased +### New features + +* Add immutable xor filters behind the `xor` feature, with 8- and 16-bit fingerprints, pre-hashed input APIs, and compatible serialization. + ## v0.4.0 (2026-08-18) ### Breaking changes diff --git a/README.md b/README.md index f8d1593..a245df0 100644 --- a/README.md +++ b/README.md @@ -73,6 +73,7 @@ Enable multiple algorithms by listing their features together, such as `features | `tdigest` | `TDigestMut`, `TDigest` | Quantile and rank estimation, with high accuracy near distribution tails. | | `theta` | `ThetaSketch` and set operations | Distinct counts, set expressions, and Jaccard similarity. | | `tuple` | `TupleSketch` and set operations | Theta-style keys with user-defined summaries attached to retained entries. | +| `xor` | `XorFilter`, `XorFilterBuilder` | Compact immutable probabilistic set membership with 8- or 16-bit fingerprints. | See the [API documentation](https://docs.rs/datasketches) for configuration, accuracy guarantees, serialization, and examples for each algorithm. diff --git a/datasketches/Cargo.toml b/datasketches/Cargo.toml index 169ee7e..db22578 100644 --- a/datasketches/Cargo.toml +++ b/datasketches/Cargo.toml @@ -46,6 +46,7 @@ hll = [] tdigest = [] theta = [] tuple = [] +xor = [] [[test]] name = "bloom_test" @@ -87,6 +88,11 @@ name = "tuple_test" path = "tests/tuple_test/main.rs" required-features = ["tuple"] +[[test]] +name = "xor_test" +path = "tests/xor_test/main.rs" +required-features = ["xor"] + [dev-dependencies] googletest = { workspace = true } insta = { workspace = true } diff --git a/datasketches/src/codec/family.rs b/datasketches/src/codec/family.rs index c6ab908..98207ca 100644 --- a/datasketches/src/codec/family.rs +++ b/datasketches/src/codec/family.rs @@ -106,6 +106,15 @@ impl Family { min_pre_longs: 3, max_pre_longs: 4, }; + + /// Xor filter for probabilistic set membership. + #[cfg(feature = "xor")] + pub const XORFILTER: Family = Family { + id: 22, + name: "XORFILTER", + min_pre_longs: 3, + max_pre_longs: 3, + }; } impl Family { diff --git a/datasketches/src/codec/mod.rs b/datasketches/src/codec/mod.rs index 30d1075..1cd4cfc 100644 --- a/datasketches/src/codec/mod.rs +++ b/datasketches/src/codec/mod.rs @@ -31,6 +31,7 @@ pub use self::encode::SketchBytes; feature = "tdigest", feature = "theta", feature = "tuple", + feature = "xor", ))] #[allow(dead_code)] // some utilities are only used for certain sketches pub(crate) mod assert; @@ -44,5 +45,6 @@ pub(crate) mod assert; feature = "tdigest", feature = "theta", feature = "tuple", + feature = "xor", ))] pub(crate) mod family; diff --git a/datasketches/src/hash/mod.rs b/datasketches/src/hash/mod.rs index c5c26c4..04cd807 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(feature = "bloom")] +#[cfg(any(feature = "bloom", feature = "xor"))] mod xxhash; -#[cfg(feature = "bloom")] +#[cfg(any(feature = "bloom", feature = "xor"))] pub(crate) use self::xxhash::*; #[cfg(any( @@ -95,6 +95,7 @@ pub(crate) const DEFAULT_UPDATE_SEED: u64 = 9001; feature = "hll", feature = "theta", feature = "tuple", + feature = "xor", ))] fn read_u64_le(bytes: &[u8]) -> u64 { let mut buf = [0u8; 8]; diff --git a/datasketches/src/lib.rs b/datasketches/src/lib.rs index e169c4c..6013b29 100644 --- a/datasketches/src/lib.rs +++ b/datasketches/src/lib.rs @@ -51,6 +51,8 @@ pub use self::thetafamily::common as thetacommon; pub use self::thetafamily::theta; #[cfg(feature = "tuple")] pub use self::thetafamily::tuple; +#[cfg(feature = "xor")] +pub mod xor; // common modules pub mod codec; diff --git a/datasketches/src/xor/filter.rs b/datasketches/src/xor/filter.rs new file mode 100644 index 0000000..6fd7997 --- /dev/null +++ b/datasketches/src/xor/filter.rs @@ -0,0 +1,535 @@ +// 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. + +use std::hash::Hash; +use std::hash::Hasher; +use std::ops::BitXor; + +use crate::error::Error; +use crate::hash::XxHash64; + +const NUM_HASHES: u8 = 3; +const HASH_SEED: u64 = 0; +const DEFAULT_CONSTRUCTION_SEED: u64 = 0; +const LOAD_FACTOR: f64 = 1.23; +const CAPACITY_OFFSET: u64 = 32; +const MAX_CONSTRUCTION_ATTEMPTS: usize = 100; + +const MURMUR_C1: u64 = 0xff51_afd7_ed55_8ccd; +const MURMUR_C2: u64 = 0xc4ce_b9fe_1a85_ec53; + +const SPLITMIX_GAMMA: u64 = 0x9e37_79b9_7f4a_7c15; +const SPLITMIX_MUL1: u64 = 0xbf58_476d_1ce4_e5b9; +const SPLITMIX_MUL2: u64 = 0x94d0_49bb_1331_11eb; + +/// Fingerprint representation used by an [`XorFilter`]. +#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] +pub enum XorFilterType { + /// Uses 8-bit fingerprints and has an expected false-positive probability of about `1 / 256`. + Xor8, + /// Uses 16-bit fingerprints and has an expected false-positive probability of about + /// `1 / 65_536`. + Xor16, +} + +impl XorFilterType { + /// Returns the number of bits in each fingerprint. + pub const fn bits_per_fingerprint(self) -> u8 { + match self { + Self::Xor8 => 8, + Self::Xor16 => 16, + } + } + + pub(super) const fn bytes_per_fingerprint(self) -> usize { + (self.bits_per_fingerprint() / 8) as usize + } + + pub(super) fn from_bits(bits: u8) -> Result<Self, Error> { + match bits { + 8 => Ok(Self::Xor8), + 16 => Ok(Self::Xor16), + _ => Err(Error::deserial(format!( + "invalid fingerprint width: expected 8 or 16, got {bits}" + ))), + } + } +} + +#[derive(Debug, Clone, PartialEq, Eq)] +pub(super) enum Fingerprints { + Xor8(Box<[u8]>), + Xor16(Box<[u16]>), +} + +impl Fingerprints { + pub(super) fn len(&self) -> usize { + match self { + Self::Xor8(values) => values.len(), + Self::Xor16(values) => values.len(), + } + } + + pub(super) fn byte_len(&self) -> usize { + match self { + Self::Xor8(values) => size_of_val::<[u8]>(values), + Self::Xor16(values) => size_of_val::<[u16]>(values), + } + } +} + +/// An immutable xor filter for probabilistic set membership. +/// +/// A query that returns `false` proves that the item was not in the input set. A query that returns +/// `true` may be a false positive, with probability determined by [`XorFilterType`]. Values cannot +/// be added after construction; rebuild the filter when the set changes. +/// +/// Ordinary values passed to [`contains`](Self::contains) are reduced to 64-bit hashes with +/// xxHash64 and seed `0`. Use [`contains_hash`](Self::contains_hash) only with the same hashes that +/// were supplied to [`XorFilter::from_hashes`] or [`XorFilterBuilder::update_hash`]. +#[derive(Debug, Clone, PartialEq, Eq)] +pub struct XorFilter { + pub(super) filter_type: XorFilterType, + pub(super) segment_length: usize, + pub(super) num_items: usize, + pub(super) seed: u64, + pub(super) fingerprints: Fingerprints, +} + +impl XorFilter { + /// Builds a filter from precomputed 64-bit hashes. + /// + /// Duplicate hashes are removed before construction. The same hash values must be passed to + /// [`contains_hash`](Self::contains_hash) when querying the result. + /// + /// # Errors + /// + /// Returns an error if the input is too large for the portable serialization format or if no + /// peelable construction is found within the bounded retry limit. + /// + /// # Examples + /// + /// ``` + /// use datasketches::xor::XorFilter; + /// use datasketches::xor::XorFilterType; + /// + /// let filter = XorFilter::from_hashes([10, 20, 30], XorFilterType::Xor8).unwrap(); + /// assert!(filter.contains_hash(20)); + /// ``` + pub fn from_hashes( + hashes: impl IntoIterator<Item = u64>, + filter_type: XorFilterType, + ) -> Result<Self, Error> { + let mut builder = XorFilterBuilder::new(filter_type); + builder.extend_hashes(hashes); + builder.build() + } + + /// Returns `true` if an item is possibly in the input set. + /// + /// A `false` result means the item was definitely absent; a `true` result may be a false + /// positive. + #[inline] + pub fn contains<T: Hash + ?Sized>(&self, item: &T) -> bool { + self.contains_hash(hash_item(item)) + } + + /// Returns `true` if a precomputed 64-bit hash is possibly in the input set. + /// + /// This method bypasses xxHash64. The caller must use the same hash value during construction + /// and queries; mixing raw values with precomputed hashes can introduce false negatives. + #[inline] + pub fn contains_hash(&self, hash: u64) -> bool { + let mixed = mix(hash, self.seed); + let [h0, h1, h2] = indexes(mixed, self.segment_length); + + match &self.fingerprints { + Fingerprints::Xor8(fingerprints) => { + fingerprint(mixed) as u8 == fingerprints[h0] ^ fingerprints[h1] ^ fingerprints[h2] + } + Fingerprints::Xor16(fingerprints) => { + fingerprint(mixed) == fingerprints[h0] ^ fingerprints[h1] ^ fingerprints[h2] + } + } + } + + /// Returns `true` if no distinct hashes were used to build the filter. + pub fn is_empty(&self) -> bool { + self.num_items == 0 + } + + /// Returns the number of distinct 64-bit hashes used to build the filter. + pub fn num_items(&self) -> usize { + self.num_items + } + + /// Returns the fingerprint representation. + pub fn filter_type(&self) -> XorFilterType { + self.filter_type + } + + /// Returns the number of bits in each fingerprint. + pub fn bits_per_fingerprint(&self) -> u8 { + self.filter_type.bits_per_fingerprint() + } + + /// Returns the number of hash locations read by every query. + pub fn num_hashes(&self) -> u8 { + NUM_HASHES + } + + /// Returns the number of fingerprint slots in the filter. + pub fn capacity(&self) -> usize { + self.fingerprints.len() + } + + /// Returns the construction seed stored with the filter. + pub fn seed(&self) -> u64 { + self.seed + } + + /// Returns the number of fingerprint bits allocated per distinct input hash. + /// + /// Returns `0.0` for an empty filter. For sufficiently large inputs the value approaches `9.84` + /// for [`XorFilterType::Xor8`] and `19.68` for [`XorFilterType::Xor16`]. + pub fn bits_per_item(&self) -> f64 { + if self.is_empty() { + return 0.0; + } + self.capacity() as f64 * f64::from(self.bits_per_fingerprint()) / self.num_items as f64 + } + + /// Returns the estimated in-memory size of the filter in bytes. + pub fn estimated_size(&self) -> usize { + size_of::<Self>() + self.fingerprints.byte_len() + } + + fn build(keys: &[u64], filter_type: XorFilterType, base_seed: u64) -> Result<Self, Error> { + let num_items = keys.len(); + let capacity = compute_capacity(num_items)?; + let payload_bytes = capacity + .checked_mul(filter_type.bytes_per_fingerprint()) + .ok_or_else(|| Error::invalid_argument("xor filter fingerprint size overflow"))?; + if payload_bytes > i32::MAX as usize { + return Err(Error::invalid_argument(format!( + "xor filter requires {payload_bytes} fingerprint bytes, exceeding the portable limit of {}", + i32::MAX + ))); + } + + let segment_length = capacity / usize::from(NUM_HASHES); + let mut xor_mask = vec![0_u64; capacity]; + let mut count = vec![0_u32; capacity]; + let mut queue = vec![0_u32; capacity]; + let mut stack_hash = vec![0_u64; num_items]; + let mut stack_index = vec![0_u32; num_items]; + + let mut rng_state = base_seed; + let mut construction_seed = 0; + let mut stack_size = 0; + for _ in 0..MAX_CONSTRUCTION_ATTEMPTS { + rng_state = rng_state.wrapping_add(SPLITMIX_GAMMA); + construction_seed = splitmix64(rng_state); + stack_size = map( + keys, + construction_seed, + segment_length, + &mut xor_mask, + &mut count, + &mut queue, + &mut stack_hash, + &mut stack_index, + ); + if stack_size == num_items { + break; + } + } + + if stack_size != num_items { + return Err(Error::invalid_argument(format!( + "xor filter construction failed after {MAX_CONSTRUCTION_ATTEMPTS} attempts" + )) + .with_context("num_items", num_items)); + } + + let fingerprints = match filter_type { + XorFilterType::Xor8 => { + let mut values = vec![0_u8; capacity].into_boxed_slice(); + assign_fingerprints( + &mut values, + segment_length, + &stack_hash[..stack_size], + &stack_index[..stack_size], + |hash| fingerprint(hash) as u8, + ); + Fingerprints::Xor8(values) + } + XorFilterType::Xor16 => { + let mut values = vec![0_u16; capacity].into_boxed_slice(); + assign_fingerprints( + &mut values, + segment_length, + &stack_hash[..stack_size], + &stack_index[..stack_size], + fingerprint, + ); + Fingerprints::Xor16(values) + } + }; + + Ok(Self { + filter_type, + segment_length, + num_items, + seed: construction_seed, + fingerprints, + }) + } +} + +/// Builder for accumulating values and creating an immutable [`XorFilter`]. +/// +/// Values are reduced to 64-bit hashes as they are added, so the builder retains one `u64` per +/// update regardless of the original value size. Duplicate hashes are removed by +/// [`build`](Self::build). +#[derive(Debug, Clone)] +pub struct XorFilterBuilder { + filter_type: XorFilterType, + seed: u64, + hashes: Vec<u64>, +} + +impl XorFilterBuilder { + /// Creates a builder for the requested fingerprint representation. + /// + /// The default base construction seed is `0`. + pub fn new(filter_type: XorFilterType) -> Self { + Self { + filter_type, + seed: DEFAULT_CONSTRUCTION_SEED, + hashes: Vec::new(), + } + } + + /// Sets the base seed used to derive construction attempts. + /// + /// A fixed seed makes construction deterministic for a given set of hashes. The filter stores + /// the successful derived seed, which is returned by [`XorFilter::seed`]. + pub fn seed(mut self, seed: u64) -> Self { + self.seed = seed; + self + } + + /// Updates the builder with a value hashed by xxHash64 with seed `0`. + pub fn update<T: Hash>(&mut self, item: T) { + self.hashes.push(hash_item(&item)); + } + + /// Updates the builder with a precomputed 64-bit hash. + /// + /// This method bypasses xxHash64. Query the resulting filter with + /// [`XorFilter::contains_hash`] using hashes from the same source. + pub fn update_hash(&mut self, hash: u64) { + self.hashes.push(hash); + } + + /// Extends the builder with values hashed by xxHash64 with seed `0`. + pub fn extend<T: Hash>(&mut self, items: impl IntoIterator<Item = T>) { + self.hashes + .extend(items.into_iter().map(|item| hash_item(&item))); + } + + /// Extends the builder with precomputed 64-bit hashes. + pub fn extend_hashes(&mut self, hashes: impl IntoIterator<Item = u64>) { + self.hashes.extend(hashes); + } + + /// Returns the number of updates accumulated so far, including duplicates. + pub fn num_items(&self) -> usize { + self.hashes.len() + } + + /// Returns `true` if no updates have been accumulated. + pub fn is_empty(&self) -> bool { + self.hashes.is_empty() + } + + /// Builds an immutable filter after removing duplicate hashes. + /// + /// # Errors + /// + /// Returns an error if the input is too large for the portable serialization format or if no + /// peelable construction is found within the bounded retry limit. + pub fn build(mut self) -> Result<XorFilter, Error> { + self.hashes.sort_unstable(); + self.hashes.dedup(); + XorFilter::build(&self.hashes, self.filter_type, self.seed) + } +} + +fn hash_item<T: Hash + ?Sized>(item: &T) -> u64 { + let mut hasher = XxHash64::with_seed(HASH_SEED); + item.hash(&mut hasher); + hasher.finish() +} + +fn compute_capacity(num_items: usize) -> Result<usize, Error> { + if num_items > i32::MAX as usize { + return Err(Error::invalid_argument(format!( + "xor filter item count exceeds portable limit: {num_items}" + ))); + } + + let scaled = (LOAD_FACTOR * num_items as f64) as u64; + let capacity = CAPACITY_OFFSET + .checked_add(scaled) + .ok_or_else(|| Error::invalid_argument("xor filter capacity overflow"))?; + let capacity = capacity / u64::from(NUM_HASHES) * u64::from(NUM_HASHES); + let capacity = capacity.max(u64::from(NUM_HASHES)); + if capacity > i32::MAX as u64 { + return Err(Error::invalid_argument(format!( + "xor filter capacity exceeds portable limit: {capacity}" + ))); + } + Ok(capacity as usize) +} + +fn map( + keys: &[u64], + seed: u64, + segment_length: usize, + xor_mask: &mut [u64], + count: &mut [u32], + queue: &mut [u32], + stack_hash: &mut [u64], + stack_index: &mut [u32], +) -> usize { + xor_mask.fill(0); + count.fill(0); + + for &key in keys { + let hash = mix(key, seed); + for index in indexes(hash, segment_length) { + xor_mask[index] ^= hash; + count[index] += 1; + } + } + + let mut queue_length = 0; + for (index, &value) in count.iter().enumerate() { + if value == 1 { + queue[queue_length] = index as u32; + queue_length += 1; + } + } + + let mut stack_size = 0; + while queue_length > 0 { + queue_length -= 1; + let index = queue[queue_length] as usize; + if count[index] != 1 { + continue; + } + + let hash = xor_mask[index]; + stack_hash[stack_size] = hash; + stack_index[stack_size] = index as u32; + stack_size += 1; + + for hash_index in indexes(hash, segment_length) { + count[hash_index] -= 1; + xor_mask[hash_index] ^= hash; + if count[hash_index] == 1 { + queue[queue_length] = hash_index as u32; + queue_length += 1; + } + } + } + + stack_size +} + +fn assign_fingerprints<T: Copy + BitXor<Output = T>>( + fingerprints: &mut [T], + segment_length: usize, + stack_hash: &[u64], + stack_index: &[u32], + fingerprint_of: impl Fn(u64) -> T, +) { + for (&hash, &index) in stack_hash.iter().zip(stack_index).rev() { + let index = index as usize; + let [h0, h1, h2] = indexes(hash, segment_length); + fingerprints[index] = + fingerprint_of(hash) ^ fingerprints[h0] ^ fingerprints[h1] ^ fingerprints[h2]; + } +} + +#[inline] +fn indexes(hash: u64, segment_length: usize) -> [usize; 3] { + [ + reduce(hash as u32, segment_length), + reduce(hash.rotate_left(21) as u32, segment_length) + segment_length, + reduce(hash.rotate_left(42) as u32, segment_length) + 2 * segment_length, + ] +} + +#[inline] +fn reduce(hash: u32, range: usize) -> usize { + ((u64::from(hash) * range as u64) >> 32) as usize +} + +#[inline] +fn fingerprint(hash: u64) -> u16 { + (hash ^ (hash >> 32)) as u16 +} + +#[inline] +fn mix(key: u64, seed: u64) -> u64 { + let mut hash = key.wrapping_add(seed); + hash ^= hash >> 33; + hash = hash.wrapping_mul(MURMUR_C1); + hash ^= hash >> 33; + hash = hash.wrapping_mul(MURMUR_C2); + hash ^ (hash >> 33) +} + +fn splitmix64(state: u64) -> u64 { + let mut value = state; + value = (value ^ (value >> 30)).wrapping_mul(SPLITMIX_MUL1); + value = (value ^ (value >> 27)).wrapping_mul(SPLITMIX_MUL2); + value ^ (value >> 31) +} + +#[cfg(test)] +mod tests { + use super::*; + + #[test] + fn capacity_matches_reference_values() { + assert_eq!(compute_capacity(0).unwrap(), 30); + assert_eq!(compute_capacity(1).unwrap(), 33); + assert_eq!(compute_capacity(5).unwrap(), 36); + assert_eq!(compute_capacity(10_000).unwrap(), 12_330); + } + + #[test] + fn reduce_stays_in_range() { + for hash in [0, 1, u32::MAX / 2, u32::MAX] { + assert!(reduce(hash, 17) < 17); + } + } +} diff --git a/datasketches/src/xor/mod.rs b/datasketches/src/xor/mod.rs new file mode 100644 index 0000000..70e93cc --- /dev/null +++ b/datasketches/src/xor/mod.rs @@ -0,0 +1,62 @@ +// 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. + +//! Xor filters for immutable probabilistic set membership. +//! +//! An xor filter is built from the complete input set and cannot be updated afterward. Compared +//! with a Bloom filter at the same false-positive probability, it generally needs less space and +//! performs exactly three fingerprint reads per query. Construction needs temporary space linear +//! in the number of distinct hashes. +//! +//! The [`XorFilterBuilder`] hashes ordinary Rust values with xxHash64. Call +//! [`XorFilterBuilder::update_hash`] or [`XorFilter::from_hashes`] when hashes have already been +//! computed and must not be hashed again. +//! +//! # Cross-language hashing +//! +//! The serialized filter representation is portable, but Rust's [`Hash`](std::hash::Hash) +//! implementations do not always encode values like other languages. Use the strategies in +//! [`crate::hash::value`] when the input hashes must match another DataSketches implementation. +//! A filter built through the precomputed-hash APIs remains portable only when every reader uses +//! the same external hash function. +//! +//! # Examples +//! +//! ``` +//! use datasketches::xor::XorFilterBuilder; +//! use datasketches::xor::XorFilterType; +//! +//! let mut builder = XorFilterBuilder::new(XorFilterType::Xor8); +//! builder.update("apple"); +//! builder.update("banana"); +//! let filter = builder.build().unwrap(); +//! +//! assert!(filter.contains(&"apple")); +//! assert!(!filter.contains(&"grape")); +//! ``` +//! +//! # References +//! +//! * Graf and Lemire, "Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters," ACM Journal +//! of Experimental Algorithmics 25 (2020). + +mod filter; +mod serialization; + +pub use self::filter::XorFilter; +pub use self::filter::XorFilterBuilder; +pub use self::filter::XorFilterType; diff --git a/datasketches/src/xor/serialization.rs b/datasketches/src/xor/serialization.rs new file mode 100644 index 0000000..04fb5e1 --- /dev/null +++ b/datasketches/src/xor/serialization.rs @@ -0,0 +1,183 @@ +// 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. + +use crate::codec::SketchBytes; +use crate::codec::SketchSlice; +use crate::codec::assert::ensure_preamble_longs_in_range; +use crate::codec::assert::ensure_serial_version_is; +use crate::codec::assert::insufficient_data; +use crate::codec::family::Family; +use crate::error::Error; +use crate::xor::filter::Fingerprints; +use crate::xor::filter::XorFilter; +use crate::xor::filter::XorFilterType; + +const SERIAL_VERSION: u8 = 1; +const NUM_HASHES: u8 = 3; +const PREAMBLE_BYTES: usize = 3 * size_of::<u64>(); + +impl XorFilter { + /// Serializes the filter to a byte vector. + /// + /// The format uses Apache DataSketches family ID `22` and is compatible with the corresponding + /// xor-filter format in other DataSketches implementations. + pub fn serialize(&self) -> Vec<u8> { + let mut bytes = SketchBytes::with_capacity(self.serialized_size()); + + bytes.write_u8(Family::XORFILTER.min_pre_longs); + bytes.write_u8(SERIAL_VERSION); + bytes.write_u8(Family::XORFILTER.id); + bytes.write_u8(0); // flags + bytes.write_u8(self.bits_per_fingerprint()); + bytes.write_u8(NUM_HASHES); + bytes.write_u16_le(0); // unused + bytes.write_u64_le(self.seed); + bytes.write_i32_le(self.segment_length as i32); + bytes.write_i32_le(self.num_items as i32); + + match &self.fingerprints { + Fingerprints::Xor8(fingerprints) => bytes.write(fingerprints), + Fingerprints::Xor16(fingerprints) => { + for &fingerprint in fingerprints.iter() { + bytes.write_u16_le(fingerprint); + } + } + } + + bytes.into_bytes() + } + + /// Deserializes an owned filter from bytes. + /// + /// # Errors + /// + /// Returns an error if the image is truncated, belongs to another sketch family or version, or + /// contains metadata that could make a membership query index outside the fingerprint payload. + pub fn deserialize(bytes: &[u8]) -> Result<Self, Error> { + let mut cursor = SketchSlice::new(bytes); + + let preamble_longs = cursor + .read_u8() + .map_err(insufficient_data("preamble_longs"))?; + let serial_version = cursor + .read_u8() + .map_err(insufficient_data("serial_version"))?; + let family_id = cursor.read_u8().map_err(insufficient_data("family_id"))?; + let _flags = cursor.read_u8().map_err(insufficient_data("flags"))?; + let bits_per_fingerprint = cursor + .read_u8() + .map_err(insufficient_data("bits_per_fingerprint"))?; + let num_hashes = cursor.read_u8().map_err(insufficient_data("num_hashes"))?; + let _unused = cursor.read_u16_le().map_err(insufficient_data("unused"))?; + + Family::XORFILTER.validate_id(family_id)?; + ensure_serial_version_is(SERIAL_VERSION, serial_version)?; + ensure_preamble_longs_in_range( + Family::XORFILTER.min_pre_longs..=Family::XORFILTER.max_pre_longs, + preamble_longs, + )?; + let filter_type = XorFilterType::from_bits(bits_per_fingerprint)?; + if num_hashes != NUM_HASHES { + return Err(Error::deserial(format!( + "invalid number of hashes: expected {NUM_HASHES}, got {num_hashes}" + ))); + } + + let seed = cursor.read_u64_le().map_err(insufficient_data("seed"))?; + let segment_length = cursor + .read_i32_le() + .map_err(insufficient_data("segment_length"))?; + if segment_length <= 0 { + return Err(Error::deserial(format!( + "invalid segment length: expected a positive value, got {segment_length}" + ))); + } + let segment_length = segment_length as usize; + + let num_items = cursor + .read_i32_le() + .map_err(insufficient_data("num_items"))?; + if num_items < 0 { + return Err(Error::deserial(format!( + "invalid item count: expected a non-negative value, got {num_items}" + ))); + } + let num_items = num_items as usize; + + let capacity = segment_length + .checked_mul(usize::from(NUM_HASHES)) + .ok_or_else(|| Error::deserial("xor filter capacity overflow"))?; + if capacity > i32::MAX as usize { + return Err(Error::deserial(format!( + "invalid xor filter capacity: maximum is {}, got {capacity}", + i32::MAX + ))); + } + if num_items > capacity { + return Err(Error::deserial(format!( + "invalid item count: capacity is {capacity}, got {num_items}" + ))); + } + + let fingerprint_bytes = capacity + .checked_mul(filter_type.bytes_per_fingerprint()) + .ok_or_else(|| Error::deserial("xor filter fingerprint size overflow"))?; + if cursor.remaining().len() < fingerprint_bytes { + return Err(Error::insufficient_data_of( + "fingerprints", + format!( + "expected {fingerprint_bytes} bytes, got {}", + cursor.remaining().len() + ), + )); + } + + let fingerprints = match filter_type { + XorFilterType::Xor8 => { + let mut values = vec![0_u8; capacity].into_boxed_slice(); + cursor + .read_exact(&mut values) + .map_err(insufficient_data("fingerprints"))?; + Fingerprints::Xor8(values) + } + XorFilterType::Xor16 => { + let mut values = Vec::with_capacity(capacity); + for _ in 0..capacity { + values.push( + cursor + .read_u16_le() + .map_err(insufficient_data("fingerprints"))?, + ); + } + Fingerprints::Xor16(values.into_boxed_slice()) + } + }; + + Ok(Self { + filter_type, + segment_length, + num_items, + seed, + fingerprints, + }) + } + + /// Returns the serialized size of the filter in bytes. + pub fn serialized_size(&self) -> usize { + PREAMBLE_BYTES + self.fingerprints.byte_len() + } +} diff --git a/datasketches/tests/serde_tests.rs b/datasketches/tests/serde_tests.rs index 5f31c2d..225ea53 100644 --- a/datasketches/tests/serde_tests.rs +++ b/datasketches/tests/serde_tests.rs @@ -73,3 +73,7 @@ mod theta; #[cfg(feature = "tuple")] #[path = "serde_tests/tuple.rs"] mod tuple; + +#[cfg(feature = "xor")] +#[path = "serde_tests/xor.rs"] +mod xor; diff --git a/datasketches/tests/serde_tests/xor.rs b/datasketches/tests/serde_tests/xor.rs new file mode 100644 index 0000000..dc602bc --- /dev/null +++ b/datasketches/tests/serde_tests/xor.rs @@ -0,0 +1,154 @@ +// 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. + +use datasketches::error::ErrorKind; +use datasketches::xor::XorFilter; +use datasketches::xor::XorFilterBuilder; +use datasketches::xor::XorFilterType; + +const JAVA_XOR8_IMAGE: &str = concat!( + "0301160008030000956eeb2f2632d7bd0c00000004000000", + "00000000000000000000c500000000000000000000000000dd000000040000000b000000" +); +const JAVA_XOR16_IMAGE: &str = concat!( + "0301160010030000", + "956eeb2f2632d7bd", + "0c00000004000000", + "0000000000000000", + "0000000000000000", + "00000000c5b60000", + "0000000000000000", + "0000000000000000", + "0000000000000000", + "dd6e000000000000", + "04e8000000000000", + "0b23000000000000", +); + +#[test] +fn java_images_match_byte_for_byte() { + let values = [1_u64, 2, 3, 1_u64 << 63]; + + for (filter_type, image) in [ + (XorFilterType::Xor8, JAVA_XOR8_IMAGE), + (XorFilterType::Xor16, JAVA_XOR16_IMAGE), + ] { + let expected = decode_hex(image); + let mut builder = XorFilterBuilder::new(filter_type).seed(42); + builder.extend(values); + assert_eq!(builder.build().unwrap().serialize(), expected); + + let restored = XorFilter::deserialize(&expected).unwrap(); + assert_eq!(restored.filter_type(), filter_type); + assert_eq!(restored.num_items(), values.len()); + for value in values { + assert!( + restored.contains(&value), + "{filter_type:?} image did not contain {value}" + ); + } + } +} + +#[test] +fn serialization_round_trips_both_fingerprint_types() { + for filter_type in [XorFilterType::Xor8, XorFilterType::Xor16] { + let original = XorFilter::from_hashes(0..10_000_u64, filter_type).unwrap(); + let bytes = original.serialize(); + assert_eq!(bytes.len(), original.serialized_size()); + + let restored = XorFilter::deserialize(&bytes).unwrap(); + assert_eq!(restored, original); + for hash in 0..10_000_u64 { + assert!(restored.contains_hash(hash)); + } + } +} + +#[test] +fn every_truncated_image_is_rejected() { + for filter_type in [XorFilterType::Xor8, XorFilterType::Xor16] { + let bytes = XorFilter::from_hashes(0..100_u64, filter_type) + .unwrap() + .serialize(); + for end in 0..bytes.len() { + let error = XorFilter::deserialize(&bytes[..end]).unwrap_err(); + assert_eq!(error.kind(), ErrorKind::InvalidData, "length {end}"); + } + assert!(XorFilter::deserialize(&bytes).is_ok()); + } +} + +#[test] +fn invalid_preamble_fields_are_rejected() { + let valid = XorFilter::from_hashes(0..100_u64, XorFilterType::Xor8) + .unwrap() + .serialize(); + + for (offset, value) in [(0, 2), (0, 4), (1, 2), (2, 21), (4, 7), (4, 32), (5, 4)] { + let mut corrupted = valid.clone(); + corrupted[offset] = value; + let error = XorFilter::deserialize(&corrupted).unwrap_err(); + assert_eq!(error.kind(), ErrorKind::InvalidData, "offset {offset}"); + } +} + +#[test] +fn unsafe_lengths_are_rejected_before_indexing() { + let valid = XorFilter::from_hashes(0..100_u64, XorFilterType::Xor8) + .unwrap() + .serialize(); + + for segment_length in [0_i32, -1] { + let mut corrupted = valid.clone(); + corrupted[16..20].copy_from_slice(&segment_length.to_le_bytes()); + assert_eq!( + XorFilter::deserialize(&corrupted).unwrap_err().kind(), + ErrorKind::InvalidData + ); + } + + for num_items in [-1_i32, i32::MAX] { + let mut corrupted = valid.clone(); + corrupted[20..24].copy_from_slice(&num_items.to_le_bytes()); + assert_eq!( + XorFilter::deserialize(&corrupted).unwrap_err().kind(), + ErrorKind::InvalidData + ); + } +} + +#[test] +fn trailing_storage_is_ignored() { + let original = XorFilter::from_hashes(0..100_u64, XorFilterType::Xor16).unwrap(); + let mut bytes = original.serialize(); + bytes.extend_from_slice(&[0xaa; 16]); + + assert_eq!(XorFilter::deserialize(&bytes).unwrap(), original); +} + +fn decode_hex(input: &str) -> Vec<u8> { + assert_eq!(input.len() % 2, 0); + input + .as_bytes() + .chunks_exact(2) + .map(|digits| { + let digits = std::str::from_utf8(digits).unwrap(); + u8::from_str_radix(digits, 16).unwrap() + }) + .collect() +} diff --git a/datasketches/tests/xor_test/filter.rs b/datasketches/tests/xor_test/filter.rs new file mode 100644 index 0000000..31f633f --- /dev/null +++ b/datasketches/tests/xor_test/filter.rs @@ -0,0 +1,142 @@ +// 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. + +use datasketches::xor::XorFilter; +use datasketches::xor::XorFilterBuilder; +use datasketches::xor::XorFilterType; + +#[test] +fn values_have_no_false_negatives() { + let mut builder = XorFilterBuilder::new(XorFilterType::Xor8).seed(8123); + for value in 0..10_000_u64 { + builder.update(value); + } + let filter = builder.build().unwrap(); + + for value in 0..10_000_u64 { + assert!(filter.contains(&value), "false negative for {value}"); + } +} + +#[test] +fn precomputed_hashes_have_no_false_negatives() { + let hashes = (0..10_000_u64) + .map(|value| value.wrapping_mul(0x9e37_79b9_7f4a_7c15)) + .collect::<Vec<_>>(); + + for filter_type in [XorFilterType::Xor8, XorFilterType::Xor16] { + let filter = XorFilter::from_hashes(hashes.iter().copied(), filter_type).unwrap(); + for &hash in &hashes { + assert!(filter.contains_hash(hash), "false negative for {hash}"); + } + } +} + +#[test] +fn builder_accepts_mixed_value_types() { + let mut builder = XorFilterBuilder::new(XorFilterType::Xor16); + builder.update("datasketches"); + builder.update(42_u64); + builder.update([1_u8, 2, 3, 4]); + let filter = builder.build().unwrap(); + + assert!(filter.contains("datasketches")); + assert!(filter.contains(&42_u64)); + assert!(filter.contains(&[1_u8, 2, 3, 4])); +} + +#[test] +fn duplicates_are_removed_before_construction() { + let mut builder = XorFilterBuilder::new(XorFilterType::Xor8); + builder.extend_hashes([7, 7, 11, 11, 11]); + assert_eq!(builder.num_items(), 5); + + let filter = builder.build().unwrap(); + assert_eq!(filter.num_items(), 2); + assert!(filter.contains_hash(7)); + assert!(filter.contains_hash(11)); +} + +#[test] +fn construction_is_independent_of_input_order() { + let ascending = XorFilterBuilder::new(XorFilterType::Xor8).seed(424_242); + let descending = ascending.clone(); + + let mut ascending = ascending; + ascending.extend_hashes(0..50_000_u64); + let mut descending = descending; + descending.extend_hashes((0..50_000_u64).rev()); + + assert_eq!( + ascending.build().unwrap().serialize(), + descending.build().unwrap().serialize() + ); +} + +#[test] +fn metadata_describes_the_compact_payload() { + let filter = XorFilter::from_hashes(0..10_000_u64, XorFilterType::Xor8).unwrap(); + + assert!(!filter.is_empty()); + assert_eq!(filter.num_items(), 10_000); + assert_eq!(filter.filter_type(), XorFilterType::Xor8); + assert_eq!(filter.bits_per_fingerprint(), 8); + assert_eq!(filter.num_hashes(), 3); + assert_eq!(filter.capacity() % 3, 0); + assert!((9.5..10.5).contains(&filter.bits_per_item())); + assert!(filter.estimated_size() >= filter.capacity()); + assert_eq!(filter.serialized_size(), 24 + filter.capacity()); +} + +#[test] +fn empty_filter_is_well_formed() { + let builder = XorFilterBuilder::new(XorFilterType::Xor16); + assert!(builder.is_empty()); + let filter = builder.build().unwrap(); + + assert!(filter.is_empty()); + assert_eq!(filter.num_items(), 0); + assert_eq!(filter.capacity(), 30); + assert_eq!(filter.bits_per_item(), 0.0); + assert_eq!(filter.serialized_size(), 24 + 60); +} + +#[test] +fn false_positive_rates_follow_fingerprint_width() { + const NUM_ITEMS: u64 = 50_000; + const NUM_QUERIES: u64 = 100_000; + + let xor8 = XorFilter::from_hashes(0..NUM_ITEMS, XorFilterType::Xor8).unwrap(); + let xor16 = XorFilter::from_hashes(0..NUM_ITEMS, XorFilterType::Xor16).unwrap(); + + let false_positives8 = (NUM_ITEMS..NUM_ITEMS + NUM_QUERIES) + .filter(|&hash| xor8.contains_hash(hash)) + .count(); + let false_positives16 = (NUM_ITEMS..NUM_ITEMS + NUM_QUERIES) + .filter(|&hash| xor16.contains_hash(hash)) + .count(); + + assert!( + false_positives8 < 1_000, + "8-bit false-positive count was {false_positives8}" + ); + assert!( + false_positives16 < 100, + "16-bit false-positive count was {false_positives16}" + ); + assert!(false_positives16 < false_positives8); +} diff --git a/datasketches/src/codec/mod.rs b/datasketches/tests/xor_test/main.rs similarity index 54% copy from datasketches/src/codec/mod.rs copy to datasketches/tests/xor_test/main.rs index 30d1075..2b29745 100644 --- a/datasketches/src/codec/mod.rs +++ b/datasketches/tests/xor_test/main.rs @@ -15,34 +15,4 @@ // specific language governing permissions and limitations // under the License. -//! Codec utilities for datasketches crate. - -mod decode; -mod encode; -pub use self::decode::SketchSlice; -pub use self::encode::SketchBytes; - -#[cfg(any( - feature = "bloom", - feature = "countmin", - feature = "cpc", - feature = "frequencies", - feature = "hll", - feature = "tdigest", - feature = "theta", - feature = "tuple", -))] -#[allow(dead_code)] // some utilities are only used for certain sketches -pub(crate) mod assert; - -#[cfg(any( - feature = "bloom", - feature = "countmin", - feature = "cpc", - feature = "frequencies", - feature = "hll", - feature = "tdigest", - feature = "theta", - feature = "tuple", -))] -pub(crate) mod family; +mod filter; --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
