Day 76 — Rate Limiting at L7

Learning Objectives

• Implement per-API-key token bucket rate limiting
• Return standard rate limit headers (X-RateLimit-*)
• Build the per-entity sliding window from Day 21 into a complete middleware

Key Concepts

Token Bucket Algorithm:
  - Bucket holds up to B tokens (burst capacity)
  - Tokens refill at rate R per second
  - Each request consumes 1 token
  - If empty: return 429

Rate limit headers (standard):
  X-RateLimit-Limit:     10        (requests per window)
  X-RateLimit-Remaining: 7         (tokens left)
  X-RateLimit-Reset:     1704067200 (Unix timestamp when bucket refills)
  Retry-After:           13        (seconds to wait before retry, on 429)

Per-entity vs global:
  Per-API-key: "Stripe API allows 100 req/s"
  Per-IP:      "DDoS mitigation, before auth"
  Per-user:    "Free plan 100/day, Pro 10000/day"

Exercise: Token Bucket Rate Limiter Middleware

package ratelimit

import (
    "fmt"
    "net/http"
    "sync"
    "time"
)

type TokenBucket struct {
    mu       sync.Mutex
    tokens   float64
    capacity float64
    rate     float64 // tokens per second
    lastFill time.Time
}

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

// Take tries to consume one token. Returns (allowed, remaining, resetAfter).
func (tb *TokenBucket) Take() (bool, float64, time.Duration) {
    tb.mu.Lock()
    defer tb.mu.Unlock()

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

    // Refill tokens based on elapsed time
    tb.tokens = min(tb.capacity, tb.tokens+elapsed*tb.rate)

    if tb.tokens < 1 {
        // Calculate when 1 token will be available
        waitSecs := (1 - tb.tokens) / tb.rate
        return false, 0, time.Duration(waitSecs * float64(time.Second))
    }

    tb.tokens--
    return true, tb.tokens, 0
}

type RateLimiter struct {
    mu       sync.Mutex
    buckets  map[string]*TokenBucket
    capacity float64
    rate     float64
    cleanup  *time.Ticker
}

func NewRateLimiter(capacity, ratePerSec float64) *RateLimiter {
    rl := &RateLimiter{
        buckets:  make(map[string]*TokenBucket),
        capacity: capacity,
        rate:     ratePerSec,
        cleanup:  time.NewTicker(5 * time.Minute),
    }
    go rl.cleanupLoop()
    return rl
}

func (rl *RateLimiter) getBucket(key string) *TokenBucket {
    rl.mu.Lock()
    defer rl.mu.Unlock()
    if _, ok := rl.buckets[key]; !ok {
        rl.buckets[key] = NewTokenBucket(rl.capacity, rl.rate)
    }
    return rl.buckets[key]
}

func (rl *RateLimiter) cleanupLoop() {
    for range rl.cleanup.C {
        rl.mu.Lock()
        // Remove buckets that are full (haven't been used recently)
        for key, bucket := range rl.buckets {
            bucket.mu.Lock()
            if bucket.tokens >= bucket.capacity*0.99 {
                delete(rl.buckets, key)
            }
            bucket.mu.Unlock()
        }
        rl.mu.Unlock()
    }
}

// Middleware returns a per-entity rate limiting handler
// keyFn extracts the rate limit key from the request (API key, user ID, IP)
func (rl *RateLimiter) Middleware(keyFn func(*http.Request) string) func(http.Handler) http.Handler {
    return func(next http.Handler) http.Handler {
        return http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
            key := keyFn(r)
            bucket := rl.getBucket(key)
            allowed, remaining, retryAfter := bucket.Take()

            // Always set rate limit headers
            w.Header().Set("X-RateLimit-Limit", fmt.Sprintf("%.0f", rl.capacity))
            w.Header().Set("X-RateLimit-Remaining", fmt.Sprintf("%.0f", remaining))

            if !allowed {
                w.Header().Set("Retry-After", fmt.Sprintf("%.0f", retryAfter.Seconds()))
                w.Header().Set("Content-Type", "application/json")
                w.WriteHeader(http.StatusTooManyRequests)
                fmt.Fprintf(w, `{"error":"rate limit exceeded","retry_after":%d}`,
                    int(retryAfter.Seconds()))
                return
            }

            next.ServeHTTP(w, r)
        })
    }
}

func main() {
    // Rate limit by API key: 10 req/s burst 50
    limiter := NewRateLimiter(50, 10)

    handler := http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
        fmt.Fprintf(w, `{"data":"response"}`)
    })

    // Key extraction: use API key if authenticated, else IP
    keyFn := func(r *http.Request) string {
        if subject := auth.GetSubject(r.Context()); subject != "" {
            return "user:" + subject
        }
        return "ip:" + realClientIP(r)
    }

    http.ListenAndServe(":8080",
        Chain(handler,
            APIKeyAuth(store),
            limiter.Middleware(keyFn),
        ),
    )
}

Real-World Context

Stripe's API allows 100 req/s. GitHub's API allows 5000 req/hour. These are token buckets. The X-RateLimit-* headers are de facto standard — clients use them to implement polite backoff. Without Retry-After, clients retry immediately (thundering herd). With it, they wait the exact right amount.