Rate Limiting Across Multiple Servers

01 The idea

The problem this lesson solves

One API client may send three accepted requests per minute. You enforce this with a counter inside the application and the test passes. Then you deploy a second app instance. Five requests alternate between the two instances and all five are accepted. The bug is not in incrementing an integer; it is in where the decision lives. This lesson develops a rate limiter from that failure, then compares the algorithms and contracts needed to make the behavior precise.

You need basic programming and arithmetic. This module introduces the design vocabulary; the next module develops HTTP step by step.

02 Worked example

Share a three-request budget across two servers

03 The method

Understand the mechanism

Define what the limit actually counts

A rate limit is a policy about identity, resource and time. “Three requests per minute” leaves several questions unanswered. Is the identity a user, API client, IP address or organization? Are reads and writes charged equally? Does an attempted request consume budget, or only a request that reaches the protected operation? Is the minute a wall-clock window or any rolling interval?

For the first example, count accepted requests from one authenticated client in a fixed 60-second window. The budget is three. Attempts four and five are denied before they call the protected API. If admitted work later fails, this policy still counts the admission; refunding tokens would be a separate design with its own races.

Identity must be stable across app instances. A client-supplied arbitrary account id is not sufficient unless authenticated and authorized. IP-based limits can protect anonymous endpoints, but many legitimate users may share an address and one attacker may use many addresses. A service may combine per-client and global limits for different goals.

The limiter is also different from a concurrency limit. Ten requests per second can still create hundreds of simultaneous operations if each takes a long time. A concurrency limit caps work currently in progress; a rate limit controls admissions over time. Protecting a dependency may require both.

Fixed windows and the boundary burst

A fixed-window limiter associates a counter with a client and window number, such as floor(time/60). During that window, an atomic decision admits requests while the count remains within the policy. Old window records can expire after they are no longer needed.

With a budget of three, requests at 10, 20 and 30 seconds pass; a request at 40 seconds is rejected. But consider three requests at 59.9 seconds and three at 60.1 seconds. They belong to different fixed windows, so all six can pass within roughly 0.2 seconds. The implementation has obeyed a fixed-window contract and violated a stricter “at most three in any sixty seconds” contract.

This is why algorithm choice follows the wording of the requirement. A fixed window is inexpensive and easy to explain. It can be appropriate when bursts around boundaries are acceptable. It should not be advertised as exact rolling-window enforcement.

An implementation that runs INCR and then sets expiration in a separate request also needs to consider a crash between them. The counter might be created without its intended expiry. Combine the relevant state transition and expiry initialization in a server-side atomic operation, and define how window identity is computed across callers.

Sliding logs, weighted windows and token buckets

An exact sliding-log limiter retains admission timestamps. At time t it removes timestamps outside the chosen interval, counts the survivors and admits only if budget remains. It can enforce a rolling-window policy precisely under its stated boundary convention. Its state and work grow with the number of retained events, so it may be expensive for high-volume identities.

A sliding-window counter approximates the recent load using a current bucket and a weighted part of a previous bucket. It uses less state but loses exact information about when requests arrived within the earlier bucket. The approximation error matters near bursty boundaries; call it an approximation rather than presenting it as equivalent to a log.

A token bucket has capacity B and refill rate r tokens per second. Before an admission, compute tokens = min(B, old_tokens + r×elapsed). If at least one token remains, subtract one and admit. Otherwise reject or wait according to policy. With B=3 and r=1/s, three immediate requests can pass, a fourth immediate request cannot, and another request can pass after one second if no others consume the refill.

The bucket permits bursts up to its capacity while limiting longer-term admission rate. Over an interval of length t, a full starting bucket can permit approximately B + r×t admissions, subject to discrete decisions and the implementation. It is not the same contract as “no more than B requests in every interval of length t.”

Make the shared decision atomic

Return to two app instances, A and B. Each private counter starts at zero. Round-robin arrivals 1,3,5 reach A and 2,4 reach B. A accepts three and B accepts two, so five requests consume a supposedly shared budget of three. Sticky routing may hide this until routing changes or an app restarts.

Both instances need to consult a shared authority or a designed distributed quota-allocation scheme. For the simple shared-counter version, the decisive operation must combine checking the budget and changing the state. A separate GET followed by SET is unsafe: A and B can both read count=2 and both conclude that one slot remains.

An atomic increment-and-compare can count every attempt, returning whether the resulting value is within the budget. An atomic check-and-increment can instead count admissions only. Both can enforce a fixed-window admission cap, but they have different counter meanings. Define what the stored value represents before using it in metrics or retry guidance.

A token bucket similarly needs one atomic read-refill-deduct-write transition for an identity. Making only the final write atomic is insufficient if the refill decision used stale state. The authoritative store’s failure and replication behavior then become part of the limiter’s guarantee.

Decide what happens when the limiter cannot answer

A timeout contacting the limiter is not proof that the client exceeded its quota. It is a failure to obtain a decision. Failing open admits the request despite that uncertainty; failing closed refuses or defers it. Choose according to the operation’s cost and risk, and describe the user-visible behavior.

A public search endpoint may prefer a degraded local cap during a limiter outage to preserve partial service. An expensive irreversible operation may prefer rejection until it can obtain a trustworthy decision. A service error is often more honest than a quota-exceeded response when the quota itself is unknown. Do not teach clients to interpret infrastructure failure as normal budget exhaustion.

When a client is actually throttled, HTTP 429 communicates too many requests. Retry guidance should reflect the algorithm and policy. A fixed-window reset time may be known; a shared token bucket’s future availability can change because other requests consume tokens. Clients still need bounded retries with backoff and jitter.

The limiter can itself become a bottleneck. A shared store adds a network hop and concentrates state. Local quota allocation can reduce that cost, but allocated tokens may be stranded on quiet instances or overshoot a desired global policy unless the allocation protocol accounts for them. This is an explicit performance-versus-precision decision.

Verify behavior under races and failures

Test more than a sequential series of requests. Start many concurrent attempts when exactly one admission remains and verify that only one wins. Send requests through different app instances. Cross a window boundary. Restart an app. Delay the limiter response until the caller times out, then retry.

Separate admissions from completed business work in measurements. Three admissions do not guarantee three successful API operations. Likewise, a denied attempt should not have already triggered the expensive side effect. The limiter belongs before that side effect, while authentication and request validation may need to happen first to choose the correct identity and cost.

Observe allowed, denied and decision-error counts separately, plus decision latency and store saturation. A rise in denied requests may mean abuse or a policy that is too strict. A rise in decision errors suggests an availability problem. Combining them into one rejection metric hides the difference.

The design is defensible when you can state the exact policy, prove that concurrent requests share one valid decision boundary, and explain what happens when that boundary is unavailable. The word “distributed” alone supplies none of those guarantees.

policy: 3 requests per client per fixed 60-second window
identity: authenticated API client
state: counter(client, window), expires after window
decision: atomic_increment(counter) <= 3
on denied: return 429 with retry guidance
on counter timeout: apply the documented failure policy

budget = 3
routes = ["A", "B", "A", "B", "A"]
local = {"A": 0, "B": 0}
local_allowed = shared_allowed = shared_count = 0
for server in routes:
    if local[server] < budget:
        local[server] += 1
        local_allowed += 1
    if shared_count < budget:
        shared_count += 1
        shared_allowed += 1
print(f"local_allowed={local_allowed}")
print(f"shared_allowed={shared_allowed}")
print(f"shared_denied={len(routes)-shared_allowed}")

local_allowed=5
shared_allowed=3
shared_denied=2

05 Cheat sheet

Review the decisions

Use this table to explain the mechanism and its limit without memorizing a product name.

06 Where & why

Check the primary references

Use official references for protocol and implementation details. The questions here are teaching prompts.

07 Interview questions

Explain the reasoning out loud

Answer before opening the explanation. The questions progress from vocabulary to decisions and failure behavior.

08 Practice problems

Practice a new case

Solve the new cases before revealing hints. Complete worked solutions follow the set.

Worked solutions