论文标题
杜鹃Trie：利用内存级并行性进行有效的DRAM索引
Cuckoo Trie: Exploiting Memory-Level Parallelism for Efficient DRAM Indexing
论文作者
论文摘要
我们介绍了杜鹃Trie，这是一种快速，存储效率的有序索引结构。杜鹃Trie的设计目的是具有内存级并行性 - 现代阶外处理器可以利用它并并行执行DRAM访问 - 而无需牺牲记忆效率。因此，杜鹃的特里打破了当前索引面临的基本性能障碍，其瓶颈是一系列依赖的指针插入DRAM访问 - 例如，穿越搜索树路径 - 处理器无法并行化。我们的评估表明，杜鹃的表现优于最先进的索引高达20％ - 在各种数据集和工作负载上，通常具有较小或可比的内存足迹。
We present the Cuckoo Trie, a fast, memory-efficient ordered index structure. The Cuckoo Trie is designed to have memory-level parallelism -- which a modern out-of-order processor can exploit to execute DRAM accesses in parallel -- without sacrificing memory efficiency. The Cuckoo Trie thus breaks a fundamental performance barrier faced by current indexes, whose bottleneck is a series of dependent pointer-chasing DRAM accesses -- e.g., traversing a search tree path -- which the processor cannot parallelize. Our evaluation shows that the Cuckoo Trie outperforms state-of-the-art-indexes by up to 20%--360% on a variety of datasets and workloads, typically with a smaller or comparable memory footprint.
