Rate Limiting Algorithms

Rate limiting restricts how many requests a client may make in a period of time. It protects a service from overload, limits abuse, enforces fair use between tenants, and caps cost. Requests over the limit are rejected, usually with HTTP status 429 Too Many Requests and a Retry-After header, or queued.

A limiter needs three decisions: the key (what is counted, such as user ID, API key, or IP address), the limit (for example 100 requests per minute), and the algorithm that tracks usage. This article covers the algorithms. For the system-level design see design a rate limiter. For service-to-service throttling see rate limiting and backpressure between services.

Where limiting runs

• At the API gateway or edge, before requests reach services.
• Inside a service, for per-tenant or per-endpoint limits that need business context.
• On the client side, to avoid sending requests that will be rejected.

Token bucket

A token bucket holds up to capacity tokens. Tokens are added at a fixed refill rate. Each request removes one token (or more, for expensive requests, so a request costing 5 tokens counts as five normal requests). If the bucket has no tokens, the request is rejected.

flowchart LR
    R[Refill at rate r tokens per second] --> B[(Bucket, capacity C)]
    Q[Incoming request] --> D{"tokens at least 1?"}
    B --> D
    D -->|yes| A[Remove token and allow]
    D -->|no| X[Reject with 429]

Properties:

• Allows bursts up to capacity, then enforces the average rate r.
• State per key is two numbers: the token count and the last refill timestamp. Memory is O(1) per key.
• Tokens are not added by a background timer. On each request, the limiter computes the tokens accrued since the last timestamp: tokens = min(capacity, tokens + elapsed * rate).

Used by many API providers and by cloud services for burst-tolerant limits.

public class Main {
    /** Token bucket in integer arithmetic: tokens are stored in thousandths, so no rounding drifts. */
    static class TokenBucket {
        private static final long SCALE = 1000;
        private final long capacityMilli;
        private final long refillPerSec;
        private long tokensMilli;
        private long lastMs;

        TokenBucket(int capacity, int refillPerSec, long nowMs) {
            if (capacity < 1 || refillPerSec < 1) {
                throw new IllegalArgumentException("capacity and refill rate must be at least 1");
            }
            this.capacityMilli = capacity * SCALE;
            this.refillPerSec = refillPerSec;
            this.tokensMilli = capacityMilli;
            this.lastMs = nowMs;
        }

        synchronized boolean allow(long nowMs) {
            long elapsedMs = nowMs - lastMs;
            tokensMilli = Math.min(tokensMilli + elapsedMs * refillPerSec, capacityMilli);
            lastMs = nowMs;
            if (tokensMilli >= SCALE) {
                tokensMilli -= SCALE;
                return true;
            }
            return false;
        }
    }

    public static void main(String[] args) {
        // capacity 3, refill 1 token per second
        var bucket = new TokenBucket(3, 1, 0);
        long[] times = {0, 0, 0, 0, 500, 1000, 1000, 3000};
        for (long t : times) {
            System.out.println("t=" + t + "ms allowed=" + bucket.allow(t));
        }
    }
}

t=0ms allowed=true
t=0ms allowed=true
t=0ms allowed=true
t=0ms allowed=false
t=500ms allowed=false
t=1000ms allowed=true
t=1000ms allowed=false
t=3000ms allowed=true

The method takes the current time as a parameter, which keeps it testable and deterministic. The state is kept in integers (tokens in thousandths) because a double accumulates rounding error, which can leave a bucket just under 1.0 token when exactly 1.0 is due. synchronized makes the read-modify-write of the two fields atomic when several threads share one bucket. The time must not go backwards between calls; a production version would take it from a monotonic clock such as System.nanoTime.

Leaky bucket

A leaky bucket is a queue with a fixed size that is drained at a constant rate. Requests join the queue if there is room and are dropped if the queue is full. A worker processes queued requests at the constant rate.

• Output is smooth at exactly the drain rate, with no bursts, which suits protecting a downstream that needs a steady load.
• A burst of requests fills the queue and adds waiting time. When the queue is full, new requests are dropped while older queued requests wait for their turn.
• State: the queue (or a counter of queued requests). A variant used as a meter tracks a level that drains over time and rejects when adding a request would overflow it.

Fixed window counter

Time is divided into fixed windows, such as each calendar minute. A counter per key and window is incremented per request and reset when the window changes. Requests are rejected when the counter exceeds the limit.

• Simple and memory-cheap: one counter per key.
• Boundary problem. A client can send the full limit at the end of one window and the full limit at the start of the next, producing up to twice the limit within a short span crossing the boundary. With 100 per minute, 200 requests can arrive within a couple of seconds.

Sliding window log

The limiter stores the timestamp of each accepted request per key. On a new request it removes timestamps older than the window, counts the remainder, and accepts if the count is below the limit.

• Exact: no boundary problem.
• Memory is O(limit) per key because it stores every timestamp in the window. For large limits and many keys this is costly.

Sliding window counter

A hybrid: keep counters for the current and previous fixed windows and estimate the count in the sliding window by weighting the previous window by how much of it still overlaps.

estimated = current_count + previous_count * (1 - elapsed_in_current / window)

Example: limit 100 per minute, previous window had 80 requests, current window has 30 so far, and 15 seconds of the current minute have elapsed. Overlap of the previous window is 1 - 15/60 = 0.75. Estimate: 30 + 80 * 0.75 = 90. The request is allowed.

• Memory is two counters per key.
• The result is an approximation because it assumes requests in the previous window were evenly distributed. In practice the error is small.

Comparison

Distributed rate limiting

With many gateway or service instances, a per-instance in-memory limiter would allow N times the limit if a client's requests spread over N instances. The counters must be shared, commonly in Redis, which is fast and supports atomic operations.

Fixed window with Redis

INCR  rl:{user}:{window_id}
EXPIRE rl:{user}:{window_id} 60   (when the key is first created)

INCR is atomic, so concurrent instances do not lose updates. The window ID is the current time divided by the window length, rounded down. The key expires so old windows are cleaned up. INCR and EXPIRE are two commands, so a crash between them can leave a key without an expiry. Setting the expiry only when INCR returns 1, or running both in a script, limits this risk.

Token bucket or sliding window with Redis

These need a read-modify-write on several values (tokens and timestamp, or a sorted set of timestamps). Running the steps as separate commands is a race condition: two instances can read the same state and both allow. The solution is to run the logic atomically inside Redis with a Lua script, which Redis executes without interleaving other commands. Alternatively, use a sorted set for the sliding log (ZADD timestamp, ZREMRANGEBYSCORE old entries, ZCARD count) inside a transaction or script.

sequenceDiagram
    participant C as Client
    participant G as Gateway instance
    participant R as Redis
    C->>G: Request
    G->>R: EVAL token bucket script for key
    R-->>G: allowed or rejected, tokens left
    alt allowed
        G->>C: Forward request and return response
    else rejected
        G->>C: 429 with Retry-After
    end

Design considerations

• Latency. One Redis round trip per request adds time to every call. Options: keep a local token allowance per instance and sync periodically (approximate but cheap), or place Redis close to the gateways.
• Availability. Decide the behavior when the store is down: fail open (allow requests, risking overload) or fail closed (reject requests, risking an outage caused by the limiter). Many systems fail open for general limits and fail closed only for limits that protect against abuse or cost.
• Scale. Shard keys across Redis nodes with consistent hashing or Redis Cluster hash slots.
• Clock use. Use the Redis server's time or a single source in the script, not each client's clock, to avoid skew between instances.
• Hot keys. A single very active key concentrates load on one shard. Local pre-aggregation can reduce it.

Response headers

Clients need to know their state. Common headers are Retry-After (seconds until retry) on 429 responses and rate-limit headers showing the limit, remaining requests, and reset time. Header names vary between providers, and there is an IETF draft to standardize RateLimit headers. See API pagination, idempotency, and versioning.

Interview questions

• Why can a fixed window counter let through twice the limit? Counters reset at window boundaries. A client can use the full limit just before the reset and the full limit again just after it, so the total in a short span across the boundary can reach twice the limit.
• Token bucket or leaky bucket? Token bucket permits bursts up to its capacity while enforcing an average rate, which fits APIs. Leaky bucket outputs at a constant rate, which fits feeding a downstream that cannot handle bursts.
• How do you avoid races in a Redis-based token bucket? Execute the refill-and-consume logic in a single Lua script, which Redis runs atomically, so no other command interleaves between the read and the write.
• What happens if the rate limit store fails? The limiter must choose fail open or fail closed. Failing open keeps the service available but unprotected. Failing closed protects backends but rejects legitimate traffic.