Latch-Free Index Trees That Scale: Avoiding Thread Switches & Stalls

  • David B. Lomet; Phil Bernstein, Microsoft

Latch contention is a frequent impediment to high and scalable performance when accessing indexed data, even when I/O induced thread stalls have been much reduced. Latch-free techniques have the potential to overcome this impediment. Our Bw-tree used delta updating together with whole state replacement, using a compare and swap (CAS). Whole state replacement resulted in redundant and expensive work by competing threads during structure modifications, limiting scalability. This talk introduces latch-free notices. Notices (1) enable contending threads to establish early the thread doing the bulk of the work, hence avoiding this expensive and redundant work. (2) They form a barrier to safeguard state that is being replaced. (3) They direct ongoing updates to the appropriate elements of node states. This yields a high-performance index sequential access method that scales.

Watch Next