Seqlocks: Consistent Reads Without Reader-Side Writes

A reader/writer lock charges every reader for the privilege of excluding writers: the reader must modify a counter, which means a write to a shared cache line, which means coherence traffic even when the data itself is untouched. When readers outnumber writers by orders of magnitude and the data is small, that accounting dominates the work. A seqlock removes it by making the reader a pure observer: it reads the data, reads a counter before and after, and retries if the counter indicates that a write overlapped. No reader ever writes anything.

The scheme is old and has a long history in kernel timekeeping, where it is used for exactly the case it suits: a small structure updated by one writer on a timer and read by many threads on every call.

The counter discipline

A seqlock pairs the protected data with a single unsigned sequence number. Writers increment the counter to an odd value before modifying the data and increment it again to an even value afterwards. An even counter therefore means no write is in progress, and an odd counter means one is.

A reader takes the sequence before reading, reads the data, takes the sequence after, and accepts the result only if the two values are equal and even. If they differ, or if either is odd, a write overlapped the read and the reader tries again.

typedef struct {
    atomic_uint seq;
    long long value;                 /* protected by the sequence discipline */
    long long other;
} seqlock_data;

static inline void read_pair(const seqlock_data *d, long long *a, long long *b)
{
    unsigned s0, s1;
    for (;;) {
        s0 = atomic_load_explicit(&d->seq, memory_order_acquire);
        if (s0 & 1u)                 /* a write is in progress: do not bother reading */
            continue;
        *a = d->value;
        *b = d->other;
        atomic_thread_fence(memory_order_acquire);   /* keep the data loads before s1 */
        s1 = atomic_load_explicit(&d->seq, memory_order_relaxed);
        if (s0 == s1)
            return;
    }
}

The equality test is doing the real work. It is not sufficient to check that the counter is even at the end, because a writer could have started and finished entirely within the reader’s window, leaving the counter even and unchanged in parity but advanced by two. Comparing the full value catches that case. The underlying issue is the one described in Atomicity and Ordering Are Separate Guarantees: the data reads and the counter reads are separate accesses, and only the happens-before relations between them make the pair meaningful.

The parity check at the start is an optimisation, not a correctness requirement: a reader that proceeds while a write is in progress will detect it at the end and retry. Skipping the read saves the memory traffic of a doomed attempt.

Why the reader must not have side effects

The reader’s loop may execute any number of times, and each iteration re-reads the data. Any effect the reader performs inside the loop happens as many times as the loop iterates. Writing a result into an output buffer is harmless because the next iteration overwrites it. Incrementing a counter, appending to a list, or freeing a pointer is not.

This is the constraint that keeps seqlocks out of general-purpose use. The read side must be a pure function of the protected data, or at least idempotent with respect to repetition. It also means the reader cannot hold a reference to a pointer it read from the protected data and then use it after the loop, because the object it pointed to may have been freed by a writer between the read and the use. A seqlock protects values, not lifetimes; the reclamation problem is the subject of Memory Reclamation for Lock-Free Structures.

Copying the whole protected structure into a local variable inside the loop is the safe idiom. It costs a copy per attempt but keeps every subsequent operation on private memory, so nothing in the loop can leak into an observable effect. The structure must be small enough for that copy to be cheap, which is why seqlocks protect time values, configuration snapshots, and small counters rather than large collections.

The writer’s ordering obligations

The writer’s sequence is: increment to odd, modify, increment to even. Both increments are stores, and the modification must be ordered between them.

static inline void write_pair(seqlock_data *d, long long a, long long b)
{
    atomic_fetch_add_explicit(&d->seq, 1, memory_order_relaxed);   /* to odd */
    atomic_thread_fence(memory_order_release);
    d->value = a;
    d->other = b;
    atomic_thread_fence(memory_order_release);
    atomic_fetch_add_explicit(&d->seq, 1, memory_order_relaxed);   /* back to even */
}

The fences are required because the increments are relaxed. A release fence before the data writes keeps them from being hoisted above the odd increment; a release fence after keeps them from being sunk below the even increment. Without them, a weakly ordered core may make the data visible before the counter goes odd, and a reader can then observe a consistent even counter alongside partially updated data.

The reader’s acquire fence between the data loads and the second counter load is the mirror image: it prevents the second load from being hoisted above the data reads, which would allow the reader to validate a counter value that was true before the data it actually observed.

There is a subtlety in the standard’s fence rules. A release fence orders preceding writes against a following store only when the fence is followed by a store, which the odd increment satisfies. On the read side, an acquire fence orders preceding loads against following operations, and the data loads precede it. The arrangement above satisfies both conditions, and it is the reason the fences sit where they do rather than being attached to the counter operations themselves.

Writers must also be serialised against each other. The sequence protocol assumes one writer at a time; two concurrent writers would both increment, and a reader could observe a consistent-looking pair of values drawn from both. Mutual exclusion on the writer side is normally a separate lock, which is why the seqlock is often described as a single-writer mechanism even though the data it protects is read concurrently.

Cost under different load mixes

The read path’s cost depends entirely on the write rate. With no concurrent writes, a reader performs two atomic loads of the counter plus the data loads, and the counter stays in the shared state in every core’s cache so the loads never transfer the line. That is cheaper than a reader/writer lock, which would require a read-side atomic increment and a matching decrement.

With writes at a low rate, the reader occasionally retries. Each retry is a full re-read, so the cost of a read becomes proportional to the expected number of attempts, which is roughly one plus the probability of overlap times the number of attempts. When a write interval is much longer than a reader’s copy, the overlap probability is small and the average attempt count stays close to one.

With writes at a high rate the scheme collapses. A reader whose data reads take longer than the interval between writes never sees a stable counter, and the loop spins indefinitely, consuming a core without making progress. There is no fairness mechanism and no backoff built in; the reader will eventually succeed only when the writer pauses. Under a write rate comparable to the read rate, a seqlock is strictly worse than a lock, because the reader does work that is discarded.

The crossover is a property of the data size and the write rate, not a fixed number. It can be estimated: the reader’s window is the time to copy the protected structure, and the retry probability is the probability that a write begins during that window. Keeping the structure small keeps the window short and the retry rate low, which is the design constraint that shaped the mechanism in the first place.

Where it sits relative to other read-mostly schemes

A reader/writer lock and a seqlock occupy opposite ends of a trade. The lock gives readers a consistent snapshot with no retry and pays for it with read-side writes; the seqlock gives readers no write traffic and pays with retries. The lock’s cost is proportional to reader count and independent of write rate; the seqlock’s cost is proportional to write rate and independent of reader count. Read-mostly workloads with a low write rate sit firmly on the seqlock side.

Read-copy-update solves the same problem with a different mechanism: the writer publishes a new version of the structure by replacing a pointer, and readers traverse whichever version they observed, with old versions reclaimed after a grace period. RCU has no reader retry at all and supports arbitrary read-side work, including side effects, at the cost of a more elaborate publication and reclamation protocol. The seqlock’s advantage over RCU is that it protects a value in place rather than requiring a separately allocated version, which matters for data that is written by hardware or that must live at a fixed address.

Seqlocks also appear outside the kernel, in code that reads a clock. The reason is the same: the read happens on a hot path, the update happens on a timer, and a reader that gets a slightly stale or retried value is acceptable. The mechanism’s applicability is bounded by the purity of the read side and by the write rate, and those two conditions exclude most general-purpose data structures.