Latch-Free Index Trees Scale by Choosing a Worker Before Reconstruction

Latch-free access changes what contention costs; it does not make contention disappear. As David Lomet explains, when many threads touch the same indexed data, a latch-based system can make them wait on one another. Updates need mutual exclusion, and reads may need latches too, to avoid interference from updates. Under high load, threads that meet at a latch either spin or yield to a thread switch. Lomet describes a switch as costing a couple of thousand instructions; either way, the work a thread appears to do in the code understates the time spent waiting or moving through the operating system.

That cost becomes important even when I/O stalls have been reduced. Caching lowers read I/O, but sustaining a high hit rate can require expensive main memory, especially for data that is rarely accessed. Log structuring, or batching writes, reduces the number of times the system takes the I/O path: writing a hundred pages together can use the same I/O path as writing one page. But Lomet’s point is that I/O is not the only source of stalls. Hekaton, a main-memory database system, used latch-free techniques for this reason.

The basic mechanism he describes is compare-and-swap (CAS). A thread reads a pointer to the current state, builds a proposed new state, then tries to replace the old pointer with the new one atomically. The replacement succeeds only if the pointer still has the value the thread originally observed. If another thread changed it first, the CAS fails. No thread has to wait for a latch to become available; a losing thread can move on and do other work.

But a failed CAS does not make the work that preceded it free. If every competing thread constructs a complete replacement state before trying to install it, only one thread’s work is used. The others have done the same expensive construction in vain. Lomet’s argument is that this redundant work can itself become a scalability limit: at high contention, building a replacement that will be discarded may cost as much as the stalls latch-free techniques were meant to avoid.

The Bw-tree’s delta updates reduce the amount of work needed to build a new state. Rather than reconstructing a whole page for each change, a thread prepends a small delta describing the update. A logical page identifier points to the newest delta, which in turn points toward the underlying base page. The base page contains most of the records; the deltas describe changes to it.

The update is installed with CAS, but the proposed new state is cheap to create because it is just a delta. This makes the approach effective for updates. Its cost accumulates on the read path: as more deltas are chained together, a reader must work through more of them to interpret the page. Since page searches are frequent, a long chain eventually degrades read performance.

The solution is consolidation. A thread gathers the base page and its deltas into a single new, read-optimized page, then uses CAS to replace the old state with the consolidated page. Updates and reads can continue while this work proceeds. Consolidation also batches the changes: instead of repeatedly reorganizing the base page for each update, the system incorporates a group of deltas at once.

Consolidation is still latch-free, but the operation is much more expensive than prepending one delta. That creates the original CAS problem again. Without a way to settle contention early, multiple threads can each build a consolidated page from the same prior state. One wins the CAS; the other completed pages are discarded. The problem is particularly acute at high load, when several threads may decide that the same hot page needs consolidation.

The proposed change is to compete for the right to do the work, rather than to compete after each thread has already done it. A thread first attempts to install a notice with CAS. The thread that succeeds becomes responsible for the expensive operation. Other threads see that notice and do not build competing replacement pages.

In consolidation, the winning thread uses the notice to mark the state it will consolidate. The notice also protects that state while the new page is being built. Other threads can continue to prepend update deltas, but those updates do not alter the protected portion being consolidated. When the new page is ready, the worker replaces the notice and the state beneath it with the consolidated page. Only the winning thread performs the expensive reconstruction; other threads can continue with their own updates.

The replacement point matters. A new delta arriving during consolidation may change the mapping-table pointer so that it points to a delta above the notice rather than directly to the notice. The consolidating thread then follows the delta chain to the notice and replaces the notice and the state below it. Deltas added above the notice remain in the chain. This means the thread installing the consolidated page does not need the mapping-table pointer to remain unchanged throughout the work; it needs to locate the notice that marks the portion of state being replaced.

The notice therefore has several roles: it establishes a winner early, safeguards the state that winner is using, and helps direct ongoing updates while the work is under way. Lomet summarizes the first role:

Craig Freedman pressed on whether ongoing updates could prevent the winning thread from installing its consolidated page. Lomet clarified that new deltas can be prepended above the notice. The consolidating thread need not replace the mapping-table pointer directly: it follows the delta chain to the notice and replaces the notice and the state below it. The newer deltas remain above the replacement.

This arrangement does not prevent all contention. Threads still compete to install the notice, and failed attempts to post one are work that does not succeed. The point is to make that early competition cheap. The costly reconstruction happens only after the winner is established. For consolidation, the protected state can then be rebuilt once, while updates continue to be represented by deltas.

Consolidation concerns one node. A B-tree split involves more than one node and cannot be represented simply as an instantaneous replacement of one complete state by another. Threads may encounter the tree while the split is partway through. Lomet calls these intermediate arrangements transition states: the system must preserve a valid interpretation of the data while the structure is changing.

The split begins with a node O whose records cover both sides of the key that will divide it. The new node N must be allocated and made available as a destination for the high-key range. The split notice, or sNOTICE, carries the split key and information about N. The source distinguishes preparing that destination from resolving contention at O: first the thread allocates a slot for N in the mapping table and installs the sNOTICE at that new slot; then it attempts a CAS at O to install the sNOTICE there. That second CAS is the contention point. If it succeeds, the thread has won the right to carry out the split.

After the sNOTICE wins at O, it provides the information needed to route updates during the split. Low-key updates remain with O; high-key updates go to N. The notice protects the earlier contents of O while the winning thread copies the high records and relevant high-range deltas into storage for N. The work does not modify the protected old state.

The newly allocated N is initially a destination, not yet a completed high page. Once the high records and the deltas that belong with them have been assembled into a consolidated state, the notice can be updated so that the high page is available in its completed form. Until then, the notice directs threads to the state they can safely use. The lower range remains associated with O, while the high range is being prepared for N.

O may temporarily contain high records that logically belong to N. The old state cannot simply be edited in place to remove them while it is also serving as the protected input to the split. Lomet says O can be consolidated later to form the low node without those high records. This is one reason transition states matter: a reader or update path must understand how the range is divided even before the old node has been cleaned up.

Lomet compares this with B-link trees, whose handling of intermediate states allows a node to retain contents that have also been moved to a new page. In the split he describes, a thread must interpret the old node as containing more than the range that logically belongs there during the transition. The comparison concerns this ability to operate while the structure is between its earlier and final forms, not a claim that every detail of the two procedures is identical.

The split also illustrates how a notice both guards data and routes new work. Protecting the earlier contents lets the winning thread construct N from a stable input. Routing updates to O or N lets the index remain active rather than waiting for the split to finish. Those are separate requirements: a stable source for reconstruction does not by itself tell later updates where to go, and routing alone would not preserve the contents being copied.

This is not a promise that readers always see the latest state. Lomet distinguishes this system-level concurrency from transaction locking: a reader racing with an update may see a valid earlier state rather than a later one. The system must ensure that the state a reader is traversing remains available and coherent, not that every read incorporates every concurrent change.

A merge introduces a different set of hazards. The operation involves a parent node and two adjacent child nodes: the node being deleted and the node that will absorb its contents. A thread may already have followed the parent before another thread begins the merge, so protecting the parent alone is not enough. Updates may still be in progress at the node that is about to disappear.

Lomet’s merge diagram uses three notices to cover those distinct risks. First, a PNotice is installed at the parent. It resolves contention, keeps the parent from splitting during the operation, and identifies the nodes being merged. The thread that installs it becomes responsible for the remaining work.

Next, a DNotice marks the node being deleted and redirects further updates from it to the node that will remain. This matters because some threads may have reached the deletion candidate before the PNotice was posted. The DNotice prevents those threads from continuing to modify the state that the merge is trying to collect.

An MNotice then isolates the receiving node’s state for reconstruction. Updates arriving after the notice can remain above it as deltas, without changing the state being merged. The winning thread can build a consolidated node from the protected contents of the receiving and deleted nodes, then replace the appropriate state. At the parent, an update removes the index entry that would otherwise lead to the deleted node.

The distinction between updates below and above the MNotice determines what the merge incorporates. Lomet says the merge is built from the protected state below the MNotice, including the state being collected from the receiving and deleted nodes. Updates that arrive above the MNotice after it is posted are not part of that reconstruction. They remain as deltas for the merged page. The source does not treat all updates in the system as one undifferentiated batch: the notices establish which earlier state is protected for the work and where later updates are directed.

The DNotice and MNotice work together to route those later updates. The DNotice stops further updates from changing the state being collected at D and redirects them toward M. The MNotice marks the boundary between the receiving node’s reconstruction input and updates that can continue above it. Lomet clarified in response to a question that updates above the MNotice are not folded into the new state; they are updates for the merged page and remain above the notice. The worker reconstructs from the state below the boundary.

During the transition, a search or update may need to interpret the notices and choose a node based on the key boundary between the two ranges. The MNotice indicates that the receiving node’s reconstructed state does not yet contain everything from the deleted node; the DNotice preserves the state that still has to be consulted for the relevant range. A thread looking for an item in the range associated with D may need to look there while the merge is incomplete. The notices therefore do more than select a winner. They tell the system where data and updates belong while the new structure is incomplete.

The sequence is more involved than consolidation because it must account for threads already in flight and for multiple nodes in transition. The PNotice settles which thread performs the operation and identifies the nodes. The DNotice handles updates that reach the node marked for deletion, including threads that may have reached it before the parent was marked. The MNotice protects the input for reconstructing the receiving node while allowing subsequent updates to continue above it. Lomet says he has not found a way to make this sequence simpler, and emphasizes that the substantial work follows the early contention decision.

Replacing a page or node does not mean its old storage can immediately be reclaimed. A reader may already be traversing that state. Lomet says the Bw-tree approach uses epochs to manage allocation and deallocation: storage remains available until the system can determine that no thread can still see it. At intervals, the system closes an old epoch and begins a new one; code allocates and frees storage within that scheme.

This is what lets a reader continue through an earlier version while another thread installs a new one. The reader may not see the latest update, but it should see a valid state, and the memory for that state must persist long enough for the reader to finish. Lomet presents epochs as an efficient way to handle these races, while acknowledging that memory management is not a “completely free lunch.”

He also points to a latch-free technique outside index access methods. In a log-structured store, a fetch-and-increment instruction can reserve slots as multiple threads fill a write buffer. Unlike a CAS race in which only one contender wins, multiple fetch-and-increment operations can each succeed and obtain distinct positions. The buffer can then batch page writes, reducing the number of I/O paths and associated stalls. The example shows that notices are useful for contested structural work, but not every latch-free operation needs them.

Lomet closes by noting another performance dimension he did not develop in the talk: hardware-cache efficiency. His reference to AlphaSort is a reminder that avoiding I/O and thread stalls does not settle every question about performance. Code that accesses memory widely can still pay heavily for memory latency. Notices address wasted work and contention in latch-free index trees; other performance concerns remain.