Histogram

An explicit-bucket histogram: you choose the bucket boundaries up front — say [10, 50, 100] milliseconds — and each bucket counts how many recorded values fell in its range. It answers "how are my measurements distributed?" when you already know the ranges you care about (SLA thresholds, size classes), the classic fixed-bucket histogram shape.

As a CRDT. Each bucket's count is a GCounter, so piece is a pointwise GCounter join — idempotent, commutative, and associative. Many peers can record values independently and merge histograms in any order, with any duplication, and converge; the merge is lossless — merging two replicas' histograms produces exactly the histogram of the combined stream. Because each cell is per-replica-keyed, a re-delivered patch never double-counts.

Bucketing. boundaries is a strictly-increasing list of N upper bounds defining N + 1 buckets with OTLP's upper-inclusive convention: bucket 0 is (-∞, bounds[0]], bucket i is (bounds[i−1], bounds[i]], and the last bucket is (bounds[N−1], +∞). An empty boundary list is the degenerate single catch-all bucket. Choose boundaries to fit the expected range — a value past the last boundary still counts, but all resolution beyond it is lost (if the range is unknowable up front, prefer DDSketch, whose log buckets auto-cover any range at uniform relative precision).

Configuration is a cluster-wide constant. Two histograms merge only if their boundaries match exactly — the same must-match discipline as DDSketch's accuracy and HyperLogLog's precision. Fix the boundaries once per deployment; piece rejects mismatches.

Immutable. record does not mutate the receiver; it returns a Patch whose delta carries a single bucket cell (plus a sum cell) — the minimal sparse fragment idiom shared by the zoo's sketches.

Sum, but no min/max. sum carries the running total (for the mean) as a pair of GCounterDoubles (positive and negative contributions), which keeps it mergeable. OTLP's optional min/max are deliberately omitted: they are not products of grow-only counters and would need separate min-/max-register lattices — add those alongside if a consumer ever needs them.

OTel interop. The state is structurally an OTLP HistogramDataPoint: explicit bounds (boundaries) plus bucket_counts (bucketCounts), count, and sum. The OTLP mapping itself lives with the metrics exporter, not in this module.

Samples

val replica = ReplicaId("api-server-1")

// Buckets: (-inf, 10], (10, 50], (50, 100], (100, +inf) — SLA thresholds in ms.
var latencies = Histogram.empty(boundaries = listOf(10.0, 50.0, 100.0))

// record() returns a one-bucket delta; absorb it with piece().
for (ms in listOf(7.0, 12.0, 45.0, 50.0, 220.0)) {
    latencies = latencies.piece(latencies.record(replica, ms))
}

check(latencies.bucketCounts == listOf(1L, 3L, 0L, 1L)) // 50.0 is upper-inclusive in (10, 50]
check(latencies.count == 5L)
check(latencies.sum == 334.0)

val serverA = ReplicaId("server-a")
val serverB = ReplicaId("server-b")
val boundaries = listOf(10.0, 100.0)

// Two servers count their own request latencies.
var a = Histogram.empty(boundaries)
var b = Histogram.empty(boundaries)
repeat(30) { a = a.piece(a.record(serverA, 5.0)) } // 30 fast requests
repeat(20) { b = b.piece(b.record(serverB, 500.0)) } // 20 slow requests

// Merge: pointwise GCounter join of the bucket counts.
val merged = a.piece(b)
check(merged.bucketCounts == listOf(30L, 0L, 20L))
check(merged.count == 50L)

// Idempotent: merging again with either side changes nothing.
check(merged.piece(a) == merged)
check(merged.piece(b) == merged)