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

Concurrent programming is notoriously difficult. Hence, to develop complex systems aimed for modern multicore hardware, such as database engines, programmers often rely on concurrent data structures. They can be safely accessed by many concurrent threads without additional synchronization. Under the hood, they feature sophisticated, often non-blocking, synchronization algorithms. With the proliferation of multicore hardware, many new concurrent data structures have been proposed, e.g., concurrent lists, sets, and (ordered) key-value indices (or maps, dictionaries). Each subsequent structure improves performance or introduces new features, e.g., consistent range scans (consecutive, ascending or descending, entries within a defined range) or snapshots (a read-only, static and consistent view of the entire dataset). In a paper published at PPoPP '22, we introduced Jiffy, the first linearisable, lock-free ordered index (sorted key-value map) that offers range scans (which, in our system, are based on consistent snapshots) and also batch updates (multiple put/remove operations on arbitrary keys executed atomically). Batch updates are rarely supported, although they are often demanded, e.g., they are included in API of Google's LevelDB and Facebook's RocksDB, and are extensively used in large open-source projects (e.g., Apache Hadoop, Apache Spark, and Bitcoin). However, providing batch updates in an in-memory index, which must be much faster than its SSD-backed counterparts, poses new challenges related to concurrent synchronization. We proposed a novel algorithm to make our in-memory index highly scalable, despite the rich semantics it offers. In this extended abstract, we briefly characterize the novelty of our approach.