Rate limiter - token bucket, and where the counter lives

Ask these before drawing anything

• What is being protected - a public API, an internal service, or a login form? A login limiter is an abuse control and is allowed to be strict and rude. An API limiter is a product feature that customers build against, so it has to be predictable and documented.
• What is the limit ON: an API key, an end user, an IP, a tenant, or a route? This one answer decides the key, and the key decides the shard, the storage and the hot spot. Everything else on the board follows from it.
• Is the limit a hard ceiling or a fairness mechanism? A ceiling may reject. Fairness should queue or shape, and rejecting is the wrong tool.
• Must the limit be exact, or is ten percent over acceptable? Exactness is the single most expensive requirement in this design and it is almost never needed.
• May the limiter fail open? If nobody has decided this in advance, it will be decided at three in the morning by whoever is on call.
• One region or several? A globally exact limit costs a cross-region round trip on every request, which is roughly eighty milliseconds.
• What is a denied caller told? Headers, body shape, and whether the denial is billable.

Functional

• Decide allow or deny for every request before it reaches the upstream service.
• Support more than one algorithm at once: a token bucket for burst control and a sliding window counter for the hourly quota. A request must pass both.
• Limits are defined per tier and per route class, with per-customer overrides, and are editable at runtime without a deploy.
• A denial returns HTTP 429 carrying Retry-After and the remaining quota.
• Every decision, allowed or denied, produces one event for later review.

Non-functional

• Availability 99.99 percent for the decision path. The limiter sits IN FRONT of the service, so its availability multiplies the availability of everything behind it - it has to be more available than the thing it protects.
• Added latency budget: 2 ms at p99, counter round trip included.
• Accuracy: never more than ten percent over the stated limit in steady state. Exactness is not a requirement, and buying it is the classic mistake here.
• Scale to 35,000 decisions per second with no instance holding state that matters.
• A limit change is in effect everywhere within 30 seconds.

Out of scope, stated so nobody assumes it

• Authentication. The key must already exist by the time the limiter runs.
• Bot detection and WAF rules. Different signal, different system.
• Billing for overage. The limiter emits events; pricing reads them.

The traffic

DAU                           10,000,000
MAU                           25,000,000   (2.5 x DAU)
API calls per DAU per day             50
-------------------------------------------------
requests/day = 10,000,000 x 50   = 500,000,000
average QPS  = 500,000,000 / 86,400 =     5,787
peak QPS     = 5,787 x 3            =    17,361
provision at 2 x peak               =   ~35,000

The read to write ratio is the whole problem

a cache:        reads 100 : writes 1
a news feed:    reads  50 : writes 1
a rate limiter: reads   0 : writes 1

There is no such thing as a read here. Asking whether request 101 is over the limit means having counted the hundred before it, so every single decision is a read-modify-write against state that all instances share. That sentence is the reason this design is hard and the reason a local cache cannot fix it.

What that does to the counter store

atomic INCR calls/s at peak      =  17,361
  token bucket   : 1 key  touched per call
  sliding window : 2 keys touched per call, one script

Redis, simple ops, single node  ~ 100,000 /s
  => one shard carries peak at ~17% utilisation

round trip, same AZ  = 0.4 ms p50, 1.8 ms p99
latency budget       = 2.0 ms p99
  => it fits, with nothing at all to spare

Three shards are provisioned anyway, not for throughput but so that losing one costs a third of the keyspace rather than all of it.

The hot key, which sharding does not solve

largest tenant  = 8% of traffic = 1,389 QPS at peak
all of it under ONE key -> ONE slot -> ONE shard

a cluster splits KEYSPACES, never a single key.
fix: shard the key itself -
  rl:{tenant}:{0..15}, each holding limit/16
  the caller is hashed to one of the 16 at the edge
cost: the limit is now 16 buckets, so a caller that
      lands unevenly is throttled below its real limit

Gateway fleet

17,361 peak QPS / 2,000 QPS per instance =  9 instances
run 18, split across two AZs, so losing an AZ
loses headroom rather than the service

Counter state is bounded, and that is the point

active keys = 10,000,000 callers x 5 route classes
            = 50,000,000 keys

per key: name 40 B + int64 8 B + store overhead 60 B
       = 108 B

token bucket   :  50,000,000 x 108 B =  5.4 GB
sliding window : 100,000,000 x 108 B = 10.8 GB
                 (current + previous window)

TTL = 2 windows, so expired keys leave.
This figure is a function of ACTIVE CALLERS,
never of elapsed time. It does not grow with age.

provision: 3 shards x 8 GB, 1 replica each = 6 nodes

Policy, and saying out loud that it is nothing

4 tiers x 5 route classes x 200 B    =     4 KB
per-customer overrides 2,000 x 200 B =   400 KB
=> it fits in the memory of every gateway instance,
   which is why it is loaded rather than queried

Decision events, which is the unbounded one

events/day   = 500,000,000  (one per request)
per event    = 120 B
  key id 16 + route 8 + ts 8 + verdict 1
  + remaining 4 + region 2 + framing/compression pad

raw/day      = 500,000,000 x 120 B  =  60 GB/day
1 year raw   = 60 GB x 365          =  21.9 TB
5 years raw  = 60 GB x 1,825        = 109.5 TB
columnar 5:1 =                         4.4 TB / 21.9 TB

Keeping five years of every allowed request is not a design, it is an invoice.

So the retention policy is the storage design

raw, 7 days            = 60 GB x 7      =   420 GB

then roll up to hourly, and only for keys that
were DENIED at least once (about 2% of keys):
  1,000,000 keys x 24 h x 48 B         =  1.15 GB/day
  1 year                               =   420 GB
  5 years                              =   2.1 TB

steady state total  = ~2.5 TB on object storage
versus 109.5 TB if nothing is ever thrown away

The rollup keeps only denied keys because the allowed ones answer no question anybody asks. Nobody has ever opened a dashboard to find out which customer was comfortably under its limit.

The target, and why it is stricter than the service behind it

99.99 percent, which is 52 minutes a year. That is higher than the 99.9 percent the upstream API promises, and the reason is arithmetic rather than ambition: the limiter is in series with everything behind it, so the availability the customer experiences is the product of the two. A limiter at 99.9 percent in front of an API at 99.9 percent gives the customer 99.8 percent, and the limiter has then spent half the error budget of a service it was supposed to protect.

Single points of failure, named

• The counter shard holding a given key. It is the only component that cannot be made read-only or cached away, because the decision is a write.
• The policy store, but only at process start. Once loaded, limits live in memory.
• The gateway fleet itself, which is the limiter - it is a library inside the gateway, not a service behind it, precisely so that it cannot fail separately.

Replication and failover

Three counter shards, one replica each, replication asynchronous. Failover promotes a replica in about ten seconds. Asynchronous replication means the promoted replica is a few hundred milliseconds behind, so a handful of callers get more requests through than they should during a failover. That is the correct trade and it should be said out loud: a limiter that is slightly wrong for 200 ms is fine, a limiter that is unavailable for 200 ms is not.

What degrades rather than dies

• Counter shard slow, over 5 ms: a circuit breaker opens and the decision falls back to the per-instance token bucket at limit divided by instance count. The limit becomes approximate. It stays enforced.
• Counter shard down: the same, plus an alert. Worst case aggregate enforcement drifts to instance count times the limit, which for 18 instances is an eighteen-fold ceiling - bad, and still a ceiling.
• Policy store down: keep the last loaded policy in memory indefinitely. Limits stop changing. They do not disappear.
• Decision queue full: drop the events. Telemetry is the only thing on this board permitted to be lossy, and it is marked with a dashed wire for that reason.
• Total loss: a documented kill switch that hard-allows, with the blast radius written down in advance so that nobody has to reason about it during the incident.

What must never degrade

The timeout. Five milliseconds, hard, no retry. A limiter that hangs waiting on a slow counter converts a storage problem into thread pool exhaustion in the gateway, and the gateway is carrying the allowed traffic too. More outages come from limiters waiting politely than from limiters being wrong.

A request arrives at the edge gateway, which terminates TLS and routes it. Nothing has been counted yet, and that ordering is deliberate: the limiter needs an identity, so authentication runs first. Floods of unauthenticated traffic are therefore not this system to solve - they belong to the WAF in front of it.

The gateway then builds the limit key, and this is the design decision everything else falls out of. The key is the API key, the route class and the tier joined together. Limiting by IP instead would punish an entire office behind one NAT while doing nothing at all to an attacker holding a block of IPv6 addresses.

With a key in hand the limiter loads the numbers for that tier and route from an in-memory copy of the policy store, refreshed in the background. Limits are rows rather than constants because the first thing anybody wants during an incident is to raise one customer limit without shipping a deploy.

The token bucket runs first. A bucket holds a hundred tokens and refills at ten a second; the entire state is a token count and the time it was last refilled, so the refill is arithmetic performed on read rather than a timer ticking somewhere. This is the algorithm that permits bursts deliberately - a caller who has been quiet for a minute may spend a hundred requests at once, which is what a human clicking looks like.

The sliding window counter runs second, against the hourly quota. A plain fixed window would let a caller spend the full quota at 11:59:59 and the full quota again at 12:00:00, which is twice the limit inside one second. The sliding window keeps the previous window too and weights it by how much of it is still in view, removing the boundary burst for the price of one more integer.

Both algorithms need the same thing: a counter that every gateway instance shares. That counter is the expensive part of this system. The check and the increment must be a single atomic operation the store performs itself, because reading the value, deciding, and writing it back lets two concurrent requests both observe 99 and both be allowed. The cost is a network round trip on every request, including the 98 percent that will be allowed - a limiter taxes the traffic it is protecting.

Allowed requests continue to the upstream API. Denied ones get a 429 carrying Retry-After and the remaining quota, because a denial that tells the client nothing is retried immediately, and the limiter then spends the rest of the incident counting retries of retries.

Finally, every decision is dropped on a queue that nothing waits for. It drains into a usage history that is rolled up hourly for the keys that were actually denied. That history is the only mechanism by which anybody ever discovers the limits were set wrong, which makes the cheapest component on the board the one that decides whether the system is any good.

Regions

Three: us-east-1, eu-central-1, ap-southeast-1. The counter store is REGIONAL, deliberately not global. A globally exact limit would mean a cross-region round trip of roughly eighty milliseconds on every request, which is forty times the entire latency budget. So each region enforces its own share of the limit and a background job reconciles the global total every thirty seconds.

A caller that shifts traffic between regions can therefore exceed its global limit for up to thirty seconds. That is written in the customer documentation rather than hidden, because a limit nobody can predict is worse than a limit that is slightly loose.

What is stateful, and how it moves

• The counter store is the only stateful component, and its state is disposable by construction - every key has a TTL of two windows. A migration therefore does not migrate: stand up the new cluster, dual-write for two window lengths, cut reads over, drop the old one. Nothing is copied and nothing is lost that was not about to expire anyway.
• The policy store is a small relational database with ordinary backups. It is read at process start and refreshed in the background, so it can be offline for a rolling restart without affecting a single decision.
• The usage history is on object storage, partitioned by day, and never migrated - old partitions are read by the new reader or expired.

Rollout

• Ship the limiter in SHADOW MODE first: compute the verdict, emit the event, allow everything. Run it for a full week so that the usage history is real before a single customer is throttled.
• Read the shadow data and fix the limits. The first set of numbers is always wrong, and finding that out from a dashboard costs nothing while finding it out from a customer costs a great deal.
• Enable enforcement per tier, cheapest tier first, one region at a time, with a per-tier kill switch.
• Watch the denial rate rather than the error rate. A denial rate that jumps from two percent to forty in one deploy is a bad limit, not an attack, and the two look identical on a latency graph.

Rollback

• Level one, seconds: flip the enforcement flag for a tier back to shadow. No deploy, no restart, and the events keep flowing so that the incident is still observable.
• Level two: raise the limits in the policy store. In effect within thirty seconds everywhere.
• Level three: the documented kill switch that hard-allows every request. Blast radius is the upstream service, which is exactly the thing the limiter was protecting, so this one has an owner and a written pager expectation rather than being an option somebody discovers.
• There is no level four, because the limiter is a library inside the gateway. Rolling it back further means rolling back the gateway, and that is a different runbook.