A rate limiter looks like a counter until the requirements become real. Then it has to make a decision across many application instances, preserve tenant isolation, tolerate retries, and avoid becoming the dependency that takes down the service it protects.

The important design question is not “Which algorithm is best?” It is: what error are we willing to make when state is delayed, unavailable, or split across regions?

Start with the contract

Before choosing Redis or writing a Lua script, define:

  • the identity being limited: user, API key, tenant, IP, route, or a composite;
  • whether limits control cost, abuse, fairness, or downstream capacity;
  • the window and burst policy;
  • the response contract, including 429, Retry-After, and remaining quota;
  • the acceptable error: reject a valid request or admit extra traffic;
  • whether the limit must be global or region-local.

An authentication endpoint usually prefers a conservative failure. A read-only public API may accept a small overshoot to remain available.

Compare the algorithms by behavior

Fixed window

Store a counter per identity and time bucket. It is cheap, but a client can use the full quota at the end of one window and again at the start of the next.

Sliding log

Store every request timestamp and remove entries older than the window. It is precise but memory grows with traffic, so it is rarely the default for a high-volume API.

Sliding-window counter

Blend the previous and current fixed-window counts based on elapsed time. It is approximate, memory-efficient, and smooths the boundary burst.

Token bucket

Tokens refill at a steady rate up to a capacity. Each request consumes tokens. This naturally represents “sustained rate plus allowed burst” and is often the most useful product contract.

Make the decision atomic

A token bucket stores tokens and last_refill. A single atomic operation must:

  1. read the current state;
  2. calculate the refill from elapsed time;
  3. cap it at bucket capacity;
  4. admit or reject the requested cost;
  5. persist the new token count and timestamp;
  6. return the decision and retry delay.

Doing this as separate GET and SET calls creates a race. In Redis, a Lua script or a transactional primitive keeps the state transition atomic.

elapsed = max(0, now - last_refill)
available = min(capacity, tokens + elapsed * refill_rate)

if available >= request_cost:
    persist(available - request_cost, now)
    return ALLOW

retry_after = (request_cost - available) / refill_rate
return REJECT, retry_after

Use server time when possible. Client clocks drift, and a clock moving backward should not mint tokens.

Work one request by hand

Suppose the contract allows a burst of 20 requests and refills at 5 tokens per second. The stored state is 3.5 tokens at timestamp 100.0. A request costing 4 tokens arrives at 100.3.

The refill is (100.3 - 100.0) × 5 = 1.5, so the bucket now contains min(20, 3.5 + 1.5) = 5. The request is admitted and persists 1 token at 100.3.

Now let a second cost-4 request arrive at 100.5. The bucket refills by 1 token, reaching 2. It is rejected. The deficit is 2 tokens, so the earliest retry is 2 / 5 = 0.4 seconds away.

That arithmetic reveals three implementation decisions that summaries usually hide:

  • fractional tokens require either floating-point care or fixed-point integers;
  • last_refill should advance on a rejected request, otherwise the same elapsed interval can be counted again;
  • the returned retry delay must round conservatively or a client can wake up before one full request-cost is available.

I prefer fixed-point arithmetic for a high-value limiter: store microtokens as integers and compute time in milliseconds. The range and overflow behavior can then be tested exactly.

A Redis Lua state transition

The following is deliberately explicit. The two hash fields and expiry are updated inside one script, and TIME uses the datastore clock instead of trusting every application instance.

local now_parts = redis.call("TIME")
local now_ms = now_parts[1] * 1000 + math.floor(now_parts[2] / 1000)

local state = redis.call("HMGET", KEYS[1], "tokens", "last_ms")
local tokens = tonumber(state[1]) or tonumber(ARGV[1])
local last_ms = tonumber(state[2]) or now_ms

local capacity = tonumber(ARGV[1])
local refill_per_ms = tonumber(ARGV[2])
local cost = tonumber(ARGV[3])
local ttl_seconds = tonumber(ARGV[4])

local elapsed = math.max(0, now_ms - last_ms)
tokens = math.min(capacity, tokens + elapsed * refill_per_ms)

local allowed = 0
if tokens >= cost then
  tokens = tokens - cost
  allowed = 1
end

redis.call("HSET", KEYS[1], "tokens", tokens, "last_ms", now_ms)
redis.call("EXPIRE", KEYS[1], ttl_seconds)

local retry_ms = 0
if allowed == 0 then
  retry_ms = math.ceil((cost - tokens) / refill_per_ms)
end

return {allowed, math.floor(tokens), retry_ms}

Redis guarantees atomic script execution, but atomic does not mean free: a long script blocks other work on that server. Keep the script bounded, pre-load it in production, and measure its latency separately from the application request.

Key design is part of capacity design

A key such as rl:{tenant}:{route} enables tenant and route isolation. Add a configuration version when limits can change without waiting for old keys to expire.

The expiry should outlive the time required to refill an empty bucket, but idle buckets should disappear. Without expiry, every observed identity becomes permanent storage.

Hot keys are the hidden scaling constraint. A global anonymous limit can concentrate all traffic on one key even when the rest of the Redis cluster is idle. Sharding the key increases throughput but makes the decision approximate because totals must be combined.

Decide the failure mode explicitly

When the limiter store times out, the application has three choices:

  • fail closed: reject; protects a sensitive dependency but reduces availability;
  • fail open: allow; preserves availability but can amplify abuse or cost;
  • local fallback: enforce a smaller in-process budget until shared state recovers.

The local fallback is often a practical compromise. It must be bounded, observable, and understood as approximate. Emit metrics for store latency, rejected requests, admitted fallback requests, and identities responsible for hot keys.

Multi-region is a product trade-off

A strongly consistent global limit adds cross-region latency. Independent regional limits are fast but can admit up to the sum of regional quotas. Common designs allocate a quota to each region and rebalance slowly, or keep strict limits only for costly operations.

Do not call an eventually consistent counter “global” without explaining its overshoot bound.

An explicit bound is better than “eventually consistent.” With three independent regions, each configured for 100 requests per minute, the global system can admit 300 in the worst case. Allocating 34, 33, and 33 gives a global ceiling near 100, but a quiet region strands unused capacity. Leasing quota from a coordinator improves utilization at the cost of another state machine and a behavior to define when leases cannot renew.

The HTTP response is part of the limiter

RFC 6585 defines 429 Too Many Requests and allows Retry-After; it intentionally does not specify how the server identifies a client or counts requests. The response should identify the policy without exposing internal keys:

HTTP/1.1 429 Too Many Requests
Content-Type: application/problem+json
Retry-After: 1
Cache-Control: no-store

{
  "type": "https://api.example.com/problems/rate-limit",
  "title": "Request quota exhausted",
  "status": 429,
  "policy": "write-api"
}

The IETF RateLimit header work is still an Internet-Draft as of this writing, not a published RFC. If those fields are adopted, pin behavior to the draft version you implement and do not present draft syntax as a stable standard.

Test the boundaries

The useful tests are concurrent and failure-oriented:

  • many requests arriving with one token remaining;
  • a retry arriving after the first request committed;
  • Redis latency crossing the application timeout;
  • time moving backward or far forward;
  • configuration changing while keys are active;
  • one tenant producing a hot key;
  • traffic shifting rapidly between regions.

A good rate limiter is not the one with the cleverest counter. It is the one whose fairness, overshoot, latency, and failure behavior can be explained before production explains them for you.

References