Concurrency

Two requests read a likes counter, both see 41, both write 42. One increment is gone, nothing raised an error, no log line records the loss. Concurrency is the business of keeping many operations in flight without producing that outcome, and every control that prevents it buys correctness at a throughput ceiling you should be able to state.

A race on a shared counter: read-modify-write loses an increment; an atomic increment does not100%−+FitSVGEsc

Scroll to zoom · drag to pan · 0 fits · Esc closes

Concurrency is not parallelism

Concurrency is managing several tasks in flight at once, interleaved on one core if need be. Parallelism is executing them in the same instant, which needs more than one core: an event loop is concurrent and not parallel.

Waiting is what dominates a backend request — an SSD read takes 100 µs, a datacenter round trip 0.5 ms, a call from India to US East around 200 ms — and a thread blocked for those 200 ms holds memory and a connection while doing nothing. Throughput therefore comes from overlapping waits, not more CPU. Little's Law prices it: concurrency = arrival rate × latency, so 500 QPS against a 200 ms dependency keeps 500 × 0.2 = 100 requests in flight. A 20-connection pool serves 20 and queues the rest until callers time out — that pool is a semaphore, and its size is a decision, not a default.

The window that loses the update

The lost increment has a measurable width. A read-modify-write cycle costs two round trips at 0.5 ms each plus application time, so call the window 1 ms, and put 500 requests per second on that one row. Overlap is symmetric, so count both sides: another update races mine if it starts inside my 1 ms window, or if it started up to 1 ms before me and is still open. The exposed span is 2 ms wide, not 1. Treating arrivals as Poisson at the average rate, that span holds 500 × 0.002 = 1 arrival, so the chance of at least one is 1 − e^(−1) ≈ 63%. Nearly two in three updates race something — not an exotic failure at Twitter scale, but the steady state of any hot row.

Collapsing the two round trips into one removes the window: UPDATE posts SET likes = likes + 1 WHERE id = ? computes inside the storage engine, which serialises writes to the row for you. The last seat has the same shape and the same fix — not "read it, check it is free, write it", but one conditional statement whose rowcount is the answer:

UPDATE seats SET user_id = :user WHERE id = :seat AND user_id IS NULL;
-- 1 row updated: the seat is yours. 0 rows: someone else won, tell them.

Everything harder exists for what one statement cannot express: a change spanning several rows, several services, or a decision made in application code.

Deadlock and starvation

Deadlock is a cycle of waits. Transaction A updates account 1 then account 2; transaction B, transferring the other way, takes 2 then 1, and each holds what the other needs. The database breaks the cycle by killing one after a timeout, turning a correctness bug into a latency spike and an error the caller sees. The fix is ordering: take locks in one globally agreed order — sort the account ids, update the lower first — and no cycle can form. A lock timeout is the backstop, not the strategy.

Starvation is a runnable process the scheduler keeps overlooking: a writer waiting on a lock a stream of readers keeps re-acquiring may never run. Fair queueing, or a bounded wait that blocks new readers, removes it. Neither shows up in a load test at 10% of production traffic, which is why both arrive as incidents.

Choosing the control, cheapest first

Atomic operations. Compare-and-swap, INCR, a single-statement conditional update: no lock to manage, no deadlock, no window. Do not move past these until you can say why the operation will not fit in one statement.

Optimistic control. Read a row with its version, do the work, write with WHERE version = :seen. Zero rows updated means someone committed first, so re-read and retry. The arithmetic says when that pays: at the 63% conflict rate above, attempts per success are 1 ÷ (1 − 0.63) ≈ 2.7, and every retry re-enters the arrival rate and raises the conflict rate again — that feedback is how a hot row collapses under a retry storm. Below a few percent conflict it holds no lock and costs nothing; above roughly ten it is the wrong tool. Retrying also runs the operation twice, which is at-least-once: duplicates are normal, so the handler needs idempotency or the retried charge bills twice.

Pessimistic control. SELECT ... FOR UPDATE takes the row lock upfront and holds it to commit. Conflicts cost waiting rather than wasted work, the better trade under contention — but hold time is now a hard ceiling. A transaction holding the lock 2 ms, including the commit fsync, lets that row serve 1 ÷ 0.002 = 500 operations per second; ask for 1,000 and the queue grows without bound, and more application servers do not help, because the contended row is one row. This is the machinery behind ACID's I, and the isolation level does not settle it by itself. Read committed stops nothing here. PostgreSQL's repeatable read is snapshot isolation with first-updater-wins, so the second writer aborts with a serialisation failure — real protection, but you still have to catch it and retry. MySQL's InnoDB, where repeatable read is the default, serves that SELECT from a consistent snapshot and takes no lock, so a value computed in application code overwrites the winner silently and the lost update survives. Under InnoDB what closes it is SELECT ... FOR UPDATE or an atomic statement, not the name of the level; serialisable closes it on both engines and costs the most.

Design the contention away. Immutable data cannot be raced — append a like event and count rows, and there is nothing to overwrite. Message passing gives each key one consumer, so a partitioned queue handles an account's events in order with no lock at all. Only when the contending parties are separate machines and none of this fits are you asking for distributed locking, which needs leases and fencing tokens and is the most expensive answer here.

In an interview

You will not be asked to implement a lock-free queue. What is tested is whether you notice shared mutable state on a write path and reach for the cheapest control that fits: the last seat, the counter every request touches, the balance two transfers modify at once. Name the contention before the fix — "every like hits one row, so at 500 QPS the read-modify-write window races about 60% of the time; I'd make it an atomic increment, and if I need a check too, a conditional update whose rowcount tells me who won." Then price it: optimistic below a few percent conflict, pessimistic above that with the hold time stated. If you propose retries, finish the chain out loud — retry means at-least-once, which means duplicates, which means idempotent handlers.

The mistake that loses points is saying "we'll add a lock" without naming what it locks, how long it is held, and the throughput ceiling that creates. It reads as pattern-matching, and invites the follow-up most candidates cannot answer: what happens when the holder crashes. A close second is reaching for a distributed lock when one conditional UPDATE would have done the job.

Check yourself

1. A wallet balance row takes 800 updates/second, each a read-modify-write with two datacenter round trips. Estimate the conflict rate and choose a control.

The window is about 2 × 0.5 ms = 1 ms, and overlap is two-sided, so the exposed span is 2 ms: arrivals average 800 × 0.002 = 1.6 and 1 − e^(−1.6) ≈ 80% of updates race another. Optimistic versioning would need 1 ÷ 0.2 = 5 attempts per success, with retries pushing contention higher still — rule it out. Use one atomic statement, SET balance = balance + :delta WHERE id = :id AND balance + :delta >= 0, and let the rowcount reject an overdraft. Take the row lock only if the update spans several rows, and quote its ceiling when you do.

2. You hold a row lock for 4 ms per transaction and the product wants 1,200 writes/second to that row, while another endpoint on the same service makes 300 QPS of calls to a dependency whose p99 is 200 ms through a 30-connection pool. What breaks first, and what do you change?

The row goes first, and by a wide margin. Its ceiling is 1 ÷ 0.004 = 250 writes/second against the 1,200 asked for — 4.8x oversubscribed, a backlog growing at roughly 950 requests/second, and the symptom is lock-wait timeouts rather than slowness. The pool is only 2x over: Little's Law puts 300 × 0.2 = 60 calls in flight against 30 connections, so it clears 30 ÷ 0.2 = 150 QPS and backs up at about 150/second. It fails second, but wider — pool-acquire timeouts land on requests that never reach the dependency, healthy ones included, so it is the louder incident even though the row saturates sooner. Do not answer the row with a shorter transaction: 1,200 writes/second needs the hold under 1 ÷ 1200 ≈ 0.83 ms, and one datacenter round trip to commit is 0.5 ms of that, so there is nothing to trim 4 ms down to. Shard the row instead — each shard still ceilings at 250/s, so five cover 1,250 and sixteen leave peak headroom — and sum on read, if the total tolerates being milliseconds stale. The pool is a separate fix: 60 connections is the arithmetic floor, and it only relocates the queue unless the dependency can absorb 60 concurrent calls, so if it cannot, cap the concurrency deliberately and shed the excess.