Harnessing epoch-based reclamation for efficient range queries
Harnessing epoch-based reclamation for efficient range queries
复制标题
利用基于纪元的回收来实现高效的范围查询
DOI：
10.1145/3178487.3178489
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Trevor Brown
中科院分区：
文献类型：
--
作者：
Maya Arbel;Trevor Brown
在内存数据库等应用程序中，非常需要具有范围查询操作的并发集。然而，很少有集合实现提供范围查询。已知的使用范围查询（或可用于构建范围查询的操作）扩展数据结构的技术存在许多问题，限制了它们的可用性。例如，它们带来很高的开销或严重依赖于垃圾收集。在这项工作中，我们将展示如何使用高效的范围查询来扩展数据结构，而不依赖于垃圾收集。我们确定了基于时代的内存回收算法的一个特性，使其成为实现范围查询的理想选择，并生成了三种算法，分别使用锁、事务内存和无锁技术。我们的算法比以前的工作适用于更多的数据结构，并且在大规模的英特尔系统上显示出高效率。
Concurrent sets with range query operations are highly desirable in applications such as in-memory databases. However, few set implementations offer range queries. Known techniques for augmenting data structures with range queries (or operations that can be used to build range queries) have numerous problems that limit their usefulness. For example, they impose high overhead or rely heavily on garbage collection. In this work, we show how to augment data structures with highly efficient range queries, without relying on garbage collection. We identify a property of epoch-based memory reclamation algorithms that makes them ideal for implementing range queries, and produce three algorithms, which use locks, transactional memory and lock-free techniques, respectively. Our algorithms are applicable to more data structures than previous work, and are shown to be highly efficient on a large scale Intel system.