Approach: implement a thread-safe token-bucket in Go using a mutex and refill-on-access (calculate tokens added since last timestamp). This avoids a background goroutine and is efficient for local usage.go
package ratelimit
import (
"sync"
"time"
)
// TokenBucket is a thread-safe token bucket rate limiter.
type TokenBucket struct {
rate float64 // tokens per second
capacity float64 // max tokens (burst)
tokens float64 // current tokens
last time.Time // last refill timestamp
mu sync.Mutex
}
// NewTokenBucket creates a new TokenBucket.
func NewTokenBucket(tokensPerSecond float64, burst float64) *TokenBucket {
if tokensPerSecond <= 0 {
tokensPerSecond = 1
}
if burst <= 0 {
burst = tokensPerSecond
}
return &TokenBucket{
rate: tokensPerSecond,
capacity: burst,
tokens: burst,
last: time.Now(),
}
}
// AllowRequest attempts to consume one token. Returns true if allowed.
func (tb *TokenBucket) AllowRequest() bool {
tb.mu.Lock()
defer tb.mu.Unlock()
now := time.Now()
elapsed := now.Sub(tb.last).Seconds()
// Refill tokens based on elapsed time
tb.tokens += elapsed * tb.rate
if tb.tokens > tb.capacity {
tb.tokens = tb.capacity
}
tb.last = now
if tb.tokens >= 1.0 {
tb.tokens -= 1.0
return true
}
return false
}
Key points:- Refill-on-access computes tokens = min(capacity, tokens + elapsed*rate). This is O(1) and avoids goroutines/tickers.- Mutex ensures concurrency safety across goroutines.- Burst capacity allows short spikes up to capacity.Limitations when scaling to multiple instances:- Local limiter only protects a single process. With N instances, aggregate allowed rate = N * rate, so global limits are not enforced.- Clock skew between machines can affect refill calculations.- Local state can't be shared; clients could route unevenly causing hot spots.Distributed enforcement options:- Centralized store: use Redis with an atomic Lua script implementing token-bucket semantics (refill based on stored timestamp and tokens). This enforces a single global limiter and is fast (single round-trip + script).- Redis leaky bucket using INCR with TTL or sorted sets for more complex windows.- Token distribution: run a centralized token server (gRPC/HTTP) that hands out tokens; instances ask the server (adds network latency, availability concerns).- Distributed quota via consistent hashing: partition keys so each instance enforces a shard of users.- Hybrid: local token buckets with periodic sync to a central counter for coarse-grained global enforcement (reduces load on central store but is eventually consistent).Trade-offs:- Centralized stores add network latency and become a potential bottleneck or SPOF (use clustering/replication).- Atomic Redis/Lua approach is a common balance: correctness, high throughput, and low complexity.- Consider client-side caching, backoff strategies, and exponential retry to handle transient denials.Edge cases:- High-precision rates: use floats carefully; use integers with nanoseconds if needed.- Burst > rate: long inactivity fills up to capacity.- Persisting state across restarts requires external storage if needed.