论文标题
捆绑参考：高度连续性可线化范围查询的抽象
Bundled References: An Abstraction for Highly-Concurrent Linearizable Range Queries
论文作者
论文摘要
我们提出捆绑的参考文献，这是一个新的构建块，可为高度并发链接的数据结构提供可线化的范围查询操作。捆绑的参考文献允许范围查询穿越与目标原子快照一致的数据结构的路径，并由应访问应访问的最小数量以保持线性化的速度。我们将技术实施到跳过列表，二进制搜索树和链接的列表数据结构中。我们的评估表明，在混合工作负载中，我们的设计在最先进的技术上提高了3.9倍的跳过列表，而二进制搜索树的设计则提高了2.1倍。我们还将捆绑的数据结构集成到DBX1000内存数据库中，在同一竞争者中可获得20％的增益。
We present bundled references, a new building block to provide linearizable range query operations for highly concurrent linked data structures. Bundled references allow range queries to traverse a path through the data structure that is consistent with the target atomic snapshot and is made of the minimal amount of nodes that should be accessed to preserve linearizability. We implement our technique into a skip list, a binary search tree, and a linked list data structure. Our evaluation reveals that in mixed workloads, our design improves upon the state-of-the-art techniques by 3.9x for a skip list and 2.1x for a binary search tree. We also integrate our bundled data structure into the DBx1000 in-memory database, yielding up to 20% gain over the same competitors.
