Processing may take a few seconds...

Chapter


Title

Jiffy: A Lock-free Skip List with Batch Updates and Snapshots

Authors

[ 1 ] Instytut Informatyki, Wydział Informatyki i Telekomunikacji, Politechnika Poznańska | [ P ] employee

Scientific discipline (Law 2.0)

[2.3] Information and communication technology

Year of publication

2022

Chapter type

chapter in monograph / paper

Publication language

english

Keywords
EN
  • ordered index
  • lock-free skip list
  • batch update
  • snapshot
  • linearizability
Abstract

EN 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.

Date of online publication

28.03.2022

Pages (from - to)

400 - 415

DOI

10.1145/3503221.3508437

URL

https://dl.acm.org/doi/pdf/10.1145/3503221.3508437

Book

PPoPP '22 : Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming

Presented on

27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming PPoPP '22, 2-6.04.2022, Seoul, Republic of Korea

Open Access Mode

publisher's website

Open Access Text Version

final published version

Date of Open Access to the publication

at the time of publication

Points of MNiSW / chapter

20.0

Points of MNiSW / conference (CORE)

140.0

This website uses cookies to remember the authenticated session of the user. For more information, read about Cookies and Privacy Policy.