Rate Limiting: The Matrix of CAP

The Quest Begins (The "Why")

Picture this: I’m building a tiny API that lets users upload cat pictures. Everything works locally, but once I spin up a few containers behind a load balancer, the rate‑limit starts leaking like a sieve. One user can blast 100 requests per second while my limit is supposed to be 10. I stare at the logs, muttering “Why does this feel like I’m fighting Neo in a lobby shoot‑out?” The problem isn’t the code—it’s the distributed nature of the system. I need a guarantee that, no matter how many nodes I have, the limit is respected. That’s when the CAP theorem slapped me in the face and said, “Pick two, buddy.”

The Revelation (The Insight)

The CAP theorem isn’t some abstract math beast; it’s a practical checklist for any distributed service:

• Consistency – every node sees the same data at the same time.
• Availability – every request gets a response (even if it’s stale).
• Partition tolerance – the system keeps working when the network splits.

You can only have two of the three at any moment. For a rate limiter, the real requirement is consistency: if two nodes think they’ve each only seen 5 requests, they’ll both let the 6th through and you’ll exceed the limit. So we must sacrifice availability during a partition—better to reject requests than to let them slip through. In other words, we design a CP system (Consistent + Partition‑tolerant) and accept that, when the network glitches, the limiter may become unavailable (return 503 or retry‑later).

The insight? Centralize the counter in a single source of truth that can guarantee atomic updates, then treat every node as a thin client that talks to that source. Redis (or any strongly consistent store) gives us exactly that: a single lock‑free, atomic increment that survives partitions because the client will simply fail to reach Redis and we can fail fast.

Here’s a quick ASCII picture of the flow:

+--------+      RPC/HTTP      +--------+      Redis (CP)      +--------+
|  Node  | -----------------> |  LB    | -----------------> |  Store   |
| (API)  |   request/response |        |   INCR/Lua script  | (token)  |
+--------+                    +--------+                    +--------+

All nodes ask Redis: “Increment my bucket; if the new value > limit, reject.” Because Redis processes commands sequentially, we get a globally consistent view—no more phantom requests slipping through the cracks.

Wielding the Power (Code & Examples)

The Struggle: Per‑Instance Counters

My first attempt was embarrassingly simple: each service instance kept its own in‑memory counter.

// BAD: per‑instance token bucket (inaccurate under load)
type Limiter struct {
    mu      sync.Mutex
    tokens  int64
    limit   int64
    last    time.Time
}

func (l *Limiter) Allow() bool {
    l.mu.Lock()
    defer l.mu.Unlock()
    now := time.Now()
    // refill logic omitted for brevity
    if l.tokens > 0 {
        l.tokens--
        return true
    }
    return false
}

When I ran three replicas behind LB, a bursty client could hit each replica once, consuming three tokens while the global limit allowed only one. The system was AP (always available) but violated consistency—exactly the trap CAP warns about.

The Victory: Centralized Token Bucket with Redis

Now the “spell” that actually works:

-- redis-limiter.lua  (atomic token bucket)
local key = KEYS[1]          -- e.g. "rate:user:123"
local limit = tonumber(ARGV[1])
local refill = tonumber(ARGV[2])   -- tokens per second
local now = tonumber(ARGV[3])

local bucket = redis.call('HMGET', key, 'tokens', 'last')
local tokens = tonumber(bucket[1]) or limit
local last = tonumber(bucket[2]) or now

-- refill based on elapsed time
if last < now then
    local added = math.floor((now - last) * refill)
    tokens = math.min(limit, tokens + added)
    last = now
end

if tokens >= 1 then
    tokens = tokens - 1
    redis.call('HMSET', key, 'tokens', tokens, 'last', last)
    redis.call('EXPIRE', key, 3600)   -- keep key alive for an hour
    return 1   -- allowed
else
    redis.call('HMSET', key, 'tokens', tokens, 'last', last)
    return 0   -- rejected
end

And the thin Go wrapper:

func Allow(userID string) bool {
    // SHA of the lua script is pre‑loaded; we just EVALSHA
    res, err := redisClient.EvalSHA(ctx, limiterSHA, []string{
        fmt.Sprintf("rate:%s", userID),
    }, strconv.FormatInt(limit, 10),
        strconv.FormatInt(refill, 10),
        strconv.FormatInt(time.Now().Unix(), 10)).Int()
    if err != nil {
        // On any Redis error we fail closed (choose consistency)
        log.Printf("Redis error: %v – failing closed", err)
        return false
    }
    return res == 1
}

Why this beats the naïve version:

• Atomicity – The Lua script runs as a single Redis command, so two concurrent requests can’t both read the same token count and both decrement it.
• Partition handling – If Redis is unreachable, the call errors and we return false (reject). We sacrifice availability but keep the guarantee that we never exceed the limit.
• Scalability – Adding more API nodes doesn’t increase state; they all share the same Redis bucket.

Common traps to avoid:

1. Using INCR alone – It increments but doesn’t refill tokens based on time; you’d need a separate key for timestamps, opening a race window. The Lua script bundles refill + decrement atomically.
2. Treating Redis as eventually consistent – If you switch to a read‑replica or a cache‑aside pattern, you lose the CP guarantee. Stick to the primary node for writes (or use a strongly consistent Redis cluster).

Why This New Power Matters

Now I can confidently tell my product owner: “Our cat‑picture API will never let a single user hammer more than 10 uploads per second, even if we spin up a hundred instances.” The system behaves predictably under load, and the failure mode is clear—when the network glitches, we simply reject excess traffic instead of letting it slip through.

Beyond rate limiting, the same CP pattern works for any quota‑based feature: API keys, loyalty points, or even inventory reservation. You learn to ask the right question early: “Do I need perfect counts right now, or can I tolerate a little slop?” Answering that tells you whether to reach for a CP solution (Redis, ZooKeeper, etcd) or an AP one (CRDTs, eventual‑consistent caches).

So go ahead—grab a Redis instance, drop that Lua script in, and wrap it in a thin client. Test it with hey or wrk and watch the limiter hold the line.

Your turn: Try building a sliding‑window limiter with the same pattern, or swap Redis for a strongly consistent database like CockroachDB and see how the latency trade‑off shifts. What other quota‑driven feature will you make bullet‑proof next? Drop a comment or tweet your experiment—I’d love to hear how it went!

---

Happy coding, and may your limits always be respected!