Write a Blog >>
PPoPP 2022
Sat 2 - Wed 6 April 2022
Wed 6 Apr 2022 12:30 - 12:45 - Session 8 Chair(s): Naama Ben-David

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 Apr

Displayed time zone: Eastern Time (US & Canada) change

12:00 - 13:15
Session 8Main Conference
Chair(s): Naama Ben-David VMware
12:00
15m
Talk
Bundling Linked Data Structures for Linearizable Range Queries
Main Conference
Jacob Nelson Lehigh University, Ahmed Hassan Lehigh University, Roberto Palmieri Lehigh University
12:15
15m
Talk
Elimination (a,b)-trees with fast, durable updates
Main Conference
Anubhav Srivastava University of Waterloo, Trevor Brown University of Waterloo
12:30
15m
Talk
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
15m
Talk
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
15m
Talk
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