Latch-Free Index Trees That Scale: Avoiding Thread Switches & Stalls
David Lomet presents latch-free notices as a way to make index trees scale under high contention. Notices let contending threads elect a single winner early, so that the expensive work of consolidating pages, splitting nodes, and merging nodes is done once rather than redundantly, while the notice also guards the state being replaced and routes concurrent updates. The talk covers latch-free basics with CAS, the cost of delta chains, and detailed walkthroughs of consolidation, splits, and merges in the Bw-tree.
Dave Lomet opens by framing the problem: latch contention, not just I/O, throttles index performance at high load, because threads block one another through spin loops, thread switches, and OS transitions that add thousands of instructions to the apparent code path. He presents latch-free techniques as the remedy, starting from compare-and-swap (CAS) on a mapping table pointer, where a losing thread can still do useful work if the design leaves it a way to do so. The core weakness he identifies in the original Bw-tree is that delta updates reduced the cost of building new state, but whole-state replacement via consolidation still let many threads redundantly build expensive consolidated pages, and only the winner’s work survived.
Delta updates and consolidation
Delta updates prepend cheap change records to a base page through CAS, but read performance degrades as delta chains grow, so periodic consolidation merges deltas into a fresh base page, again installed by CAS. Lomet notes that consolidation is itself lock-free, but its cost is high and it is the point where redundant work accumulates. He also describes the Bw-tree’s batching effect: deltas are effectively a queue of pending updates that are folded into the base page in bulk.
Notices: deciding the winner early
The central contribution is the notice, a special delta posted via CAS that acts as a claim on the right to perform a structure modification. The first thread to post its notice wins, and all remaining work (the expensive consolidation, the split copy, the merge) is done by that single thread after the contention point. Losers do not build redundant state; they go on to post ordinary deltas above the notice. The notice also serves two other roles: it protects the state beneath it from concurrent change while the winner rebuilds that state, and it directs ongoing updates to the correct place. Lomet’s guiding principle is to do as little work as possible before the notice is posted, since anything done earlier is wasted if the thread loses.
A recurring question from the audience concerned starvation: if updates keep arriving and each one invalidates the consolidator’s CAS, could a hot page never be consolidated? Lomet’s answer, which the discussion made clearer, is that a thread encountering a notice can walk the delta chain to find the notice and replace it at the right point, so a notice remains reachable even after other deltas have been prepended. Another exchange clarified that the old base state stays valid for readers because of epoch-based memory reclamation: storage is freed only once no thread can still see it. Lomet is candid that readers may observe a state that is slightly stale or that races with concurrent updates, but they always see a consistent, balanced state, and he argues that any concurrency control scheme, latched or not, must tolerate such races at the system level, which is distinct from transactional serializability.
Structure modifications
Splits are harder because they touch multiple nodes and require transition states. Before the notice is posted, the splitting thread only allocates a stub: a new logical page ID in the mapping table pointing to a split notice carrying the split key and the new node’s address. The CAS installing the split notice on the old node is the contention point. After that, the winner copies the high records and high deltas into the new node, consolidates them there, and then atomically installs the new node’s pointer. Lowkey updates continue to go to the old node and highkey updates go to the new node, with the split notice routing between them. Lomet draws a parallel to B-link trees, where a node can temporarily hold data that logically belongs to its sibling, and readers must understand that transitional state.
Merges follow a similar pattern with three notices. A parent index notice (P) freezes the parent so that it cannot split and identifies which adjacent children are merging, and its posting is the contention point. A delete notice (D) on the node being removed redirects further updates to the surviving node, which handles threads that read the parent before P was posted. A merge notice (M) on the surviving node protects the state being combined while the heavy merge work proceeds offline, and updates arriving after M are stacked above it. The winning thread finally replaces the parent’s index term to complete the merge. Lomet acknowledges that merges have historically been the hardest part of B-trees, and that the notice-based sequence, though it has many steps, is simpler than the earlier Bw-tree version.
Other latch-free considerations
Lomet notes that memory management in all of these approaches requires epochs to ensure threads see either a before or an after state, and he argues epochs are the most effective mechanism for this. He also observes that latch-free techniques extend beyond access methods: the log-structured store allocates space in its write buffer with an atomic fetch-and-add, so every thread succeeds in claiming a slot, and batching many page writes into one I/O reduces the number of trips through the I/O path. He closes by pointing to cache efficiency, drawing on the AlphaSort work with Jim Gray, as another important but unaddressed dimension of scalability, and he references the Bw-tree and Deuteronomy papers, including Alibaba’s work that introduced the consolidation approach discussed in the talk.