Jiffy: a lock-free skip list with batch updates and snapshots
Jiffy: a lock-free skip list with batch updates and snapshots
复制标题
Jiffy：具有批量更新和快照的无锁跳过列表
DOI：
10.1145/3503221.3508437
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
P. Wojciechowski
中科院分区：
文献类型：
--
作者：
Tadeusz Kobus;Maciej Kokociński;P. Wojciechowski
在本文中，我们将介绍Jiffy，这是第一个无锁、线性化、有序的键值索引，它提供了(1)批量更新，即自动执行的放置和删除操作，以及(2)一致快照，例如范围扫描操作。Jiffy是作为一个多版本的无锁跳跃表构建的，它依赖于系统提供的时间戳（例如，通过时间戳计数器寄存器获得的x86_64）以最小的成本生成版本号。为了更快地遍历跳跃表并更好地利用CPU缓存，键值条目被分组到称为修订的不可变对象中。通过（自动）控制新修订的大小，我们的索引可以适应不同的争用级别（例如，较小的修订更适合写繁重的工作负载）。对索引的结构修改导致修改的大小发生变化，这是通过（无锁）跳跃表节点拆分和合并操作进行的，这些操作与更新操作密切协调。尽管语义丰富，Jiffy在不同的工作负载上提供了高度可扩展的性能。与Jiffy支持批量更新的基于锁的竞争对手相比，我们的索引执行大规模批量更新的效率提高了7.4倍。此外，Jiffy通常优于最先进的无锁有序索引，后者具有线性范围扫描操作，但缺乏批量更新。
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.