How Lock-Free Index Trees Scale: Avoiding Thread Switches and Stalls

Database luminary David Lomet (founder of Microsoft Research's Database Group and member of the National Academy of Engineering) delivered a technical talk systematically explaining the design philosophy behind latch-free index trees. The talk built on his earlier work leading the BW-Tree project at Microsoft and introduced a new mechanism called "Notices" to address scalability bottlenecks under high concurrency.

This article distills his core arguments: why traditional latches limit scalability, the fundamentals of lock-free techniques, the limitations of Delta updates and consolidation, and how Notices dramatically reduce wasted work under high contention.

Why Latches Become a Scalability Bottleneck

Lomet begins by clarifying a counterintuitive insight: under heavy load, hot data can actually hurt performance. At low load, hot data makes buffer pool caching and hardware caching more efficient — but as the system approaches its performance ceiling, the contention caused by high update rates becomes the limiting factor.

The root of the problem is that traditional latches rely on mutual exclusion. Updates must acquire a latch for exclusive access, which disrupts both writes and reads — reads must also acquire latches to avoid being interrupted by concurrent updates. The result is that under extreme load, threads collide with and block each other.

Once a collision occurs, the cost is far higher than the code might suggest: a thread either enters a spin-wait (stall), performs a thread context switch (consuming roughly thousands of instructions), or drops down to the OS layer to handle I/O. Lomet specifically notes that even with SQL Server's own OS layer, the cost of a thread switch cannot be avoided. The actual code execution path is therefore far longer than it appears on paper.

This is precisely why Microsoft's in-memory database system Hekaton chose latch-free techniques, with Lomet's team providing the accompanying BW-Tree.

Lock-Free Fundamentals: The Double-Edged Sword of Compare-and-Swap

The core tool of lock-free technology is Compare-and-Swap (CAS). It atomically switches a pointer from an old state to a new state — provided the old state hasn't changed since it was last read; otherwise the operation fails. Ultimately, only one thread succeeds in installing the new state.

The elegance of CAS is that a failing thread is never blocked — it can go do other useful work. This stands in sharp contrast to the "dead wait" of latches. But lock-free is no silver bullet; it has two pitfalls:

• Multiple threads may redundantly construct the same new state;
• If constructing the new state is expensive, the work done by all failing threads is entirely wasted.

Lomet emphasizes that under high contention, this "wasted work" can be just as costly as a thread switch. In other words, if lock-free techniques are applied carelessly, scalability can suffer just the same.

CAS is typically implemented as a single CPU instruction on modern processors (e.g., CMPXCHG on x86), with atomicity guaranteed by hardware — no OS involvement needed. It is the cornerstone of lock-free data structures: a thread reads the current value as its "expected value" before making a modification, then uses CAS to attempt switching the pointer from the expected value to the new value. If another thread has modified the pointer in the meantime, CAS fails and the thread must retry. This mechanism fundamentally eliminates mutual-exclusion waiting, but introduces the ABA problem: a pointer changes from A to B and back to A, and CAS cannot detect the intermediate change, potentially concluding incorrectly that the state is unchanged. BW-Tree avoids this through a Mapping Table for indirect addressing — CAS operates on slot pointers within the mapping table, pages are never modified in-place, and an epoch mechanism ensures old versions are not reclaimed before all threads have stopped referencing them.

Delta Updates and Consolidation: BW-Tree's Strategy and Its Limits

BW-Tree's Delta updates dramatically lower the cost of constructing new states. Instead of the mapping table pointer pointing directly to a page, a CAS installs a Delta update node that points to the old page. The Delta records incremental modifications to the page, making it extremely cheap to construct.

But Delta updates hurt read performance. A single Delta is harmless, but as updates accumulate, Deltas pile up in a chain, and reads must linearly traverse the entire chain. Since page searches are extremely frequent, this has a significant performance side effect.

The solution is periodic consolidation: all Deltas are merged with the base page to reconstruct a read-optimized "consolidated page," which is then installed via CAS to replace the old structure with its long Delta chain. Consolidation itself is also lock-free, relying on CAS.

Lomet compares Delta updates to a "queue of pending updates" — the system applies these updates to the base page in bulk rather than one at a time, amortizing the cost of large-scale reorganization. "Delta updates + consolidation" is a quite useful strategy, but it still has a problem: when multiple threads simultaneously compete to perform consolidation, only the winner's work is effective, and all other threads' consolidation work is wasted.

Notices: Competing for the Right to Act, Not for the Result

This is the core problem that the new Notices mechanism addresses. In the traditional approach, threads each build a new page and then compete to install it — losers' construction work is entirely discarded. The idea behind Notices is to let threads first compete for the right to perform the work.

The thread that wins the competition doesn't immediately install a new page. Instead, it first publishes a Notice at the contention point, signaling to other threads: "I've claimed this job." Other threads seeing the Notice no longer build redundant new states — they simply stack their Delta updates on top of the Notice and continue their own work.

The key principle is: do as little work as possible before publishing a Notice. Work done before a Notice is published is wasted on a loss, so expensive work should be deferred as much as possible until after contention is resolved. This way, the only wasted work is the attempt to publish the Notice itself.

Once a Notice is published, it protects the old state beneath it from modification, allowing the winning thread to leisurely build the consolidated page "offline" — this is the most expensive part, but it's done by only one thread. Meanwhile, other threads' ongoing updates can still be stacked as Deltas on top of the Notice, without interference.

Worth noting is the handling of read-write race conditions. A thread traversing the old state is "unaware" of the new consolidated node being installed — it continues along the old path. The system uses an epoch mechanism to manage memory allocation and reclamation, guaranteeing that the old state persists until no thread can still observe it. Lomet acknowledges that such race conditions exist in nearly every concurrency control approach — including latches — and implementers must be prepared to handle them. A read may not see the most recent state, but it will always see a valid state.

Handling Structural Modifications: The Challenge of Splits and Merges

Consolidation only involves a single node, which is relatively straightforward. The real difficulty lies in B-tree-style Structure Modification Operations (SMOs), which involve multiple nodes — Notices must additionally provide transition states.

Node split: Very little preparation is done before publishing a Notice — allocate a mapping table slot (stub) for the new node and point it to a split Notice containing the split key and the new node's address. The contention point is installing an S-Notice on the old node via CAS. Once installed, the S-Notice routes updates: low-key updates go to the old node, high-key updates go to the new node. The expensive work — copying high-key records and high-key Deltas to the new node — happens after contention is resolved, performed by a single thread. Lomet notes this is precisely an improvement over BW-Tree: expensive work is deferred until after contention resolves.

Transition states are involved here as well. Similar to the B-link tree approach, the old page briefly holds both old and new data simultaneously, then lazily removes the high-key records. Threads must understand this transition state — knowing that the old page temporarily contains records that logically don't belong to it.

Node merge: This has historically been the hardest part of B-trees. The process requires multiple Notices working in concert: publish a P-Notice on the parent index node to freeze the subtree state, prevent parent splits, and resolve contention; publish a D-Notice on the node being deleted to redirect subsequent updates to the absorbing node; publish an M-Notice on the merging node to protect the state being merged.

The three Notice types have distinct roles: P-Notice determines who performs the merge; D-Notice prevents further updates to the deleted node; M-Notice protects the merge state from interference. Only what lies below the M-Notice is included in the final merged state; updates stacked above include those originally destined for both the deleted node and the merging node. The expensive merge work is likewise performed by only the single thread that won the P-Notice.

The B-link tree (a B-tree variant proposed by Lehman and Yao in 1981) is the classic reference for handling concurrent structural modifications. Its core idea is to add a "link pointer" to the right sibling in each node, along with a high key. When a split is in progress, even if the parent node hasn't been updated yet, following the link pointer rightward allows finding the new node containing the target key — eliminating the requirement that a split atomically modify both child and parent nodes simultaneously. This transforms what would otherwise be a multi-step atomic SMO into a transition state that can be completed in stages, at the cost of reads potentially needing to follow one extra rightward link. Lomet drew on this philosophy in Notices' node split design — the old node briefly holds both old and new data, threads must understand the transition state and can follow pointers to find the correct position — a direct echo of the B-link tree's design philosophy.

Further Considerations: Memory Management and Cache Efficiency

Lomet closes with a few additional points. Memory management must ensure threads only ever see a "before state" or an "after state" — never a fragmented intermediate — which BW-Tree achieves with an epoch mechanism that he considers the most efficient way to handle this.

Lock-free opportunities aren't limited to access methods. In log-structured storage, allocating buffer space uses a fetch-and-increment atomic instruction: when two threads compete, both succeed — one gets the low buffer region, one gets the high buffer region, and everyone is happy. This bulk writing not only reduces the number of storage writes but can be managed in a remarkably simple way.

He also touches on a direction he leaves unexplored: hardware memory cache efficiency. Accessing uncached main memory can cost 100 or more cycles, so achieving cache-friendliness — as in the AlphaSort work he did with Jim Gray — is equally critical for performance. Lomet laughs that he's "already said too much" and leaves this for another time.

The epoch mechanism is the mainstream approach in lock-free systems for safely reclaiming memory, solving the core question of "when can an old version of an object be safely freed." The basic idea: the system maintains a global epoch counter; each thread registers the current epoch before accessing shared data and deregisters on exit. Replaced old objects are not freed immediately — they are marked as "pending reclamation" with the epoch at retirement. When all active threads' epoch numbers have advanced past the retiring epoch, it is safe to conclude no thread still holds a reference to the object, and memory is truly released. Compared to reference counting, the epoch mechanism has nearly zero overhead on the read path (only requiring reads and writes to a thread-local variable) and naturally avoids circular reference issues; the trade-off is deferred reclamation, which can accumulate large backlogs of pending objects when threads stay in critical sections for extended periods. Both Hekaton and BW-Tree employ this mechanism.