HyperLogLog

A HyperLogLog cardinality estimator: a sketch that answers "how many distinct items have been added?" using a fixed, small amount of memory instead of keeping the full set.

As a CRDT. HyperLogLog is a join-semilattice whose piece takes the element-wise maximum of the register arrays. Two replicas that independently add overlapping streams converge to the same estimate when merged — no coordination required. This makes it a natural fit for distributed cardinality queries: unique peers, unique events, unique keys observed across the mesh.

Precision. The precision parameter p controls the number of registers m = 2^p (valid range: 4–18 inclusive). Higher precision reduces the relative standard error (1.04 / sqrt(m)) at the cost of memory (ceil(m * 6 / 8) bytes). The default (p = 14) gives m = 16384 registers and ~0.81% relative error.

Storage. Registers are packed at 6 bits per register (values 0–63), reducing state size by 25% compared to the previous 1-byte-per-register form. The backing ByteArray has size ceil(m * 6 / 8). Register i spans bits [i*6, i*6+5] across at most two consecutive bytes. See getRegister and setRegisterInto.

Wire format. The packed register array is serialized directly. This is a wire-breaking change vs the previous 1-byte-per-register format (pre-1.0, intentional). Old-format data is not compatible.

Accuracy. The estimate uses standard HyperLogLog bias-correction combined with a small-range linear-counting correction (HLL++-style). For very low cardinalities the linear count of empty registers is used; for the rest the harmonic-mean HLL formula applies.

Hash function. Elements are hashed with a 32-bit MurmurHash3 implemented inline in pure Kotlin — no external library, no platform API, deterministic on all targets. The hash is stable across runs and platforms for any given input string.

Immutable. add does not mutate the receiver; it returns a Patch. The delta inside the patch is a sparse fragment: only the changed register is non-zero (all others are zero). For a no-op add (the new ρ does not exceed the stored max) the delta is all-zero — an empty fragment that Quilter can skip without broadcasting.

piece is the join: a new instance whose registers are element-wise max. A sparse delta is a valid lattice fragment — element-wise max makes the join correct and idempotent regardless of how many registers are non-zero.

Parameters

Samples

var hll = HyperLogLog.empty(precision = 14)

// Add a stream of items — duplicates do not inflate the count.
// add() returns a sparse Patch; apply it with piece().
hll = hll.piece(hll.add("alice"))
hll = hll.piece(hll.add("bob"))
hll = hll.piece(hll.add("alice")) // duplicate — no-op delta, nothing changes

// The estimate is approximate but close to 2 for small cardinalities.
check(hll.estimate() in 1L..3L)

val a = ReplicaId("A")
val b = ReplicaId("B")

// Replica A sees users 0–999; replica B sees users 500–1499 (500 in common).
var hllA = HyperLogLog.empty(precision = 14)
var hllB = HyperLogLog.empty(precision = 14)
repeat(1_000) { i -> hllA = hllA.piece(hllA.add("user-$i")) }
repeat(1_000) { i -> hllB = hllB.piece(hllB.add("user-${i + 500}")) }

// Merge: element-wise max of registers.
val merged = hllA.piece(hllB)

// The merged estimate is close to 1500 (the true distinct count).
val estimate = merged.estimate()
check(estimate in 1_200L..1_800L) { "expected ≈1500, got $estimate" }

// Idempotent: merging again with either replica changes nothing.
check(merged.piece(hllA) == merged)
check(merged.piece(hllB) == merged)