Sketch Benchmark Laboratory

Decide What a Fair Benchmark Must Reveal

A sketch benchmark is like a wind tunnel for compact streaming algorithms. A wind tunnel does not merely announce that one wing “won”; it controls the airflow, measures lift and drag repeatedly, records uncertainty, and exposes the conditions where the result changes. Likewise, the laboratory feeds known workloads to exact and approximate implementations, records accuracy and systems cost, and identifies the crossover where one design becomes the better engineering choice.

Suppose the true distinct count is 100. Three seeded trials estimate 96, 101, and 108. Their signed errors are −4, +1, and +8; relative absolute errors are 4%, 1%, and 8%. Reporting only the mean estimate 101.7 hides the 8% tail. A useful report gives the distribution, confidence interval, memory, update/query throughput, merge cost, and workload conditions. It also asks whether a stated 95% interval actually covers truth about 95% of the time.

A workload generator produces a versioned stream from parameters and a seed. An exact oracle computes ground truth with a method whose limits are understood. An error distribution is the collection of trial-level errors, not one average. Calibration compares nominal confidence with empirical coverage. Throughput is completed operations divided by measured steady-state time; latency distributions, CPU, allocation, and peak resident memory remain separate. Merge cost measures compatible partial-state combination. An adversarial case stresses assumptions such as uniform hashing, positive updates, order independence, or bounded cardinality.

Stakeholders are algorithm authors, platform engineers, SREs, capacity planners, reviewers, and product owners choosing a production sketch. Acceptance requires deterministic replay, independent exact truth, standardized adapters, repeated seeded trials, controlled warm-up and measurement, raw immutable results, environment fingerprints, statistically defensible summaries, resource guards, and a decision table tied to explicit SLOs and budgets.

Design Workloads, Oracles and Reproducibility

The laboratory benchmarks counters, membership filters, cardinality estimators, frequency sketches, samplers, and quantile summaries through a common lifecycle: configure, update, query, merge, serialize, restore, and report state bytes. Users submit a declarative experiment containing dataset/generator version, distribution parameters, event count, seed schedule, sketch adapter/version, parameter grid, warm-up, repetitions, isolation mode, metrics, budgets, and acceptance rules. The scheduler expands this into immutable run manifests and sends them to isolated workers.

Workload families include uniform, Zipf, bursty, drifting, duplicate-heavy, ordered, shuffled, turnstile where supported, high-cardinality, heavy-tail latency, partitioned merge, and adversarial hash/counter cases. Exact oracles use integers, sets, dictionaries, sorted arrays, or reservoir inclusion accounting and are cross-checked on small fixtures. A result row contains manifest digest, seed, host/runtime fingerprint, timestamps, truth, estimate, error metrics, update/query/merge timings, peak memory, serialized bytes, status, and raw artifact checksums.

Target SLOs include deterministic regeneration of every workload, zero result mixing across manifest digests, 99.9% runner availability, run-start p99 below 30 seconds, ≤2% timing drift between calibrated reference runs on a stable pool, and hard CPU/memory/time quotas. Privacy rules default to synthetic data; production replays require minimization, access control, encryption, expiry, and provenance. Threats include malicious adapters, fork bombs, dataset exfiltration, clock manipulation, cherry-picked seeds, changed dependencies, corrupted artifacts, poisoned baselines, and over-parallelization that distorts measurements.

flowchart TD
    U[Experiment author] --> V[Validate specification]
    V --> X[Expand parameter grid]
    X --> M[Immutable run manifests]
    M --> Q[Resource-aware scheduler]
    Q --> W[Isolated workers]
    D[Generators and datasets] --> W
    A[Sketch adapters] --> W
    O[Exact oracles] --> W
    W --> R[Raw trial artifacts]
    R --> C[Statistical analysis]
    C --> P[Decision report]
    P --> G[Review and approval]
    W --> T[Metrics traces audit]
    classDef navy fill:#17365D,color:#fff,stroke:#102844;
    classDef teal fill:#147D84,color:#fff,stroke:#0c5c61;
    classDef crimson fill:#C6284D,color:#fff,stroke:#8e1935;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#482675;
    class U,D,A,O navy;
    class V,X,M,Q,W teal;
    class R,C,P purple;
    class G,T crimson;

Build the Pluggable Experiment Harness

Build vertically. Slice 1 generates a seeded stream, computes exact truth, runs one adapter, and emits a raw JSON-compatible result. Slice 2 adds repeated seeds, error distributions, timing warm-up, and deterministic replay. Slice 3 adds parameter grids, merge trials, memory/serialization metrics, and isolated execution. Slice 4 adds artifact checksums, comparative reports, regression gates, and signed approvals. Each slice has a fixture whose expected digest and metrics are independently testable.

The adapter contract is intentionally small: create(config), update(key,value), query(request), merge(other), serialize(), and state_bytes(). Capabilities declare whether deletions, weights, merge, or confidence intervals are supported; the scheduler never invents unsupported operations. Run schemas are versioned. Resource validation happens before grid expansion and again before worker launch. Old results remain readable through explicit schema migrations; incompatible adapters are quarantined rather than coerced.

from dataclasses import dataclass
from hashlib import sha256
from math import log
from random import Random
from statistics import median
from time import perf_counter_ns
import json

class ExactDistinct:
    name = "exact_set"
    def __init__(self, _: dict): self.values = set()
    def update(self, key: int, value: int = 1) -> None: self.values.add(key)
    def query(self) -> float: return float(len(self.values))
    def merge(self, other: "ExactDistinct") -> None: self.values |= other.values
    def state_bytes(self) -> int: return 8 * len(self.values)

class LinearCounter:
    name = "linear_counting"
    def __init__(self, config: dict):
        self.bits = int(config["bits"])
        if not 32 <= self.bits <= 1_000_000: raise ValueError("unsafe bitmap size")
        self.bitmap = bytearray((self.bits + 7) // 8)
    def update(self, key: int, value: int = 1) -> None:
        slot = int.from_bytes(sha256(str(key).encode()).digest()[:8], "big") % self.bits
        self.bitmap[slot // 8] |= 1 << (slot % 8)
    def query(self) -> float:
        occupied = sum(byte.bit_count() for byte in self.bitmap)
        zeros = self.bits - occupied
        return float("inf") if zeros == 0 else -self.bits * log(zeros / self.bits)
    def merge(self, other: "LinearCounter") -> None:
        if self.bits != other.bits: raise ValueError("incompatible bitmap sizes")
        self.bitmap = bytearray(a | b for a, b in zip(self.bitmap, other.bitmap))
    def state_bytes(self) -> int: return len(self.bitmap)

@dataclass(frozen=True)
class Experiment:
    events: int = 20_000
    universe: int = 4_000
    seeds: tuple[int, ...] = (11, 13, 17, 19, 23)
    bits: int = 16_384
    max_work: int = 1_000_000
    schema_version: int = 1
    def validate(self) -> None:
        if self.schema_version != 1: raise ValueError("unsupported schema")
        if not self.seeds or self.events <= 0 or self.universe <= 0: raise ValueError("invalid workload")
        if self.events * len(self.seeds) > self.max_work: raise ValueError("experiment exceeds work budget")

def workload(spec: Experiment, seed: int) -> list[int]:
    rng = Random(seed)
    return [rng.randrange(spec.universe) for _ in range(spec.events)]

def trial(adapter_type, config: dict, values: list[int]) -> dict:
    oracle = ExactDistinct({})
    candidate = adapter_type(config)
    start = perf_counter_ns()
    for key in values:
        oracle.update(key); candidate.update(key)
    elapsed = perf_counter_ns() - start
    truth, estimate = oracle.query(), candidate.query()
    return {"truth": truth, "estimate": estimate,
            "relative_error": abs(estimate-truth)/truth if truth else 0.0,
            "updates_per_second": len(values)/(elapsed/1e9),
            "state_bytes": candidate.state_bytes()}

def run(spec: Experiment) -> dict:
    spec.validate()
    raw = [trial(LinearCounter, {"bits": spec.bits}, workload(spec, seed)) for seed in spec.seeds]
    digest = sha256(json.dumps(spec.__dict__, sort_keys=True, default=list).encode()).hexdigest()[:16]
    errors = sorted(row["relative_error"] for row in raw)
    return {"manifest_digest": digest, "adapter": LinearCounter.name, "raw_trials": raw,
            "median_relative_error": median(errors), "max_relative_error": max(errors)}

def self_test() -> None:
    spec = Experiment(events=5_000, universe=1_000, seeds=(3,5,7), bits=8_192)
    first, second = run(spec), run(spec)
    assert first["manifest_digest"] == second["manifest_digest"]
    assert [(r["truth"], r["estimate"]) for r in first["raw_trials"]] == [(r["truth"], r["estimate"]) for r in second["raw_trials"]]
    assert first["max_relative_error"] < 0.10
    left, right = LinearCounter({"bits": 1024}), LinearCounter({"bits": 1024})
    for x in range(50): left.update(x)
    for x in range(50,100): right.update(x)
    left.merge(right)
    assert abs(left.query()-100) / 100 < 0.10
    try: left.merge(LinearCounter({"bits": 2048}))
    except ValueError: pass
    else: raise AssertionError("incompatible merge accepted")
    try: Experiment(events=600_000, seeds=(1,2)).validate()
    except ValueError: pass
    else: raise AssertionError("work budget not enforced")
    print("benchmark checks passed", first["manifest_digest"], round(first["median_relative_error"], 4))

if __name__ == "__main__": self_test()

flowchart TD
    S[Versioned run schema] --> G[Seeded generator]
    G --> O[Exact oracle fixture]
    O --> A[One adapter trial]
    A --> R[Repeated seeds and raw rows]
    R --> P[Parameter and merge sweeps]
    P --> I[Isolated workers and quotas]
    I --> E[Immutable evidence]
    E --> C[Comparative canary report]
    C -->|Gates pass| D[Publish decision]
    C -->|Drift or invariant fail| B[Rollback baseline]
    B --> O
    classDef navy fill:#17365D,color:#fff,stroke:#102844;
    classDef teal fill:#147D84,color:#fff,stroke:#0c5c61;
    classDef crimson fill:#C6284D,color:#fff,stroke:#8e1935;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#482675;
    class S,G,O navy;
    class A,R,P,I teal;
    class E,C purple;
    class D,B crimson;

Find Crossovers and Break the Candidates

Verification tests the laboratory before trusting what it says about sketches. Unit and property tests cover generators, seed isolation, oracle identities, adapter capability declarations, merge equivalence, serialization, quantiles, manifest hashing, and schema migration. Metamorphic tests shuffle insertion order for order-invariant algorithms, repartition mergeable streams, duplicate or scale weights where the mathematics predicts a response, and compare restored state with uninterrupted execution.

An approachable end-to-end study compares an exact set with linear counting from 100 to 1 million distinct keys, identifying the point where fixed bitmap memory beats the exact baseline while error remains acceptable. The professional matrix covers HLL, Bloom/Cuckoo filters, CMS/Count Sketch, reservoir sampling, and KLL/GK quantiles across uniform, Zipf, drift, heavy-tail, merge, and adversarial workloads. Each cell runs at least 30 preregistered seeds, reports p50/p95/p99 accuracy and latency, empirical confidence coverage, peak memory, serialized bytes, throughput, merge cost, failures, and cost per billion updates.

Failure injection kills workers mid-trial, throttles CPU, fills disk, corrupts artifacts, delays object storage, changes the clock source, poisons a baseline, leaks adapter state between runs, and schedules noisy neighbours. Metrics expose queue/run time, retries by reason, quota kills, host calibration drift, timer anomalies, artifact checksum failures, oracle disagreements, seed coverage, and report exclusions. Audit logs preserve manifest approval, adapter/dataset provenance, retry lineage, exclusions, baseline changes, and the final decision owner.

Publish the Benchmark Dossier

The deliverable includes adapter and experiment schemas, generator/oracle specifications, parameter calculators, a pinned execution image, environment fingerprints, preregistration, immutable raw results, checksums, analysis code, comparative tables, crossover plots, calibration curves, benchmark report, correctness dossier, privacy review, incident notes, and an operational runbook. Every chart links back to raw rows and a manifest digest; every recommendation states its workload region, SLO weights, limitations, and rejected alternatives.

The runbook begins with queue delay, timing drift, oracle mismatch, quota kill, missing seed, corrupt artifact, adapter crash, storage outage, and baseline regression. It supplies diagnostics, exclusion rules, retry policy, escalation, invalidation criteria, and evidence-preservation steps. The demonstration regenerates a seeded fixture, runs exact and linear-counting adapters, shows raw error and memory rows, verifies compatible merge, rejects incompatible merge and excessive work, recomputes the report, then changes the decision weights to reveal a crossover.

Peer reviewers ask: Was the hypothesis and seed schedule fixed before results? Are workloads representative and adversarial? Is the oracle independent? Are warm-up, isolation, timing, and memory methods defensible? Are tails and failures visible? Does merging preserve the advertised guarantee? Can every figure be regenerated? Is the recommendation conditional rather than universal? Handoff requires tagged code/images, checksums, clean one-command replay, signed review, retained raw evidence, rehearsed incident handling, ownership, and no undocumented exclusions.