Grudge: A Decaying Score Sketch for Multi-Tenant Systems

Grudge is a probabilistic Go data structure that does for behavioral scores what a count-min sketch does for counts. It maps an unbounded key space—client IDs, tenants, IPs, cache keys—onto scores stored in fixed, constant memory, with reads and writes completing in roughly 120 nanoseconds and zero allocations, while scores automatically decay toward zero over time. It was extracted and generalized from FAIR, a fairness-based throttling system.

Internally it uses an L-levels-by-M-cells table, hashing each key into one cell per level via Kirsch–Mitzenmacher derivation from a single 64-bit hash. Updates add a delta to every level, while queries take the minimum by default, giving a one-sided error guarantee where the true score is never underestimated. Configurable decay modes—exponential, linear, or none—model different forgiveness behaviors, and an optional Rotator keeps multiple hashed generations to bound how long a worst-case false positive can persist.

On top of this single mechanism, developers can build rate limiters, abuse scoring, circuit breakers, cache admission policies, and fair schedulers; the library demonstrates this with a token-bucket-style debt meter. For adversary-controlled keys, a collision-resistant SipHash option replaces the default murmur3 hasher. Grudge is deliberately policy-free—it only stores and decays scores—with zero-allocation behavior enforced by tests, and it ships under the MIT license.