Seqlock

Deep dive

How it works

In: a small record (N words) to read or write · Out: a consistent copy for readers · State: a sequence counter (odd = write in progress) next to the data · Cost: read = 2 counter loads + N data loads, no shared writes; write = 2 counter stores + N stores

writer:  seq=s+1 (odd) | fence | write data | seq=s+2 (even, Release)
reader:  s1=seq (Acquire); if odd retry | copy data | fence(Acquire) | s2=seq; if s1 != s2 retry

1. Writer: seq.store(s+1, Relaxed); fence(Release); write the fields; seq.store(s+2, Release).
2. Reader: s1 = seq.load(Acquire); if odd, spin; copy every field with relaxed atomic loads; fence(Acquire); s2 = seq.load(Relaxed); accept the copy iff s1 == s2.
3. Why the fences: if the reader's copy saw any value written after the odd store, the release-fence/acquire-fence pair makes that odd store visible to the second counter load, so s2 != s1. Without them, the second load can be reordered before the data loads (on ARM, and by compilers on any CPU).
4. Data fields must be atomics (relaxed) in C++/Rust; a racy plain read is undefined behaviour even if the result is discarded. Relaxed loads compile to plain mov/ldr, so it costs nothing.

Code

use std::sync::atomic::{fence, AtomicU64, Ordering::{Acquire, Relaxed, Release}};

/// N 64-bit words protected by a sequence counter. Pack your POD struct into words (e.g. via bytemuck).
pub struct SeqLock<const N: usize> {
    seq: AtomicU64,
    data: [AtomicU64; N],
}

impl<const N: usize> SeqLock<N> {
    pub fn new(init: [u64; N]) -> Self {
        SeqLock { seq: AtomicU64::new(0), data: init.map(AtomicU64::new) }
    }

    /// Must not run concurrently with another `write` (single writer, or hold a writer mutex).
    pub fn write(&self, v: &[u64; N]) {
        let s = self.seq.load(Relaxed);
        self.seq.store(s.wrapping_add(1), Relaxed); // odd: write in progress
        fence(Release); // the odd store becomes visible before any of the data stores below
        for (d, &x) in self.data.iter().zip(v) { d.store(x, Relaxed); }
        self.seq.store(s.wrapping_add(2), Release); // even: publishes the data stores
    }

    pub fn read(&self) -> [u64; N] {
        loop {
            let s1 = self.seq.load(Acquire);
            if s1 & 1 == 1 { std::hint::spin_loop(); continue; } // writer active
            let mut out = [0u64; N];
            for (o, d) in out.iter_mut().zip(&self.data) { *o = d.load(Relaxed); }
            fence(Acquire); // data loads complete before the re-check
            if self.seq.load(Relaxed) == s1 { return out; }
        }
    }

    /// Non-blocking variant for callers that prefer to do other work than spin.
    pub fn try_read(&self) -> Option<[u64; N]> {
        let s1 = self.seq.load(Acquire);
        if s1 & 1 == 1 { return None; }
        let out = std::array::from_fn(|i| self.data[i].load(Relaxed));
        fence(Acquire);
        (self.seq.load(Relaxed) == s1).then_some(out)
    }
}

// Example: a quote updated by one feed thread, read by many strategy threads.
// let q = SeqLock::<3>::new([0; 3]); q.write(&[bid, ask, ts]); let [bid, ask, ts] = q.read();

Complexity and constants

• Reader: 2 counter loads, N data loads, 1 fence (free on x86, dmb ishld on ARM). In cache, order of 2-10 ns for a few words; if the writer just wrote, one miss per touched line (order of 50-100 ns).
• Writer: 2 counter stores + N stores; the writer pays to invalidate readers' copies of the lines.
• Retry probability ≈ (read duration + write duration) / interval between writes; keep both short.
• Scales to any number of readers because readers only share lines in the S (shared) state.

Efficiency

• Cost: a read is two counter loads, N data loads and one fence (free on x86, dmb ishld on ARM): order of 2-10 ns in cache for a few words, plus one miss per touched line (order of 50-100 ns) right after a write. A write is 2 counter stores plus N stores. Retry probability is about (read time + write time) / interval between writes. Bound: cache misses after a write, not compute.
• Levers:
  • seq and data in the same or adjacent lines — one miss serves both (see false sharing) — small records
  • latch variant (two copies, Linux seqcount_latch) — readers never wait for a write — NMI or time-critical readers
  • try_read with a fallback — no spinning behind a preempted writer — user-space writers
  • 64-bit counter — no wrap during a slow read — user space
  • keep records to a few words — shorter read and write windows, fewer retries — high write rates
• Naive → standard → state of the art:
  • reader-writer lock · readers write the lock word, which bounces between cores
  • seqlock · order of 2-10 ns per read, no reader writes
  • seqcount latch, or RCU for pointer-rich data · wait-free readers

Implementation notes

• Put seq and the data in the same or adjacent cache lines (readers need both); keep unrelated writes away (false sharing).
• Multiple writers: guard writes with a mutex/spinlock, or make the odd transition a CAS from even s to s+1 (Acquire), which doubles as a writer lock.
• Latch variant (Linux seqcount_latch): keep two copies; the writer bumps seq and updates copy 0, bumps again and updates copy 1. Readers pick copy[seq & 1] and never wait for an in-progress write. Safe even when a reader interrupts the writer (NMI).
• In the kernel, writers disable preemption (or IRQs) so a reader on the same CPU cannot spin forever behind a preempted writer. In user space, a writer preempted mid-write makes readers spin; use try_read with fallback or keep writes tiny.
• For generic T: Copy, either map to atomic words, or use ptr::read_volatile + compiler fences like many crates do (works in practice, formally a data race in the Rust/C++ model).

Pitfalls

• Using a pointer read inside the read section before validating: the writer may have freed it. Copy first, validate, then use.
• Missing the acquire fence before the second counter load: torn reads accepted silently, mostly on ARM.
• Plain (non-atomic) data reads in C++/Rust: the compiler may assume no concurrent writes and, for example, read a field twice and get two values.
• Two writers without mutual exclusion: both make the counter odd/even out of step and readers accept torn data.
• Readers starving behind a high-rate writer; measure retry counts.
• Counter wrap: a 32-bit counter can wrap during a very slow read (2^31 writes); use 64-bit in user space.

Variants and alternatives

In production

OS kernels: Linux seqlock_t/seqcount_t (timekeeping core, jiffies_64 on 32-bit), vDSO clock_gettime (user-space reads of kernel time data with a sequence counter), seqcount_latch in ktime_get_mono_fast_ns. Networking: DPDK rte_seqlock, Linux u64_stats_sync. Language runtimes: Java StampedLock. Trading: low-latency shared-memory market data, Rust crate seqlock.

Implementations

Sources

• Hans-J. Boehm, Can Seqlocks Get Along With Programming Language Memory Models?, MSPC 2012. paper
• Linux kernel documentation, Sequence counters and sequential locks (Documentation/locking/seqlock.rst). docs
• Paul E. McKenney, Is Parallel Programming Hard, And, If So, What Can You Do About It?, chapter on sequence locks. book