Introduction

Most traditional algorithms and data structures are designed for tasks whose working set fits entirely into main memory. In these cases, there are a myriad of textbook algorithms and data structures that can easily be optimized for specific applications. For an application whose data set resides partially on disk, however, the set of usable algorithms and data structures is often much more limited. Programs that access data on disk often explicitly move data in and out of main memory. Because these explicit I/O operations substantially increase code complexity, these programs tend to use only canonical data structures such as hash tables, queues and B-trees.

Programming disk-based data structures that can be accessed concurrently is even more difficult. In addition to managing the movement of data to and from memory, programs must also use a mechanism for concurrency control to avoid data races between concurrent operations. Programmers typically use locks to guarantee that critical sections of code execute atomically. Designing an correct locking protocol for a complex data structure that is free of problems such as deadlock or starvation, while still maintaining good performance, is a challenging task.

We have implemented LibXac, a C library that supports non-durable and durable atomic transactions on memory-mapped files. LibXac is designed to provide a simple programming interface for writing code that concurrently accesses data on disk. This interface simplifies the programming of complex, concurrent, disk-based data structures.

Programming Interface

LibXac provides a simple interface for accessing data on disk based on memory mapping. Memory mapping provides the programmer with the illusion of a single-level of storage, allowing the programmer to access data in memory and data on disk in the same way.

LibXac also simplifies concurrent programs by providing support for atomic transactions. Instead of memory-mapping a file normally, using mmap, programmers can transactionally memory-map a file using the LibXac's xMmap function. A program can concurrently access the data in the file inside a transaction. LibXac automatically detects the memory locations that the transaction accesses and guarantees that the transaction executes atomically.

The code in Figure 1 illustrates a simple program that sums the first integer on 5 random pages in a file and stores the result on a 6th random page. The code on the left illustrates an incorrect version that uses locks and normal memory-mapping (if two of these programs run concurrently, deadlock is possible). The code on the right illustrates a similar, correct program written using LibXac.

Implementation

LibXac's implementation is based on memory mapping. Instead of explicitly managing a buffer pool, LibXac relies on the virtual memory manager of the operating system to cache pages in memory. The runtime automatically detects the pages a transaction accesses by manipulating the virtual memory protections on the page and handling segmentation faults. Our implementation relies only on the memory-mapping (mmap) and fault handling capabilities of the Linux operating system. This implementation is more portable than existing transaction systems that rely on features of special research operating systems. LibXac uses a multiversion concurrency control algorithm that ensures that transactions always see a consistent view of the transactional file, even if the transaction aborts.

Progress

We have successfully completed a prototype implementation of LibXac. To demonstrate the ease of programming with LibXac, we have modified serial implementations of a B-tree and a cache-oblivious B-tree to support durable concurrent insertions. In a performance study, LibXac on these search trees provides performance comparable to the Berkeley DB [3], a high-quality transaction system written using explicit I/O. These promising results suggest that, despite the overheads required for maintaining transaction atomicity, it is possible to efficiently support a simple interface for programming disk-based data structures.

Future Work

LibXac is efficient for durable transactions because a transaction commit for a durable transaction must force data out to disk so that the file can be restored to a consistent state in case of a program crash. The cost of doing this disk write dominates any overhead that LibXac incurs for concurrency control. For non-durable transactions however, the overhead of automatically detecting pages accessed by a transaction is much more significant. We hope to investigate ways to make LibXac more efficient for non-durable transactions. Other aspects of the LibXac design and implementation could be improved upon. Another possibility for future work would be to modify the design to be more scalable and test LibXac on a distributed system. Finally, LibXac also represents a software implementation of transactional memory [2]. We are investigating ways in which a system such as LibXac can be merged with hardware or other software schemes for transactional memory to provide practical system support for unbounded transactions [1].

Research Support:

This research is supported in part by the Singapore-MIT Alliance and by NSF Grants ACI-0324974 and CNS-0305606.

References:

[1] C. Scott Ananian, Krste Asanovi'c, Bradley C. Kuszmaul, Charles E. Leiserson, and Sean Lie. Unbounded Transational Memory. In Proceedings of the 11th International Symposium on High-Performance Computer Architecture (HPCA'05), pp.316-327, San Franscisco, California, United States, February 2005.

[2] Maurice Herlihy and J. Eliot B. Moss. Transactional Memory: Architectural Support for Lock-Free Data Structures. In Proceedings of the Twentieth Annual International Symposium on Computer Architecture, 1993.

[3] Sleepycat Software. The Berkeley Database. http://www.sleepycat.com, 2005.