PPoPP 2022 (series) / Main Conference /
Bundling Linked Data Structures for Linearizable Range Queries
Wed 6 Apr 2022 12:00 - 12:15 - Session 8 Chair(s): Naama Ben-David
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 implement our technique into 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.
Wed 6 AprDisplayed time zone: Eastern Time (US & Canada) change
Wed 6 Apr
Displayed time zone: Eastern Time (US & Canada) change
12:00 - 13:15 | |||
12:00 15mTalk | Bundling Linked Data Structures for Linearizable Range Queries Main Conference | ||
12:15 15mTalk | Elimination (a,b)-trees with fast, durable updates Main Conference | ||
12:30 15mTalk | Jiffy: A Lock-free Skip List with Batch Updates and Snapshots Main Conference Tadeusz Kobus Poznan University of Technology, Maciej Kokociński Poznan University of Technology, Paweł T. Wojciechowski Poznan University of Technology | ||
12:45 15mTalk | Multi-Queues Can Be State-of-the-Art Priority Schedulers Main Conference Anastasiia Postnikova ITMO University, Nikita Koval JetBrains, Giorgi Nadiradze IST Austria, Dan Alistarh IST Austria | ||
13:00 15mTalk | PathCAS: An Efficient Middle Ground for Concurrent Search Data Structures Main Conference Trevor Brown University of Waterloo, William Sigouin University of Waterloo, Dan Alistarh IST Austria |