Design an API rate limiter

01Functional requirements

A rate limiter decides whether a request may start before the application spends resources on it. We group requests by verified account and operation, such as account A creating a report. A token represents permission to perform a chosen amount of work.

1. FR1: Account-operation decisions. Decide whether the account has enough allowance for the requested operation before starting expensive work. Derive one consistent account-operation key on the server; a caller cannot choose a new identity or arbitrary key to escape the limit.

2. FR2: Permitted bursts. Support a token-bucket policy with a declared burst capacity and gradual refill. A normal request costs one token; selected expensive operations may have a reviewed higher cost.

3. FR3: Useful denials. Reject requests that lack enough allowance with HTTP 429 and documented retry guidance. Denied requests do not subtract tokens; invalid costs are rejected.

4. FR4: Managed policies. Allow authorized operators to install versioned capacity, refill, cost, and failure policies. Apply changes to existing bucket balances explicitly rather than silently treating them as new accounts.

5. FR5: Unauthenticated protection. Apply a separate unauthenticated/IP-based control to login attempts. An IP address is not a unique person: an office or mobile network may put many callers behind one address.

Out of scope

• Absorbing an unlimited network flood; protect the network edge separately.
• Billing and deduplication of business effects. Protective token accounting does not prove that a report, payment, or other application operation happened only once.

Example. Rate and concurrency are different controls. A caller sending 20 requests/second can still exhaust workers if each request runs for a minute; a separate concurrency cap limits work already in progress.

02Nonfunctional requirements

These are independently chosen exercise assumptions to validate, not measured production guarantees.

1. NFR1: Decision latency. At least 95% of measured regional checks must add less than 5 ms, from the gateway call through the completed store decision. Benchmark with the intended replication settings and realistic uneven traffic across keys.

2. NFR2: Peak decision capacity. Sustain the assumed peak of 100,000 checks/second. Capacity testing must execute the complete refill/compare/consume operation; fitting the bucket records in memory is not sufficient.

3. NFR3: Burst and refill contract. Use capacity 40 and refill 20 tokens/second, with normal request cost one. An idle full bucket permits 40 immediate requests and then refills gradually; it does not promise exactly 20 admissions in every clock-aligned second.

4. NFR4: Owner-level accounting. Two concurrent requests must never spend the same stored allowance at the store responsible for that key. Refill, comparison, subtraction and save must happen as one indivisible operation. This does not by itself protect against losing a committed subtraction when switching to a replica that has not received it.

5. NFR5: Strict global accounting. If the strict-global extension is required, regions together must never be entitled to spend more than the one global budget. For a 40-token budget, grants of 15, 15 and 10 tokens fit; three grants of 40 do not. Do not reissue an old region’s allowance while it might still spend that allowance.

6. NFR6: Timeout behavior. Every timed-out decision must retain an uncertain outcome or invoke that endpoint’s reviewed fallback. A missing response must never silently become permission; expensive exports and login protection can require a stricter fallback than cheap reads.

7. NFR7: Policy propagation. Assume ordinary approved policy changes reach the regional bucket stores within 30 seconds. Check the installed version on each store. For an urgent reduction, confirm that required stores applied it before treating the new limit as effective.

Accounting scope. The baseline provides account-operation protection at one owning store; regional buckets are not automatically a global contractual quota. Confirm whether the stricter extension is required. Three independent 40-token regional buckets permit a combined burst of 120.

03Back-of-the-envelope Estimates

Size the records and the decision work separately. The records can fit in memory while the code checking them is already too busy.

1. Bucket records. Assume one million active account-operation pairs, each using 100 bytes. 1,000,000 × 100 = 100 MB of raw state. Add record encoding, expiry data, policy records, extra copies and memory-allocation overhead.
2. Safe expiry. An empty bucket with capacity 40 and refill 20 tokens/second becomes full after 40 ÷ 20 = 2 seconds without spending. Delete an inactive bucket only when treating it as full would match its real balance. Deleting an active partially empty bucket earlier would give the caller extra credit.
3. Network payload. At 100,000 checks/second and 200 bytes per request plus response, payload is 100,000 × 200 = 20 MB/second, before protocol overhead. Measure the complete refill-and-spend call, not only a simple key lookup.
4. Decision machines. Suppose testing shows one bucket-store machine handles 25,000 complete checks/second. Four provide 100,000/second with no spare. Five have the same nominal total after one loss, but only if current records can be recovered and moved safely. That arithmetic does not itself implement failover.
5. An exact history alternative. Recording 100 accepted timestamps for each of one million keys means 100 million entries. At eight bytes per timestamp, timestamps alone use 800 MB. A token bucket stores a balance and time instead, because it implements a different burst-and-refill policy.

04API Design and Retry Contracts

The API gateway is the server that first checks the caller’s identity and maps the route to an operation such as report creation. It asks the limiter whether to start that work. The caller cannot choose its own account or token cost.

POST /internal/rate-decisions
Content-Type: application/json

{"verifiedAccount":"A","operation":"report.create","cost":5,"policyVersion":7}

{"allowed":true,"remaining":35,"retryAfterSeconds":0,"policyVersion":7}

1. Build the key. The gateway combines verified account A with the standard operation name report.create. Requests using equivalent routes must reach the same account-operation bucket. Otherwise changing the URL could create a fresh allowance.
2. Set the cost. The installed policy charges five tokens for this report. With a full 40-token bucket, the example returns 35 remaining. policyVersion:7 identifies the reviewed configuration used for the decision, not a client-selected exemption.
3. Run one decision. The internal checkAndConsume(verifiedAccount, operation, cost, policyVersion) call returns whether allowed, the remaining balance and retry guidance. Only an allowed result starts the report. The report’s final response is a separate outcome.
4. Explain denial. The public response is 429 when the bucket lacks tokens. Denial does not subtract tokens. For a separate one-token example with 0.2 tokens and refill 2/second, the missing 0.8 takes 0.4 seconds; an integer Retry-After of 1 second avoids advising an earlier retry.
5. Reject invalid costs. A negative cost must not add allowance. Derive allowed costs and keys on trusted code, rather than accepting arbitrary caller fields.

05Data Model and Access Paths

The limiter reads a policy and changes one bucket. The bucket store is the main database responsible for that account-operation balance: every API server must use the same stored balance when making a decision.

• Policy records tell the gateway and bucket store the capacity, refill rate, cost and outage rule. A version makes a configuration change recognizable.
• Bucket records retain the remaining tokens and the time used for the last refill. Use store-controlled time; if the clock moves backward, earn no negative tokens and do not move the saved timestamp backward.
• Retained operation results are needed when a retry must recover the same accounting decision. Store the account, operation ID, result and expiry for the documented retry period. The report application separately stores its own business result.
• Policy changes must update existing balances deliberately. For example, lowering capacity requires clamping a larger stored balance; it must not silently recreate every customer with a new full bucket.

06Baseline: Make the token decision atomic

First make two API servers share one bucket correctly. A token represents permission to do work. Capacity limits how much permission can accumulate; refill adds permission with elapsed time.

Follow one decision

1. The gateway authenticates the account, selects the operation name and assigns its configured cost.
2. The bucket store loads that account-operation record and obtains current store-controlled time.
3. It computes newBalance = min(capacity, oldTokens + elapsedSeconds × refillRate). The minimum prevents idle time from accumulating unlimited credit.
4. It compares the balance with the cost. If enough tokens exist, it subtracts the cost; otherwise it denies without subtracting.
5. It saves the balance and refill time, then returns the decision. Steps 2–5 execute as one indivisible store operation, called an atomic operation. No other request for this key may intervene after the check but before subtraction.
6. The gateway starts application work only after an allowed response. It returns 429 for a known denial.

For a smaller arithmetic example, start with one token, capacity 10 and refill 2/second. After three seconds the store computes min(10,1 +3×2) =7. Five simultaneous one-token calls take turns through the complete operation and leave two. If each server separately read seven and saved its own subtraction, several could spend the same balance.

A database transaction or store-side script can provide the atomic operation. Copying changes to another machine is a separate question: if a replacement has not received a subtraction, failover can restore spent tokens. If the quota must never restore acknowledged tokens, recover every acknowledged subtraction before using the replacement and prevent the old writer from accepting more decisions. Otherwise pause those checks or explicitly state that failover can restore some spent allowance; an atomic script alone cannot provide that recovery guarantee.

Pick the required rule before the algorithm. These mechanisms do not promise identical admissions.

07Evolution: Add a hierarchy without hiding its approximation

First test a larger bucket-store machine if CPU or network is the limit. Extra memory does not make one very busy key’s decisions independent.

Spread many different accounts

1. Divide bucket records among store machines. A hash of the verified account-operation key selects its owner, so all servers send that key’s decisions to the same machine.
2. Keep API servers free of the shared balance. Adding an API process must not create a new full allowance.
3. Add cheap local flood protection before the shared check, and a separate limit on expensive jobs already running. These protect different resources. Fifty local processes each granting 40 tokens could admit 2,000 requests; they are not a single 40-token quota.
4. Distribute reviewed policy versions and measure installation. Ordinary changes must reach owners within the 30-second target; urgent reductions need confirmation that each required owner applied them.

If the product needs one budget across regions

1. Three independent 40-token buckets permit 120 immediate requests. Choose one global decision service if every request must use one budget and the extra network delay is acceptable.
2. Alternatively, let a global service reserve limited portions for regions. For example, grants of 15, 15 and 10 divide a 40-token budget. A region may spend only its reserved portion. These grants are called token leases.
3. The global service records each grant ID, its region and reserved credit. If a region fails and its remaining credit is unknown, leave that credit reserved; do not give it to a replacement. Reuse it only after the old region can no longer spend it. A local timeout or expiry entry alone does not stop the old region’s store from accepting requests.
4. Preserve the same accounting limits for newly refilled credit. If that protocol cannot be shown, use one authority or state the approximation instead of calling independent buckets a strict global quota.

08Failure and Recovery Scenarios

Use request R7, account A’s report costing five tokens, to test each boundary:

1. Known allow or deny. The gateway sends R7’s account-operation check to the bucket owner. An allowed result starts the report; a denied result returns 429 without starting it.
2. Lost limiter reply. The store may have subtracted tokens before its reply disappeared. A repeated protective check may spend twice conservatively. If strict accounting requires one spend, the store saves R7’s operation ID and decision with the subtraction, then returns that saved decision on retry.
3. Lost report reply. Spending a token does not prove one report was created. The report service needs its own stable request ID and saved report result, so a repeated application request recovers that report.
4. Unavailable bucket store. Apply the endpoint’s reviewed policy: a cheap public read may get a small short-lived local allowance; an expensive export may reject; login protection may require severe fallback throttling. Never convert a missing response into unlimited permission.
5. Store failover. Check whether the replacement contains acknowledged spending before routing decisions to it. A script that was atomic on the failed machine cannot restore missing state on another machine.
6. Recovery burst. Give clients retry guidance, cap waiting calls and vary retry delays randomly. This jitter prevents all rejected clients from returning together at the same instant.

09Trade-offs and Validation

Explain the shared balance and the resource it protects before adding more limiters.

• Measure the decision: check latency, allowed and denied counts, installed policy versions and calls concentrated on one key.
• Measure dependency failures: separate store errors, emergency fallback use and work delayed by failover from ordinary quota denials.
• Measure actual protection: watch running exports and downstream saturation, not only accepted calls/second. At 20 requests/second lasting a minute, about 1,200 jobs can occupy workers.
• Protect administration: authorize policy edits, audit changes and limit configuration requests. A bad reduction can reject healthy customers just like an outage.
• Protect tenant data: do not expose one account’s usage through another account’s responses or metric labels.

Close with the small example: three seconds refill the balance to seven, five requests leave two, and a lost reply makes the accounting outcome uncertain. State which record resolves that uncertainty and whether the regional limit is approximate or globally coordinated.