grudge

package module
v0.1.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jul 7, 2026 License: MIT Imports: 8 Imported by: 0

README

grudge

CI Go Reference Go Report Card

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.

Documentation

Overview

Package grudge implements a constant-memory sketch that maps an unbounded key space to a decaying scalar score updated by feedback. It is to behavioral scores what a count-min sketch is to counts.

A Sketch holds L levels of M cells. Each key maps to one cell per level via L hashes derived from a single 64-bit hash (Kirsch–Mitzenmacher). Scores decay toward zero on access (lazily, so an idle sketch does no work), and an Aggregator (Min by default) collapses a key's L per-level scores into one. Min-aggregation shields a key: its estimate is exact whenever at least one of its cells is free of colliding traffic.

The three properties that make the structure useful:

  • Collision shielding via L independent levels and min-aggregation.
  • Lazy decay: scores fade toward zero, computed on access, no background work.
  • Rotation (see Rotator): periodic reseeding bounds how long any false positive can persist.

grudge is policy-free: it stores and decays scores but makes no throttle, allow, or sampling decision. Callers interpret scores. See spec/SPEC.md for the normative specification.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func SuggestLevels 

func SuggestLevels(hotKeys, cellsPerLevel uint32, targetP float64) uint32

SuggestLevels returns the number of levels L needed so that an innocent key is falsely dragged up (all of its cells contaminated) with probability at most targetP, given hotKeys concurrently-hot keys and cellsPerLevel cells per level. It solves, for L: 

targetP = (1 - (1 - 1/M)^H)^L

where M = cellsPerLevel and H = hotKeys, and returns ceil(L) with a floor of 1. This is FAIR's CalculateL, relocated. The caller supplies M (memory and per-level collision are its choice) and gets the L that meets the target.

It panics on degenerate inputs — hotKeys == 0, cellsPerLevel < 2 (a single cell collides with certainty), or targetP outside (0, 1) — because these have no meaningful answer and reaching them signals a configuration error.

Types

type Aggregator 

type Aggregator func(levelScores []float64) float64

Aggregator collapses a key's per-level scores into a single value. The input slice has length L (one score per level) and is never empty. Implementations must not retain or mutate the slice; it is reused across calls. 

var Max Aggregator = func(levelScores []float64) float64 {
	m := levelScores[0]
	for _, v := range levelScores[1:] {
		if v > m {
			m = v
		}
	}
	return m
}

Max returns the largest level score. 

var Mean Aggregator = func(levelScores []float64) float64 {
	var sum float64
	for _, v := range levelScores {
		sum += v
	}
	return sum / float64(len(levelScores))
}

Mean returns the arithmetic mean of the level scores. Useful when Min is too strict. 

var Min Aggregator = func(levelScores []float64) float64 {
	m := levelScores[0]
	for _, v := range levelScores[1:] {
		if v < m {
			m = v
		}
	}
	return m
}

Min returns the smallest level score. It is the recommended default: it yields the collision-shielding property, since a key's estimate is dragged up only when every one of its cells is contaminated.

type Clock 

type Clock interface {
	Now() time.Time
}

Clock abstracts the current time so sketches can be driven by a controlled clock in tests and simulations.

type Config 

type Config struct {
	// Levels (L) is the number of hash levels; must be >= 1.
	Levels uint32
	// CellsPerLevel (M) is the number of cells per level; must be >= 1.
	CellsPerLevel uint32
	// Decay is the decay function. Required; use None to disable decay.
	Decay Decay
	// Lo and Hi bound every score; require Lo < Hi and Lo <= 0 <= Hi. Hi may
	// be +Inf only when Decay is not None.
	Lo, Hi float64
	// Aggregator collapses per-level scores. Required; Min is recommended.
	Aggregator Aggregator
	// Hasher builds the per-generation hasher. nil uses Murmur3.
	Hasher HasherFactory
	// Clock supplies the current time. nil uses the real system clock.
	Clock Clock
}

Config parameterizes a single Sketch (one generation).

type Decay 

type Decay interface {
	// Apply returns the score after dtMillis of idle time. Callers guarantee
	// dtMillis >= 0.
	Apply(score float64, dtMillis int64) float64
}

Decay evolves a score over elapsed idle time. Implementations MUST be monotone toward zero (never increase |score|, never cross zero) and MUST compose across time subdivision: 

Apply(Apply(s, t1), t2) == Apply(s, t1+t2)   (within float64 epsilon)

Composition is what allows lazy evaluation (decaying only on access) and, later, the additive merge law to hold. 

var None Decay = noneDecay{}

None is the identity decay: scores persist until explicitly changed or rotated out. Sketches using None may not set Hi = +Inf (scores could grow without bound).

func Exponential 

func Exponential(lambdaPerSec float64) Decay

Exponential returns a decay of the form score·e^(−λ·Δt) where λ is per second. λ = 0 is a valid no-op decay (distinct from None only in type). This is FAIR's decay.

func Linear 

func Linear(ratePerSec float64) Decay

Linear returns a decay that drains the score toward zero at a constant ratePerSec: max(0, s−r·Δt) for positive scores, min(0, s+r·Δt) for negative. This is the token-bucket refill.

type Hasher 

type Hasher interface {
	Hash64(key []byte) uint64
}

Hasher produces a 64-bit hash of a key. The Sketch derives its L level indexes from this single hash via the Kirsch–Mitzenmacher construction.

type HasherFactory 

type HasherFactory func(seed uint64) Hasher

HasherFactory builds a Hasher bound to a seed. Rotation calls it once per generation with a fresh seed.

func Murmur3 

func Murmur3() HasherFactory

Murmur3 is the default hasher factory: fast, but NOT resistant to an adversary who chooses keys (murmur3 has seed-independent collision families). For attacker-controlled key spaces use SipHash.

The murmur3 64-bit variant takes a uint32 seed; the low 32 bits of the uint64 seed are used. This truncation is harmless because the seed is random.

Caveat on hash strength: the sketch derives all L level indexes from this one 64-bit hash via the Kirsch–Mitzenmacher construction, which amplifies any hash weakness — a single 64-bit collision collides at every level and bypasses min-aggregation shielding entirely. With attacker-controlled keys, prefer SipHash.

func SipHash 

func SipHash() HasherFactory

SipHash is a keyed-PRF hasher factory for adversarial key spaces: an attacker who does not know the key cannot manufacture the collisions that would defeat the Kirsch–Mitzenmacher-amplified level shield (see the caveat on Murmur3). It costs roughly 2x a murmur3 hash. The uint64 seed is expanded into SipHash's 128-bit key via two splitmix64 iterations.

type Result 

type Result struct {
	Aggregate   float64
	LevelScores []float64 // length L
	CellIndexes []uint32  // length L
}

Result is the detailed outcome of a query.

type Rotator 

type Rotator struct {
	// contains filtered or unexported fields
}

Rotator manages N generations of a Sketch under changing seeds. Reads serve from the oldest ("primary") generation; writes apply to all generations so younger ones are warm when promoted. Every Period the primary is dropped, the next generation is promoted, and a fresh generation is appended. This bounds the lifetime of any false positive to Generations x Period.

func NewRotator 

func NewRotator(cfg RotatorConfig) (*Rotator, error)

NewRotator creates a Rotator and starts its background rotation goroutine. Call Close to stop it.

func (*Rotator) Close 

func (r *Rotator) Close()

Close stops the rotation goroutine and releases the ticker. It is idempotent.

func (*Rotator) Query 

func (r *Rotator) Query(key []byte) float64

Query returns the key's aggregate from the primary generation.

func (*Rotator) QueryDetailed 

func (r *Rotator) QueryDetailed(key []byte) Result

QueryDetailed returns the primary generation's detailed query result.

func (*Rotator) Rotations 

func (r *Rotator) Rotations() int64

Rotations returns the number of rotations performed (observability/tests).

func (*Rotator) TryUpdate 

func (r *Rotator) TryUpdate(key []byte, delta, limit float64) bool

TryUpdate decides on the primary generation's aggregate; if admitted, the delta is applied to all generations (warming the younger ones). The decision is atomic within the primary, but the fan-out to younger generations is not cross-generation atomic, matching the warm-write model.

func (*Rotator) Update 

func (r *Rotator) Update(key []byte, delta float64)

Update applies delta to the key in every generation.

func (*Rotator) UpdateAndQuery 

func (r *Rotator) UpdateAndQuery(key []byte, delta float64) float64

UpdateAndQuery applies delta to all generations and returns the primary's post-update aggregate.

type RotatorConfig 

type RotatorConfig struct {
	// Sketch is the per-generation configuration.
	Sketch Config
	// Generations is the number of concurrent generations; must be >= 2.
	Generations uint32
	// Period is the rotation interval; must be > 0.
	Period time.Duration
	// Ticker drives rotation. nil uses a real ticker with Period.
	Ticker Ticker
}

RotatorConfig parameterizes a Rotator.

type Sketch 

type Sketch struct {
	// contains filtered or unexported fields
}

Sketch is one generation: L levels of M cells under a single hash seed. All exported methods are safe for concurrent use.

func New 

func New(cfg Config) (*Sketch, error)

New creates a Sketch with a random seed.

func NewWithSeed 

func NewWithSeed(cfg Config, seed uint64) (*Sketch, error)

NewWithSeed creates a Sketch with a fixed seed. Two sketches built with the same seed, config, clock, and op sequence produce identical observable output.

func (*Sketch) Config 

func (s *Sketch) Config() Config

Config returns the configuration the sketch was built with.

func (*Sketch) Query 

func (s *Sketch) Query(key []byte) float64

Query decays the key's L cells to now and returns the aggregated score.

func (*Sketch) QueryDetailed 

func (s *Sketch) QueryDetailed(key []byte) Result

QueryDetailed decays the key's L cells and returns the aggregate along with per-level scores and cell indexes. Unlike the other operations it allocates its returned slices per call.

func (*Sketch) Seed 

func (s *Sketch) Seed() uint64

Seed returns the hash seed of this sketch.

func (*Sketch) TryUpdate 

func (s *Sketch) TryUpdate(key []byte, delta, limit float64) bool

TryUpdate applies delta only if the post-decay aggregate plus delta stays within limit, returning whether it was applied. It is the atomic conditional-consume for strict quota semantics: unlike Query followed by Update, no concurrent operation on this key can interleave between the check and the apply.

It holds all L of the key's cell locks simultaneously — still deadlock-free because every operation acquires cells in ascending level order — so it costs more lock contention than the optimistic path. Callers that tolerate small over-admission should prefer Query + Update. Whether or not delta is applied, the cells are decayed to now.

func (*Sketch) Update 

func (s *Sketch) Update(key []byte, delta float64)

Update decays the key's L cells to now, then adds delta to each (clamped). delta must be finite; a NaN or Inf delta panics, since one poisoned cell corrupts every key hashing there.

func (*Sketch) UpdateAndQuery 

func (s *Sketch) UpdateAndQuery(key []byte, delta float64) float64

UpdateAndQuery applies delta and returns the post-update aggregate in a single pass over the L cells.

type Ticker 

type Ticker interface {
	C() <-chan time.Time
	Stop()
}

Ticker abstracts a periodic tick so rotation can be driven deterministically in tests.

Source Files

View all Source files

Directories

Path Synopsis
Package grudgetest provides controllable Clock and Ticker fakes for driving grudge (and its consumers, like FAIR and recipe packages) deterministically in tests.
 Package grudgetest provides controllable Clock and Ticker fakes for driving grudge (and its consumers, like FAIR and recipe packages) deterministically in tests.
internal
hash
Package hash provides the concrete 64-bit hashers used by grudge.
 Package hash provides the concrete 64-bit hashers used by grudge.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.