cardinality-estimator-safe

cardinality-estimator-safe is a fork of Cloudflare's cardinality-estimator, replacing its data representations with boring old owned data and eliminating all uses of unsafe. Its serialization formats are intended to be reasonable with serde_json, and efficient with bincode.

cardinality-estimator-safe estimates the number of distinct elements in a stream or dataset in an efficient manner. This library uses HyperLogLog++ with an optimized low memory footprint and high accuracy approach, suitable for large-scale data analysis tasks.

Overview

cardinality-estimator-safe is efficient in terms of memory usage, latency, and accuracy. This is achieved by leveraging a combination of unique data structure design, efficient algorithms, and HyperLogLog++ for high cardinality ranges.

Compared to other crates

• cardinality-estimator is currently vulnerable to memory safety violations due to its pervasive use of unsafe that appears to contain incorrect assumptions.
• amadeus-streaming writes out a huge array when serializing small cardinalities. it contains unsafe code without much documentation to justify it, though that code can be avoided by avoiding the SIMD paths.
• hyperloglogplus serialization is not compact, writing out even phantom data when serializing.

cardinality-estimator-safe is meant for serialization-heavy use-cases. it serializes to a fairly compact representation with serde_json, and is designed to be especially compact with binary encoders like bincode and postcard. you can see samples with cargo run --features with_serde --example json.

cardinality-estimator-safe is generic over BuildHasher instead of Hasher like cardinality-estimator, so it's possible to add a salt/prefix to the hashes for some resistance against malicious estimate inflation when users control any input data.

Crate status

• all unsafe code has been eliminated, but there are still many potential panics in the code.
• fuzzing harnesses are improved from cardinality-estimator, and excersized to try to discover any paths to a panic.
• serialization and deserialization have been completely rewritten.
• deserialization performance for hyperloglog representations is currently less than optimal, but there are easy ways to make it fast.
• some of the code could definitely be refactored for further clarity.

Getting Started

To use cardinality-estimator-safe, add it to your Cargo.toml under [dependencies]:

[dependencies]
cardinality-estimator-safe = "2.1.0"

Then, import cardinality-estimator-safe in your Rust program:

use cardinality_estimator_safe::CardinalityEstimator;

let mut estimator = CardinalityEstimator::<12, 6>::new();
estimator.insert("test");
let estimate = estimator.estimate();

println!("estimate = {}", estimate);

Please refer to our examples and benchmarks in the repository for more complex scenarios.

Low memory footprint

The cardinality-estimator achieves low memory footprint by leveraging an efficient data storage format. The data is stored in three different representations - Small, Array, and HyperLogLog - depending on the cardinality range. For instance, for a cardinality of 0 to 2, only 8 bytes of stack memory and 0 bytes of heap memory are used.

Low latency

The crate offers low latency by using auto-vectorization for slice operations via compiler hints to use SIMD instructions. The number of zero registers and registers' harmonic sum are stored and updated dynamically as more data is inserted, resulting in fast estimate operations.

High accuracy

The cardinality-estimator-safe achieves high accuracy by using precise counting for small cardinality ranges and HyperLogLog++ with LogLog-Beta bias correction for larger ranges. This provides expected error rates as low as 0.02% for large cardinalities.

Benchmarks

Benchmarks are added to directly compare Cloudflare's cardinality-estimator with cardinality-estimator-safe. They are included beside Cloudflare's original benchmarks for context.

To run benchmarks you first need to install cargo-criterion binary:

cargo install cargo-criterion

Then benchmarks with output format JSON to save results for further analysis:

make bench

We've benchmarked cardinality-estimator against several other crates in the ecosystem:

• cardinality-estimator
• hyperloglog
• hyperloglogplus
• amadeus-streaming
• probabilistic-collections

Please note, that hyperloglog and probabilistic-collections crates have bug in calculation of precision p based on provided probability:

• incorrect formula: p = (1.04 / error_probability).powi(2).ln().ceil() as usize;
• corrected formula: p = (1.04 / error_probability).powi(2).log2().ceil() as usize;

We're continuously working to make cardinality-estimator the fastest, lightest, and most accurate tool for cardinality estimation in Rust.

Benchmarks presented below are executed on Linux laptop with 13th Gen Intel(R) Core(TM) i7-13800H processor and compiler flags set to RUSTFLAGS=-C target-cpu=native.

Memory usage

Table below compares memory usage of different cardinality estimators. The number in each cell represents stack memory bytes / heap memory bytes / heap memory blocks at each measured cardinality.

cardinality-estimator-safe has a small memory overhead compared to cardinality-estimator. It uses the second-lowest stack memory, and the second-lowest heap memory for cardinalities up to 128, and a small constant overhead for cardinalities 256 and above.

Note, that hyperloglogplus implementation has particularly high memory usage especially for cardinalities above 256.

Insert performance

Table below represents insert time in nanoseconds per element.

cardinality-estimator-safe approaches the performance of cardinality-estimator across most cardinality ranges, despite containing no unsafe code.

Estimate performance

Table below represents estimate time in nanoseconds per call.

cardinality-estimator-safe is matches the performance of cardinality-estimator, with the lowest estimate time for all cardinalities.

Note, that amadeus-streaming implementation is also quite effective at estimate operation, however it has higher memory usage as indicated by table above. Implementations probabilistic-collections, hyperloglogplus and hyperloglogplus have much higher estimate time, especially for higher cardinalities.

Error rate

Table below represents average absolute relative error across 100 runs of estimator on random elements at given cardinality.

cardinality-estimator-safe matches cardinality-estimator, performing on par with amadeus-streaming and hyperloglog estimators, but especially well with low error rate for cardinalities up to 128.

Note, that probabilistic-collections implementation seems to have bug in its estimation operation for cardinalities >=32768.