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.
翻译:我们展示了捆绑的参考材料,这是为高度同时锁定的链接数据结构提供可线性范围查询操作的新构件。 捆绑的引用材料允许通过与目标原子快照一致的数据结构进行测距查询。 我们用三种数据结构展示了我们的技术: 链接列表、 跳过列表和二进制搜索树。 我们的评估显示, 在混合工作量中, 我们的设计可以改进最先进的技术, 以1.2x- 1. 8x为跳过列表, 1.3x-3.7x为二进搜索树。 我们还将我们捆绑的数据结构纳入 DBx1000 模拟数据库, 给同一竞争者带来高达40%的收益 。