Day 92 — Rate Limiting Algorithms Deep Dive

Key Concepts

Exercise — All 5 Algorithms

package ratelimit

import (
    "sync"
    "sync/atomic"
    "time"
)

// 1. Fixed Window — fast but vulnerable to boundary bursts
type FixedWindow struct {
    mu        sync.Mutex
    limit     int
    count     int
    windowEnd time.Time
    period    time.Duration
}

func NewFixedWindow(limit int, period time.Duration) *FixedWindow {
    return &FixedWindow{limit: limit, period: period, windowEnd: time.Now().Add(period)}
}

func (fw *FixedWindow) Allow() bool {
    fw.mu.Lock()
    defer fw.mu.Unlock()
    now := time.Now()
    if now.After(fw.windowEnd) {
        fw.count = 0
        fw.windowEnd = now.Add(fw.period)
    }
    if fw.count >= fw.limit {
        return false
    }
    fw.count++
    return true
}

// 2. Sliding Window Log — accurate, memory-heavy (stores each request timestamp)
type SlidingWindowLog struct {
    mu      sync.Mutex
    limit   int
    period  time.Duration
    entries []time.Time
}

func NewSlidingWindowLog(limit int, period time.Duration) *SlidingWindowLog {
    return &SlidingWindowLog{limit: limit, period: period}
}

func (swl *SlidingWindowLog) Allow() bool {
    swl.mu.Lock()
    defer swl.mu.Unlock()
    now := time.Now()
    cutoff := now.Add(-swl.period)

    // Evict old entries
    valid := swl.entries[:0]
    for _, t := range swl.entries {
        if t.After(cutoff) {
            valid = append(valid, t)
        }
    }
    swl.entries = valid

    if len(swl.entries) >= swl.limit {
        return false
    }
    swl.entries = append(swl.entries, now)
    return true
}

// 3. Sliding Window Counter — approximation using two fixed windows
type SlidingWindowCounter struct {
    mu          sync.Mutex
    limit       int
    period      time.Duration
    curCount    int
    prevCount   int
    windowStart time.Time
}

func NewSlidingWindowCounter(limit int, period time.Duration) *SlidingWindowCounter {
    return &SlidingWindowCounter{limit: limit, period: period, windowStart: time.Now()}
}

func (swc *SlidingWindowCounter) Allow() bool {
    swc.mu.Lock()
    defer swc.mu.Unlock()
    now := time.Now()
    elapsed := now.Sub(swc.windowStart)

    if elapsed >= swc.period {
        // Shift windows
        swc.prevCount = swc.curCount
        swc.curCount = 0
        swc.windowStart = now
        elapsed = 0
    }

    // Weighted count: prev window contribution + current window
    ratio := 1.0 - elapsed.Seconds()/swc.period.Seconds()
    estimated := float64(swc.prevCount)*ratio + float64(swc.curCount)
    if int(estimated) >= swc.limit {
        return false
    }
    swc.curCount++
    return true
}

// 4. Token Bucket — allows burst up to capacity B, refills at rate R tokens/sec
type TokenBucket struct {
    mu       sync.Mutex
    tokens   float64
    capacity float64
    rate     float64 // tokens per second
    lastTime time.Time
}

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

func (tb *TokenBucket) Allow() bool {
    tb.mu.Lock()
    defer tb.mu.Unlock()
    now := time.Now()
    elapsed := now.Sub(tb.lastTime).Seconds()
    tb.lastTime = now

    tb.tokens = min(tb.capacity, tb.tokens+elapsed*tb.rate)
    if tb.tokens < 1.0 {
        return false
    }
    tb.tokens--
    return true
}

func min(a, b float64) float64 {
    if a < b {
        return a
    }
    return b
}

// 5. Leaky Bucket — smooth constant outflow regardless of input burst
type LeakyBucket struct {
    capacity  int64 // queue depth
    current   atomic.Int64
    drainRate time.Duration // time between each drain
    done      chan struct{}
}

func NewLeakyBucket(capacity int64, drainRate time.Duration) *LeakyBucket {
    lb := &LeakyBucket{capacity: capacity, drainRate: drainRate, done: make(chan struct{})}
    go lb.drain()
    return lb
}

func (lb *LeakyBucket) drain() {
    ticker := time.NewTicker(lb.drainRate)
    defer ticker.Stop()
    for {
        select {
        case <-lb.done:
            return
        case <-ticker.C:
            for {
                cur := lb.current.Load()
                if cur <= 0 {
                    break
                }
                if lb.current.CompareAndSwap(cur, cur-1) {
                    break
                }
            }
        }
    }
}

func (lb *LeakyBucket) Allow() bool {
    for {
        cur := lb.current.Load()
        if cur >= lb.capacity {
            return false
        }
        if lb.current.CompareAndSwap(cur, cur+1) {
            return true
        }
    }
}

func (lb *LeakyBucket) Stop() { close(lb.done) }

Real-World Context

• AWS API Gateway uses token bucket (burst capacity + sustained rate).
• Stripe uses sliding window counter per API key.
• DDoS mitigation layers prefer token bucket at L4 (per-IP) and sliding window counter at L7 (per path/endpoint) because token bucket allows legitimate burst while bounding steady-state rate.