Concurrent Cache-Oblivious B-Trees Using Transactional Memory
Concurrent Cache-Oblivious B-Trees Using Transactional Memory
复制标题
使用事务内存的并发缓存不经意 B 树
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Jim Sukha
中科院分区：
文献类型：
--
作者：
Bradley C. Kuszmaul;Jim Sukha
用于外部存储器中存储的数据集的合并性B-Trees表示可以从使用Tran SiCtional Memory（TM）中受益的应用程序，但对于现有的TM实现构成了一些挑战。使用TM，程序员可以通过执行查询和更新作为单个交易来修改串行的，内存高速缓存的B-Tree（Co B-Tree）以直接的方式支持并发操作。在本文中，我们描述了必须克服的三个障碍，但是，在实施有效的外部记忆并发co b-tre e之前。首先，如果基础数据集太大而无法适合主机，则必须在事务内执行输入/输出（I/O）。但是，许多TM实施都禁止此类交易I/O。其次，在持久数据上运行的CO B-TREE需要一个TM系统，如果程序员希望能够在Pro Gram崩溃后能够将数据恢复到一致的状态，则支持持久交易。最后，Co B-Trees操作生成巨石交易，即修改整个数据结构的交易，因为对CO B-Trees的性能保证仅是摊销的界限。在大多数TM实施中，这些交易创建了一个串行瓶颈，因为它们与在Co B-Tree上运行的所有其他并发的Tran Sactions冲突。在这三个问题中，我们认为解决第一个交易I/O问题的解决方案和耐用性是使用支持内存映射数据交易的TM系统。我们通过使用Libxac来证明这种方法的可行性，Libxac支持内存映射的交易，以将CO B-Tree的现有序列实现转换为仅使用几个小时工作的并发版本。我们认为可以将这种方法推广，可以将内存映射的交易用于同时访问存储在外部内存中的数据的其他应用程序。
Cache-oblivious B-trees for data sets stored in external memory represent an application that can benefit from the use of tran sactional memory (TM), yet pose several challenges for existing TM implementations. Using TM, a programmer can modify a serial, in-memory cache-oblivious B-tree (CO B-tree) to support concurrent operations in a straightforward manner, by performing queries and updates as individual transactions. In this paper, we describe three obstacles that must be overcome, however, before one can implement an efficient external-memory concurrent CO B-tre e. First, CO B-trees must perform input/output (I/O) inside a transaction if the underlying data set is too large to fit in main mem ory. Many TM implementations, however, prohibit such transaction I/O. Second, a CO B-tree that operates on persistent data requires a TM system that supports durable transactions if the programmer wishes to be able to restore the data to a consistent state after a pro gram crash. Finally, CO B-trees operations generate megalithic transactions, i.e., transactions that modify the entire data struc ture, because performance guarantees on CO B-trees are only amortized bounds. In most TM implementations, these transactions create a serial bottleneck because they conflict with all other concurrent tran sactions operating on the CO B-tree. Of these three issues, we argue that a solution for the first tw o issues of transaction I/O and durability is to use a TM system that supports transactions on memory-mapped data. We demonstrate the feasibility of this approach by using LibXac, a library t hat supports memory-mapped transactions, to convert an existing serial implementation of a CO B-tree into a concurrent version with only a few hours of work. We believe this approach can be generalized, that memory-mapped transactions can be used for other applications that concurrently access data stored in external memory.