Collaborative Research: High-Performance Data Access through Memory Abstraction

摘要几十年来，通过内存抽象B树进行的高性能数据访问一直是外部内存搜索的首选数据结构，因为它们最大限度地减少了搜索期间执行的磁盘块访问次数。然而，众所周知，B-树在经验上是次优的，因为它们仅在一个粒度级别(通常是磁盘块)上利用数据局部性，而不是在诸如磁盘磁道之类的较粗粒度上利用数据局部性，或者在诸如高速缓存线之类的细粒度上利用数据局部性。缓存无关数据结构和算法的理论发展表明，如何在每个粒度同时实现近乎最佳的引用局部性。缓存无关数据结构的一个显著特征是，它们将程序员从针对缓存和磁盘影响调优代码的负担中解放出来。PI最近的实验表明，缓存无关B树(CO B树)的性能可以超过高度调优的传统B树。CO B树实现了卓越的性能，因为它们针对所有内存效应进行了近似优化。相比之下，缓存感知算法忽略了内存层次结构的重要方面。然而，CO B树还没有准备好在文件系统和数据库中使用，因为它们缺乏工业强度B树的基本功能，例如支持可变大小的密钥、并发访问和事务。研究人员建议调查CO B-树如何实现其潜力。研究人员计划研究开发全功能CO B树所需的数据结构、字符串和分布式系统中的广泛算法问题。此外，研究人员计划解决在线调度问题，以便虚拟内存系统能够为缓存遗忘提供有效的支持。这项算法工作对于将CO技术转移到计算机科学、工程和科学计算的其他领域是必要的，并旨在改变科学家和工程师处理海量数据集的方式。

ABSTRACT High-Performance Data Access through Memory Abstraction B-trees have been the data structures of choice for external-memory searching for decades because they minimize the number of disk-block accesses performed during a search. It is well known, however, that B-trees are empirically suboptimal because they exploit data locality at only one level of granularity, typically disk blocks, but not at coarser granularities, such as disk tracks, or finer granularities, such as cache lines. Theoretical developments on cache-oblivious data structures and algorithms have shown how to achieve nearly optimal locality of reference simultaneously at every granularity. A striking feature of cache-oblivious data structures is that they free the programmer from the burden of tuning the code for cache and disk effects. The PIs' recent experiments suggest that cache-oblivious B-trees (CO B-trees) can surpass the performance of highly tuned traditional B-trees. CO B-trees achieve superior performance because they approximately optimize for all memory effects. In contrast, cache-aware algorithms ignore important aspects of the memory hierarchy. CO B-trees are not yet ready to be used in file systems and data bases, however, because they lack essential capabilities of industrial-strength B-trees, such as support for variable-size keys, concurrent accesses, and transactions. The researchers propose to investigate how CO B-trees can achieve their potential. The researchers plan to study the wide range of algorithmic problems in data structures, stringology, and distributed systems required to develop a full-featured CO B-tree. In addition, the researchers plan to solve online scheduling problems so that virtual-memory systems can provide efficient support for cache-obliviousness. This algorithmic work is necessary to transfer CO technology to other areas of computer science, engineering, and scientific computing and is intended to transform how scientists and engineers manipulate massive data sets.