Seqlock and Lockless Read Design¶

Overview¶

Seqlock is a synchronization mechanism optimized for read-dominated workloads.

Unlike mutexes and reader-writer locks, readers do not acquire locks.

Instead, readers validate the consistency of a snapshot using a sequence counter.

This design minimizes reader-side synchronization overhead while preserving data consistency.

Motivation¶

Traditional synchronization primitives require readers to participate in lock acquisition.

Examples:

Mutex

Reader:
    lock()
    read()
    unlock()

RWLock

Reader:
    rdlock()
    read()
    unlock()

Although reader-writer locks allow concurrent readers, readers still modify shared lock state.

In highly read-dominated workloads, this may become a scalability bottleneck.

Sequence Counter Concept¶

A sequence counter tracks update activity.

Convention:

Even
    Stable data

Odd
    Writer active

Example:

Initial:

seq = 0

Writer Begin:

seq = 1

Update data

Writer End:

seq = 2

Readers use the sequence value to determine whether a consistent snapshot was obtained.

Reader Algorithm¶

Reader workflow:

Read start sequence

Read shared data

Read end sequence

Validate snapshot

Validation rules:

start_seq == end_seq

and

sequence is even

If validation fails:

Retry

This allows readers to remain lockless while still obtaining consistent data.

Writer Algorithm¶

Writer workflow:

Acquire writer ownership

Transition sequence:
    even -> odd

Update shared data

Transition sequence:
    odd -> even

Only one writer may update protected data at a time.

Writer serialization is required to prevent concurrent modifications.

Lockless Reader Design¶

A key characteristic of seqlock is that readers never modify synchronization state.

Reader operations consist only of:

Load sequence

Read data

Validate sequence

No lock acquisition occurs.

No reader counters are maintained.

This eliminates reader-side contention.

Reader Retry Behavior¶

Readers may be forced to retry when:

A writer is active

or

A writer completed an update during the snapshot

Retry frequency depends on:

Writer critical section duration

Writer update frequency

Reader polling frequency

Scheduler behavior

Long writer critical sections increase retry probability.

Writer Serialization¶

Seqlock is lockless for readers but not for writers.

Multiple writers must still be serialized.

Common implementations use:

Spinlock

Mutex

CAS ownership acquisition

to ensure only one writer performs updates at a time.

Memory Ordering¶

A typical seqlock implementation follows:

Writer Begin
    Acquire ownership

Update shared data

Writer End
    Release updated state

Readers observe sequence state using acquire semantics.

This creates a publish-and-observe synchronization relationship.

Advantages¶

Very low reader overhead

Excellent read scalability

Simple reader implementation

Suitable for small snapshots

Limitations¶

Retry Cost¶

Readers may repeatedly retry under heavy write activity.

Seqlock is therefore unsuitable for write-dominated workloads.

Pointer Lifetime Problem¶

Seqlock guarantees:

Data consistency

Seqlock does not guarantee:

Object lifetime safety

Example:

Reader:
    ptr = global_ptr

Writer:
    free(ptr)

Retry cannot recover from a use-after-free condition.

Seqlock vs Reader-Writer Lock¶

Feature	RWLock	Seqlock
Multiple Readers	Yes	Yes
Reader Lock Required	Yes	No
Reader Retry	No	Yes
Reader State Updates	Yes	No
Writer Serialization	Yes	Yes
Read Scalability	Good	Excellent

Relationship to RCU¶

Seqlock solves:

Consistent snapshot acquisition

RCU solves:

Object lifetime management

Seqlock and RCU address different synchronization problems and are often used in different parts of the kernel.

Summary¶

Seqlock provides lockless readers through sequence-based snapshot validation.

Readers avoid lock acquisition and validate consistency using a sequence counter.

This design offers excellent read scalability but requires writer serialization and cannot solve object lifetime management problems.