Constant-Time Snapshots with Applications to Concurrent Data Structures
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.
Conference DayMon 1 MarDisplayed time zone: Eastern Time (US & Canada) change
10:00 - 11:00
|Efficient Algorithms for Persistent Transactional Memory|
Pedro RamalheteCisco Systems, Andreia CorreiaUniversity of Neuchatel, Switzerland, Pascal FelberUniversity of NeuchâtelLink to publication
|Investigating the Semantics of Futures in Transactional Memory Systems|
Jingna ZengKTH Royal Institute of Technology, Sweden / IST, ULisboa, Shady IssaINESC-ID, Paolo RomanoINESC-ID / IST, ULisboa, Luis RodriguesINESC-ID, IST, ULisboa, Seif HaridiKTH Royal Institute of Technology, SwedenLink to publication
|Constant-Time Snapshots with Applications to Concurrent Data Structures|
Yuanhao WeiCarnegie Mellon University, Naama Ben-DavidVMware Research, Guy E. BlellochCarnegie Mellon University, Panagiota FatourouFORTH ICS and University of Crete, Greece, Eric RuppertYork University, Canada, Yihan SunUniversity of California, RiversideLink to publication
|Reasoning About Recursive Tree Traversals|
Yanjun WangPurdue University, Jinwei LiuBeijing Jiaotong University, Dalin ZhangBeijing Jiaotong University, Xiaokang QiuPurdue UniversityLink to publication