Latch-Free and Faster: David Lomet on the Engineering of High-Performance Database Kernels and the Future of Concurrent Access Methods
“To build a system, you need a team.”
Q1. The Bw-tree, which emerged from your Deuteronomy project, won the 2023 ICDE 10-Year Most Influential Paper Award — a recognition that its ideas have proven durable well beyond the original publication. For database engineers who know the Bw-tree by reputation but may not have read the original paper, can you explain the core insight that makes it latch-free — what specifically does the design avoid that traditional B-tree implementations require, and what is the fundamental reason that avoiding it matters so much for throughput on modern multi-core hardware?
Latches are the traditional way to coordinate access to shared data. The accessing thread places a latch on all access paths to some contended-for shared data. The latch, if it s a write latch, blocks access from all other threads so that the accessing thread can safely modify the shared data, hence ensuring that the updates are made against data that does not change during the update. But latches lead to blocking of other threads. At high scale and high contention, this means that many threads can end up being blocked, awaiting their turn to see and/or update the shared data. Latch-free, at the conceptual level, permits all threads to safely access shared data and not block. Hence contention induced thread stalls or switches are avoided and performance scales. Contention for hot data typically rises as performance increases. Threads stalls then can become the limiting factor in building high performance systems.
Q2. Latch-free programming in access methods is often described as conceptually appealing but notoriously difficult to implement correctly — particularly around the correctness of concurrent structural modifications, page splits, and merges without holding latches. Can you walk us through the hardest correctness challenge you encountered in the Bw-tree implementation, how you approached it, and what the experience taught you about the gap between a latch-free algorithm that is correct in theory and one that is correct in the presence of real hardware memory models and compiler optimizations?
Traditionally latch-free methods have not been employed because they are difficult to implement. For example, if one were to gain access to a page not protected by a latch, one might see the page while it is being changed. An update to a changing page is what we call a bug. That said, it is difficult to avoid such a problem, especially when a page is being updated in-place. We avoided this problem by avoiding update-in-place. Instead, we updated by prepending deltas (the changes desired) into a “queue” of changes. This posting is very fast as it does not require changing the structure of the shared page. And prepending can be done atomically, avoiding contention most of the time, and when it occurs, resolving it very simply be doing the prepending again.
The challenge comes when one wants to integrate the prepended change list of updates into a read optimized format. We call that effort “consolidation”. Prepending permits us to amortize the consolidation cost of integrating changes over a batch updates. Our latest work shows also how one can do that while avoiding having multiple threads racing to do the consolidation, with only one succeeding. Instead, a thread prepends a consolidation “notice” to the list of updates. That notice tells other threads that they can ignore the need for consolidating the updates because the thread posting the notice has already accepted that task.
Finally, it is worth noting that latch-free techniques require some infrastructure to be built so that storage management is handled correctly and efficiently. Most systems require some form of storage management, but latch-free systems infrastructure differs from most of these. The good news is that this infrastructure can be efficient and effective. And it has the virtue that this memory management is localized in one sub-system that can be quite general purpose.
Q3. Thread stalls and thread switches — the costs that latch-free programming is designed to reduce or eliminate — are increasingly understood as the dominant bottleneck in high-concurrency database workloads on modern NUMA architectures with hundreds of cores. How do you think about the relationship between latch-free access methods and the broader question of thread scheduling and core affinity in database kernel design — and what architectural decisions at the kernel level tend to undermine the throughput gains that a well-designed latch-free index can theoretically deliver?
One has to work to reduce thread switches and stalls everywhere. So a latch-free approach is helpful but does not do the entire job. One needs effective data caching and effective I/O cost reduction as well. Main memory systems get their performance mostly by avoiding I/O stalls. Their problem is one of cost, where data in memory is about a factor of 10 higher cost than keeping it on flash storage. But there are cost-effective caching approaches. In addition to caching nodes high in a B-tree to reduce index node I/Os, one can also cache records instead of pages, etc. I/O costs can be reduced by layering the indexing method on top of a log structured store. Log structuring is one of the great system level ideas, though I believe it is a bit mis-named. It is actually a method of batching writes, so that instead of having, say, 100 writes of individual pages with their associated I/O costs, one has a single write of a 100 page buffer. You pay an implementation cost because these buffer writes re-locate pages, and that relocation needs to be tracked, and a mapping needs to be maintained. But this can be done surprisingly cheaply. This is another area that I have also worked on.
Q4. The Deuteronomy architecture introduced a clean separation between the transactional component and the data component, with the latch-free Bw-tree index and the LLAMA log-structured store as the key elements of the data layer. That separation proved directly influential in both Microsoft Hekaton and Azure Cosmos DB. Looking back at that architectural choice, what were the specific engineering benefits that the separation enabled that would have been significantly harder or impossible to achieve in a more monolithic design — and what trade-offs did it introduce that are less often discussed?
Hekaton wanted a main memory, latch free index ONLY. They had their own method of persisting changes. The fact that we had the Bw-tree as a separable component made its use in Hekaton much easier. The Bw-tree was also used as a separate component in Cosmos DB. There, its latch-free design was secondary to the fact that it was layered on top of our log structured store. The log structured store supported “blind updates”, enabling Cosmos DB to support “instant” updating of key words from documents. Supporting blind writes meant that it was not necessary to read in pages containing key words from prior documents in order to update the key word index. We also had a transactional component that permitted transaction isolation to be achieved with many different back ends. In fact, we used the recovery log buffers as part of our record cache, getting double duty use from our transactional mechanism.
Q5. You have been engineering database kernels since the 1970s — contributing to DEC’s Rdb, Microsoft SQL Server, and the Deuteronomy research system — and you have watched the hardware substrate change dramatically from single-core mainframes to massively parallel NUMA systems to NVMe storage that approaches DRAM latency. How has the fundamental challenge of access method design changed across those hardware generations, and what assumptions that were reasonable in earlier database kernel engineering are now the most dangerous to carry forward into the design of access methods for current and near-future hardware?
As hardware engineers have run into scaling problems, they have exported a substantial part of that problem to software. This is a very old problem for hardware engineers. Eventually it became clear to them that they could not continue scaling performance by making single threaded chip designs. The last big push in that engineering direction was the introduction of RISC processor chips. But that introduced an access speed gap between processors and main memory, so I am not even talking about the gap in going to external storage. This is a hard problem. Software engineers have been pushing to cope with these latency differentials for much of the last three decades, the earliest prominent software systems work being AlphaSort.
I facetiously refer to this at times as the hardware engineers exporting their problems to the software engineers. But this is exactly what you want to happen. Most implementation effort becomes at least just a bit less performance critical as one goes up the “logic” stack. And it can be more specialized in software that is closer to the higher-level goals of the systems. The RISC systems were based on a similar observation. Make the low level parts simpler and faster, and tailor the higher level parts, which were less pervasive and more special purpose, to effectively use the simple but very high performance lower level elements.
I’ll give you one example from early in my career of how engineering has had to become more aware of and supportive of multi-processing. We used to support multi-processing (he says “in the early days” 😊) by multiplexing on a uniprocessor. Doing this introduced race conditions, but they were mostly dealt with by careful selection of when to permit the switching of the single hardware processor between software tasks. This avoids having to cope with arbitrary points of conflict. This is not now an effective strategy in most cases because we want to exploit multiple hardware processors (and chips) to achieve maximum performance.
Q6. You founded and led the Database Group at Microsoft Research Redmond for over 20 years, authored more than 120 papers, hold over 65 patents, and have seen your research translated directly into production systems used by millions. That combination — deep theoretical contribution and direct production impact — is genuinely rare in database research. Looking at the current generation of database researchers and systems builders, where do you see the most promising unexplored territory in latch-free and concurrent access method design — and what problem in this space do you believe deserves more attention than it is currently receiving?
Making predictions is difficult, especially of the future. I was once, long ago at IBM, a believer that careful program overlays would always beat virtual memory in performance. My understanding was that IBM had built virtual memory support into their 370 computers, and the only thing that they saw when they turned it on was system performance dropping by 10%. But this was the wrong way to look at the problem. Using virtual memory made programming much easier. And programs built with virtual memory in mind actually were simpler and ended up being every bit as fast as those using careful overlays. So I was right… but wrong.
I am retired now, so my crystal ball is a bit foggy. But getting more “nines” of availability surely continues to be a big problem. This will require running multiple standby systems. Coordinating their execution and fail-over is a challenge. Latching is a low level, more local mechanism than this, as is latch-free technology. But low level execution performance and cost will always be important.
Qx.Anything else you wish to add?
Two things:
- To build a system, you need a team. The Deuteronomy project involved both novel architecture and novel mechanisms. This was emphatically not a one person project. I was incredibly lucky in having great colleagues on this effort. It was the team that made it happen. Success in influencing Microsoft products required receptive and highly skilled software development engineers who did so much of the work in making the technology and its transfer a success.
- Good abstractions are essential to every level of systems architecture and implementation. This is why data management systems support transactions and atomicity. A good abstraction needs to be easy to use, easy to define, capable of efficient implementation. Good abstractions enable technological progress. If there is a secret sauce in building systems, that is it. In the current context, this was (a) latch-free technology, some of which already existed, which avoided contention bottlenecks; log structuring, which reduced write I/O costs; and flexible caching, which reduced read I/O costs.
…………………………………………………………………………..
David Lomet founded (1995) and managed the Database Group at Microsoft Research Redmond for over 20 years. He previously worked at DEC (Cambridge Research Lab and Rdb database group), Wang Institute, and IBM (Yorktown Research Lab and Federal Systems Division). His career spans industrial research, academia, and product development. He won an IBM fellowship to the University of Pennsylvania, where he received a PhD in computer science .
Lomet has worked in architecture, languages, and systems. His primary focus is database systems. He is an inventor of transactions while on sabbatical at Newcastle-on-Tyne working with Brian Randell. He has authored over 120 papers (http://dblp.uni-trier.de/pers/hd/l/Lomet:DavidB=),including two SIGMOD best paper awards, and an ICDE Most Influential paper award. He holds 65 patents. His technical focus is on indexing, concurrency control, and recovery. His Deuteronomy project, includes the Bw-tree, used in SQL Server’s Hekaton main memory DBMS (www vldb.org/pvldb/vol6/p1178-lomet.pdf) and both Bw-tree and the LLAMA log structured store used in DocumentDB (www.vldb.org/pvldb/vol8/p1668-shukla.pdf) [now Azure Cosmos DB]. Deuteronomy won Microsoft Redmond Lab’s 2017 Outstanding Research Project Award.
Lomet served as Computer Society 1st VP, treasurer, and secretary and he served on the CS Board of Governors (2015–2021). He also initiated successful efforts to expand the Board of Governors to include leaders from conferences, publications, and membership areas. Other CS service includes the T&C Board, where he initiated and helped lead the effort to share conference surpluses among TCs, conferences, and CS. He served as program committee cochair for ICDE and VLDB, and as ICDE conference cochair. He was chair of the Technical Committee on Data Engineering and a member of the ICDE steering committee. He received the Computer Society’s Outstanding Contribution Award and SIGMOD’s Contributions Award for his service as editor in chief of the IEEE Data Engineering Bulletin (http://tab.computer.org/tcde/bull_about.html) for 25 years. He has served as VLDB program committee cochair, member of the VLDB board, and an editor of ACM TODS, VLDB Journal, and DAPD Journal. He is an IEEE CS Golden Core Member, a Fellow of IEEE, ACM, AAAS, and a member of the National Academy of Engineering.