Jiffy: A Lock-free Skip List with Batch Updates and Snapshots
In this paper we introduce Jiffy, the first lock-free, linearizable, ordered key-value index that offers both (1) batch updates, i.e., put and remove operations that are executed atomically, and (2) consistent snapshots used by, e.g., range scan operations. Jiffy is built as a multiversioned lock-free skip list and relies on system-provided timestamps (e.g., on x86_64 obtained through the Time Stamp Counter register) to generate version numbers at minimal cost. For faster skip list traversals and better utilization of CPU caches, key-value entries are grouped into immutable objects called revisions. By (automatically) controlling the size of new revisions, our index can adapt to varying contention levels (e.g., smaller revisions are more suited for write-heavy workloads). Structure modifications to the index, which result in changing the size of revisions, happen through (lock-free) skip list node split and merge operations that are carefully coordinated with the update operations. Despite rich semantics, Jiffy offers highly scalable performance across varied workloads. Compared to Jiffy’s lock-based rivals that support batch updates, our index can execute large batch updates up to 7.4 times more efficiently. Moreover, Jiffy often outperforms the state-of-the-art lock-free ordered indices that feature linearizable range scan operations but lack batch updates.
Wed 6 AprDisplayed 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 |