论文标题
技术报告：捆绑链接的数据结构可线化范围查询
Technical Report: Bundling Linked Data Structures for Linearizable Range Queries
论文作者
论文摘要
我们提出了捆绑的参考，这是一个新的构建块，可为高度并发锁定的链接数据结构提供可线化的范围查询操作。捆绑的参考允许范围查询可以穿越与目标原子快照一致的数据结构。我们使用三个数据结构来演示我们的技术：链接列表，跳过列表和二进制搜索树。我们的评估表明，在混合工作负载中，我们的设计可以改进最先进的技术，而跳过列表的最先进技术则可以提高1.2x-1.8倍，而对于二进制搜索树来说，我们的设计可以改进1.2x-1.8倍，1.3x-3.7倍。我们还将捆绑的数据结构集成到DBX1000内存数据库中，在同一竞争者中可获得高达40％的增益。
We present bundled references, a new building block to provide linearizable range query operations for highly concurrent lock-based linked data structures. Bundled references allow range queries to traverse a path through the data structure that is consistent with the target atomic snapshot. We demonstrate our technique with three data structures: a linked list, skip list, and a binary search tree. Our evaluation reveals that in mixed workloads, our design can improve upon the state-of-the-art techniques by 1.2x-1.8x for a skip list and 1.3x-3.7x for a binary search tree. We also integrate our bundled data structure into the DBx1000 in-memory database, yielding up to 40% gain over the same competitors.
