Your rate limiter is approximate by design: windows, one writer, and where the count lives

Two requests arrive at the same millisecond. Both run the same four lines: read the counter, compare it to the limit, decide, write the counter back. Both read 99. Both compare 99 < 100 and find it true. Both write 100. Both are admitted. The counter is now 100, one request short of the truth, and the endpoint that was supposed to accept one hundred calls has accepted one hundred and one.

Do that once and nothing happens. Do it under a burst — which is the only time a rate limiter matters — and the arithmetic gets ugly fast. In the small harness at the end of this post, two hundred concurrent requests against a limit of ten were all admitted, and the counter finished at 4. Not 10. Not 11. Four. The limiter did not merely let traffic through; it also lost track of how much it had let through, so every subsequent decision was made against a number that had nothing to do with reality.

That failure has a name — read-modify-write without atomicity — and most engineers know it. What is less often noticed is that fixing it is not enough. A limiter also has to decide where the count lives when your code runs in twenty places at once, what a "window" means when the clock you read is not the clock your neighbour reads, who gets to choose the key, and which way it fails when the counter store is down. Those are design decisions, and unlike the race they cannot be fixed later with a mutex.

Everything below is about the enforcement layer, not the policy layer. What the limit should be, how a daily allowance refills, and how to explain it to a user is a product question I have written about separately. This post is about the machine that decides yes or no, and the ways it lies.

One note on evidence, because it matters for the numbers: where I quote a platform's behaviour, it is from that platform's documentation and I say so. Where I give a figure, it is either arithmetic you can redo or output from the harness in this post, which is included so you can run it yourself. I have not measured anyone's production latency and I do not invent any.

A limit is a promise about an interval, not a number per window

"One hundred requests per minute" sounds like one decision. It is two, and they are independent:

• The sustained rate — the long-run average the client is allowed. For 100 per 60 seconds, that is 1.667 per second.
• The burst — how much of that allowance the client may spend at once after being quiet. This number is not in the sentence "100 per minute", and every implementation picks one for you.

Once you separate them, the guarantee becomes writable. A limiter with sustained rate r and burst B promises that in any interval of length t, no more than B + r·t requests are admitted. The burst term is what makes short intervals survivable; the rate term is what makes the upstream bill predictable. Neither is optional, and a limit specified as a single number is a limit whose burst nobody chose on purpose.

A limiter also makes two promises that are not about numbers at all, and they are the ones clients actually depend on:

The third one is the whole problem of edge computing in one sentence. On a single server, the count is a variable and the promise is trivial. On a serverless platform, the count is either a remote service that adds latency to every request, or a local copy that is wrong by design.

Fixed windows are cheap and wrong at the boundary

The simplest limiter keeps one integer per key per window:

window = int(now // 60) if counts.get((key, window), 0) < 100: counts[(key, window)] = counts.get((key, window), 0) + 1 admit() 

It is O(1) memory per key, one comparison, no per-request log, and it has a hole exactly the size of one window's allowance. A client that sends 100 requests at 59.8 seconds past the minute and 100 more at 60.0 seconds is inside two different windows, both under the limit, and has sent 200 requests in 0.4 seconds. In my harness that pattern was admitted 200 times out of 200 against a 100-per-minute limit.

This is not a rare edge case. It is the normal behaviour of any client that retries in a loop or batches on a schedule, and it produces the pattern every on-call engineer has seen at least once: a spike at the top of the minute that looks like an attack and is in fact a well-behaved client doing everything the documentation told it to do.

You can narrow the hole — subtract the previous window's count, shorten the window, add a second shorter window — but each of those is an approximation with its own boundary, and the honest way in is to pick an algorithm whose bound you can write down.

Two algorithms that fix the boundary without keeping a log

Sliding window counter. Keep two integers per key: the count in the current window and the count in the previous one. Estimate the trailing window as prev·(1−f) + curr, where f is the fraction of the current window elapsed. Memory is two numbers instead of a list of timestamps, and the estimate is smooth instead of a step.

Its error is bounded and worth knowing precisely. Suppose the limit is L per window and the previous window's L requests all happened just before the boundary, while the estimator assumes they were spread evenly. At fraction f into the new window, the estimator believes L(1−f) of them are still inside the trailing window, so it will admit up to L·f more. The over-admission is therefore at most L·f, and the worst case in any trailing window is L(1+f) — under 2L, strictly better than the fixed window, and never exactly L. If a vendor tells you their sliding-window limiter is exact, ask what happens in that placement.

GCRA, or one timestamp per key. The generic cell rate algorithm stores a single number: the theoretical arrival time, the moment the next request would be due if the client kept exactly to the sustained rate. With emission interval T (window divided by limit) and burst tolerance τ, the decision is:

next = max(tat, now) + T admit if next - τ <= now tat = next 

Three lines, one 64-bit value per key, and an exact bound: in any interval of length t, at most floor((t + τ)/T) + 1 requests are admitted. With T = 600 ms and τ = (B−1)·T, a client may burst B requests after idling, then runs at 1.667 per second forever. No window boundary exists, so there is nothing to burst across.

The bound is worth checking rather than trusting, so I checked it: 10,865 requests offered at a mean of three per second against a cap of 1.667 per second, over one simulated hour. GCRA admitted 5,974 against a theoretical 6,001, and no interval of up to sixty seconds contained more than floor((t + τ)/T) + 1 requests. The busiest ten seconds held 20, against a bound of 21. If you are picking an algorithm today and want one integer per key, this is the one to pick.

Where the count lives: five placements and their failure modes

Now the part that no local test exercises. The count has to live somewhere every instance can reach, and each place trades a different thing away.

Two rows deserve a sentence each.

The KV row is the trap that catches people who assume a key-value store is a counter. Cloudflare's KV documentation is explicit that reads are eventually consistent, that changes may take up to sixty seconds or more to be visible in other locations, and that it "is not ideal for applications where you need support for atomic operations or where values must be read and written in a single transaction". A counter built on read-modify-write against that is not a limiter; it is a random number generator with extra steps.

The platform's own limiter row is the one to understand before you build anything. Cloudflare's Rate Limiting API documents that limits apply separately in each Cloudflare location, that "requests can exceed your configured limit while counts update in the background", that sharing a namespace across Workers "does not make the combined limit strict", and that the number of Workers does not determine how many requests can exceed the limit. The period must be 10 or 60 seconds, delta lets you weight an expensive call as ten cheap ones, the decision uses the count before the call, and a refused call does not add to the count. What it buys is a check that costs almost nothing and catches floods; what it does not buy is a number you can put in a contract.

That is not a criticism. It is the correct trade for the first layer, and the documentation says the quiet part out loud: for one strict limit across locations, implement the limiter on Durable Objects.

Read, decide, write: the race you cannot see with one client

Here is the interleaving, with a two-hundred-thread harness and a limit of ten:

Both admitted, count incremented once. In the harness, 200 concurrent requests against a limit of 10 produced 200 admissions and a final counter of 4 — because the lost updates compounded: each writer wrote a value derived from an ever-staler read, so the counter went down relative to the number of admissions. The version that does the compare and the increment inside one critical section produced 10 admissions and a counter of 10.

Two things about this are worth internalising.

await is not a lock. The bug does not require threads. In JavaScript, every await is a yield point: the event loop is free to run the next request's handler while yours is waiting for a database round trip. A single-threaded runtime makes the interleaving narrower, not impossible — and narrow races are worse, because they pass your tests and appear at 3 a.m. under load.

A retry does not fix it. If your client retries the refused request, and the refusal was wrong in the other direction — the counter was incremented but the response failed — you now have the duplicate-execution problem, which is a different article. Keep them separate: the limiter decides admission, and idempotency keys make the admitted work safe to repeat. One cannot substitute for the other.

Making the update atomic where the platform lets you

The general rule is one statement, or one lock, per decision. Three concrete forms, in order of how often I reach for them.

A conditional update in SQL. The entire decision is a single statement whose affected-row count is the answer:

INSERT INTO limiter (key, window_id, n) VALUES (:key, :window, 1) ON CONFLICT(key) DO UPDATE SET n = CASE WHEN limiter.window_id = excluded.window_id THEN limiter.n + 1 ELSE 1 END, window_id = excluded.window_id WHERE limiter.window_id <> excluded.window_id OR limiter.n < :limit RETURNING n; 

One row returned means admitted; zero rows means refused. There is no window between the compare and the write, because there is no window — it is one statement. Note that the WHERE clause on the DO UPDATE is what makes it conditional; without it you have an unconditional upsert that increments past the limit and a limiter that never refuses.

A batch() when you need two statements. D1 has no interactive transactions — you cannot BEGIN, read, decide, and COMMIT from application code. What it has is batch(), which runs several statements as one transaction. Cloudflare's own concurrency guidance is blunt about the reason: a D1 database "is inherently single-threaded, and processes queries one at a time", and one that is overloaded queues requests and then returns an overloaded error. Your atomicity comes from that single writer, not from your code being clever.

A single-writer object. Route every decision for a key to one object that owns it, and the read-modify-write stops being concurrent at all. That is the next section, and it is the only form that stays strict when the traffic is spread across the planet.

One writer per key, and the clock problem disappears

Cloudflare's Durable Objects give each object a globally unique name, a single thread, and storage colocated with the compute that owns it. Sending every request for key to idFromName(key) means every decision about that key is made by the same object, one at a time, in front of the same storage. The race is not prevented; it is made impossible by the topology.

The documented subtlety is what "one at a time" means for await. The runtime applies input gates: while a storage operation is executing, no events are delivered to the object except storage completion events. That makes the classic interleaving safe — with one caveat the documentation states plainly: two concurrent calls initiated by the same event, without awaiting the first, still interfere, because there is no incoming event to defer between them. The gates protect you from other requests, not from your own Promise.all.

Here is a limiter object that keeps GCRA state, with the load in the constructor so the first request does not race the load:

import { DurableObject } from "cloudflare:workers"; export class KeyLimiter extends DurableObject { private tat: number | undefined; constructor(ctx: DurableObjectState, env: Env) { super(ctx, env); // Load before the first request is delivered, not inside it. ctx.blockConcurrencyWhile(async () => { this.tat = (await ctx.storage.get<number>("tat")) ?? undefined; }); } async check(emissionMs: number, burstMs: number) { const now = Date.now(); const next = Math.max(this.tat ?? 0, now) + emissionMs; const allowAt = next - burstMs; if (allowAt > now) { return { admit: false, retryAfterMs: allowAt - now }; } // No await between the read above and this write: the decision is // one synchronous step. The output gate holds the response until // the write commits, so a crash cannot admit without counting. this.tat = next; void this.ctx.storage.put("tat", next); return { admit: true, retryAfterMs: 0 }; } } 

Three properties that matter more than the code:

• The decision is synchronous. this.tat is read, compared and written with no await in between, so no other event can be delivered mid-decision. The put() is not awaited, and does not need to be: output gates hold the outgoing response until the storage write completes, and drop the response if the write fails. Do not put a fetch() or a KV read in the middle of that critical section — the gates cover storage, not arbitrary I/O.
• The clock is single-sourced. Every reading of Date.now() for this key comes from the same object on the same machine. The TAT is a wall-clock millisecond value compared only against that same object's clock, so skew between data centres never enters the decision. This is the second reason to route by key rather than replicate counters.
• Idle keys have to be reaped. An object hibernates after being idle and its in-memory state goes with it — the storage value is what survives. Persist the TAT (as above) and delete keys that have been idle longer than a window, either on a timer with an alarm or from the Worker when it sees retryAfterMs === 0 after a long gap. Unreaped keys are the difference between a limiter and an unbounded table of timestamps.

And the ceiling: an individual Durable Object is inherently single-threaded, with a documented soft limit of about 1,000 requests per second and an overloaded error when its queue fills. That number is per key, not per service — which is exactly the point. One abusive key saturates one object and nobody else notices. A key that legitimately needs more than a thousand checks a second needs sharding: key + ":" + shard, with each shard holding limit/shards and a documented over-admission of up to one shard's allowance. Sharding is the price of strictness, and it is worth paying only for the few keys that need it.

The clock is part of the limit

Every window algorithm needs a definition of now, and there are four clocks in the room: the client's, the edge's, the store's, and yours in the logs. They disagree.

Never take the window from the client. A Date.now() in a browser is user-editable, and a device with a clock five minutes fast spends its allowance in a window nobody else is in. Send the server's resets_at and render a countdown from it.

Derive the window from one integer, not from formatted time. Math.floor(Date.now() / 1000 / 60) is a window id; "2026-11-15 04:00" in a timezone is a bug waiting for a DST change. The integer is comparable, sortable, shardable and timezone-free; the string needs a parser on both sides and a rule about which offset wins.

Wall clock for windows, monotonic for durations. Date.now() can jump backwards when the host's clock is corrected; performance.now() cannot, but it is meaningless across processes. Use wall clock only where you must (the window id, the Retry-After), and use monotonic time for anything you measure — including how long the limiter itself took.

One authority per key. If two instances compute different now values for the same key, one of them will occasionally see a window the other has already left, and the key gets two allowances. Routing by key solves it for free; a shared counter store does not, because each caller still brings its own clock.

The key is a choice, and the attacker gets to make it

Who is "one client"? Every limiter answers this, and the answer is where most of the collateral damage lives.

IP is the wrong default, and Cloudflare's documentation says so: it is "not recommended to use IP addresses or locations (regions or countries), since these can be shared by many users in many valid cases". A mobile carrier NAT, a school, an office, a privacy proxy — all one IP, all one allowance. If your limit is 100 per hour per IP, a classroom of thirty students gets three requests each.

User or token is the right key when you have one, and the endpoint's own auth decides when you do. Keying on a verified user id also means the limiter runs after authentication, which is the only point where the key is trustworthy — an unauthenticated key is a number the attacker chose.

The key space is an attack surface. A limiter stores state per key, so a client that can invent keys can grow your table without bound. Arithmetic, not guesswork: a Worker isolate has 128 MB of memory per isolate, which the documentation notes includes the JavaScript heap and WebAssembly allocations, and the V8 cost of a map entry with a string key is roughly 100–150 bytes including the string header, the slot and the value — that figure is an estimate, and a heap snapshot in DevTools is what turns it into a measurement. At that estimate, a million keys needs 100–150 MB, which is the entire isolate budget and then some. The bound is around a hundred thousand keys per isolate before the limiter is the reason your Worker dies.

Two remedies, both honest:

• Cap the table and evict. A fixed-size map with FIFO eviction (a JS Map iterates in insertion order; LRU needs a re-insert on hit) keeps memory flat and slightly over-admits for keys that were evicted. Say so in the docstring, because the next person will wonder why the limit is soft.
• Bucket the keys. Hash the key into a fixed number of counters (hash(key) % 4096). Memory becomes constant and unrelated clients share a bucket, so the effective limit is the bucket's. That is fine for flood protection and unacceptable for billing — decide which one you are building.

Salt the key before you log or store it. ip_hash in an event table is a pseudonym, not a secret; an unsalted SHA-256 of an IPv4 address is reversible in seconds by enumeration. Use a per-deployment salt and keep it out of the logs.

When limits overlap, say which one fired. A typical stack has per-user, per-route, per-IP and global limits, and the effective limit is the minimum. Return that in the response — RateLimit-Policy: user=100/60s or a field in the body — or your support tickets will be "it says 100 but it stopped at 7" forever.

The count store is a dependency: pick a direction to fail

The moment the counter lives in a remote service, the limiter can fail. "Fail closed" and "fail open" are both defensible; choosing per endpoint is the design.

Three rules make the failure survivable whichever way you choose:

Give the check a deadline. Every remote decision gets a timeout (50 ms is a reasonable starting point for a same-continent hop; measure yours) and a fallback that is local and cheap — the per-isolate counter from the first layer, with its own much looser limit. A limiter that waits for a slow store has become a latency amplifier for every request, including the ones it would have admitted.

Return 503 when you are the problem. A 429 says "you are sending too much"; a 503 with Retry-After says "I cannot decide right now". Clients, SDKs and CDNs treat those differently, and the difference is the one you will need to read in the logs at 3 a.m.

Log the fallback. A counter named limiter_fallback_total is the earliest warning you get that the strict path is degraded. Without it, the limiter silently becomes a per-instance approximation and the only symptom is an invoice.

Cold starts arrive exactly when the limiter matters

A rate limiter is mostly idle and then suddenly busy. That is the same shape as a cold-start problem, and the two meet at the worst possible moment: the burst that made new instances start is also the burst the limiter has to decide about.

What actually starts, in order: the isolate evaluates your module (top-level code, imports, any await at module scope), then the request runs; a Durable Object additionally instantiates the class and opens its storage before the constructor finishes. Cloudflare caps Worker startup at one second, which is generous for a bundle and ruinous for a top-level await fetch() of a config you could have inlined.

The mitigations are unglamorous:

• Keep module scope cheap. No network, no parsing of large JSON, no building of big lookup tables at import. Compute on first use, memoise in the module.
• Keep the bundle small. Every import is code the runtime must load on a cold start, on a machine that is starting many isolates at once.
• Never let the limiter throw. A cold start that fails the check should fall through to the documented fallback, not return a 500 that reads like an outage. Wrap the decision in a try/catch that logs and degrades by policy.
• Warm deliberately. If you know a campaign starts at a fixed time, send a request thirty seconds early to the keys you are about to defend. It costs one request and removes the coldest second.

The 429 is a contract with a client you do not control

The refusal is the most important response your limiter writes, and it is usually the least designed.

HTTP/1.1 429 Too Many Requests Retry-After: 12 RateLimit-Policy: user=100/60s Content-Type: application/json {"error":"rate_limited","scope":"user","retry_after":12} 

• Retry-After in seconds, or an HTTP-date, and never a number without a unit in a body the client has to parse itself. Jitter it slightly across clients or every one of them returns at the same instant, on the second, forever.
• Do not leak what the key protects. "Rate limited because the code exists" and "rate limited because it does not" are different facts, and the difference is an enumeration oracle. Same response, same timing, both cases.
• Do not confuse "blocked", "invalid" and "unavailable". Three different statuses, three different client behaviours: back off, stop, retry later.
• Make refusals uncacheable. A 429 that a CDN caches is an outage that outlives its cause.
• Count the refusal where the work would have been counted. A limiter that refuses before authentication, and then charges the request against an anonymous bucket, is one that can be triggered for free by anyone.

What to log per decision

One structured line per decision, and no more. The fields that earn their place: timestamp, key fingerprint (salted hash, truncated), route or policy name, decision, the value the decision was made against, the store latency, whether a fallback was used, and the window or TAT. Everything else can be derived; none of this can.

Then watch two rates, not one:

• The admit rate. A limiter that admits 100% is a limiter that is misconfigured, bypassed, or keyed on something that varies per request. This is the failure that never pages anyone and costs the most.
• The refusal rate by policy. A refusal spike on one policy is the signal you want; a refusal spike on all policies is usually your own key derivation changing under load.

And be careful with metric cardinality: a counter with a key or an IP as a label is a cardinality bomb, and the bill for it arrives on the observability invoice, not the edge one.

Test it like a property, not a unit

The tests that catch real limiter bugs are not assertions about a function's return value. They are assertions about the set of decisions taken across instances and time.

• Drive a virtual clock. Do not sleep. Inject now so a test can jump from 59.9 to 60.1 in a millisecond.
• Model many instances. Instantiate the limiter N times against one shared store, or route keys through a fake single-writer, and assert the combined behaviour.
• Assert the invariant, not the responses. "No interval of length t contains more than B + r·t admissions" is checkable over the admission log and does not care how many instances you ran.
• Include the adversarial pattern. A hundred at the end of a window and a hundred at the start of the next, then the same at t−ε and t+ε for every ε you can afford. My harness admits 200/200 against a fixed window; that assertion is the whole test.
• Include real concurrency. Fire 2 × limit requests at once from independent threads and assert the sum of admissions equals the limit exactly, not "approximately". The naive store in this post returned 200 admissions for a limit of 10; the atomic one returned 10.
• Test the degraded path. Make the store time out and assert that the endpoint returns the documented 503/fallback, not a 500 and not an admit-everything.
• Test the clock. Run the same schedule with now jumping backwards by two seconds and assert the limiter does not hand out a second allowance.

The layered design I would ship

No single mechanism is both cheap and strict, so ship three layers and know what each one promises:

type Decision = { admit: true } | { admit: false; retryAfterMs: number; scope: string }; export async function decide(env: Env, key: string, policy: Policy): Promise<Decision> { const now = Date.now(); // L1: per-isolate, free, catches floods. Approximate by construction. const local = env.LOCAL.check(key, now, policy.emissionMs, policy.burstMs); if (!local.admit) return { admit: false, retryAfterMs: local.retryAfterMs, scope: "local" }; // L2: one Durable Object per key, strict. Deadline, then fall back to L1. try { const stub = env.LIMITER.get(env.LIMITER.idFromName(key)); const res = await withTimeout(stub.check(policy.emissionMs, policy.burstMs), 50); if (!res.admit) return { admit: false, retryAfterMs: res.retryAfterMs, scope: "user" }; } catch (err) { // L1 already admitted, so the fallback is: serve, and log that we are soft. console.warn("limiter_unavailable", { key: hash(key), err: String(err) }); } return { admit: true }; } 

Layer by layer:

• L1 — the isolate. Microseconds, no I/O, and it is where a flood dies before it costs anything. Its limit is deliberately looser than the strict one — say twice — because its job is to absorb, not to account. A per-isolate limit that equals the global limit multiplies your real limit by the instance count.
• L2 — the key's object. One round trip, strongly consistent, and the number you are willing to publish.
• L3 — the upstream. Whatever you are protecting will rate-limit you too. Honour its 429 and Retry-After instead of treating it as an error, and give each credential its own object so one credential's exhaustion does not stall another's.

The order matters: cheap and approximate first, expensive and exact second, and the exact layer only for keys that are worth a round trip. That is also the order the platform's own limiter sits in: it is L1 done by the network, which is why its documentation points at Durable Objects for the strict case.

What this costs

Every strict check is a write, and writes are the expensive thing in every store you might use. The honest way to size a limiter is to ask whether the check costs more than the work it protects.

• Count only what is expensive. A page view does not need a strict per-key check; a search, an export, a password attempt, and an upstream API call do. Cloudflare's delta parameter exists for exactly this: weight a search as ten and a lookup as one, so the allowance tracks cost instead of request count.
• Sample the cheap path. If a route is both high-volume and cheap, a probabilistic check (one in ten, with limits multiplied by ten) keeps the cost down and the statistical guarantee roughly intact. Document the sampling rate; do not let a future maintainer "fix" it to 100%.
• Put the limiter behind the cache. A request served from the edge cache never reaches your limiter, which is the cheapest possible outcome and also means your limit applies to origin traffic only. Say which one you mean.
• Budget for refusals. In a well-run system, refusals are a small fraction of traffic; in a badly-keyed one they are most of it, and you are paying a write for each refusal. If the refusal r...