Bundling linked data structures for linearizable range queries
Bundling linked data structures for linearizable range queries
复制标题
捆绑链接数据结构以进行线性化范围查询
DOI：
10.1145/3503221.3508412
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Palmieri, Roberto
中科院分区：
文献类型：
--
作者：
Nelson-Slivon, Jacob;Hassan, Ahmed;Palmieri, Roberto
我们提出了捆绑引用，这是一个新的构建块，为高度并发的基于锁的链接数据结构提供线性范围查询操作。绑定引用允许范围查询遍历与目标原子快照一致的数据结构的路径。我们用三种数据结构来演示我们的技术：链表、跳跃表和二叉搜索树。我们的评估表明，在混合工作负载中，我们的设计可以将最先进的技术提高1.2 -1.8倍，对于跳跃表和1.3 -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.
登录
查看更多内容
恒定时间快照以及并发数据结构的应用
DOI：
10.1145/3437801.3441602
发表时间：
2021
期刊：
ACM/SIGPLAN Conference on Principles and Practice of Parallel Programming
影响因子：
--
作者：
Wei, Yuanhao;Ben-David, Naama;Blelloch, Guy E.;Fatourou, Panagiota;Ruppert, Eric;Sun, Yihan
通讯作者：
Sun, Yihan
利用基于纪元的回收来实现高效的范围查询
DOI：
10.1145/3178487.3178489
发表时间：
2018
期刊：
Proceedings of the 23rd ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
影响因子：
--
作者：
Maya Arbel;Trevor Brown
通讯作者：
Trevor Brown
为无锁数据结构回收内存：必须有更好的方法
DOI：
10.1145/2767386.2767436
发表时间：
2015
期刊：
Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing
影响因子：
--
作者：
Trevor Brown
通讯作者：
Trevor Brown
无锁且可扩展的多版本软件事务内存
DOI：
10.1145/1941553.1941579
发表时间：
2011
期刊：
Proceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming
影响因子：
--
作者：
S. Fernandes;João P. Cachopo
通讯作者：
João P. Cachopo
DOI：
--
发表时间：
2001
期刊：
Very Large Data Bases Conference
影响因子：
--
作者：
Shu;V. Tsotras;C. Zaniolo
通讯作者：
C. Zaniolo