catalogue / caching & queues

Caching, queues & concurrency

Where good intuitions go wrong the most reliably.

7 of 7 topics live on this page

What a 95% cache hit rate still costs

Requests for one hot endpoint hit a cache first. A hit comes back in 0.5-2 ms; a miss goes on to the database and takes 50-200 ms. Because every miss is slower than every hit, the moment more than 1% of requests miss, your p99 is a database call, and the database still gets every miss at peak: 95% sounds close to 99%, but it is five times the database load.

Assumes 1,000 requests/s at peak, hits taking 0.5-2 ms and misses 50-200 ms (anywhere in each range equally likely), and a database that stays healthy at that load

Cache hit rate

peak 1,000 req/s hit up to 2 ms db 50 ms to 200 ms

cache hit, p50
database miss, p90 / p95 / p99 (each drops to cache latency at its own hit rate)
requests/s reaching the database at 1,000/s peak

Latency	At 95.0% hits	Answered by
average	7.44 ms	hits and misses blended
p50	1.29 ms	cache
p90	1.92 ms	cache
p95	2 ms	cache
p99	170 ms	database

At 95.0% hits the slowest 5% of requests are misses, and every miss is slower than every hit, so the p99 is database latency (p99 170 ms) while the average reads 7.44 ms. The database takes 50/s of the 1,000/s peak: 5× what it takes at 99% hits.

When a popular cache key expires

One key, read by every request and served from cache, until its TTL runs out. Every request that arrives before the value is back misses and asks the database for it, and each extra query slows all the others down, which keeps the key missing for longer and lets even more misses through. The dots are requests; each chart is the database queries running at once. The same traffic hits both caches; only the second one has a lock.

Assumes a 200 ms query, a database with 16 cores shared evenly by the queries running on it, at most 100 connections, a 1 s query timeout and evenly spaced requests; a real run in 1 ms steps, replayed at a third of real speed

Requests per second on the key

No protection refusing requests every request that misses queries the database itself

With a lock served from cache the first miss takes a lock and recomputes; every other miss waits for its answer

query 200 ms cores 16 max conns 100 timeout 1,000 ms

request served from cache
miss, no protection
miss, with a lock
refused: no free connection
connection limit

Cache	Queries sent	Running now	Each query takes	Requests failed	Key back in cache	Status
No protection	300	100 / 100	1.25 s	29,900	missing for 3 s	refusing requests
With a lock	1	0 / 100	-	0	after 200 ms	served from cache

At 10,000 requests/s, 2,000 requests arrive in the 200 ms the query needs on a quiet database. With no protection all 100 connections fill almost at once, each query then needs 1.25 s, longer than the timeout, so every one is cancelled before it can refill the cache, and the next misses take their place. The key never comes back: 29,900 of 30,000 requests after expiry fail. With a lock it runs 1, the key is back after 200 ms, and 1,999 requests wait for it instead of failing. Without the lock this is a cliff, not a slope: at 720 requests/s the key comes back, at 740 requests/s it never does. Serving the stale value while one request refreshes it avoids even the wait, and refreshing a little before the TTL, at random (probabilistic early expiration), keeps the expiry from meeting a crowd at all.

When the job queue falls behind

A background job queue whose 50 workers can finish 1,000 jobs a minute, simulated live through a 60 minute surge and back to a normal 800 a minute. Under capacity the line stays near empty. Over it, even by 5%, the line grows by the same number of jobs every minute the surge lasts, and only the spare capacity afterwards can clear it: 3,000 jobs waiting and 15 min to drain after 1 h at 1,050 a minute.

Simulated for real: random arrivals, each job takes 3 s on average (exponential), first come first served, no limit on the line. Dashed line: the fluid model, backlog = (arrivals - capacity) x time

Surge arrivals, % of capacity

workers 50 job 3 s normal 80 % surge 60 min

30 jobs waiting (a faint dot is a partial one)
worker on a job
idle worker
counts under the tracks: jobs in and out over the last simulated minute

keeping up Little's Law, L = λW, measured from this run over the last 5 simulated minutes

L, jobs in the system: …
λ, arrivals: …
W, time in the system: …
λ × W: …

jobs waiting in this run
fluid model

Surge at 105% for 60 min	Fluid model	This run
Added to the line per minute of surge	50 jobs	…
Waiting when the surge ends	3,000 jobs	…
Wait in line for a job that joins then	3 min	…
Time to drain at 800 jobs/min	15 min	…

Arrivals 5% over capacity add 50 jobs to the line every minute, and nothing about the line pushes back: it has no level to settle at, so it grows until the surge stops. Afterwards only the 200 jobs/min of spare capacity clears it, so the drain takes 15 min, 25% as long as the surge itself. By L = λW, a job that joins at the peak spends about 3 min waiting.

Adding workers until it gets slower

Workers share one lock and one piece of state every worker must keep in step with every other, like a cache or a cluster's membership list. The first workers add throughput almost one for one, then each adds less as they queue for the lock, and past 31 workers each extra one makes the whole pool slower, because the pairs that must stay in sync grow with the square of the pool. At 128 workers it serves 542/s, less than 8 workers would.

Gunther's Universal Scalability Law, X(N) = λN / (1 + σ(N-1) + κN(N-1)): one worker alone serves λ = 100 requests/s, σ = 0.05 of each request waits on the shared lock per extra worker, and each pair of workers costs κ = 0.001 of a request in syncing. Peak at N* = sqrt((1-σ)/κ) = 30.8.

Workers

1 worker 0 pairs to keep in sync

λ 100/s σ 0.05 κ 0.001

doing its request 100%
queued for the lock 0%
syncing with every other worker 0%

Ideal: nothing shared
Contention only (σ = 0.05)
Contention + coherency (κ = 0.001)

At 1 worker	Throughput	Per worker	Efficiency	Adding one more
Ideal: nothing shared	100/s	100/s	100%	scaling well
Contention only (σ = 0.05)	100/s	100/s	100%	scaling well
Contention + coherency (κ = 0.001)	100/s	100/s	100%	scaling well
Best pool size (contention + coherency)	904/s	29/s	29%	31 workers

How many events to write per batch

A consumer takes 10,000 events a second off a queue and writes them to a database in batches. Dots are events arriving; they collect in a batch, full batches wait for the one writer, and every write pays a fixed 5 ms before it saves anything. The chart below is the average time from arriving to saved: too small and the writer drowns in overhead and falls behind; too big and every event waits for its batch to fill and for a slow, bloated write.

Assumes 10,000 events/s arriving at random; each write costs 5 ms (round trip + commit) + 0.05 ms per event + 12.5 ns × size² (longer locks, bigger log); one writer; a batch is sent only when full (no linger timeout); queueing by Kingman's approximation

Batch size

arriving 10,000/s overhead 5 ms per event 0.05 ms growth 12.5 ns × size²

playback: 1 s on screen = 7.53 ms of real time · 1 dot = 2 events

peak: total latency per event, and what the writer can save
linear: waiting for the batch to fill
cliff: queued behind earlier batches
quadratic: the write itself
flat: 10,000 events/s arriving
shaded: the writer cannot keep up

Batch	Events	Wait to fill	Queued	Write	Latency per event	Writer can save	Status
slider	113	5.6 ms	1.05 ms	10.8 ms	17.5 ms	10,454/s	near capacity
one at a time	1	0 ns	grows forever	5.05 ms	grows forever	198/s	falls behind
lowest latency	113	5.6 ms	1.05 ms	10.8 ms	17.5 ms	10,454/s	near capacity
most throughput	632	31.6 ms	63.3 µs	41.6 ms	73.2 ms	15,195/s	keeps up
as big as allowed	10,000	500 ms	grows forever	1.75 s	grows forever	5,698/s	falls behind

At 113 per batch an event waits 5.6 ms for its batch to fill, 1.05 ms for the writer and 10.8 ms for the write: 17.5 ms from arriving to saved. Below 103 per batch the 5 ms per write eats the writer; above 3,897 each write slows faster than it grows. Latency is lowest at 113 and throughput peaks at 632; neither is anywhere near as big as possible. Real batchers also flush on a timer (a linger time) so a quiet stream never waits forever for a batch to fill.

When a queue can't keep up

Three copies of the same job queue, simulated live, fed by the same producer and drained by a worker that finishes 20 jobs a second. Once the producer is faster than the worker something has to give: the unbounded queue keeps every job until the process runs out of memory, backpressure makes the producer wait, and load shedding turns the extra jobs away with a fast 429.

Simulated event by event: random arrivals (the same ones in every lane until a producer is made to wait), one worker at 50 ms a job, bounded queues of 20, 1 MB held per waiting job, 256 MB of memory for the queue, p99 over the last 5 s

Producer rate, % of what the worker can do

Grow unbounded queue: every job is kept

Block backpressure: 20 places, a full queue makes the producer wait

Shed load shedding: 20 places, a full queue rejects the job with a 429

job 50 ms bounded 20 memory 256 MB

job waiting, unbounded queue
job waiting, bounded queue
job lost: rejected, or gone with the crashed process

At 150% the producer sends 30 jobs a second and the worker finishes 20. Grow keeps the extra 10 a second: it holds 10 MB more every second, every new job waits longer than the last, and it runs out of memory about 25.6 s after starting empty, losing every job it held. Block stays at 20 waiting and makes the producer wait about 33% of the time, so the slowness moves upstream. Shed stays at 20 waiting and rejects about 33% of jobs straight away; the caller has to retry later or give up.

grow: climbs while the overload lasts
block: never above 20
shed: never above 20

At 200% the unbounded queue fills its 256 MB in about 12.8 s. Real queues hold more, but the shape is the same: a bigger limit only buys time, because the backlog grows for as long as the producer is ahead.

How many threads should the pool have?

8 CPU cores serve requests that each need 10 ms of CPU, then wait 40 ms on a database or API while holding their thread. The strip shows what every core is doing right now: with too few threads the cores sit idle while every thread waits; near cores × (1 + wait ÷ CPU) = 40 they are packed; with hundreds, time is sliced thin and every switch pays to reload the cache, so fewer requests finish and each one takes seconds.

Assumes 8 cores; each request 10 ms of CPU then 40 ms ±50% of I/O; the scheduler shares a core within 6 ms but never slices below 0.75 ms; each switch costs 5 µs plus up to 0.2 ms to reload a 1 MB working set once a core's threads outgrow its 4 MB of cache; 1 MB of stack per thread

Threads in the pool

cores 8 CPU 10 ms wait 40 ms reload 0.2 ms

running a request (t7 = thread 7)
switching threads: saving state, reloading cache
idle: every thread is waiting on I/O

requests finished per second (left axis), measured by running the scheduler
stack memory at 1 MB per thread (right axis)

	Threads	Requests/s	Time per request	Working	Switching	Idle	Stack memory	Status