Memory-Mapped TransactionsbyJim SukhaSubmitted to the Department of Electrical Engineering and Computer Sciencein partial fulfillment of the requirements for the degree ofMaster of Engineering in Electrical Engineering and Computer Scienceat theMASSACHUSETTS INSTITUTE OF TECHNOLOGYJune 2005c Massachusetts Institute of Technology 2005. All rights reserved.Author . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Department of Electrical Engineering and Computer ScienceMay 19, 2005Certified by. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Charles E. LeisersonProfessor of Computer Science and EngineeringThesis SupervisorCertified by. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Bradley C. KuszmaulResearch ScientistThesis SupervisorAccepted by . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Arthur C. SmithChairman, Department Committee on Graduate Theses2Memory-Mapped TransactionsbyJim SukhaSubmitted to the Department of Electrical Engineering and Computer Scienceon May 19, 2005, in partial fulfillment of therequirements for the degree ofMaster of Engineering in Electrical Engineering and Computer ScienceAbstractMemory-mapped transactions combine the advantages of both memory mapping and transactionsto provide a programming interface for concurrently accessing data on disk without explicit I/O orlocking operations. This interface enables a programmer to design a complex serial program thataccesses only main memory, and with little to no modification, convert the program into correctcode with multiple processes that can simultaneously access disk.I implemented Libxac, a prototype for an efficient and portable system supporting memory-mapped transactions. Libxac is a C library that supports atomic transactions on memory-mappedfiles. Libxac guarantees that transactions are serializable, and it uses a multiversion concurrencycontrol algorithm to ensure that all transactions, even aborted transactions, always see a consistentview of a memory-mapped file. Libxac was tested on Linux, and it is portable because it iswritten as a user-space library, and because it does not rely on special operating system support fortransactions.With Libxac, I was easily able to convert existing serial, memory-mapped implementations ofa B+-tree and a cache-oblivious B-tree into parallel versions that support concurrent searches andinsertions. To test the performance of memory-mapped transactions, I ran several experimentsinserting elements with random keys into the Libxac B+-tree and Libxac cache-oblivious B-tree.When a single process performed each insertion as a durable transaction, the Libxac search treesran between 4% slower and 67% faster than the B-tree for Berkeley DB, a high-quality transactionsystem. Memory-mapped transactions have the potential to greatly simplify the programming ofconcurrent data structures for databases.Thesis Supervisor: Charles E. LeisersonTitle: Professor of Computer Science and EngineeringThesis Supervisor: Bradley C. KuszmaulTitle: Research Scientist34AcknowledgmentsThese acknowledgments are presented in a random order:I would like to thank my advisor, Charles E. Leiserson for his helpful comments on this thesis,and on his helpful advice in general.I would also like to thank Bradley C. Kuszmaul, who has been deeply involved in this projectfrom day one. Bradley’s initial idea started me on this project that eventually became Libxac, andI have had many helpful discussions with him on this topic ever since.I’d like to thank Bradley for giving me an implementation of a B+-tree, and Zardosht Kasheff forthe code for the cache-oblivious B-tree. The experimental results on search trees without Libxacare primarily the work of Bradley, Michael A. Bender, and Martin Farach-Colton.All of the people in the SuperTech group deserve a special round of acknowledgments. Thosepeople in SuperTech, also in random order, include Gideon, Kunal, Jeremy, Angelina, John, Tim,Yuxiong, Vicky, and Tushara. Everyone has been wonderfully patient in listening to my ramblingsabout transactions, names for Libxac, research, and life in general. They have all kept me (rela-tively) sane throughout the past year. In particular, I’d like to Kunal, Angelina, and Jeremy for theirfeedback on parts of my thesis draft, and more generally for choosing to serve the same sentence.I’d also like to thank Ian and Elizabeth, who are not in the SuperTech group, but have also beensubjected to conversations about transactions and other research topics. Thanks to Leigh Deacon,who kept SuperTech running administratively.Thanks to Akamai and MIT for the Presidential fellowship that funded my stay here this pastyear. Also, thanks to the people I met through SMA for their helpful comments on the presentationI gave in Singapore.Thank you to my family and to my friends, here at MIT and elsewhere. Without their support,none of this would have been possible.I apologize to all those other people I am sure I have missed that deserve acknowledgments. Iwill try to include you all when the next thesis rolls around.This work was partially supported by NSF Grant Numbers 0305606d and 0324974, and by theSingapore MIT Alliance. Any opinions, findings and conclusions or recommendations expressed inthis material are those of the author(s) and do not necessarily reflect the views of the NationalScience Foundation (NSF).56Contents1 Introduction 131.1 Explicit I/O vs. Memory Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141.2 Locks vs. Transactions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171.3 Concurrent Disk-Based Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211.4 Thesis Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 The Libxac Interface 252.1 Programming with Libxac . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262.2 Semantics of Aborted Transactions . . . . . . . . …