  In this paper we introduce Jiffy, the first lock-free, linearizable ordered
key-value index that offers both (1) batch updates, which are 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 CPU's Time Stamp Counter register to generate version
numbers at minimal cost. For faster skip list traversals and better utilization
of the CPU caches, key-value entries are grouped into immutable objects called
revisions. Moreover, by changing the size of revisions and thus modifying the
synchronization granularity, our index can adapt to varying contentions levels
(smaller revisions are more suited for write-heavy workloads whereas large
revisions benefit read-dominated workloads, especially when they feature many
range scan operations). 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, which is
comparable or exceeds the performance of the state-of-the-art lock-free ordered
indices that feature linearizable range scan operations. Compared to its
(lock-based) rivals that also support batch updates, Jiffy can execute large
batch updates up to 7.4x more efficiently.
