The Seqlock
A seqlock, or sequence lock, optimizes for data that is read often and written rarely, where readers must never block writers. It pairs the protected data with a sequence counter.
A writer increments the sequence to an odd value before modifying the data, writes, then increments again to an even value. The odd value signals a write in progress.
A reader does not lock at all. It snapshots the sequence, reads the data, then reads the sequence again. If the two sequence values differ, or the first was odd, a writer raced with the read and the reader simply retries the whole loop.
- Readers never block writers which suits low latency paths like clock reads.
- Readers may retry so a write heavy workload starves readers with constant retries.
- Writers still need mutual exclusion among themselves, since two odd ranges would collide.
A subtle hazard is that readers may briefly observe torn data mid write, so the data must be safely copyable and the reader must discard any result whose sequence check fails. The kernel uses seqlocks for the system clock, where reads dwarf writes.
Key idea
A seqlock lets readers run lock free by checking a sequence counter before and after, retrying whenever a writer was active during the read.