grudge

A constant-memory sketch that holds grudges and forgives: decaying feedback scores over unbounded key spaces.

grudge is to behavioral scores what a count-min sketch is to counts. It maps an unbounded set of keys (client IDs, tenants, IPs, cache keys…) to a scalar score that you update with feedback and that decays toward zero on its own — in a few megabytes of fixed memory, with no per-key state, no eviction, no background work, and ~120ns zero-allocation reads and writes.

It is the core data structure of FAIR (Stochastic Fair BLUE-based fairness throttling), extracted and generalized so other things can be built on it: rate limiters, abuse scoring, circuit breakers, cache admission, fair schedulers.

import "github.com/satmihir/grudge"

s, err := grudge.New(grudge.Config{
    Levels:        4,                       // hash levels (collision shield)
    CellsPerLevel: 100_000,                 // memory knob: L×M×16B payload
    Decay:         grudge.Exponential(0.01), // forgiveness: e^(−λ·Δt)
    Lo:            0,
    Hi:            1,
    Aggregator:    grudge.Min,
})

s.Update(clientID, +0.04)   // something bad happened; hold a grudge
s.Update(clientID, -0.001)  // something good happened; forgive a little
p := s.Query(clientID)      // current score — and time heals on its own

How it works

L levels × M cells. A key hashes to one cell per level (Kirsch–Mitzenmacher over a single 64-bit hash). Updates add a delta to all L cells; queries aggregate the L values (min by default). Every access first applies lazy decay — scores fade toward zero based on elapsed time, so an idle sketch does literally nothing.

Three properties do the heavy lifting:

• Collision shielding. With Min aggregation, a key's estimate is exact whenever at least one of its L cells is untouched by other traffic. The error is one-sided: Query(k) ≥ true score, never under. An innocent key is misjudged only if all L of its cells collide with hot keys — probability (1−(1−1/M)^H)^L, which SuggestLevels sizes for you.
• Decay. Nothing is punished forever. Exponential(λ) gives proportional forgiveness (FAIR's behavior); Linear(r) drains at a constant rate (token-bucket refill); None disables it.
• Rotation. A Rotator keeps N generations under different hash seeds, reads from the oldest, writes to all (so successors are warm), and periodically retires the oldest. Even a worst-case false positive lasts at most Generations × Period.

What you can build with it

A cell is one mechanism with four readings:

Reading	Update pattern	You get
Decayed counter	+1 per event	per-key rate estimation (Query·λ ≈ rate), heavy hitters, hot-key detection
Saturating latch	+1, clamp Hi=1	a Bloom filter that forgets: streaming dedup, novelty detection
Feedback score	±δ on outcomes	FAIR-style fairness, abuse scores, circuit breakers, flap damping
Debt meter	+cost, Linear decay	token-bucket rate limiting over unbounded keys

The debt meter deserves a taste — an approximate per-key token bucket (capacity B, refill r) with no per-key state:

s, _ := grudge.New(grudge.Config{
    Levels: 4, CellsPerLevel: 100_000,
    Decay: grudge.Linear(rate),   // debt drains at the refill rate
    Lo:    0, Hi: burst,
    Aggregator: grudge.Min,
})

// Strict admission: atomically debit cost iff the key has headroom.
if s.TryUpdate(key, cost, burst) {
    serve()
} else {
    reject()
}

Collisions only make this limiter stricter for a stable key, never more permissive — and a fresh, never-seen key naturally reads as "full bucket."

API sketch

s, _  := grudge.New(cfg)                  // random seed
s, _  := grudge.NewWithSeed(cfg, seed)    // deterministic (tests, replicas)

s.Update(key, delta)                      // add delta to the key's cells
v     := s.Query(key)                     // aggregated score
v     := s.UpdateAndQuery(key, delta)     // both, single pass
ok    := s.TryUpdate(key, delta, limit)   // atomic conditional-consume
r     := s.QueryDetailed(key)             // per-level scores + cell indexes

r, _  := grudge.NewRotator(grudge.RotatorConfig{
    Sketch: cfg, Generations: 2, Period: 5 * time.Minute,
})
defer r.Close()                           // same methods as Sketch

L     := grudge.SuggestLevels(hotKeys, cellsPerLevel, 1e-4) // sizing help

grudgetest provides a FakeClock and FakeTicker for driving decay and rotation deterministically in your tests.

Adversarial keys? Use SipHash

The default hasher is murmur3: fast, but it has known seed-independent collisions, and the level-derivation scheme amplifies any 64-bit collision into a collision at every level. If your keys are attacker-controlled (public APIs, per-IP limits), use the keyed PRF instead:

cfg.Hasher = grudge.SipHash() // ~2× hash cost, collision-resistant without the key

Performance

Apple Silicon, L=4, M=100_000 (see BENCHMARKS.md):

Operation	ns/op	allocs/op
Update	~111	0
Query	~119	0
UpdateAndQuery	~134	0

Cell payload at that size is ~6.4 MB per generation; zero allocations on the hot path is enforced by tests, not just measured.

Scope

grudge is deliberately policy-free: it stores and decays scores, and that's all. No throttle/allow decisions, no key enumeration or top-k, no serialization or cross-instance merge (planned; the update algebra is designed to make replica merge convergent). The normative specification lives in spec/SPEC.md.

Development

go test ./... -race        # full suite; runs under goleak
go vet ./...
go test -bench . -benchmem # hot-path benchmarks

License

MIT — see LICENSE.