Concurrency Control | System Design Interview Handbook

🔐

Where Races Come From

"what if this arrives twice?"

A race is two operations touching the same data at once, where the result depends on timing. In distributed systems they're everywhere: retries resend a request, concurrent users edit the same row, at-least-once delivery replays messages, multi-node writes land in parallel. The interview tell is a single question — "what if this request arrives twice?" — and if you don't have an answer, that's the bug they're hunting.

  Lost update — two reads, two writes, one survives:
     T1: read balance=100 ──────────── write 100+50 = 150
     T2:        read balance=100 ── write 100−30 = 70
                                        ▲ T2 overwrites T1; the +50 vanishes
     correct answer was 120. The store saw 70.

🔁

Idempotency

make running twice the same as running once

An idempotent operation has the same effect whether applied once or many times. Some are naturally idempotent — set status = 'paid', adding to a set, an upsert. Others aren't — balance = balance + 50, "send email," "create order." For those you add an idempotency key.

  Idempotency-key flow:
     request arrives with key "abc123"
              │
              ▼
     is "abc123" in the dedup store?
        ├─ yes ─▶ return the SAVED result   (a replay — do nothing new)
        └─ no  ─▶ process it, store (key → result), then return
                  dedup store keeps keys with a TTL (hours/days)

The client generates a unique key per logical operation and sends it with the request. The server records processed keys in a dedup store; a repeat key returns the stored result instead of re-executing. Size the store with a TTL long enough to outlast any retry window (idempotency keys). This is how you make a payment endpoint safe to retry.

📬

Delivery Semantics, From the Consumer's Seat

exactly-once effect, decoded

The three delivery levels look different from the receiving end. At-most-once: you might miss a message. At-least-once: you might get it twice. Exactly-once: you act on it once. Since networks can't guarantee exactly-once delivery, you build exactly-once effect from the pieces you control.

💡

The equation to memorize: exactly-once effect = at-least-once delivery + idempotent processing. The broker resends until acked (at-least-once); your consumer dedups so reprocessing changes nothing (idempotent). Together they behave as if each message landed once. When an interviewer says "exactly-once," this is the answer they want (Messaging).

🍃

Optimistic Concurrency

assume no conflict, check at write

Optimistic control bets conflicts are rare. Read the data with its version, do your work, then write only if the version hasn't changed — a compare-and-swap. If someone else wrote in between, the version moved, your write is rejected, and you retry. No locks held while you think.

  UPDATE items SET stock = 4, version = 6
  WHERE id = 42 AND version = 5     ← only succeeds if still version 5

     T1 reads v5 ──── work ──── writes WHERE v5 → OK, now v6
     T2 reads v5 ──── work ──── writes WHERE v5 → 0 rows changed → RETRY
                                        (T1 already moved it to v6)

Wins when conflicts are rare: no lock overhead, high concurrency, and the occasional retry is cheap. It degrades when conflicts are common — everyone keeps colliding and retrying, wasting work. That's the signal to switch to pessimistic locking.

🔒

Pessimistic Locking

assume conflict, lock first

Pessimistic control assumes conflict and takes a lock before touching the data — SELECT ... FOR UPDATE grabs the row so nobody else can write it until you commit. Others wait. This wins when contention is high: inventory decrements, seat booking, anything where collisions are the norm and a retry storm would be worse than a short wait.

⚠️

Locks bring deadlock: T1 holds A waiting for B, T2 holds B waiting for A, both stuck forever. Databases detect and kill one, but you avoid it by acquiring locks in a consistent order and keeping them short. Held locks also cap throughput — the whole point is serializing access, which is the opposite of concurrency. Use them where correctness demands it, not by default.

🌐

Distributed Locks

"just use a Redis lock" needs caveats

Sometimes the lock must span services, not one database — only one worker should process a job, only one scheduler should fire. A lock service (Redis, ZooKeeper, etcd) grants a lock with a lease TTL so a dead holder's lock auto-expires instead of blocking forever. Simple, until the holder isn't actually dead.

  THE EXPIRED-LEASE TRAP:
     worker A acquires lock (TTL 30s) ─▶ A pauses (GC, slow disk) 35s
        lease EXPIRES at 30s ─▶ worker B acquires the same lock
           A wakes up, still thinks it holds the lock ─▶ BOTH act. Corruption.

  FENCING TOKENS — the fix:
     each grant carries an increasing token:  A gets 33,  B gets 34
     the protected resource REJECTS any write with a token < the highest seen
     A's stale write (token 33) is refused; B's (34) wins.

⚠️

"Just use a Redis lock" is incomplete because a lease can expire while the holder is merely paused — a GC pause, a slow syscall — so two workers believe they hold it. A TTL alone can't prevent this. Fencing tokens fix it: a monotonically increasing number the downstream resource checks, rejecting any writer with a stale token. If the lock protects something that can be corrupted, you need fencing, not just a TTL.

🕰

Logical Clocks

wall clocks can't order distributed events

You can't order events across machines by timestamp, because clocks drift — two servers' wall clocks disagree by milliseconds, enough that "later" timestamp doesn't mean "happened after." Logical clocks order events by causality instead of time.

Lamport clocks ordering

A counter each node bumps on every event and carries on every message. Gives a consistent total order that respects causality: if A caused B, A's counter is lower. Can't tell whether two events were concurrent or truly ordered — only that the order it gives is legal.

Vector clocks detecting concurrency

A per-node vector of counters. Comparing two vectors tells you if one happened-before the other, or if they're genuinely concurrent — which is exactly the conflict detection Dynamo-style stores use to know two writes need resolving (leaderless replication).

ℹ️

Intuition is enough for an interview: wall clocks lie across machines, so causal ordering uses logical clocks. Lamport for a legal total order, vector clocks when you must detect concurrent writes. You won't derive the proofs; you'll name the tool and why timestamps don't cut it.

📋

Quick Reference

techniques on one card

Technique	Use when	Cost
Idempotency key	Retryable non-idempotent writes	Dedup store + TTL
Optimistic (version/CAS)	Conflicts are rare	Retries on conflict
Pessimistic (row lock)	Conflicts are common	Throughput, deadlock risk
Distributed lock	Mutual exclusion across services	Lease TTL + fencing tokens
Lamport clock	Consistent ordering of events	Can't detect concurrency
Vector clock	Detecting concurrent writes	Size grows with node count

ℹ️

The one-liners to keep ready. Always answer "what if this arrives twice?" — idempotency keys make non-idempotent writes safe to retry. Exactly-once effect = at-least-once + idempotent processing. Optimistic when conflicts are rare, pessimistic when they're common. Distributed locks need lease TTLs and fencing tokens, not just a Redis SETNX. Wall clocks can't order events across machines — use logical clocks.