The Empire Strikes Back: CAP Theorem Explained with a Rate Limiter Quest

The Quest Begins (The “Why”)

I was building a tiny API service that needed to protect itself from abusive clients. The obvious answer? A rate limiter. I imagined a simple counter: every request increments a number, and if it crosses a threshold we block the caller. Easy, right?

I slapped together a naïve version that kept the counter in a process‑level variable, protected by a mutex. It worked on my laptop, but once we deployed to a cluster of three nodes behind a load balancer, things got… weird.

• Under normal traffic, each node thought it was seeing only a third of the real request count, so users could burst far past the limit.
• When one node went down, the mutex on that node vanished, but the other nodes still had their own counters—so the limit was still off.
• Worst of all, during a network partition (the classic “split‑brain” scenario), the nodes couldn’t talk to each other, and the system either became unavailable (if we tried to keep a single source of truth) or wildly inconsistent (if we let each node keep counting).

I felt like Frodo staring at the One Ring, realizing that the simple solution I’d clung to was actually a cursed artifact. I needed to understand the real trade‑off at play.

The Revelation (The Insight)

That’s when the CAP theorem slapped me in the face like a lightsaber duel.

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

The theorem says you can only have two of the three at any given time. In a distributed system, partitions are inevitable, so you must pick either Consistency or Availability when a partition happens.

For a rate limiter, strict consistency (knowing the exact global count at every millisecond) is overkill. What we really need is to slow down abusive traffic, not to guarantee that two clients in different data centers see the exact same count at the exact same nano‑second.

If we relax consistency just a bit and aim for Availability + Partition Tolerance (AP), we can keep the limiter running even when nodes can’t talk to each other. The trade‑off is a small window where the count might be a little off—enough to let a few extra requests slip through, but not enough to break our protection goals.

That insight felt like discovering the hidden lever in a puzzle box: once you know which two pillars you’re leaning on, the rest of the design falls into place.

Wielding the Power (Code & Examples)

The Struggle – A “Consistent” Limiter

// naive.go – a terrible idea for a cluster
type limiter struct {
    mu      sync.Mutex
    count   int
    limit   int
    window  time.Duration
    lastReset time.Time
}

func (l *limiter) Allow() bool {
    l.mu.Lock()
    defer l.mu.Unlock()

    now := time.Now()
    if now.Sub(l.lastReset) > l.window {
        l.count = 0
        l.lastReset = now
    }

    if l.count >= l.limit {
        return false // reject
    }
    l.count++
    return true
}

What went wrong?

• The mu mutex only protects the counter inside one process.
• In a cluster each replica runs its own copy, so the global count is the sum of three independent counters—easily fooled by a burst.
• If a node crashes, its mutex disappears, but its counter is lost too, causing a sudden drop in the observed rate.
• During a network partition we can’t reconcile the counters, so we either block all requests (trying to stay consistent) or let each node keep counting (available but wildly inconsistent).

The Victory – An AP‑Style Limiter with Redis

We turned to a shared, eventually‑consistent store: Redis. Redis gives us single‑node atomicity (via Lua scripts) and replicates asynchronously, which means we get availability even if a replica is temporarily unreachable—writes will just queue up and propagate later.

-- ratelimit.lua  (executed atomically by Redis EVALSHA)
local key = KEYS[1]          -- e.g. "ratelimit:user:123"
local limit = tonumber(ARGV[1])
local window = tonumber(ARGV[2])

local current = redis.call("GET", key)
if current == false then
    redis.call("SET", key, 1)
    redis.call("EXPIRE", key, window)
    return 1   -- allowed
end

if tonumber(current) < limit then
    local newval = redis.call("INCR", key)
    return newval   -- allowed
end

return 0   -- blocked

And the Go wrapper:

// redis_limiter.go
type RedisLimiter struct {
    client *redis.Client
    limit  int
    window time.Duration
}

func NewRedisLimiter(client *redis.Client, limit int, window time.Duration) *RedisLimiter {
    return &RedisLimiter{client: client, limit: limit, window: window}
}

func (r *RedisLimiter) Allow(userID string) (bool, error) {
    key := fmt.Sprintf("ratelimit:%s", userID)
    // Lua script sha1 pre‑loaded for speed
    res, err := r.client.EvalSha(ctx, luaSha, []string{key}, r.limit, int(r.window.Seconds())).Result()
    if err != nil {
        return false, err
    }
    allowed := res.(int64) == 1
    return allowed, nil
}

Why this works:

• The Lua script runs atomically on the Redis node that receives the request, guaranteeing that the increment‑and‑check happens without race conditions on that node.
• Redis replicates the key asynchronously; if a network partition isolates a replica, the replica can still serve reads/writes from its local copy (availability). When the partition heals, the replicas converge (eventual consistency).
• We only need approximate correctness: a brief window where two partitions might both think they’re under the limit and let a few extra requests through. For most abuse‑prevention scenarios, that’s perfectly fine.

Common Traps (The “Boss Levels” to Avoid)

1. Forgetting the expiry – If you INCR without setting a TTL, the key lives forever and memory blows up. Always pair the increment with an EXPIRE (or use the Lua script above).
2. Using separate counters per instance – That’s basically the naive version again; you’ll never get a sensible global view.
3. Blocking on a quorum write – Trying to enforce strong consistency by waiting for a majority of Redis replicas to acknowledge each turn makes the limiter unavailable during a partition (you’ve chosen CP, not AP).

Why This New Power Matters

Now I can look at any rate‑limiting problem and ask myself: “Do I need exact counts, or do I just need to keep the bad guys from hammering my service?”

If the answer is the latter, I reach for an AP design like the Redis token bucket. It lets my service stay up and responsive even when parts of the network go sideways—exactly the kind of resilience modern cloud apps demand.

The shift from a tightly‑coupled, consistent counter to a loosely‑shared, eventually‑available one didn’t just fix a bug; it changed how I think about distributed state altogether. I now see the CAP theorem not as a dry textbook rule, but as a practical compass that tells me which trade‑offs to embrace for the job at hand.

So go ahead—grab your favorite key‑value store, slap on a Lua script, and build a limiter that laughs in the face of network partitions.

Your turn: Try swapping the Redis backend for an in‑process cache with a gossip‑based CRDT. What happens to the accuracy‑vs‑availability balance when you add a gossip interval of 5 seconds versus 30 seconds? Share your findings in the comments—I’m excited to see what you discover!