Rate Limiting Like a Jedi: CAP Theorem Explained

The Quest Begins (The "Why")

I still remember the night our API started choking under a sudden traffic spike. Users were seeing 502 errors, the monitoring dashboard flashed red, and I felt like I was trying to hold back a horde of stormtroopers with a toothpick. We had a simple in‑memory counter for rate limiting, but as soon as we added a second instance behind a load balancer the counters diverged—some users got through, others got blocked unfairly.

The problem wasn’t just the code; it was a fundamental tension between consistency (every node seeing the same count) and availability (the system staying up even when parts can’t talk). I’d heard of the CAP theorem before, but it felt like one of those academic concepts you file away for “later”. That night, “later” became “now”. I needed to understand what we could actually guarantee when the network decided to take a coffee break.

The Revelation (The Insight)

The CAP theorem says that in a distributed system you can only have two of the following three guarantees:

• Consistency – every read receives the most recent write or an error.
• Availability – every request gets a response (non‑error) without guarantee it’s the latest data.
• Partition tolerance – the system continues to operate despite arbitrary message loss between nodes.

Since network partitions are inevitable in the real world, P is non‑negotiable. That leaves us with a choice: CP or AP.

For a rate limiter, the question is: Do we want to be perfectly accurate (no user ever exceeds the limit) even if that means rejecting requests during a partition, or do we prefer to stay alive and allow a tiny bit of over‑limit traffic?

I chose AP. Why? Because in most user‑facing APIs a brief over‑limit is far less painful than turning away legitimate users when a node can’t talk to its peers. Think of it like Neo dodging bullets in The Matrix—you accept that a few might graze you, but you keep moving forward and survive the barrage.

With an AP rate limiter we trade strong consistency for eventual consistency: each node tracks its own counter, and we reconcile them lazily (e.g., via a background Redis sync). When the partition heals, the counts converge, and any temporary over‑limit is harmless.

Here’s a quick ASCII picture of what happens during a partition:

   +--------+      +--------+      +--------+
   |  Node1 |<---->|  Node2 |<---->|  Node3 |
   +--------+      +--------+      +--------+
        |             |             |
   (healthy)   (partition)   (healthy)
        |             |             |
   +--------+      +--------+      +--------+
   |  Redis |      |  Redis |      |  Redis |
   +--------+      +--------+      +--------+

When the link between Node 1 and Node 2 drops, each side keeps counting locally. No global lock, no blocked requests—just independent counters that will later be merged.

Wielding the Power (Code & Examples)

The Struggle: A Naïve In‑Memory Counter

// BAD: per‑process map, no sharing
var counters = map[string]int{}

func allow(key string, limit int, window time.Duration) bool {
    now := time.Now()
    counters[key]++
    if counters[key] > limit {
        return false
    }
    // reset after window (simplified)
    time.AfterFunc(window, func() { counters[key] = 0 })
    return true
}

Run two instances behind a load balancer and you’ll see the limit double‑count or halve‑count depending on which node gets the request. During a network glitch, one node might keep counting while the other stops, leading to wild inconsistencies.

The Victory: AP Rate Limiter with Redis (Lua Script)

We use Redis as a fast, eventually‑consistent store. The script increments a counter and sets an expiry—all atomically. If Redis is unreachable we fall back to allowing the request (availability) and log the miss for later reconciliation.

// redisRateLimiter.go
package ratelimit

import (
    "context"
    "time"

    "github.com/go-redis/redis/v8"
)

var lua = redis.NewScript(`
    local current = redis.call("INCR", KEYS[1])
    if current == 1 then
        redis.call("EXPIRE", KEYS[1], ARGV[2])
    end
    return current
`)

type Limiter struct {
    client *redis.Client
    limit  int
    window time.Duration
}

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

func (l *Limiter) Allow(ctx context.Context, key string) (bool, error) {
    now := time.Now()
    // Convert window to seconds for EXPIRE
    expire := int(l.window.Seconds())

    count, err := lua.Run(ctx, l.client, []string{key}, 1, expire).Int()
    if err != nil {
        // Redis down → choose availability: let it through, but log.
        // In a real system you might increment a local fallback counter.
        return true, err
    }
    return count <= l.limit, nil
}

Why this beats the naive version

• Atomicity – The Lua script guarantees that INCR and EXPIRE happen as one indivisible operation, so no race condition between increment and expiry.
• Partition tolerance – If Redis is unreachable, the error path returns true (allow) and we keep serving traffic. When the partition heals, the counter catches up.
• Eventual consistency – All nodes see the same Redis value (assuming they can reach it). Brief divergences are harmless and self‑heal.

Common traps to avoid

1. Treating Redis as CP – If you wrap every call in a MULTI/EXEC transaction and then return an error on failure, you’ll turn the limiter into a CP system: during a partition you’ll start rejecting requests, defeating the availability goal.
2. Over‑relying on local fallbacks – Storing a per‑process counter as a backup can cause drift that never reconciles. Keep the fallback simple (just allow) and let Redis be the source of truth when it’s back.

Why This New Power Matters

Adopting an AP rate limiter changed how we think about resilience. Instead of scrambling to add more locks or hoping our sticky sessions never break, we now have a system that gracefully degrades: under normal load it’s accurate enough, and under a network hiccup it stays alive, letting legitimate traffic through while keeping the abuse window bounded.

The insight isn’t just about rate limiting—it’s a lens for any distributed counter, cache, or leader election. Ask yourself: Do I need strict correctness right now, or can I tolerate a brief inconsistency for the sake of uptime? Answering that question early saves you from over‑engineering and gives you a clear path to a system that feels like a Jedi’s lightsaber—elegant, reliable, and ready to deflect whatever the galaxy throws at you.

Your Turn

Grab a service you own that currently uses a simple in‑memory limiter or a basic token bucket. Swap it out for the Redis‑backed AP version above, inject a fake network partition (e.g., block Redis with iptables), and watch how the system behaves. Did it stay available? Did the over‑limit stay within acceptable bounds? Share your results—let’s keep the quest going!

Happy coding, and may your partitions be short and your limits ever in your favor. 🚀