go-sharded-token-bucket-ratelimit
The limiter is sharded (16 shards by default, configurable), each shard owning a mutex, a map[string]*bucket, and a container/list LRU. Refill is computed lazily inside refill() on every access — no background goroutines, no timers. Two properties are load-bearing:
time.Now by default, which carries the monotonic component, so it can never actually go backward). Negative elapsed time is clamped to zero and the bucket's last timestamp is only advanced when real time passes, so a wall-clock jump backwards grants nothing. This mirrors monotonic-clock semantics even under an adversarial injected clock.tokens + elapsed·rate and then hard-capped at burst on every access. A full bucket at t0 stays exactly burst at t0+1s (never burst+ε, never drifting above the cap), and grants are exactly min(burst, tokens + elapsed·rate).~/ratelimit/limiter.go:
package ratelimit
import (
"container/list"
"sync"
"time"
)
const (
defaultShards = 16
defaultCapacity = 1024
)
type Limiter struct {
rate float64
burst float64
now func() time.Time
shardCount int
capacity int
shards []*shard
}
type Option func(*Limiter)
func WithClock(now func() time.Time) Option { return func(l *Limiter) { l.now = now } }
func WithShards(n int) Option { return func(l *Limiter) { if n > 0 { l.shardCount = n } } }
func WithCapacity(n int) Option { return func(l *Limiter) { if n > 0 { l.capacity = n } } }
func New(rate float64, burst int, opts ...Option) *Limiter {
if rate < 0 || burst < 0 {
panic("ratelimit: rate and burst must be non-negative")
}
l := &Limiter{rate: rate, burst: float64(burst), now: time.Now,
shardCount: defaultShards, capacity: defaultCapacity}
for _, o := range opts {
o(l)
}
l.shards = make([]*shard, l.shardCount)
perShard := (l.capacity + l.shardCount - 1) / l.shardCount // ceil
for i := range l.shards {
l.shards[i] = &shard{rate: l.rate, burst: l.burst,
keys: make(map[string]*bucket), lru: list.New(), capacity: perShard}
}
return l
}
type shard struct {
mu sync.Mutex
rate float64
burst float64
keys map[string]*bucket
lru *list.List // front = most recently used
capacity int
}
type bucket struct {
tokens float64
last time.Time
elem *list.Element
}
// refill applies refill due between b.last and now. Negative elapsed (clock
// moved backwards) is clamped to zero: no tokens for time that did not pass.
func (b *bucket) refill(now time.Time, rate, burst float64) float64 {
if elapsed := now.Sub(b.last); elapsed > 0 {
b.tokens += rate * elapsed.Seconds()
if b.tokens > burst {
b.tokens = burst // hard cap: full bucket stays exactly full, no drift
}
b.last = now
}
return b.tokens
}
func (l *Limiter) Allow(key string) bool { return l.AllowN(key, 1) }
func (l *Limiter) AllowN(key string, n int) bool {
if n <= 0 {
return true
}
s := l.shardFor(key)
s.mu.Lock()
defer s.mu.Unlock()
b := s.touch(key, l.now())
if b.tokens >= float64(n) {
b.tokens -= float64(n)
return true
}
return false
}
func (l *Limiter) Tokens(key string) float64 {
s := l.shardFor(key)
s.mu.Lock()
defer s.mu.Unlock()
return s.touch(key, l.now()).tokens
}
func (l *Limiter) Reset(key string) {
s := l.shardFor(key)
s.mu.Lock()
defer s.mu.Unlock()
if b, ok := s.keys[key]; ok {
s.lru.Remove(b.elem)
delete(s.keys, key)
}
}
func (l *Limiter) Size() int {
total := 0
for _, s := range l.shards {
s.mu.Lock()
total += len(s.keys)
s.mu.Unlock()
}
return total
}
// shardFor maps a key to a shard via FNV-1a (allocation-free).
func (l *Limiter) shardFor(key string) *shard {
const (offset64 = 14695981039346656037; prime64 = 1099511628211)
var h uint64 = offset64
for i := 0; i < len(key); i++ {
h ^= uint64(key[i])
h *= prime64
}
return l.shards[h%uint64(len(l.shards))]
}
// touch returns the bucket for key, creating it full if absent, applying any
// refill, and refreshing LRU position. Callers must hold s.mu.
func (s *shard) touch(key string, now time.Time) *bucket {
if b, ok := s.keys[key]; ok {
b.refill(now, s.rate, s.burst)
s.lru.MoveToFront(b.elem)
return b
}
b := &bucket{tokens: s.burst, last: now}
b.elem = s.lru.PushFront(key)
s.keys[key] = b
if s.lru.Len() > s.capacity { // bound memory: evict least recently used
if back := s.lru.Back(); back != nil {
evicted := back.Value.(string)
s.lru.Remove(back)
delete(s.keys, evicted)
}
}
return b
}
Ran in `~/ratelimit` (Go 1.26.0, linux/amd64): `go vet ./...` clean; `go test -race` passes 9 test functions, repeated with `-count=3/5` under `GOMAXPROCS=1` and `=8`. | Test | Verifies | |---|---| | `TestBasicAllowDeny` | Burst exhaustion then denial; frozen clock ⇒ exactly 0 tokens | | `TestRefill` | 100ms at 10 tok/s refills exactly 1 token | | `TestExactFullBurstAfterOneSecond` | Full bucket at t0 grants full burst at t0+1s; refill is exact (`0 + 1s·rate == 10`); long idle caps at exactly burst, never above | | `TestFractionalRateNoDrift` | 10,000 × 100µs steps at rate 0.7: tokens stay ≤ burst and converge to exactly 0.7 ± 1e-12 | | `TestClockBackwardsNoOverGrant` | Clock jumps −30s: no refill, no over-grant; no refill until real time passes the last observed timestamp; then refill resumes and caps | | `TestLRUEvictionBoundsMemory` | With `WithShards(1), WithCapacity(3)`: exact eviction order (b evicted after touching a); `Size()` never exceeds cap | | `TestReset` | Reset forgets state; next access is a fresh full bucket | | `TestConcurrentHammersOverlappingKeys` | 100 goroutines × 500 iters over 40 shared keys + private keys (16 shards, cap 256): `-race` clean; `Size()=256` bound held; 11,469 grants / 38,531 denials | | `TestConcurrentSingleKeyNoOverGrant` | 100 goroutines on one hot key: 278 grants in 269ms at 1000 tok/s vs. ceiling 280 (burst 10 + refill) — serialized accounting, no double-granting | Backwards-clock trace (implementation, not test): allow×5 at t0 → empty; advance 2s → refill 20 capped to 5, `last=t0+2s`; clock set to `t0−28s` → `elapsed<0` clamped → still 5, `last` unchanged; consume 1 → 4; time still behind `last` → still 4; only once real time passes `t0+2s` does refill resume (capped at 5). No token is ever granted for elapsed time that did not occur.
{"model": "deepseek-v4-flash", "problem_class": "go-sharded-token-bucket-ratelimit", "result": "passed", "tests": 9}The limiter is sharded (16 shards by default, configurable), each shard owning a mutex, a map[string]*bucket, and a container/list LRU. Refill is computed lazily inside refill() on every access — no background goroutines, no timers. Two properties are load-bearing:
time.Now by default, which carries the monotonic component, so it can never actually go backward). Negative elapsed time is clamped to zero and the bucket's last timestamp is only advanced when real time passes, so a wall-clock jump backwards grants nothing. This mirrors monotonic-clock semantics even under an adversarial injected clock.tokens + elapsed·rate and then hard-capped at burst on every access. A full bucket at t0 stays exactly burst at t0+1s (never burst+ε, never drifting above the cap), and grants are exactly min(burst, tokens + elapsed·rate).~/ratelimit/limiter.go:
package ratelimit
import (
"container/list"
"sync"
"time"
)
const (
defaultShards = 16
defaultCapacity = 1024
)
type Limiter struct {
rate float64
burst float64
now func() time.Time
shardCount int
capacity int
shards []*shard
}
type Option func(*Limiter)
func WithClock(now func() time.Time) Option { return func(l *Limiter) { l.now = now } }
func WithShards(n int) Option { return func(l *Limiter) { if n > 0 { l.shardCount = n } } }
func WithCapacity(n int) Option { return func(l *Limiter) { if n > 0 { l.capacity = n } } }
func New(rate float64, burst int, opts ...Option) *Limiter {
if rate < 0 || burst < 0 {
panic("ratelimit: rate and burst must be non-negative")
}
l := &Limiter{rate: rate, burst: float64(burst), now: time.Now,
shardCount: defaultShards, capacity: defaultCapacity}
for _, o := range opts {
o(l)
}
l.shards = make([]*shard, l.shardCount)
perShard := (l.capacity + l.shardCount - 1) / l.shardCount // ceil
for i := range l.shards {
l.shards[i] = &shard{rate: l.rate, burst: l.burst,
keys: make(map[string]*bucket), lru: list.New(), capacity: perShard}
}
return l
}
type shard struct {
mu sync.Mutex
rate float64
burst float64
keys map[string]*bucket
lru *list.List // front = most recently used
capacity int
}
type bucket struct {
tokens float64
last time.Time
elem *list.Element
}
// refill applies refill due between b.last and now. Negative elapsed (clock
// moved backwards) is clamped to zero: no tokens for time that did not pass.
func (b *bucket) refill(now time.Time, rate, burst float64) float64 {
if elapsed := now.Sub(b.last); elapsed > 0 {
b.tokens += rate * elapsed.Seconds()
if b.tokens > burst {
b.tokens = burst // hard cap: full bucket stays exactly full, no drift
}
b.last = now
}
return b.tokens
}
func (l *Limiter) Allow(key string) bool { return l.AllowN(key, 1) }
func (l *Limiter) AllowN(key string, n int) bool {
if n <= 0 {
return true
}
s := l.shardFor(key)
s.mu.Lock()
defer s.mu.Unlock()
b := s.touch(key, l.now())
if b.tokens >= float64(n) {
b.tokens -= float64(n)
return true
}
return false
}
func (l *Limiter) Tokens(key string) float64 {
s := l.shardFor(key)
s.mu.Lock()
defer s.mu.Unlock()
return s.touch(key, l.now()).tokens
}
func (l *Limiter) Reset(key string) {
s := l.shardFor(key)
s.mu.Lock()
defer s.mu.Unlock()
if b, ok := s.keys[key]; ok {
s.lru.Remove(b.elem)
delete(s.keys, key)
}
}
func (l *Limiter) Size() int {
total := 0
for _, s := range l.shards {
s.mu.Lock()
total += len(s.keys)
s.mu.Unlock()
}
return total
}
// shardFor maps a key to a shard via FNV-1a (allocation-free).
func (l *Limiter) shardFor(key string) *shard {
const (offset64 = 14695981039346656037; prime64 = 1099511628211)
var h uint64 = offset64
for i := 0; i < len(key); i++ {
h ^= uint64(key[i])
h *= prime64
}
return l.shards[h%uint64(len(l.shards))]
}
// touch returns the bucket for key, creating it full if absent, applying any
// refill, and refreshing LRU position. Callers must hold s.mu.
func (s *shard) touch(key string, now time.Time) *bucket {
if b, ok := s.keys[key]; ok {
b.refill(now, s.rate, s.burst)
s.lru.MoveToFront(b.elem)
return b
}
b := &bucket{tokens: s.burst, last: now}
b.elem = s.lru.PushFront(key)
s.keys[key] = b
if s.lru.Len() > s.capacity { // bound memory: evict least recently used
if back := s.lru.Back(); back != nil {
evicted := back.Value.(string)
s.lru.Remove(back)
delete(s.keys, evicted)
}
}
return b
}
Ran in `~/ratelimit` (Go 1.26.0, linux/amd64): `go vet ./...` clean; `go test -race` passes 9 test functions, repeated with `-count=3/5` under `GOMAXPROCS=1` and `=8`. | Test | Verifies | |---|---| | `TestBasicAllowDeny` | Burst exhaustion then denial; frozen clock ⇒ exactly 0 tokens | | `TestRefill` | 100ms at 10 tok/s refills exactly 1 token | | `TestExactFullBurstAfterOneSecond` | Full bucket at t0 grants full burst at t0+1s; refill is exact (`0 + 1s·rate == 10`); long idle caps at exactly burst, never above | | `TestFractionalRateNoDrift` | 10,000 × 100µs steps at rate 0.7: tokens stay ≤ burst and converge to exactly 0.7 ± 1e-12 | | `TestClockBackwardsNoOverGrant` | Clock jumps −30s: no refill, no over-grant; no refill until real time passes the last observed timestamp; then refill resumes and caps | | `TestLRUEvictionBoundsMemory` | With `WithShards(1), WithCapacity(3)`: exact eviction order (b evicted after touching a); `Size()` never exceeds cap | | `TestReset` | Reset forgets state; next access is a fresh full bucket | | `TestConcurrentHammersOverlappingKeys` | 100 goroutines × 500 iters over 40 shared keys + private keys (16 shards, cap 256): `-race` clean; `Size()=256` bound held; 11,469 grants / 38,531 denials | | `TestConcurrentSingleKeyNoOverGrant` | 100 goroutines on one hot key: 278 grants in 269ms at 1000 tok/s vs. ceiling 280 (burst 10 + refill) — serialized accounting, no double-granting | Backwards-clock trace (implementation, not test): allow×5 at t0 → empty; advance 2s → refill 20 capped to 5, `last=t0+2s`; clock set to `t0−28s` → `elapsed<0` clamped → still 5, `last` unchanged; consume 1 → 4; time still behind `last` → still 4; only once real time passes `t0+2s` does refill resume (capped at 5). No token is ever granted for elapsed time that did not occur.
{"model": "deepseek-v4-flash", "problem_class": "go-sharded-token-bucket-ratelimit", "result": "passed", "tests": 9}