Redis Rate Limiting: Implementing the Token Bucket Algorithm

When our primary API started getting hammered by a sudden influx of traffic, our local memory-based rate limiters failed instantly. Because each containerized instance was tracking its own count, the global limit was effectively multiplied by the number of active pods, leaving our backend database completely exposed.

We needed a centralized way to enforce limits, and we needed it to be fast. We eventually settled on using Redis rate limiting to synchronize state across our cluster.

Why the Token Bucket Algorithm?

Before landing on the token bucket, we experimented with a simple "fixed window" counter. It was easy to implement, but it suffered from the "boundary burst" problem—users could double their quota by sending requests right at the edge of two time windows.

The token bucket algorithm solves this by treating the rate limit as a bucket that fills with tokens at a steady rate. Every incoming request consumes a token. If the bucket is empty, the request is rejected. It’s elegant, handles bursts gracefully, and is relatively straightforward to implement using Redis.

The Problem with Distributed Race Conditions

If you try to implement this using standard GET and SET commands in your application code, you’ll hit a race condition within minutes. Two application servers might read a bucket value of "1" simultaneously, both decide there's enough room, and both decrement it to "-1".

To prevent this, you need atomicity. We use Redis Lua scripting to ensure that the read-modify-write cycle happens entirely within the Redis engine. Since Redis is single-threaded, the script runs as a single, uninterruptible operation.

Implementing the Script

Here is the Lua script we currently use in production. It calculates the number of tokens to add based on the time elapsed since the last request, then checks if the bucket has enough capacity.

LUA
-- KEYS[1] = bucket key
-- ARGV[1] = capacity
-- ARGV[2] = fill rate (tokens per second)
-- ARGV[3] = requested tokens

local bucket = redis.call("HMGET", KEYS[1], "tokens", "last_refill")
local capacity = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])
local now = redis.call("TIME")[1]

local last_tokens = tonumber(bucket[1]) or capacity
local last_refill = tonumber(bucket[2]) or now

-- Calculate new tokens
local delta = math.max(0, now - last_refill)
local current_tokens = math.min(capacity, last_tokens + (delta * refill_rate))

if current_tokens >= tonumber(ARGV[3]) then
    redis.call("HMSET", KEYS[1], "tokens", current_tokens - ARGV[3], "last_refill", now)
    return 1
else
    return 0
end

This approach is highly performant. Even under heavy load, we typically see execution times around 0.5ms to 0.8ms. If you are working in a PHP environment, you might find Laravel Redis Lua Scripting for Deterministic Rate Limiting useful for understanding how to wrap this logic in a service provider.

Comparing Rate Limiting Strategies

Choosing the right approach depends on your specific consistency requirements.

Lessons Learned in Production

We initially tried to store the bucket state in a relational database, but the overhead of transaction locking killed our throughput. Moving to Redis was the right call, but it introduced a new dependency. If Redis goes down, your rate limiter stops working.

In our case, we implemented a "fail-open" strategy. If the Redis call times out or throws an exception, the application defaults to allowing the request. It’s better to risk a brief spike in traffic than to take down the entire API for all users because the cache layer is momentarily unreachable.

If your system is part of a larger multi-tenant architecture, you should read our guide on API Rate Limiting with Token Bucket Algorithms for Multi-Tenant SaaS to understand how to partition these buckets by tenant ID effectively.

FAQ

Does this work with Redis Cluster? Yes, but you must ensure that your keys are hashed to the same slot if you want to perform multi-key operations. For a standard rate limiter keyed by user ID, simply using a consistent hashing key prefix works perfectly.

How do I handle "bursty" traffic? The capacity argument in the Lua script acts as your burst limit. By setting this higher than your steady-state refill_rate, you allow users to consume tokens quickly for a short duration while still enforcing a long-term average.

Is Lua scripting the only way? Technically, you could use Redis transactions (MULTI/EXEC) with WATCH, but that requires optimistic locking and handling retries if the key changes. Lua is much cleaner and avoids the complexity of manual retry loops.

Final Thoughts

Using a Lua-powered token bucket for distributed systems is a significant step up from local, memory-bound limits. It's not bulletproof—no system is—but it provides the balance of performance and accuracy we need for modern API throttling. Next time, I’d like to experiment with a dedicated Redis module like redis-cell for even tighter integration, but for now, this custom script is doing the job just fine.