Rate Limiting, Throttling and Quota Management Questions

I'll implement a sharded in-memory rate limiter in Go providing both token-bucket and leaky-bucket behaviors, per-key limits, and a global fallback. Sharding reduces lock contention under high concurrency.

Approach:

• Use N shards each with a mutex and map[key]*bucket to limit lock scope.
• Each bucket stores last timestamp and algorithm state; both algorithms expose Allow(now) bool.
• Global fallback bucket used when a key has no explicit config.
• Time is passed as time.Now() to allow testing.

package ratelimit

import (
	"sync"
	"time"
)

// Algorithm type
type Algo int
const (
	TokenBucket Algo = iota
	LeakyBucket
)

type config struct {
	ratePerSec float64
	capacity   float64
	algo       Algo
}

// Token bucket and leaky bucket implement this:
type bucket interface {
	allow(now time.Time) bool
}

// TokenBucket implementation
type tokenBucket struct {
	rate     float64 // tokens per second
	capacity float64
	tokens   float64
	last     time.Time
	sync.Mutex
}

func newTokenBucket(rate, capacity float64, now time.Time) *tokenBucket {
	return &tokenBucket{rate: rate, capacity: capacity, tokens: capacity, last: now}
}

func (b *tokenBucket) allow(now time.Time) bool {
	b.Lock()
	defer b.Unlock()
	elapsed := now.Sub(b.last).Seconds()
	if elapsed > 0 {
		b.tokens += elapsed * b.rate
		if b.tokens > b.capacity {
			b.tokens = b.capacity
		}
		b.last = now
	}
	if b.tokens >= 1 {
		b.tokens -= 1
		return true
	}
	return false
}

// LeakyBucket implementation (credit drains at constant rate)
type leakyBucket struct {
	rate     float64 // outflow per second (same semantics)
	capacity float64
	level    float64 // current queued tokens (0..capacity)
	last     time.Time
	sync.Mutex
}

func newLeakyBucket(rate, capacity float64, now time.Time) *leakyBucket {
	return &leakyBucket{rate: rate, capacity: capacity, level: 0, last: now}
}

func (b *leakyBucket) allow(now time.Time) bool {
	b.Lock()
	defer b.Unlock()
	elapsed := now.Sub(b.last).Seconds()
	if elapsed > 0 {
		// leak out
		b.level -= elapsed * b.rate
		if b.level < 0 {
			b.level = 0
		}
		b.last = now
	}
	// If capacity allows, accept and add one unit
	if b.level+1 <= b.capacity {
		b.level += 1
		return true
	}
	return false
}

// Sharded rate limiter
type shard struct {
	sync.Mutex
	m map[string]bucket
}

type RateLimiter struct {
	shards    []shard
	nshards   int
	globalCfg config
	globalBkt bucket
	cfgs      map[string]config
	cfgLock   sync.RWMutex
}

func NewRateLimiter(nshards int, global config) *RateLimiter {
	if nshards <= 0 { nshards = 16 }
	rs := make([]shard, nshards)
	for i := range rs { rs[i].m = make(map[string]bucket) }
	rl := &RateLimiter{
		shards:  rs,
		nshards: nshards,
		globalCfg: global,
		cfgs:    make(map[string]config),
	}
	now := time.Now()
	rl.globalBkt = makeBucketFromConfig(global, now)
	return rl
}

func (r *RateLimiter) shardFor(key string) *shard {
	h := fnv32(key)
	return &r.shards[int(h)%r.nshards]
}

// Register per-key config (optional)
func (r *RateLimiter) SetKeyConfig(key string, c config) {
	r.cfgLock.Lock()
	r.cfgs[key] = c
	r.cfgLock.Unlock()
}

// Allow checks and consumes a token for key. Uses per-key config if present else global.
func (r *RateLimiter) Allow(key string) bool {
	now := time.Now()
	// find or create bucket
	sh := r.shardFor(key)
	sh.Lock()
	b, ok := sh.m[key]
	if !ok {
		// pick config
		r.cfgLock.RLock()
		c, found := r.cfgs[key]
		r.cfgLock.RUnlock()
		if !found {
			// use global bucket (shared)
			sh.Unlock()
			return r.globalBkt.allow(now)
		}
		b = makeBucketFromConfig(c, now)
		sh.m[key] = b
	}
	sh.Unlock()
	return b.allow(now)
}

// helper to instantiate bucket
func makeBucketFromConfig(c config, now time.Time) bucket {
	if c.algo == LeakyBucket {
		return newLeakyBucket(c.ratePerSec, c.capacity, now)
	}
	return newTokenBucket(c.ratePerSec, c.capacity, now)
}

// simple FNV-1a 32bit
func fnv32(s string) uint32 {
	const (
		prime uint32 = 16777619
		offset uint32 = 2166136261
	)
	var h uint32 = offset
	for i := 0; i < len(s); i++ {
		h ^= uint32(s[i])
		h *= prime
	}
	return h
}

Key points and trade-offs:

• Token bucket allows bursts up to capacity and refills continuously — good for rate limits that allow occasional spikes.
• Leaky bucket smooths bursts by queuing and draining at constant rate — useful to enforce steady output and protect downstream.
• Sharding minimizes contention; each per-key bucket lock is fine-grained. Global fallback is a shared bucket — a hotspot; consider sharding global by key prefix or using token counts per second if it becomes bottleneck.
  Complexity: Allow is O(1) amortized. Memory grows with active keys; evictions/TTL and background cleanup can be added. Consider using lock-free atomics for extreme low-latency scenarios or RWMutex for reads if read-heavy.

Approach: use a token-bucket that stores current tokens, capacity, and refill rate (tokens/sec). On each allow_request() we refill based on elapsed time, cap at capacity, then consume a token if available. Use mutex for concurrency. For global limits across instances, persist/coordinate token state in Redis (Lua script for atomic refill+consume) or use a centralized proxy/load‑balancer (Envoy/NGINX) or token server.

package ratelimit

import (
	"sync"
	"time"
)

// TokenBucket is an in-memory token bucket.
type TokenBucket struct {
	mu        sync.Mutex
	capacity  float64       // max tokens
	tokens    float64       // current tokens (fractional allowed)
	rate      float64       // tokens per second
	lastCheck time.Time
}

func NewTokenBucket(capacity, rate float64) *TokenBucket {
	return &TokenBucket{
		capacity:  capacity,
		tokens:    capacity,
		rate:      rate,
		lastCheck: time.Now(),
	}
}

// allowRequest returns true if a token could be consumed.
func (tb *TokenBucket) AllowRequest() bool {
	tb.mu.Lock()
	defer tb.mu.Unlock()

	now := time.Now()
	elapsed := now.Sub(tb.lastCheck).Seconds()
	tb.lastCheck = now

	// Refill
	tb.tokens += elapsed * tb.rate
	if tb.tokens > tb.capacity {
		tb.tokens = tb.capacity
	}

	if tb.tokens >= 1.0 {
		tb.tokens -= 1.0
		return true
	}
	return false
}

Key points:

• Use float tokens to allow fractional refill and smoothness.
• Mutex prevents races; for very high QPS consider sharding buckets or using atomic ops.
• Time complexity: O(1) per request; space: O(1) per bucket.

Distributed/global coordination options:

• Redis + Lua script: atomically compute refill based on stored last timestamp and tokens, then decrement if possible. Scales well and is single source of truth.
• Use a centralized token server or sidecar per service that requests tokens from a central allocator.
• Offload to API gateway/proxy (Envoy, NGINX) which provides built-in distributed rate limiting.
• If strict per-user limits at extreme scale, use consistent hashing to partition keys across a Redis cluster to avoid a single hot key.

Edge cases:

• Clock skew across nodes: use monotonic clocks where possible; in Redis approach, server time is authoritative.
• Burst credit persistence: if you want long-term carryover, persist tokens+timestamp; otherwise resets are acceptable.
• Avoid thundering herd by smoothing refill or using jitter when rejecting/retrying.

Requirements & goals:

• Protect backend from traffic spikes while preserving fair access for users.
• Per-user (or per-API-key) and global limits, support bursts, predictable degradation, clear client signals, safe rollout with monitoring and rollback.

High-level design:

• Edge layer (API gateway / CDN) enforces rate limits. Gateway consults a fast in-memory store (Redis or in-process token bucket) and a centralized policy service for dynamic rules. Downstream services assume limited, smoothed traffic.

Components:

1. Policy store: central store of limits (per-user, per-plan, global) with versioning.
2. Enforcement at edge:
   • Local cache of policies for low latency.
   • Counters stored in Redis (sharded by key) with TTLs for sliding-window or token-bucket state.
3. Metrics/monitoring: per-key/throttle metrics, error rates, latency, backend saturation metrics; alerting on abnormal reject rates or downstream CPU/queue rise.
4. Dashboard & audit logs for impacted keys.

Rate-limit model & burst handling:

• Use token-bucket per user: capacity = burst allowance, refill rate = steady allowed rate. Token-bucket supports bursts up to bucket size then enforces steady rate.
• Global limiter: leaky-bucket/queue-like smoothing or aggregate token-bucket to cap total throughput.
• Combine: per-user token-bucket + global token-bucket. If global exhausted, return prioritized or degraded responses.

Token-bucket vs Leaky-bucket trade-offs:

• Token-bucket: flexible bursts, easy per-key state, good UX. Slightly complex to synchronize across distributed edge nodes (use Redis for global counters).
• Leaky-bucket: enforces smooth output, simpler for global smoothing, but less accommodating to legitimate bursts.
• Recommendation: token-bucket per-user + leaky-bucket/aggregate smoothing at global level.

Client signaling:

• Use standard RFC 6585/429 with headers:
  • Retry-After: seconds when appropriate
  • X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset (per-user)
  • X-Global-RateLimit-Remaining, X-Global-RateLimit-Reset (optional)
• Provide informative error body JSON with link to docs and plan-specific limits.

Rollout and monitoring plan:

1. Start with conservative non-blocking mode ("soft-limit" or 429 but also accept) and log all events for 1–2 weeks.
2. Run canary: enable enforcement for <1% of traffic or low-risk tenants; compare errors and support tickets.
3. Gradually increase enforcement (5% → 25% → 100%) with automated health checks (backend 5xx, latency, SLO burn rate).
4. Provide customer communication: docs, dashboard, per-customer telemetry, email for high-volume keys nearing limits.
5. Autoscaling & emergency overrides: when limits trigger false positives, allow temporary overrides and dynamic rule adjustments.

Monitoring & SLOs:

• Track reject rate, user impact, support tickets, backend queue depth, CPU/memory.
• Alert if rejects spike without corresponding backend protection benefit (e.g., backend healthy but many 429s).
• Periodic review: adjust refill rates/burst sizes based on observed legitimate traffic patterns.

Edge cases & best practices:

• Distinguish read vs write endpoints (tighter limits on expensive ops).
• Grace period for new keys; allow warm-up bursts.
• Client-identification: prefer API keys over IP; fallback to IP-based limits to curb anonymous abuse.
• Synchronization: use local token caches with Redis fallback to reduce latency and avoid thundering herd.

This design balances availability, fairness, and UX while enabling safe rollout and observability.