Skip to the content ForoHackers
Log inJoin

Reader-writer locks and the writer who never gets in: a timeline

Concurrency and parallelismDebuggingPerformance engineering
#1211 · mutex_mike · · Report

A reader-writer lock lets many readers in at once, or exactly one writer. The tempting implementation, "readers may enter whenever no writer is active", has a nasty property: if readers keep arriving, the writer never gets in.

time ->   0    1    2    3    4    5    6    7
R1        [==========]
R2             [==========]
R3                  [==========]
R4                       [==========]
W              ....waiting..............  (never enters)

At every instant there is at least one reader inside, so "no active writer and..." keeps letting new readers in, and the writer waits as long as the traffic lasts. That is writer starvation.

Fixes and what they cost:

  • Writer preference: once a writer is waiting, new readers queue behind it. Writers get through; now a stream of writers can starve readers.
  • Fair (FIFO) queue: everyone is served in arrival order, readers batched together while adjacent. Starvation is gone; throughput drops slightly, because readers cannot always overtake.
  • Avoid the lock: for read-mostly data, replace the structure atomically and let readers use the old copy until they finish.

There is no free lunch, there is only a choice of who you let wait.

#2149 · race_condition_rita · · Report

Failure model first: is a stale read acceptable for a short time? If yes, the copy-on-write approach is the cleanest, and the whole lock goes away. If readers must see the latest write, you need the lock and a fairness policy. And please write the policy down, because "we did not think about it" is also a policy.

#2150 · null_terminated_hopes · · Report

The timeline is lovely and I hate it. I once debugged this in a cache layer: one slow writer, a thousand readers, a graph with a perfect flat line during the incident. Production was waiting very patiently for a lock it would never get.

#2151 · two_phase_commitment · · Report

Databases know this problem well, which is why lock managers keep a queue and are careful about letting new shared locks jump ahead of a waiting exclusive one. A schema change that waits for a long-running reader, with new readers piling up behind it, is the same story with worse consequences.

#2152 · mutex_mike · · Report

Right, Two Phase: the "DDL waits for a long query, then everything waits for the DDL" incident has the same shape as my diagram, just with a worse name. The cure is the same too: a timeout on the waiter, so the queue cannot back up forever.

Log in or join to reply.