Module sketch 

Count-min frequency sketch keyed directly on BLAKE3 hashes (ADR 040).

Keys are already uniform 32-byte hashes, so each row’s column index is a disjoint 4-byte slice of the key reduced mod the sketch’s width — no hash functions. Counters are saturating u8 — classic TinyLFU uses 4-bit counters, and the extra headroom is free at one byte each. Halving ages them.

ShardedCountMinSketch is the form the estimator uses. It splits the counter array into SHARDS independently locked CountMinSketches of cols / SHARDS columns each, routed by a 4-byte slice of the key that no row index reads. An increment or an estimate locks exactly one shard.

Two properties of one wide sketch of cols columns are load-bearing for the policies that read the estimates, and sharding keeps both:

• Aging cadence is global, not per shard. Both readers compare estimates against a shared scale: super::tinylfu::ProbationAdmission tests one estimate against a node-wide promotion_threshold, and super::tinylfu::TinyLfuEviction ranks candidates from different shards least-frequent-first. Counters are only comparable if every counter is caught up to the same clock when it is read. So the halving clock is one node-wide observation counter, and a shard halves lazily — on its next touch — by however many windows have elapsed since it last caught up. The work stays sharded (1 / SHARDS of the array under one shard’s lock, landing on one observer), while the cadence stays global. A shard clocked on its own traffic would age at a rate set by key skew, which is exactly what a frequency sketch must not do.
• Per-row collision rate. Two distinct keys share a row counter only if they share a shard (probability 1 / SHARDS) and then a column within it (SHARDS / cols) — the same 1 / cols a single wide sketch gives, because the shard slice and the row slices are disjoint bytes of a uniform hash.

The over-report rate carries over as exactly as the per-row rate does. The sketch reads a key hotter than it is when every one of its ROWS counters also holds some other key’s count. The polluting keys need not be the same one across rows, so “two keys collide in all ROWS rows” is a far rarer event that does not bound the error — do not size the sketch from it. For N live keys the rate is (1 - e^(-N / cols))^ROWS, and SHARDS cancels out: a shard divides the columns and the keys in the same proportion. So sharding costs nothing in accuracy and the width alone sets it. The rate turns on N / cols, which holds the shipped cols = 65536 under one percent out to roughly 25000 live keys. See super::tinylfu::TinyLfuEstimator::new for the sizing and its floor.

Structs

CountMinSketch

A plain count-min counter array. It carries no aging clock of its own: ShardedCountMinSketch owns the node-wide clock and calls Self::halve, which is what keeps every shard on one cadence.

ShardedCountMinSketch

A CountMinSketch split into SHARDS independently locked pieces on one node-wide aging clock.

Constants

SHARDS

Number of independently locked shards in a ShardedCountMinSketch.