Concurrent b-skiplist design delivers faster data access performance
A Simple Optimistic B-Skiplist Algorithm
Data Structures and Algorithms
Summary
Managing shared data efficiently when many users access it at once can be tricky. The authors designed a new way to organize and manage data called an optimistic concurrent B-skiplist, which reduces slowdowns caused by users interfering with each other. They combined clever locking techniques tailored to the structure's layout so that most operations don't slow down other users. Their tests show this design is often much faster and more responsive than prior similar methods. This makes it easier for computers to handle lots of data quickly when many tasks run simultaneously.
What this means in practice
- •For database engineers: Build high-throughput, low-latency index structures for multi-threaded query processing using optimistic B-skiplists.
- •For cloud platform developers: Implement scalable concurrent data indexing in cloud services to improve performance under heavy parallel workloads.
Authors
Jianting Guo, Yicong Luo, Helen Xu
Abstract
We present the first optimistic concurrent B-skiplist, built on optimistic lock coupling (OLC). OLC replaces the multi-cache-line RW lock with a compact, single-cache-line lock: readers validate a version number without writing to shared memory, avoiding cache invalidations and retrying only on a detected conflict. Although OLC was thought poorly suited to skiplists, where a single per-element lock may span structurally unrelated levels, the B-skiplist's blocked layout places each level (and associated lock) in its own node. We exploit the B-skiplist's upfront knowledge of promotion height with a hybrid top-down scheme that traverses upper levels optimistically and locks only from the promotion level down, so most inserts never dirty a cache line. On 128 threads, the proposed optimistic B-skiplist achieves $1.2-10\times$ higher throughput over state-of-the-art concurrent skiplist implementations. Furthermore, the optimistic B-skiplist achieves $0.8-4.3\times$ the throughput compared to high-performance optimistic B+-tree implementations based on RW locks and OLC. Finally, the optimistic B-skiplist achieves up to $13\times$ lower latency than concurrent skiplists and tree-based indices, and is within $1.6\times$ of the latency of the OLC-based B+-tree.