Constant-time snapshots with applications to concurrent data structures
Constant-time snapshots with applications to concurrent data structures
复制标题
恒定时间快照以及并发数据结构的应用
DOI：
10.1145/3437801.3441602
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Sun, Yihan
中科院分区：
文献类型：
--
作者：
Wei, Yuanhao;Ben-David, Naama;Blelloch, Guy E.;Fatourou, Panagiota;Ruppert, Eric;Sun, Yihan
给定一个并发的数据结构，我们提出了一种方法，有效地采取快照的组成CAS对象。更具体地说，我们支持返回快照句柄的常数时间操作。此快照句柄以后可用于在拍摄快照时读取任何基对象的值。阅读基本对象的早期版本无需等待，所需时间与自快照拍摄以来成功写入对象的次数成比例。重要的是，我们的方法保留了所有的时间界限和原始数据结构的并行性。我们的快速，灵活的快照产生简单，高效的实现原子多点查询的一个大类的并发数据结构。例如，在使用CAS更新子指针的搜索树中，一旦拍摄快照，就可以原子地搜索键的范围，找到匹配某些标准的第一个键，或者检查键的集合是否全部存在，只需在树的快照上运行标准顺序算法。为了评估我们的方法的性能，我们将其应用于三个搜索树，一个平衡，两个不平衡。实验表明，支持快照的开销在各种工作负载上都很低。此外，在几乎所有情况下，从我们的快照构建的树上的范围查询的性能与支持原子范围查询的最先进的并发数据结构一样好或更好。
Given a concurrent data structure, we present an approach for efficiently taking snapshots of its constituent CAS objects. More specifically, we support a constant-time operation that returns a snapshot handle. This snapshot handle can later be used to read the value of any base object at the time the snapshot was taken. Reading an earlier version of a base object is wait-free and takes time proportional to the number of successful writes to the object since the snapshot was taken. Importantly, our approach preserves all the time bounds and parallelism of the original data structure.Our fast, flexible snapshots yield simple, efficient implementations of atomic multi-point queries on a large class of concurrent data structures. For example, in a search tree where child pointers are updated using CAS, once a snapshot is taken, one can atomically search for ranges of keys, find the first key that matches some criteria, or check if a collection of keys are all present, simply by running a standard sequential algorithm on a snapshot of the tree.To evaluate the performance of our approach, we apply it to three search trees, one balanced and two not. Experiments show that the overhead of supporting snapshots is low across a variety of workloads. Moreover, in almost all cases, range queries on the trees built from our snapshots perform as well as or better than state-of-the-art concurrent data structures that support atomic range queries.
登录
查看更多内容
需要时提供帮助，但仅此而已：高效读/写部分快照
DOI：
--
发表时间：
2009
期刊：
J. Parallel Distributed Comput.
影响因子：
--
作者：
Damien Imbs;M. Raynal
通讯作者：
M. Raynal
时间最优、空间高效的单扫描仪快照
DOI：
--
发表时间：
2007
期刊：
ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
影响因子：
--
作者：
P. Fatourou;Nikolaos D. Kallimanis
通讯作者：
Nikolaos D. Kallimanis
带串联的完全持久列表
DOI：
--
发表时间：
1991
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
James R. Driscoll;D. Sleator;R. Tarjan
通讯作者：
R. Tarjan
DOI：
10.1145/3460874
发表时间：
2018-07
期刊：
ACM Transactions on Parallel Computing (TOPC)
影响因子：
--
作者：
Kjell Winblad;Konstantinos Sagonas;B. Jonsson
通讯作者：
Kjell Winblad;Konstantinos Sagonas;B. Jonsson
基于时间戳的多版本STM算法
DOI：
10.1007/978-3-642-45249-9_14
发表时间：
2014
期刊：
Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems
影响因子：
--
作者：
Priyanka Kumar;Sathya Peri;K. Vidyasankar
通讯作者：
K. Vidyasankar