-
Notifications
You must be signed in to change notification settings - Fork 0
Wait Free Reads and Crash Safe
A process crash terminates a process at an unexpected point in its execution. This includes software failures and deliberate termination through kill -9 or abort; the operating system keeps running. A hardware power failure, by contrast, loses any contents of memory and the PageCache (the operating system's file-page cache) that have not been persisted. This article examines structural readability under the former kind of failure.
A write operation on a data structure is usually more than one machine instruction. Inserting a key may require allocating a node, filling its fields, modifying its parent, and then updating an entry link. If these steps directly modify the structure that readers are accessing, a partially completed intermediate state may arise between any two steps. The traditional approach blocks readers with a lock and lets them proceed only after the writer has restored structural consistency.
But making readers wait for writers carries write-path latency into the read path: if a writer is preempted, encounters a page fault, or stalls for a long time, readers stall with it. Improving concurrent read and write performance therefore begins with a question: how can readers avoid intermediate states without waiting for a writer to finish?
One answer separates modifying the structure from making the modification visible. When a local structure needs replacement, the writer completes the changes in a copy, then replaces the entry link pointing to it with a single atomic operation. This combines Copy-on-Write (COW) with atomic publication. The entry link may be a parent-to-child link; it need not be the root of the entire data structure.
Through this link, readers access either the complete structure before the modification or the complete structure after it. Once publication completes, the old structure must remain available until its existing readers have stopped accessing it; only then may it be reclaimed. Construct first, publish next, reclaim last: this order keeps the structure seen by readers complete and consistent at every moment.
flowchart TB
accTitle: Copy-on-Write and Atomic Publication
accDescr: Two panels compare the states before and after publication. Before publication, the entry link points to the old structure while the new structure is built separately. Once the new structure is complete, an atomic replacement redirects the entry link. New readers access the new structure, while existing readers may still access the retained old structure.
subgraph before["① Before publication"]
direction LR
old["Entry → complete old structure<br/>Readers search normally"]
building["New structure<br/>Writer builds it; unpublished"]
old -.Copy and modify.-> building
end
subgraph after["② After publication"]
direction LR
current["Entry → complete new structure<br/>New readers search normally"]
retained["Old structure retained<br/>For existing readers"]
current ~~~ retained
end
before -->|New structure complete<br/>Atomically replace entry| after
Structural consistency answers whether readers can access valid data. Whether they can complete a lookup independently also depends on whether the lookup path requires waiting or retrying. Suppose a reader follows the published structure, neither waits for a writer to release a node lock nor retries because a writer is updating it, and finishes in a finite number of its own steps. Its read can then complete even if the writer stops. This property is called wait-free reads. It meets Herlihy's definition of wait-freedom, with the guarantee here limited to read-side lookups.
Allowing concurrent writers to wait for one another when they conflict makes it possible to coordinate related, multi-step updates with locks, without requiring every write operation to complete independently of other writers. This greatly simplifies data-structure design and makes wait-free reads applicable to a broader range of structures. The key is to confine waiting to writers; readers still access only complete, published structures. This is a pragmatic engineering philosophy.
First, establish the conditions for local replacement: the new structure must be fully initialized before publication; publication of its entry link must be atomic and use the correct memory ordering; and the old structure must not be reclaimed until readers have stopped accessing it.
Consider a local replacement. Let S0 be the old structure, S1 the new structure being prepared for publication, and R the entry link pointing to one of them. The write operation may stop after any instruction, but the entry link has only two observable states:
- The writer has not yet published:
Rstill points to the completeS0. Even if the new storage is only partially initialized, it is unreachable fromR. - Publication has completed:
Rpoints to the fully initializedS1. The old structure remains available until its existing readers finish.
Atomic publication is a single transition between these states. No reader can observe a partially updated entry link. Consequently, wherever the writer stops, a read starting from R can reach only a complete, published structure.
To extend this conclusion to the entire data structure, the update design must also ensure that every local publication preserves the completeness and consistency of the published structure. Given a complete and consistent initial structure, this property holds after any number of such publications. Together with a wait-free lookup path, it lets readers independently complete reads of a valid structure when the writer stops at any step.
Now suppose the writing thread stops at some step and never executes again. The structure remains readable, and concurrent readers do not need to wait for the thread to resume. If the whole process stops, however, its readers disappear too. Does the same argument hold when another process takes over reading?
The new process must first find the bytes of the old structure. Ordinary heap memory is no longer accessible to a new process after the original process exits. A shared file mapping (file mmap with MAP_SHARED) places the structure in file pages managed by the operating system's PageCache. After the process exits, the data remains accessible through the operating system. This does not imply that the data has already been persisted to disk. See the Linux mmap documentation for the distinction between shared and private mappings.
Retaining the bytes is not enough: the new process must also locate the nodes again. When it remaps the same file, the mapping's base address may change, so the old absolute pointers cannot be used directly. Storing node references as offsets relative to the mapping base lets the new process locate each node by adding its offset to the new base. The file must also record an identifiable entry point and the valid range, so the new process knows where to begin reading.
Only after both byte retention and address reconstruction have been addressed can the argument for concurrent reads be applied to a new process.
Under these conditions, the two scenarios correspond point by point:
| Concurrent reads and writes | Reading after a process crash |
|---|---|
| The writing thread stops at any instruction | The original process stops at the same instruction |
| The published entry link in shared memory | The entry offset saved in the file |
| Concurrent readers in the same process | A recovery process that remaps the file |
| Unpublished, unreachable new nodes | Unpublished, unreachable bytes in the file |
| Readers do not wait for the writing thread | Recovery does not wait for the process that has disappeared |
Remapping changes the base address but leaves the node connections represented by offsets unchanged. A recovery reader can therefore start at the saved entry point and traverse the same published structure. Section (4) showed that this structure remains complete and consistent when the writer stops, while wait-free reads guarantee that reading does not depend on the original writer continuing to execute. Thus, a read that a concurrent reader can complete after a writer stalls can also be completed by a recovery reader after the process crashes. This is the isomorphism between wait-free reads and crash safety with respect to structural readability.
Recovery here only reads the structure left by the old process; it does not resume writing to that structure. Even if the original write-side locks remain unreleased, they do not prevent reading through the published entry point. This is the same requirement that lets concurrent readers proceed without waiting for writers to unlock.
The argument above has concrete implementations in two different data structures.
Crash-Safe Parallel Patricia (CSPP), based on a Patricia Trie (a compressed prefix tree), was originally designed for high-performance concurrent reads and writes. For local nodes that need replacement, it completes a copy first, then atomically publishes the new node reference; readers follow the published connections. OffsetSkipList (OSL) is based on a SkipList. It likewise constructs a replacement version array in new storage before publishing it atomically. Neither structure's lookup path waits for write-side locks or retries because a writer has not finished an update.
Both structures represent node references as relative offsets and support file mmap. Structural constraints are established first for high-performance concurrent reads. File mmap then retains the bytes, and relative offsets allow nodes to be located again. The same constraints thus support reading after a process crash, without first repairing the writer's unfinished local changes.