Rate Limiter Algorithms: Token Bucket vs Sliding Window

Picture an authentication service at 2 AM: 50,000 login attempts in 60 seconds from 2,000 rotating IP addresses. Credential stuffing — an attacker replaying username/password pairs leaked in an earlier breach. With no rate limiting, the database absorbs the full load, response times climb from tens of milliseconds to seconds, and legitimate users time out.

The obvious first limiter fails: a fixed-window counter at 100 requests per minute per IP. Spread across 2,000 IPs, the attack needs only 25 attempts per IP per minute. The obvious second attempt — per-account limits plus tight per-IP limits on unauthenticated endpoints — cuts the attack's throughput but also throttles enterprise customers behind NAT sharing a single IP.

Rate limiting is three problems: algorithm choice, key selection, and distributed coordination. Get any wrong and you block legitimate traffic or let attackers through. Below: the five algorithms with exact math, production code for each, the key-selection trap that breaks real deployments, and how to keep your rate limiter alive when Redis fails.

The Quick Start

Algorithm 1: Token Bucket

The token bucket^⁠[2] refills at a fixed rate and allows clients to burst up to the bucket capacity. Each request costs one token. A client idle for 30 seconds can immediately spend 30 seconds' worth of tokens (capped at capacity), then settles into the sustained rate. This is the most permissive algorithm — clients with legitimate bursts (mobile apps waking up, batch processors, connection-pooled clients) can absorb their spikes without hitting the limit.

The mental model: imagine a bucket that tokens drip into at a constant rate until it is full. Every request removes one token. Empty bucket = request rejected.

graph TD
    Req["Incoming Request"] --> Refill["Refill tokens<br/>elapsed × rate"]
    Refill --> Check{"tokens ≥ 1?"}
    Check -->|Yes| Decr["Decrement token"]
    Decr --> Allow["✓ Allow request"]
    Check -->|No| Reject["✗ Reject<br/>429 + Retry-After"]

type TokenBucket struct {
    tokens     float64
    capacity   float64
    refillRate float64 // tokens per second
    lastRefill time.Time
    mu         sync.Mutex
}
 
func NewTokenBucket(capacity, refillRate float64) *TokenBucket {
    return &TokenBucket{
        tokens:     capacity,
        capacity:   capacity,
        refillRate: refillRate,
        lastRefill: time.Now(),
    }
}
 
func (tb *TokenBucket) Allow(n float64) (bool, time.Duration) {
    tb.mu.Lock()
    defer tb.mu.Unlock()
 
    now := time.Now()
    elapsed := now.Sub(tb.lastRefill).Seconds()
    tb.tokens = min(tb.capacity, tb.tokens+elapsed*tb.refillRate)
    tb.lastRefill = now
 
    if tb.tokens >= n {
        tb.tokens -= n
        return true, 0
    }
 
    // Time until n tokens are available. Scale before converting:
    // time.Duration(needed/tb.refillRate) truncates a float64 like 0.1 to
    // 0s. Round up to whole seconds when writing a Retry-After header,
    // which takes integer seconds.
    needed := n - tb.tokens
    return false, time.Duration(needed / tb.refillRate * float64(time.Second))
}

Key math: A bucket with capacity 100 and refill rate 10/s allows a burst of 100 requests instantly, then sustains 10 req/s. That shape — burst tolerance plus a steady sustained rate — absorbs client bursts (a mobile app catching up after being offline, a batch job flushing a queue) without penalizing well-behaved traffic. Stripe described its API rate limiter as a token bucket^⁠[1], and AWS API Gateway's throttling "rate" and "burst" settings are the refill rate and bucket capacity^⁠[2]. The key insight: set capacity based on the burst you'll tolerate, not the sustained rate. A 100ms spike of 50 requests? Set capacity to 50. A 1-second spike? Set capacity to your req/s rate. This algorithm wins because real traffic is bursty, and token bucket acknowledges that instead of punishing it.

Algorithm 2: Leaky Bucket

The leaky bucket queues requests and drains them at a constant rate. Unlike token bucket, bursts are delayed (queued), not rejected — until the queue fills, and then new requests are rejected. Use it only when the downstream needs a smooth rate rather than a capped average: an SMS or email provider that enforces a per-sender send rate, a partner API with a hard QPS contract. For most APIs, the queueing latency it forces on callers is overly restrictive.

type LeakyBucket struct {
    queue      chan func()
    ratePerSec int
    stop       chan struct{}
}
 
func NewLeakyBucket(capacity, ratePerSec int) (*LeakyBucket, error) {
    if capacity <= 0 || ratePerSec <= 0 || ratePerSec > int(time.Second) {
        return nil, fmt.Errorf("leaky bucket: need capacity > 0 and 0 < ratePerSec <= 1e9, got %d, %d", capacity, ratePerSec)
    }
    lb := &LeakyBucket{
        queue:      make(chan func(), capacity),
        ratePerSec: ratePerSec,
        stop:       make(chan struct{}),
    }
    go lb.drain()
    return lb, nil
}
 
// drain runs one queued job every 1/ratePerSec seconds — the constant "leak".
// A burst waits in the queue instead of reaching the downstream all at once.
// Jobs run on this goroutine, so a job slower than one tick slows the leak.
func (lb *LeakyBucket) drain() {
    ticker := time.NewTicker(time.Second / time.Duration(lb.ratePerSec))
    defer ticker.Stop()
 
    for {
        select {
        case <-ticker.C:
            select {
            case job := <-lb.queue:
                job()
            default:
                // Nothing queued this tick; skip.
            }
        case <-lb.stop:
            return
        }
    }
}
 
// Submit queues job to run at the leak rate. false means the bucket is full
// (or closed): reject the request, e.g. with a 429.
func (lb *LeakyBucket) Submit(job func()) bool {
    select {
    case <-lb.stop:
        return false
    default:
    }
    select {
    case lb.queue <- job:
        return true
    default:
        return false // Queue full
    }
}
 
// Close stops the leak. Jobs still queued are dropped, not run.
func (lb *LeakyBucket) Close() { close(lb.stop) }

Algorithm 3: Fixed Window Counter

Count requests in a fixed time window. When the window resets, the counter resets. Simplest to implement: one integer per key. But it has a sharp edge case called the boundary spike: if a client sends all their requests at the window boundary, they can exceed the intended rate.

type FixedWindow struct {
    limit      int
    window     time.Duration
    counter    int
    windowEnd  time.Time
    mu         sync.Mutex
}
 
func NewFixedWindow(limit int, window time.Duration) *FixedWindow {
    return &FixedWindow{
        limit:     limit,
        window:    window,
        windowEnd: time.Now().Add(window),
    }
}
 
func (fw *FixedWindow) Allow() bool {
    fw.mu.Lock()
    defer fw.mu.Unlock()
 
    now := time.Now()
    if now.After(fw.windowEnd) {
        fw.counter = 0
        fw.windowEnd = now.Add(fw.window)
    }
 
    if fw.counter < fw.limit {
        fw.counter++
        return true
    }
    return false
}

The spike problem: With a 100 req/min limit in a 60-second window, a client can send 100 requests at second 59 (last second of window), then 100 more at second 60 (first second of new window), effectively doubling the rate to 200 req/min for that 2-second window. This spike can overload backends that expect steady traffic. Acceptable for non-critical internal APIs; risky for user-facing endpoints or auth/payment flows where you need stronger guarantees.

Algorithm 4: Sliding Window Log

Store the exact timestamp of each request in a sorted set (Redis ZSET^⁠[3]). To check if a request is allowed, remove timestamps older than the window, count remaining requests, and compare to the limit. Very accurate but O(n) memory per key.

// Redis Lua script for atomic sliding window log check
const slidingWindowLogScript = `
local key = KEYS[1]
local limit = tonumber(ARGV[1])
local window_ms = tonumber(ARGV[2])
local now_ms = tonumber(ARGV[3])
local member = ARGV[4] -- unique per request (e.g. a UUID)
 
local window_start = now_ms - window_ms
redis.call('ZREMRANGEBYSCORE', key, '-inf', window_start)
local current = redis.call('ZCARD', key)
 
if current < limit then
    -- The member must be unique: using now_ms as the member makes
    -- same-millisecond requests overwrite each other and count once.
    redis.call('ZADD', key, now_ms, member)
    redis.call('EXPIRE', key, math.ceil(window_ms / 1000))
    return 1 -- Allow
else
    return 0 -- Reject
end
`

Advantages: the count is the true number of requests in the trailing window — no boundary spike, no approximation error. Worth it for low-volume, high-stakes endpoints such as login and payment initiation. Disadvantage: memory scales with request volume. For a key handling 1,000 req/min, you store 1,000 timestamps. For billions of keys, this is expensive. Only use when the precision is worth the cost.

Algorithm 5: Sliding Window Counter

Approximate sliding window log by tracking two fixed-window counters: current and previous. Weight the previous window's count by the fraction of the current window that overlaps it. This approximates the sliding window log with O(1) memory per key.

The math: at time t inside the current window, the observed rate is curr + prev * ((windowSize - elapsed) / windowSize). When the clock crosses the window boundary, curr becomes prev and a new curr = 0 starts.

graph LR
    subgraph PW["Previous window"]
        direction TB
        P["count = prev<br/>(e.g. 80)"]
    end
    subgraph CW["Current window<br/>(elapsed since currStart)"]
        direction TB
        C["count = curr<br/>(e.g. 25)"]
    end
    PW -.weighted<br/>overlap.-> Rate["Observed rate<br/>= curr + prev × (1 − elapsed/window)<br/>= 25 + 80 × 0.6 = 73"]
    CW --> Rate
    Rate --> Decide{"rate < limit?"}
    Decide -->|Yes| Allow["✓ Allow"]
    Decide -->|No| Reject["✗ Reject"]

Two integers per key replace a potentially-unbounded timestamp log. Trade: the weighting assumes the previous window's load was uniform, so the estimate drifts from the true rate. Cloudflare's analysis of this approximation over 400 million requests found a 6% average gap between estimated and real rate, yet only 0.003% of requests wrongly allowed or limited^⁠[4] — an estimation error only flips a decision for clients near the threshold.

type SlidingCounter struct {
    limit       int
    window      time.Duration
    curr        int
    prev        int
    currStart   time.Time
    mu          sync.Mutex
}
 
func NewSlidingCounter(limit int, window time.Duration) *SlidingCounter {
    return &SlidingCounter{
        limit:     limit,
        window:    window,
        currStart: time.Now(),
    }
}
 
func (sc *SlidingCounter) Allow() bool {
    sc.mu.Lock()
    defer sc.mu.Unlock()
 
    now := time.Now()
    elapsed := now.Sub(sc.currStart)
 
    if elapsed > sc.window {
        sc.prev = sc.curr
        sc.curr = 0
        sc.currStart = now
        elapsed = 0
    }
 
    // Weight previous window by overlap fraction
    fraction := 1.0 - (float64(elapsed) / float64(sc.window))
    weighted := float64(sc.prev) * fraction
 
    if weighted+float64(sc.curr) < float64(sc.limit) {
        sc.curr++
        return true
    }
    return false
}

The math: if 70% of the current 60-second window has elapsed and the previous window had 80 requests with a 100 req/min limit, we weight the previous count as 80 × 0.30 = 24 (30% of the 60s overlaps the previous window). The request is allowed while the current window holds fewer than 76. Memory stays at two counters per key regardless of traffic volume — that, not precision, is the reason to pick it over the log.

Distributed Rate Limiting

Single-machine rate limiting breaks at scale when 50 pods each enforce locally — attackers hit each independently. You need shared state via Redis with atomic Lua scripts^⁠[3], plus a fallback to conservative local token buckets when Redis is down. For latency-critical APIs, use local in-memory limiters with periodic async sync to Redis, accepting approximate enforcement to keep a network round-trip off every request. For deeper patterns, see Scaling Redis for High-Throughput Workloads and the probabilistic-drop variant.

What to Rate Limit By

Key selection matters as much as the algorithm. Choose the wrong key and you'll either block legitimate traffic or let attackers through.

Primary key: authenticated identity (user ID, API key). This is always available for authenticated endpoints and is the only reliable limit. Set per-user limits based on their subscription tier: free tier 100 req/min, professional 1,000 req/min, enterprise 10,000 req/min. This way, if one user is compromised, the damage is limited to that user's quota, not the entire service.

Secondary key: IP address (only for unauthenticated endpoints). Understand its failure modes:

• False positives: Enterprise users behind NAT share a single IP. A company with 500 employees on the same network can hit an IP-based limit of 10 req/min in seconds, all legitimate traffic.
• False negatives: Attackers rotate IPs. A credential-stuffing run spread across 2,000 rotating IPs keeps every single IP under the per-IP limit.

Use IP limits defensively: catch obvious attack patterns (scanning 1,000 endpoints in 10 seconds, or 50 login attempts in 5 seconds) but don't rely on them as primary enforcement. For login specifically, OWASP recommends limiting or increasingly delaying failed attempts^⁠[5].

Tiered limiting (the working model): Combine both. Limit per-user generously (e.g., 1,000 req/min for authenticated users) and per-IP tightly (e.g., 10 req/min for unauthenticated). When a user hits the per-IP limit on /login, they simply authenticate first (switching to the higher per-user limit). When an attacker rotates IPs, each IP hits a low limit. This accepts some false positives (enterprises behind NAT) to cut false negatives (attackers), and the false positives have a workaround (authentication).

Client-Side Rate Limiting

When your client hits a 429 response, retry with randomized exponential backoff^⁠[6] — full jitter below — to spread retry attempts across the window:

func exponentialBackoffWithJitter(attempt int) time.Duration {
    // Cap at 60 seconds
    maxBackoff := time.Duration(math.Min(60, math.Pow(2, float64(attempt)))) * time.Second
    // Full jitter: random delay between 0 and maxBackoff
    jitter := time.Duration(rand.Int63n(maxBackoff.Milliseconds())) * time.Millisecond
    return jitter
}

Why full jitter matters: Without jitter, all clients retrying at the same time create a thundering herd. Full jitter spreads retries uniformly, smoothing the load spike. Use the Retry-After header if provided; otherwise calculate your own.

For internal APIs you control, implement a client-side token bucket that prevents sending requests you know will be rejected:

func (c *Client) Do(ctx context.Context, req *http.Request) (*http.Response, error) {
    // Block until a token is available; respects context cancellation
    for {
        allowed, retryAfter := c.bucket.Allow(1)
        if allowed {
            break
        }
        select {
        case <-time.After(retryAfter):
        case <-ctx.Done():
            return nil, ctx.Err()
        }
    }
    return http.DefaultClient.Do(req.WithContext(ctx))
}

This eliminates round-trip costs for requests that would be rejected anyway.

Production Checklist

• Choose algorithm based on burst tolerance: token bucket for bursty clients (mobile, batch jobs), sliding window counter for precise enforcement at scale
• Rate limit by authenticated identity (user ID, API key) first; use IP limits defensively only for unauthenticated endpoints
• Store counters in Redis with atomic Lua scripts; distribute via shared state, not local counts
• Return HTTP 429 with Retry-After, X-RateLimit-Limit, X-RateLimit-Remaining, and X-RateLimit-Reset headers
• Implement exponential backoff with full jitter (0 to 2^attempt seconds) on the client side
• Deploy a local token bucket failover when Redis is unreachable — fail open (reduce limits) rather than fail closed (reject everything)
• Monitor token bucket age to detect when rate limit keys have expired; replenish if needed
• Set alerts when 429 rate exceeds 1% of traffic (early sign of abuse or misconfiguration)

The Redis Lua script for an atomic token bucket

Token-bucket-in-Redis only works if the read-modify-write is atomic. The naïve GET + math + SET loses the race; EVAL with the Lua script below executes inside the Redis single-thread, so concurrent consumers cannot double-spend tokens:

-- token_bucket.lua — atomic refill + consume
-- KEYS[1] = bucket key (e.g. "rl:user:42")
-- ARGV[1] = capacity   (max tokens)
-- ARGV[2] = refill_rate (tokens per second)
-- ARGV[3] = now        (current unix time, ms)
-- ARGV[4] = cost       (tokens to consume; usually 1)
-- Returns: { allowed (1/0), tokens_remaining, retry_after_ms }
 
local capacity     = tonumber(ARGV[1])
local refill_rate  = tonumber(ARGV[2])
local now_ms       = tonumber(ARGV[3])
local cost         = tonumber(ARGV[4])
 
local data         = redis.call("HMGET", KEYS[1], "tokens", "last_refill_ms")
local tokens       = tonumber(data[1]) or capacity
local last_refill  = tonumber(data[2]) or now_ms
 
local elapsed_ms   = math.max(0, now_ms - last_refill)
local refill       = (elapsed_ms / 1000.0) * refill_rate
tokens             = math.min(capacity, tokens + refill)
 
local allowed      = tokens >= cost and 1 or 0
local retry_ms     = 0
 
if allowed == 1 then
  tokens = tokens - cost
else
  retry_ms = math.ceil(((cost - tokens) / refill_rate) * 1000.0)
end
 
redis.call("HMSET", KEYS[1], "tokens", tokens, "last_refill_ms", now_ms)
redis.call("PEXPIRE", KEYS[1], math.ceil((capacity / refill_rate) * 1000) * 2)
 
return { allowed, math.floor(tokens), retry_ms }

The matching Prometheus alerts that catch limiter-driven incidents — abuse spikes, Redis outages forcing a fail-open, and key-cardinality drift that explodes memory:

# alerts/rate-limiter.yml
groups:
  - name: rate-limiter
    rules:
      - alert: HighRejectionRate
        expr: |
          sum(rate(http_requests_total{status="429"}[5m]))
          / sum(rate(http_requests_total[5m])) > 0.01
        for: 3m
        labels: { severity: warning }
        annotations:
          summary: "429 rate >1% of traffic"
          description: "Either abuse or limiter misconfiguration. Check top-N rate-limited identities."
 
      - alert: LimiterFailedOpen
        expr: rate(rate_limiter_redis_errors_total[5m]) > 0
        for: 1m
        labels: { severity: critical }
        annotations:
          summary: "Rate limiter cannot reach Redis — failing open"
          description: "Local-token-bucket fallback is active. Restore Redis before quota abuse compounds."
 
      - alert: LimiterKeyCardinalityHigh
        # Count keys in Redis (redis_exporter), not via a per-key Prometheus
        # label: that would move the cardinality explosion into Prometheus.
        # Assumes the limiter owns db0, and that this scrape job targets
        # primaries only — a replica reports the same keyspace as its
        # primary, so summing across replicas inflates the count.
        expr: |
          sum(redis_db_keys{job="ratelimit-redis", db="db0"}) > 500000
        for: 15m
        labels: { severity: warning }
        annotations:
          summary: "Rate limiter has >500k unique keys"
          description: "Probably keying on a high-cardinality field (per-request ID instead of per-user). Memory will OOM Redis at scale."

Set the LimiterKeyCardinalityHigh threshold against your actual user count — the failure mode it catches is "we accidentally keyed by request ID" which inflates Redis memory linearly with traffic.

Anti-Patterns in Production

Three failure modes look fine in code review and unit tests and surface only under real traffic.

Anti-pattern 1: Keying on the request URL with path parameters baked in

Picture a rollout of per-endpoint rate limiting that uses the raw request path as part of the key. The intent is reasonable — different limits for /api/v1/orders vs /api/v1/search. The implementation isn't:

// Broken: every order ID becomes its own rate-limit key
key := fmt.Sprintf("rl:%s:%s", userID, r.URL.Path)
// → rl:user:42:/api/v1/orders/9f8e7d6c-...

Every order ID now mints its own key, so Redis key count and memory grow with the number of distinct orders requested, and the limiter never trips: a client walking through orders spreads its requests across one key per order. The fix is to canonicalise the route before keying — routers such as chi expose the matched template, not just the resolved path:

// Fixed: use the route template, not the resolved URL.
// chi fills the pattern during routing: attach this limiter per route with
// r.With(...). In a root-level r.Use(...) middleware it is still "".
template := chi.RouteContext(r.Context()).RoutePattern()
// → /api/v1/orders/{id}
key := fmt.Sprintf("rl:%s:%s", userID, template)

If your framework doesn't expose the template, hash the route definition at registration time and tag requests with it. Never let user-controlled URL segments enter the key.

Anti-pattern 2: Failing closed when the limiter store is unreachable

Redis goes down for 90 seconds during a failover. The limiter throws on every EVAL call. The middleware returns 500. The entire API is offline — not because the upstream is broken, but because the limiter is.

The fix is fail-open with a conservative local fallback, plus a circuit breaker so you don't hammer a dead Redis:

func (l *Limiter) Allow(ctx context.Context, key string) (bool, error) {
    if l.breaker.State() == StateOpen {
        return l.localFallback.Allow(key), nil // permissive but bounded
    }
    allowed, err := l.redisCheck(ctx, key)
    if err != nil {
        slog.WarnContext(ctx, "rate limiter: redis check failed, using local fallback", "err", err)
        l.breaker.RecordFailure()
        metrics.LimiterFailedOpen.Inc()
        return l.localFallback.Allow(key), nil
    }
    l.breaker.RecordSuccess()
    return allowed, nil
}

Doorman's design doc names the same trade-off: a client that can't renew its lease can run in pessimistic mode (capacity zero, i.e. fail closed), optimistic mode (use everything it asked for), or safe mode, capped at a per-client "safe capacity"^⁠[7]. Keep the local fallback tighter than the Redis-backed limit (e.g. 50% of nominal) to bound abuse during the outage. Page on LimiterFailedOpen so the on-call sees fail-open is active even when user-facing latency looks normal.

Anti-pattern 3: Shipping a new algorithm without shadow mode

Switching from fixed window to sliding window counter is a one-line config change. It's also a behaviour change — the boundary tolerance disappears, so clients that previously sneaked through right at the window edge now get 429s. Do it at noon on a weekday, and an iOS app whose retry logic isn't compatible with Retry-After can go into a tight loop, multiplying the very traffic the new limiter was supposed to control.

Always run the new limiter in shadow mode for 24-48 hours first. Compute the decision both ways, log the divergence, but only enforce the old one:

oldDecision := l.fixedWindow.Allow(key)
newDecision := l.slidingCounter.Allow(key)
if oldDecision != newDecision {
    metrics.LimiterShadowDivergence.WithLabelValues(
        boolToStr(oldDecision), boolToStr(newDecision),
    ).Inc()
}
return oldDecision // still authoritative

The divergence metric tells you how much traffic will be newly rejected before you flip the switch. If divergence is above ~2% of traffic, the cutover needs a coordinated client release first.

Frequently Asked Questions

Keep Reading

• Scaling Redis for High-Throughput Workloads — Redis is your rate limit store; understand its latency profile and failure modes
• Caching Strategies at Scale — rate limiting often pairs with caching; understand the interaction
• Understanding Raft Consensus — rate limiting is a coordination problem; understanding consensus helps with distributed decisions