To implement a thread-safe sliding-window rate limiter in Go that protects login endpoints per key, we can use a bucketized counter (fixed number of sub-windows across the window duration). This gives O(1) update and O(B) check cost (B = number of buckets), bounded memory per key, and avoids storing timestamps for every request (unlike sliding logs). We'll keep a per-key struct with its own mutex for concurrency, store keys in a sync.Map, and include a simple TTL-based cleanup for idle keys.go
package limiter
import (
"sync"
"sync/atomic"
"time"
)
// Limiter limits events per key over a sliding window.
type Limiter struct {
max int
window time.Duration
bucketDur time.Duration
bucketN int
clockNow func() time.Time
entries sync.Map // map[string]*entry
cleanupInt time.Duration
closed int32
}
type entry struct {
mu sync.Mutex
buckets []int
start time.Time // start time of buckets[0]
lastSeen time.Time
total int
}
// NewLimiter creates a limiter with max events per window.
// bucketDur is the resolution (e.g., 1s). If bucketDur==0 we use 1s.
func NewLimiter(max int, window time.Duration, bucketDur time.Duration) *Limiter {
if bucketDur <= 0 {
bucketDur = time.Second
}
bn := int(window / bucketDur)
if bn < 1 {
bn = 1
}
l := &Limiter{
max: max,
window: window,
bucketDur: bucketDur,
bucketN: bn,
clockNow: time.Now,
cleanupInt: window * 2,
}
// start background cleaner
go l.cleaner()
return l
}
// Allow returns true and records an event if key is within limit.
func (l *Limiter) Allow(key string) bool {
now := l.clockNow()
v, _ := l.entries.LoadOrStore(key, &entry{
buckets: make([]int, l.bucketN),
start: now.Truncate(l.bucketDur),
lastSeen: now,
})
e := v.(*entry)
e.mu.Lock()
defer e.mu.Unlock()
// Advance buckets to current time
elapsed := now.Sub(e.start)
shift := int(elapsed / l.bucketDur)
if shift >= l.bucketN {
// window fully advanced: reset
for i := range e.buckets {
e.buckets[i] = 0
}
e.total = 0
e.start = now.Truncate(l.bucketDur)
} else if shift > 0 {
// rotate buckets
for i := 0; i < shift; i++ {
idx := (i + int((e.start.UnixNano()/int64(l.bucketDur))) ) % l.bucketN // placeholder idx calc below
// simpler rotation: shift array left by shift
}
// implement rotation more simply:
newB := make([]int, l.bucketN)
for i := 0; i < l.bucketN; i++ {
src := (i + shift) % l.bucketN
newB[i] = e.buckets[src]
}
e.buckets = newB
// zero out newly exposed buckets (the most recent 'shift' buckets)
for i := l.bucketN - shift; i < l.bucketN; i++ {
e.total -= e.buckets[i]
e.buckets[i] = 0
}
e.start = e.start.Add(time.Duration(shift) * l.bucketDur)
// recompute total (safe)
sum := 0
for _, c := range e.buckets {
sum += c
}
e.total = sum
}
// find current bucket index (most recent bucket is last)
curIdx := l.bucketN - 1
// check limit
if e.total >= l.max {
e.lastSeen = now
return false
}
// record event
e.buckets[curIdx]++
e.total++
e.lastSeen = now
return true
}
// cleaner removes entries not seen for cleanupInt to reduce memory.
func (l *Limiter) cleaner() {
t := time.NewTicker(l.cleanupInt)
defer t.Stop()
for atomic.LoadInt32(&l.closed) == 0 {
<-t.C
now := l.clockNow()
l.entries.Range(func(k, v interface{}) bool {
e := v.(*entry)
e.mu.Lock()
age := now.Sub(e.lastSeen)
e.mu.Unlock()
if age > l.cleanupInt {
l.entries.Delete(k)
}
return true
})
}
}
