Semaphores and rate limiters

Two quantities are in play whenever work fans out over a list. Concurrency is the number of requests already sent and not yet answered, in the air between your process and the provider at a given instant. Throughput is a rate: how many requests complete per second or per minute. A provider publishes rates, a client is configured with counts, and most of the difficulty in bulk work lives in the conversion between the two.

Something has to enforce the count, because nothing about a batch enforces it naturally. A loop that builds 40,000 coroutines runs at memory speed and every one of them wants a socket, so between "here are the items" and "here is the request" there has to be a gate. The semaphore is the usual gate: a counter initialised to N, which a coroutine decrements before it may proceed and increments again when its call returns, so at most N calls are ever inside the guarded region at once. Read as a queueing system it is a queue with N servers, and the gap between p50 and p99 latency is the time items spend waiting for one. The concern here is upstream of that: what N should be when the constraint is not your own latency budget but somebody else's published allowance, and what happens to the derivation when the inputs move.

The question only arises where work fans out over a collection — a nightly re-embedding job, a CSV upload that summarises every row, an evaluation harness scoring a test set, a worker draining a queue of documents. A single interactive chat request has nothing to bound, because there is one call and it is either made or not. Anything holding a list has to decide how much of that list is allowed to be in the air at once, and the number tends to be written quickly by whoever drew the batch job.

Latency is the conversion factor#

The error is a unit error, and it survives code review because both sides of it look like the same number. A semaphore's N is a count of things currently outstanding. An account page's "500 requests per minute" is a count divided by time. Those are different quantities in the same way that the number of cars on a motorway is different from the number of cars passing a toll booth each hour, and you cannot set one from the other without knowing how long each car spends on the road.

For provider calls the time each request spends on the road is the end-to-end latency. A slot occupied by a call with 800 ms latency turns over 1.25 times per second, so 500 slots deliver 625 requests per second, which is 37,500 per minute. Against a 500-per-minute allowance that is seventy-five times over, before any allowance is made for a slower tail. The semaphore was doing exactly what it promises. It was never a promise about rate.

The conversion has a name. Little's law, proved by John Little in 1961 for a far more general setting than HTTP clients, says that for any stable system the average number of items inside it equals the arrival rate multiplied by the average time each item spends inside: L = λ × W. It holds regardless of the distribution of arrivals or service times, which is unusual for a queueing result and is why it is safe to use on traffic that is nothing like Poisson. Applied to a provider client, L is the number of requests in flight, λ is the request rate, and W is the observed latency. You want a rate at or just under the published one, so you solve for L:

def in_flight_bound(rpm_allowed: int, latency_seconds: float, headroom: float = 0.8) -> int:
    """Max concurrent requests that keeps the sustained rate under rpm_allowed."""
    target_rps = (rpm_allowed / 60.0) * headroom
    return max(1, int(target_rps * latency_seconds))


in_flight_bound(500, 0.8)     # -> 5
in_flight_bound(500, 0.8, 1.0)  # -> 6, no headroom

Five hundred requests per minute is 8.33 per second; at 800 ms per request, 8.33 × 0.8 gives 6.67 requests in flight, so 6 is the bound before any headroom is applied — which is what the function returns when headroom is passed as 1.0. The gap between 6 and 500 is the whole chapter. Six is also a number that surprises people enough to check it twice, because it feels far too small for a job with 40,000 items to get through, and it checks out: six slots turning over every 800 ms is 450 requests per minute, which sits inside the 500 the account is rated to serve. The default headroom then applies to the rate rather than to the latency, which is easy to lose because both factors happen to be 0.8 here: the headroom takes 8.33 requests per second down to 6.67 requests per second, and multiplying that by the 0.8-second latency gives a little over five, floored to 5. That is what the function returns by default, and what the 800 ms row of the table below carries.

It is worth knowing why the law is that general, because "it holds for any distribution" is exactly the sort of claim that gets taken on trust and then misapplied. Little's law is an accounting identity rather than a probabilistic result. Over a long window, add up the time every item spent inside the system. That total can be counted per item, as the number of items multiplied by the average time each one spent inside, or it can be counted moment by moment, as the average number inside multiplied by the length of the window. Both counts measure the same quantity, so they must agree, and dividing through by the window length gives in-flight equals rate times latency. Nothing in that argument mentions how arrivals are spaced or how long any individual call takes, which is what makes it safe on bursty batch traffic. What it does assume is stability — that the window is long enough for the system to have finished roughly as much as it started — and that assumption is the one a short staging run breaks.

There is a circularity in the inputs worth naming before it bites. The latency to feed into the formula is the latency at the concurrency you are about to run, and you do not have that measurement until you run it. Latency measured with one call in flight is optimistic, because it excludes the queueing that appears on the provider's side once you are one of many tenants pushing at your allowance, and it excludes any serialisation inside your own client. The loop in practice is: derive a bound from single-call latency, run at that bound for a few minutes, re-measure, re-derive. The numbers usually settle within two rounds, and if they do not — if latency climbs every time you raise concurrency — the system is telling you it is already saturated somewhere, which is the diagnosis chapter 5 takes apart.

The headroom factor exists because the published limit is enforced on the provider's clock, not yours, and the two do not agree about where a minute starts. Many providers enforce over a sliding or sub-minute window, so traffic averaging exactly 500 per minute but arriving unevenly will exceed the instantaneous rate during part of it. A factor of 0.8 costs a fifth of the theoretical ceiling and removes most of that class of rejection; chapter 3 argues that a fifth is more than you should be giving away, and shows how to earn some of it back.

Slower calls let you run more of them at once#

The relationship runs the other way too, which is what makes a hardcoded concurrency number unsafe over the life of a service. The same allowance supports wildly different in-flight bounds depending on what the calls are doing.

Two of those columns are pure arithmetic and check each other. Completions per slot per minute is 60 divided by the latency, so a 250 ms call turns a slot over 240 times a minute, an 800 ms call 75 times, a 2.5-second call 24 times and a 9-second call 6.7 times. The sustained rate is that figure multiplied by the number of slots, which is why one slot of fast classification delivers 240 requests a minute and 30 slots of slow extraction deliver about 201. The in-flight column is not a bare rate-times-latency product: the headroom factor and the floor to an integer both push it downward, and the longer-latency rows carry further margin beyond that. What survives all of it is the direction. Slots and latency multiply, so the same allowance buys more slots as calls get slower, and the same number of slots delivers more requests per minute as calls get faster.

Two things in that table are worth reading carefully. The bound rises with latency, so the workload that feels slowest tolerates the most parallelism, and a team that tunes concurrency on the long-extraction path and reuses the constant on the short-classification path will be seven times over the limit with a number that was measured honestly. The other is the right-hand column: with the 0.8 headroom applied and the result floored to an integer, only the 800 ms row lands near the allowance. Short calls are limited by rate long before concurrency becomes interesting, and long calls leave request budget unused because something else — the token allowance, which is the next chapter — binds first.

The floor also stings at low latency. At 250 ms the arithmetic gives 1.67 slots, and one slot delivers 240 requests per minute against an allowance of 500. Integers are a poor fit for this workload, which is a hint that a pure concurrency bound is the wrong instrument for fast calls; a rate limiter with a fractional interval expresses "one call every 120 ms" without rounding away half the quota.

A semaphore has no clock#

The deeper property behind all of this is that a semaphore contains no notion of time. It admits a new call the instant a previous one releases, and it does not know or care whether that release came 8 seconds later or 8 milliseconds later. So a bound derived from an 800 ms measurement silently becomes a bound on a much higher rate the moment latency drops, and latency drops for reasons that have nothing to do with you: the provider ships a faster serving stack, a prompt-caching hit removes 300 ms of prefill, your own retry path starts returning fast failures, or the traffic mix shifts toward shorter outputs after a prompt change. The configuration did not change and the request rate doubled.

A rate limiter does hold a clock. The token-bucket form is the standard — a bucket refilled with permits at a fixed rate, from which every call must take one before it goes out, so an idle bucket allows a short burst and a busy one paces calls to the refill rate — and in Python aiolimiter gives you one in a line:

from aiolimiter import AsyncLimiter

# 400 requests per 60s window, refilled continuously (500 rpm with headroom).
rate = AsyncLimiter(max_rate=400, time_period=60)
in_flight = asyncio.Semaphore(12)


async def summarise(client: httpx.AsyncClient, row: Row) -> str:
    async with rate:            # bounds requests per minute
        async with in_flight:   # bounds requests outstanding at any instant
            resp = await client.post(ENDPOINT, json=build_payload(row))
            resp.raise_for_status()
            return resp.json()["content"][0]["text"]

Both are present because they defend different things and neither implies the other. The limiter alone permits 400 calls to leave in the first second of every window if latency is high enough that none has returned, which is a burst the provider will reject and which also puts 400 simultaneous requests' worth of memory, sockets and pending payloads inside your process. The semaphore alone permits an unbounded rate whenever calls get fast. Under steady latency the two settings agree and one of them is redundant; the point of carrying both is that latency is exactly the thing you cannot promise will stay steady.

Ordering matters in that snippet. Acquiring the rate token first and the in-flight slot second means a coroutine waiting for the clock is not holding a concurrency slot hostage, which keeps the two queues independent. Reversing them lets a backlog on the limiter pin every slot while nothing is on the wire.

Where a bare semaphore is the right instrument#

The one place a bare semaphore is exactly right is when the resource being protected is genuinely a count rather than a rate: memory held by in-flight payloads, entries in a connection pool, open file handles, rows locked in a transaction. Those are bounded by how many exist at once and are indifferent to how quickly they turn over. Provider quota is not one of those, and the habit of reaching for a semaphore because it is the concurrency primitive everyone knows is how a published rate ends up in a constructor that expects a count.

Two further consumers of the same allowance are easy to forget while staring at the formula. Rejected requests count: a 429 is a request the provider received, evaluated against your account and answered, and on most APIs it is charged against your request-rate budget even though it produced no tokens. That is the same arithmetic that makes a retry storm self-sustaining rather than self-correcting, and it is why the rejections in the scenario above accelerated the client instead of slowing it. The other consumer is every other process on the same key. A semaphore is a per-process object, so four pods each holding a bound of 6 are collectively running 24 in flight against an allowance sized for 6, and the derivation has to be divided by the replica count or moved somewhere the replicas share. That is a real limitation of everything in this chapter, and it gets its own treatment once bulk work moves onto a worker fleet in chapter 7.

Which leaves the gather over every item at once. The memory cost of admitting a whole collection into the process is one problem; the rate cost is a separate failure and it arrives first. Every coroutine in that list runs immediately up to its first real await, and if the only thing between the coroutine and the socket is a semaphore, the first N of them are on the wire within a scheduling tick and the rest are queued to follow the moment a slot frees.

The instrument a bulk client needs, then, is a pair. A semaphore sized by rate × latency bounds what is outstanding and protects your own process; a token-bucket limiter sized just under the published rate bounds what leaves per minute and protects the account, and it keeps doing so on the day the provider makes every call twice as fast. Both numbers are derived from a measurement rather than copied from a documentation page, and both have to be re-derived when the workload changes shape.

That derivation used one published limit. Most accounts publish two, they are consumed by different traffic, and the one that binds you is not always the one you sized against.