betaFeedback

WorksComputer Science

A Simple Optimistic B-Skiplist Algorithm

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×1.2-10\times higher throughput over state-of-the-art concurrent skiplist implementations. Furthermore, the optimistic B-skiplist achieves 0.8−4.3×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×13\times lower latency than concurrent skiplists and tree-based indices, and is within 1.6×1.6\times of the latency of the OLC-based B+-tree.

Introduction.

The skiplist [31] is a popular choice for the in-memory index (i.e., the memtable) in many key-value stores, such as HBase [17], RocksDB [32], and LevelDB [26], for its simple structure and concurrency control (CC) schemes [18, 30, 19, 11, 12]. The skiplist stores elements in a collection of ordered linked lists. The bottom level contains all the key-value pairs, and each subsequent level contains a subset of the elements of the level immediately below it. The skiplist determines which levels a key appears in probabilistically, avoiding complex rebalancing operations.

The simple structure of the skiplist comes at the cost of poor locality, since each node stores only one key. Blocked data structures like the B-tree [4] alleviate this by collocating keys in a single node, reducing cache misses during traversal. In the I/O model (or external-memory model) [3], blocking nodes asymptotically improves the height (and traversal time) of a B-tree compared to a skiplist or binary tree. Given a cache-line size ZZ, the operation time (find and insert) of a B-tree is O(log⁡Zn)O(\log_Z n), asymptotically smaller than the O(log⁡2n)O(\log_2 n) time of a skiplist or binary tree.

Bridging locality and concurrency. Luo et al. Luo et al. [27] introduced a concurrent B-skiplist that collocates elements within a node. Rather than promoting elements with probability 1/21/2, a B-skiplist with node size BB promotes elements with probability Θ(1/B)\Theta(1/B) and, for all levels ℓ=0,1,…,log⁡Bn\ell= 0,1,\ldots,\log_B n, collocates elements on level ℓ\ell between elements promoted to level ℓ+1\ell+ 1. Golovin Golovin [13] showed theoretically that when B=Θ(Z)B = \Theta(Z), the B-skiplist matches the bounds of the classical B-tree in expectation, and these results are borne out in practice [27]: the B-skiplist achieves over 2× higher throughput and 3–5× fewer cache misses than a state-of-the-art concurrent skiplist from Facebook’s Folly library [1].

Locality issues in today’s concurrent B-skiplists. To support concurrent operations, the B-skiplist employs partitioned reader-writer (RW) locks [10] with a one-pass traversal algorithm that avoids revisiting nodes [27]. RW locks can be acquired in shared mode (by incrementing a reader counter) or in exclusive mode (by setting a write bit). Naive RW lock implementations do not scale well because any write to a shared-memory location invalidates copies of the cache line across all cores, even when the lock is acquired in shared mode. The RW locks in the B-skiplist therefore use partitioning [2] with multiple reader counts (one per cache line) to avoid false sharing.

Throughput on uniform YCSB workloads

Figure 1. Throughput on uniform YCSB workloads on 128 threads. The load phase and workloads A–C involve varying ratios of point finds and inserts, while workload E involves range queries and inserts.

However, partitioning introduces new locality challenges: writers must scan all partitions to acquire the lock, incurring additional cache misses. For example, with 128 threads and 64-byte partitions (1 cache line each), the partitioned counter is 8192 bytes—far larger than the default B-skiplist node size of 2048 bytes [27]. The concurrency-control metadata thus adds cache-line accesses to every node visit, eroding the locality benefits of the B-skiplist’s blocked layout.

Our approach: optimistic lock coupling. We introduce a concurrent B-skiplist based on optimistic lock coupling (OLC) [23] that improves the cache locality and performance of the state-of-the-art concurrent B-skiplist by replacing its partitioned RW lock with a compact, cache-friendly OLC lock. The proposed optimistic B-skiplist maintains the simplicity of traditional skiplist CC schemes while improving performance and scalability.

OLC [23] improves cache performance by combining lock-based and lock-free synchronization: readers validate a version number without writing to shared memory, avoiding cache invalidations, while the entire lock fits on a single cache line. In B-trees, Leis et al. demonstrated that OLC achieves near-linear scalability, outperforming traditional lock coupling by up to 4× [23].

To our knowledge, this is the first application of OLC to a B-skiplist. OLC has been applied to linked lists [15], skiplists [15], binary trees [6], and B-trees [7, 23].

Challenges to OLC in the B-skiplist. Prior work on OLC-based skiplists [15] observed that OLC is poorly suited to skiplists, because a skiplist typically stores an element’s forward pointers for all its levels in a single tower under one per-element lock, coupling unrelated levels. The tower optimization is meant to improve locality in skiplists by avoiding cache misses during downwards traversals, but comes at the cost of coarser lock granularity producing false conflicts.

The B-skiplist optimizes for locality without giving up on concurrency through its blocked layout: since each block collocates different elements at each level, promoted elements must reside in a different node at each level. Therefore, the B-skiplist’s blocking also enables fine-grained, per-level concurrency.

Finally, applying OLC to the B-skiplist raises additional challenges not present in B-trees because 1) B-skiplist traversals require both horizontal and vertical steps, requiring version reads and validations in two dimensions rather than one, and 2) promoted inserts must update forward pointers at multiple levels, requiring careful ordering of pointer updates and version increments to avoid blocking readers unnecessarily.

Designing an efficient OLC-based B-skiplist. Despite these challenges, the B-skiplist’s structure and randomized promotion make it well-suited for OLC. Building on the top-down insertion algorithm of the RW-lock-based B-skiplist (details in § 2), our CC scheme replaces the multi-cache-line RW lock with a single-cache-line OLC lock, incurring 1.8× fewer cache references on write-heavy workloads (Table 1.1).

B-skiplistCacheMemoryThroughput
MissesReferences(GB)(ops/μs)
RW-lock61E9220E96.759
Optimistic57E9120E96.3102

Table 1.1. Cache misses, cache references, memory usage, and throughput of the optimistic B-skiplist (this work) and the RW-lock B-skiplist [27]. Throughput is for YCSB [8] workload A (50% inserts/50% finds); all other data is for load + workload A (200M ops total).

We further exploit the B-skiplist’s upfront knowledge of promotion height with a hybrid top-down mechanism: writers traverse levels above the promotion height optimistically, never acquiring a write lock, and take write locks only at the promotion level and below. Since promotion probability decreases geometrically, most inserts reach low heights, so the write lock covers only a few levels and writers access the vast majority of nodes without dirtying a cache line. When a retry does occur, it is cheap, as the traversal path is likely still in cache.

Contributions. This paper makes the following contributions:

  • The design of an OLC-based concurrent B-skiplist that optimizes for locality in the concurrency control mechanism.

  • A hybrid top-down OLC-based CC mechanism for the B-skiplist that completes insertions in a single top-to-bottom pass.

  • A C implementation of the OLC-based concurrent B-skiplist.

  • An empirical evaluation against several in-memory skiplist-based and B-tree-based indices on YCSB [8] and TPC-C [25] workloads.

Results summary. We evaluate the OLC-based B-skiplist (OLC-BSL) against the RW-lock-based B-skiplist (RW-BSL) [27], Facebook’s Folly ConcurrentSkipList (FLY-SL) [1], an optimized RW-lock-based B+{}^{+}-tree (RW-B+{}^{+}T) [36], and an OLC-based B+{}^{+}-tree (OLC-B+{}^{+}T) [23, 34] on YCSB [8] workloads (details in § 5). Figure 1.1 shows throughput across workloads; Figure 1.2 shows strong scaling on workload A.

Strong scaling on uniform YCSB workload A

Figure 1.2. Strong scaling on uniform YCSB workload A (50%/50% finds/inserts).

On 128 threads, the optimistic B-skiplist achieves 0.8–10× the throughput and from 1.6× higher to 13× lower latency when compared to all other tested systems. As shown in Figure 1.1, on the write-heavy workloads (load and workload A), the OLC-B-skiplist achieves 1.2–4.4× speedup compared to the other indices. Furthermore, on the read-heavy point workloads B and C, the OLC-B-skiplist achieves higher (1.2–4×) speedup compared to skiplist-based indices and is competitive (0.8–0.9×) with the OLC-B+{}^{+}-tree, which is the fastest tested B-tree-based index. In terms of scaling, the optimistic B-skiplist achieves 74×, 81×, and 57× throughput speedup over 1 thread on YCSB [37] workloads A and C, and the load phase, respectively.

Background

This section reviews the structure and operations of skiplists and B-skiplists, then covers the concurrency primitives this paper builds on: lock coupling, reader-writer (RW) locks, and optimistic lock coupling (OLC).

Operations. A key-value dictionary stores key-value pairs (k,v)(k, v) with the following operations:

  • find(k): return the associated value vv.

  • insert(k, v): add (k,v)(k, v) to the data structure.

  • delete(k): remove kk and its associated value.

  • range(k, f, length): apply the function ff to the length key-value pairs with the smallest keys that are at least kk.

Finds, inserts, and range queries comprise the YCSB [8] workloads used in our evaluation (§ 5).

Example of a B-skiplist with node size B = 4

Figure 2.1. Example of a B-skiplist with node size B=4B = 4.

Skiplist structure and operations. The skiplist [31] is a hierarchy of ordered linked lists: level 0 contains all keys, and each level ℓ>0\ell> 0 contains a subset of the elements at level ℓ−1\ell- 1, bounded by a left sentinel (−∞-\infty) and a right sentinel (∞\infty). As in trees, nodes at level ℓ=0\ell= 0 are leaf nodes and those at levels ℓ>0\ell> 0 are internal nodes. All nodes have a next pointer to their successor in the same level; internal nodes also have a down pointer to the node with the same key in the level below, and the root is the leftmost node at the highest level.

The skiplist’s defining feature is its randomized self-balancing: each element’s height equals the number of successive “heads” when flipping a coin with probability pp (usually p=1/2p = 1/2; any constant p=1/cp = 1/c suffices for the asymptotic bounds). Thus, the maximum height of an element in a skiplist with nn elements is O(log⁡n)O(\log n) in expectation and with high probability (w.h.p.), and an element’s promotion level is independent of the skiplist structure. At each level, the pred (resp. succ) of a key kk is the largest key less than kk (resp. smallest greater than kk).

All skiplist operations traverse left-to-right and top-to-bottom from the root, supporting point operations in O(log⁡n)O(\log n) time in expectation and w.h.p.; we detail the blocked variant in § 2.1.

B-skiplist structure and operations

Structure. The B-skiplist [13] is a blocked skiplist with multiple elements per node. Given a cache-line size ZZ and node size B=Θ(Z)B = \Theta(Z), the promotion probability is p=Θ(1/B)p = \Theta(1/B).

The header of a node is its first (and smallest) key; by construction, every header at level ℓ\ell has been promoted to level ℓ+1\ell+ 1.

Each node in a B-skiplist has a next pointer, and all keys in node xx are smaller than the header of x→nextx\mathbin{\to}\text{next}. Each internal node (level ℓ>0\ell> 0) also contains an array of BB down pointers, one for each key, each pointing to the corresponding node at the level below.

Bounds. In the external-memory model (§ 1), a B-skiplist with nn elements and node size B=Θ(Z)B = \Theta(Z) supports finds and inserts in Θ(log⁡Z(n))\Theta(\log_{Z}(n)) cache-line transfers in expectation, matching B-tree bounds. Range

Algorithm 2.1 Lock coupling step
1: Input: x: current node, read lock of x held from previous iteration
2: y ← x.next
3: read_lock(y)
4: read_unlock(x)
5: x ← y

queries over rr elements take Θ(log⁡Z(n)+r/Z)\Theta(\log_Z(n) + r/Z) transfers in expectation.

Operations. B-skiplist traversals follow the same left-to-right, top-to-bottom order as the skiplist, but examine multiple elements per node.

The find(k) operation initializes curr to the upper-left sentinel and scans right until the header of curr->next exceeds kk, then follows the down pointer of the pred element within curr. This repeats until the leaf level, where it checks for kk’s presence. Range queries perform a find to the start key, then iterate left-to-right at the leaf level.

The insert(k, v) operation performs a find-like traversal to locate the pred at each level. Let hh be the promotion height of kk. If h=0h = 0, kk is inserted into the leaf node containing its pred. If h>0h > 0, a split is performed at levels ℓ=0,…,h−1\ell= 0, \ldots, h - 1, linking in new nodes with kk as the header; at each level, keys greater than kk are copied to the new node.

Deletes are symmetric to inserts, and disconnect and deallocate a node when deleting the last key in the node.

Insertion order in a B-skiplist. Golovin’s theoretical paper [13] does not prescribe the insertion order (top-down or bottom-up). Most skiplist algorithms use bottom-up insertion, linking new nodes from the leaf level up to the promotion height [31, 30, 18, 19]. The RW-lock-based B-skiplist [27] instead uses top-down insertion, starting from the promotion height down to the leaf level. The key advantage of this design is that insertion can finish in one top-down traversal compared to a bottom-up algorithm, which requires a top-down traversal followed by a bottom-up traversal.

Concurrency control.

Lock coupling (also known as hand-over-hand locking, HOH) [5, 14, 20] traverses a linked list while holding at most two locks: it acquires the lock on the successor before releasing the lock on the predecessor. Holding a lock on curr permits safe access to curr->next for key comparisons or boundary checks. During inserts, both locks are held to link a new node between curr and curr->next. Lock coupling extends naturally to skiplists, which are towers of linked lists.

Reader-writer (RW) locks. Reader-writer locks (RW locks) [10] allow concurrent shared access via

Algorithm 2.2 Optimistic lock coupling step
1: Input: x: current node, vx: version of x read in previous iteration
2: y ← x.next
3: vy ← LoadVersion(y)
4: if IsWriteLocked(vx) ∨ vx ≠ LoadVersion(x)
5:     goto retry
6: x ← y
7: vx ← vy

read_lock() or exclusive access via write_lock(). Multiple threads may hold the lock in read mode simultaneously; any thread holding it in write mode blocks all others. Algorithm 2.1 shows one HOH traversal step under RW locks.

RW-lock-based concurrency control in the B-skiplist. The RW-lock-based B-skiplist [27] uses lock coupling top-to-bottom and left-to-right, following the top-down insertion algorithm. It exploits upfront knowledge of the promotion level to take write locks starting at the promotion level.

OLC. An optimistic lock packs a write bit and a version number into a single 64-bit word [24, 23]. The LSB acts as the write bit; writers set it on lock acquisition and increment the version (clearing the LSB) on release.

In OLC, readers detect concurrent modifications by comparing the version before and after accessing a node without modifying shared state, eliminating cache-line invalidations. Readers may occasionally retry, but retries are rare in practice. OLC is a form of optimistic concurrency control (OCC) [21]: threads traverse without locks and restart if they detect a concurrent modification before committing.

OLC traversals. OLC traversals follow the same order as HOH but replace read locking with version validation [23]. A thread reads the next node’s version (analogous to acquiring the next lock), then validates the current node by checking that its version is unchanged and not write-locked (analogous to releasing the current lock). Algorithm 2.2 shows one traversal step; validation failure triggers a retry from the root.

Proposed node structure.

This section contrasts the node layouts of the RW-lock-based B-skiplist [27] and the proposed optimistic B-skiplist. We also address practical concerns such as version overflow and the ABA problem.

In the RW-lock-based B-skiplist, each node begins with the partitioned RW lock, followed by metadata (number of elements, node level, next pointer, and first key of the next node), then keys and values in structure-of-arrays (SoA) layout. Reading a node requires at least two cache-line accesses for the write bit and reader counter before reaching any useful data.

Node layouts in the RW-lock-based B-skiplist and the proposed optimistic B-skiplist

Figure 3.1. Node layouts in the RW-lock-based B-skiplist and the proposed optimistic B-skiplist.

In the proposed optimistic B-skiplist, each node begins with the 8-byte version number, followed by metadata and SoA-layout keys and values. The first cache-line access thus contains the version number and complete metadata, reducing both memory latency and footprint compared to the RW-lock-based design.

Version overflow and ABA. The ABA problem arises when a version number wraps around to a previously-seen value, causing a reader to incorrectly conclude that no modification occurred. With a 64-bit version, this is not a practical concern: at 10910^9 modifications per second, a full wraparound takes 263/1092^{63}/10^9 seconds ≈292\approx292 years. Even if wraparound did occur, the version continues from zero, which is safe under the same argument.

Optimistic algorithms

This section presents the algorithms and design of the optimistic B-skiplist (see § 2), detailing the Find and Insert algorithms and how they maintain consistency under OLC. We also discuss deadlock freedom and the memory reclamation mechanism required to support lock-free readers.

OLC is effective for the B-skiplist because most writes affect only the leaves: the number of elements in internal nodes decreases exponentially by level, so write conflicts at upper levels are exceedingly rare. Even when a retry occurs, the traversal path is likely still in cache, keeping the retry cost low.

Algorithms

Find. Algorithm 4.1 shows the Find operation. The algorithm begins at the root, loading its version before entering the traversal loop; Validate(x,v)(x, v) issues a LoadVersion on node xx and checks that the result equals vv. At each level, the algorithm moves right while the next header does not exceed the search key, following the OLC step in Algorithm 2.2.

At internal levels (i>0i > 0), descent uses a two-phase validation. First, the algorithm validates the current node before dereferencing the child pointer (line 30). This is necessary because a concurrent writer may leave the pointer in an indeterminate state, making an unvalidated dereference unsafe. Second, the algorithm validates the current node again after loading the child’s version, completing the OLC handoff (line 33). At the leaf level (i=0i = 0), the algorithm searches for the key locally, validates the node before returning, and returns the associated value if found.

Range query. The Scan operation extends Find. It takes in a starting key kk, an accumulator, a callback function (e.g., Sum), and a stop condition such as a max length or an end key. The algorithm first performs a Find to locate the leaf node curr containing the largest key ≤k\le k. It then iteratively applies the callback to each key-value pair until the stop condition is met or the node ends. Upon reaching the end of the leaf node, the algorithm validates curr, reads curr.next, and continues until the stop condition is met or the last leaf node is reached. If any validation fails, the accumulator is reset and the operation retries from the root.

Insertion. Algorithm 4.2 shows the hybrid OLC-based Insert operation. Writers begin with an optimistic read phase, using the same traversal as Find, until their promotion level. The key insight is that the promotion height is known upfront due to the B-skiplist’s probabilistic nature.

Since promotions occur with geometrically decreasing probability, most insertions reach low heights, so the optimistic traversal covers the vast majority of levels, minimizing cache invalidations and write-lock hold time.

Upon reaching the promotion level, the algorithm acquires a write lock on node xx and transitions to the write phase. If the promotion level is zero (i.e., the leaf level), the key-value pair is inserted directly (line 4) and the operation terminates. Otherwise, the algorithm enters a top-down promotion phase (lines 10–35), processing one level at a time while h>0h > 0.

At each level, the algorithm locates the correct position by traversing horizontally under HOH locking (lines 16–19), then splits xx and links in a new node pp (lines 21–30). Since the promotion height is known upfront, the correct number of new nodes is preallocated and write-locked before traversal. The insertion then proceeds level-by-level to the leaves.

Figure 4.1 illustrates the hybrid CC protocol. The optimistic read phase (top panel) descends through upper levels by checking version numbers without acquiring

An example of Insert(30) at height = 1

Figure 4.1. An example of Insert(30) at height = 1. The hybrid OLC protocol consists of two phases. The read phase traverses optimistically from the top level down to the promotion level. Upon reaching the promotion level, the write phase switches to exclusive locks.

Algorithm 4.1 Find(L, k)
Require: Skiplist L, key k
Ensure: Value associated with k, or Nil
1: retry:
2:   x ← L.root
3:   vₓ ← LoadVersion(x)
4:   for i ← MAX LEVEL − 1 to 0 do
5:     while x.next header ≤ k do
6:       y ← x.next
7:       if y = Nil
8:         goto retry
9:       vᵧ ← LoadVersion(y)
10:      if IsWriteLocked(vₓ) ∨ ¬Validate(x, vₓ)
11:        goto retry
12:      x ← y, vₓ ← vᵧ
13:    if IsWriteLocked(vₓ)
14:      goto retry
15:    r ← FindRank(x.keys, k)
16:    if i = 0
17:      if x.keys[r] = k
18:        val ← x.values[r]
19:        if ¬Validate(x, vₓ)
20:          goto retry
21:        return val
22:      else
23:        if ¬Validate(x, vₓ)
24:          goto retry
25:        return Nil
26:    else
27:      z ← x.children[r]
28:      if z = Nil
29:        goto retry
▷ Phase 1: validate child pointer
30:     if ¬Validate(x, vₓ)
31:       goto retry
32:     v𝓏 ← LoadVersion(z)
▷ Phase 2: validate child version
33:     if ¬Validate(x, vₓ)
34:       goto retry
35:     x ← z, vₓ ← v𝓏
36: return Nil

write locks. Upon reaching the promotion level, the algorithm acquires a write lock on the target node and transitions to the write phase (second panel). The subsequent panels show how locks are acquired level-by-level as the new node is linked into the structure.

Deletion. Like Insert, Delete(kk) begins with an optimistic read phase, descending from the top level to kk’s promotion level. At that level, the algorithm acquires a write lock and switches to the write phase, using HOH locking to locate the node containing kk, read its child cc, and delete kk from it. A B-skiplist invariant guarantees that cc also contains kk, so the algorithm repeats this process level-by-level down to the leaf. After each deletion, if the node is now empty, the algorithm unlinks it by updating its predecessor’s next pointer.

Unlike the RW-B-skiplist, the OLC-B-skiplist cannot immediately deallocate a disconnected node, because optimistic readers may still hold references to it. To support safe memory reuse, the OLC-B-skiplist uses epoch-based reclamation (EBR) [12]. EBR defers reclamation until all threads that could have observed a node have passed through a safe point, ensuring readers always access valid memory.

Correctness

Skiplist structure. Following prior work [27], we relax the inclusion invariant—the property that every element at level hh must appear

Algorithm 4.2 Insert(L: Skiplist, k: Key, v: Value)
1: h ← PromotionLevel(k)
   new nodes ← allocate h write-locked nodes
   ▷ After optimistic traversal, x is the node at promotion level h holding a write lock
2: r ← FindRank(x.keys, k)
3: if h = 0
4:     InsertLeaf(x, r + 1, k, v)
5:     WriteUnlock(x)
6:     return
7: else
8:     InsertInternal(x, r + 1, k, new nodes[h − 1])
9:     parent ← x, x ← x.children[r]
10: while h > 0 do ▷ Top-down promotion
11:     h ← h − 1
12:     WriteLock(x)
13:     if parent ≠ Nil
14:         WriteUnlock(parent)
15:         parent ← Nil
16:     while x.next header ≤ k do
17:         WriteLock(x.next)
18:         x′ ← x, x ← x.next
19:         WriteUnlock(x′)
20:     r ← FindRank(x.keys, k)
21:     p ← new nodes[h]
22:     p.next header ← x.next header
23:     p.next ← x.next, p.level ← h
       ▷ Insert k into p before reading p.keys[0]
24:     if h > 0
25:         InsertInternal(p, 0, k, new nodes[h − 1])
26:     else
27:         InsertLeaf(p, 0, k, v)
       ▷ Move x.keys[r + 1..] into p at slot 1
28:     SplitKeys(x, p, r + 1)
29:     x.next header ← p.keys[0] ▷ p.keys[0] = k
30:     x.next ← p
31:     if h > 0
32:         parent ← x, x ← x.children[r]
33:     else
34:         WriteUnlock(x)
35:         WriteUnlock(p)
36:         return

at all lower levels — only during insertions. Under the top-down algorithm, an element may appear at higher levels before lower ones. The invariant is restored upon completion of any insertion, and the final pointer structure matches that of a bottom-up algorithm.

This relaxation does not affect the theoretical bounds, which depend on the expected height and number of nodes traversed per level and are determined by the probabilistic coin flips that fix each element’s promotion level, not the insertion order.

Deadlock freedom. Since readers operate entirely under OLC without acquiring locks, they cannot participate in a deadlock. Writers use a spinlock with the same top-down HOH algorithm as the RW-lock-based B-skiplist; because locks are acquired strictly top-down, no cycle can form among waiting writers. Correctness follows from the coupling discipline: every move to the next node is performed under a valid coupling — holding the current lock (HOH) or validating the current version (OLC) — ensuring the traversal path remains consistent at every step.

Evaluation.

This section evaluates the OLC-B-skiplist on YCSB [8], TPC-C, and delete workloads against the RW-lock-based B-skiplist [27], an optimistic skiplist from Facebook’s Folly library [1], an RW-lock-based optimistic B+-tree [36], and an OLC-based B+-tree [23, 34].

Overall, the OLC-B-skiplist achieves 0.8–10× the throughput of the other tested indices, up to 13× lower latency than the skiplists and RW-B+-tree, and latency within 1.6× of the OLC-B+-tree. Furthermore, the OLC-B-skiplist achieves 74×, 81×, and 57× self-relative speedup from 1 to 128 threads on YCSB [37] workloads A, C, and the load phase, respectively.

Setup.

Hardware. We ran the experiments on a server with an AMD EPYC 9555 64-Core Processor with 1007 GB of memory. The server has a 3 MiB L1 data cache, a 2 MiB L2 instruction cache, a 64 MiB L2 cache, and a 256 MiB L3 cache. The 64 cores are distributed on 4 NUMA nodes and support a maximum of 128 threads. To minimize NUMA effects, we ran 1–16-thread experiments on a single NUMA node, 32-thread experiments on two NUMA nodes, and 64- and 128-thread experiments on all four NUMA nodes.

All times are the median of 5 trials after one warm-up trial. To measure latency, each thread measures the average time taken for a batch of 10 operations1 and stores it in a thread-safe vector. After all operations complete, we sort the per-thread measurements and compute latency at each percentile.

Workloads. We follow the standard YCSB [37] procedure, which consists of a load phase and a run phase. In the load phase, 100 million (100M) elements are inserted into an empty index. In the run phase, a mixture of 100M operations is executed, with the mixture determined by the YCSB workload. Operations within each phase run concurrently; the phases run sequentially.

Table 5.1 presents details of the selected YCSB workloads. We tested workloads2 A, B, C, and E from the core YCSB workloads generated with RECIPE [22].

WorkloadDescription
Load100% inserts from empty
A50% finds, 50% inserts
B95% finds, 5% inserts
C100% finds
E95% short range iterations (max_len = 100), 5% inserts

Table 5.1. YCSB workload descriptions.

We evaluate each workload under both uniform and zipfian distributions in the run phase. In the uniform workloads, elements in both phases are drawn from a uniform distribution. In the zipfian workloads, load-phase elements are uniform while run-phase query elements are drawn from a zipfian distribution.

Additionally, we tested all indices on the Transaction Processing Performance Council’s TPC-C benchmark [25], which simulates large-scale online business activity. Specifically, we used the implementation3 [9] from the DBx1000 in-memory database [38]. It supports a representative sample of the TPC-C benchmark with only Payment and New Order transactions (which account for 88% of the transactions in TPC-C). Our evaluation was conducted using 128 warehouses and 128 threads. Execution terminates once any thread reaches 100,000 transactions, yielding a total of 8 to 11 million completed transactions across the different indices.

The YCSB and TPC-C benchmarks do not include deletion, so we generated two delete workloads that mirror the same write percentages as YCSB workloads A (50%/50% finds/deletes) and B (95%/5% finds/deletes), i.e., with deletes instead of inserts. To ensure that the keys to be deleted are in the index, we used the keys from the run phase of YCSB workload C (100% finds).

Systems setup. To ensure fairness, all test drivers execute concurrent operations using pthreads [29], and all keys and values are 64-bit integers.

We use the RW-lock-based B-skiplist4 (RW-B-skiplist, RW-BSL) in C++ as our primary baseline [27], with default parameters5.

We implemented the OLC-B-skiplist6 (OLC-BSL) in C using the same parameters as the RW-B-skiplist [27].

Throughput on zipfian YCSB workloads

Figure 5.1. Throughput on zipfian YCSB workloads on 128 threads.

To isolate performance differences to the CC scheme, we adopted the RW-B-skiplist’s fixed-size nodes but omit that description from Section 4 for simplicity. Fixed-size nodes require a slight modification of the insert algorithm and CC scheme, but do not affect the key feature that writes only occur up to the promotion level.

We use a C++ concurrent skiplist7 from Facebook’s Folly library (FLY-SL) as a representative high-performance non-blocked (one key per node) skiplist [1]. Folly’s skiplist uses optimistic concurrency control: reads are lock-free and mostly wait-free, while writes require locking [18, 19]. We use the native interface for point operations and the iterator interface for range queries (since it lacks native range-query support), with initial height set to 20. Folly’s skiplist only stores keys.

We also tested a C++ concurrent B+^{+}-tree8 [36] based on RW locks and OCC [21] (RW-B+^{+}-tree, RW-B+^{+}T). Its OCC protocol uses HOH read locks to traverse from the root to the second-to-last level, then acquires write locks at the leaf to insert the key. If a split is required, the algorithm relinquishes all locks and retries from the root under write locks.

Finally, we tested a C++ OLC-based B+^{+}-tree9 (OLC-B+^{+}-tree, OLC-B+^{+}T) [23, 34]. The implementation does not support multi-node range queries, so we omit workload E for this index.

We compiled all baselines using g++ 13.3.0 and the OLC-B-skiplist using gcc 13.3.0 (all with -O3fast).

Throughput. YCSB benchmarks.

Figures 1.1 and 5.1 report throughput on uniform and

Throughput.

zipfian YCSB workloads. Overall, the OLC-B-skiplist achieves speedups over skiplist-based indices and the RW-B+B^{+}-tree on all workloads. Furthermore, it is faster than the OLC-B+B^{+}-tree on write-heavy workloads (load and workload A), and slightly slower on read-heavy workloads (workloads B and C). All systems achieve higher throughput on zipfian workloads than on uniform workloads because query paths have better temporal locality under skewed distributions.

For the load phase, the OLC-B-skiplist is about 2.7×, 4×, 4.3×, and 3× faster than the RW-B-skiplist, Folly, RW-B+B^{+}-tree, and OLC-B+B^{+}-tree, respectively. On point-operation workloads (A, B, and C), the OLC-B-skiplist is about 1.2–1.8× faster than the RW-B-skiplist, 3.7–4.4× faster than Folly, 1.1–2.4× faster than the RW-B+B^{+}-tree, and achieves 0.8–1.2× the throughput of the OLC-B+B^{+}-tree. On insert/range-query workload E, the OLC-B-skiplist is around 1.3–1.4× faster than the RW-B-skiplist, 9–10× faster than Folly, and 1.2× faster than the RW-B+B^{+}-tree.

YCSB discussion. The OLC-B-skiplist improves cache efficiency over the RW-B-skiplist by fitting all concurrency metadata (version number and write bit) on a single cache line. Table 1.1 shows that on the load phase and workload A, the OLC-B-skiplist incurs 1.1× fewer cache misses and 1.8× fewer cache references than the RW-B-skiplist.

In practice, retries are rare, enabling the OLC-B-skiplist to scale well on write-heavy workloads. During the load phase (100% inserts, the worst case for optimism), at most 6% of operations retry. In workload A (50%/50% finds/inserts), about 1% retry. In workloads B and E (95%/5% reads/inserts), retries drop to about 0.5%.

The OLC-B-skiplist is especially well-suited to write-heavy workloads: its hybrid scheme acquires write locks only from the promotion level down, exploiting upfront knowledge of promotion height to minimize lock hold time. The OLC-B-skiplist achieves 1.2–4.3× higher throughput on write-heavy workloads (load and workload A) compared to the B+B^{+}-tree-based indices, which must lock multiple nodes simultaneously because the level to which a split propagates is unknown before traversal.

The OLC-B-skiplist is slightly slower than the OLC-B+B^{+}-tree on read-heavy workloads because the B-skiplist may traverse horizontal chains at each level before descending, visiting more nodes than a B-tree’s vertical descent. Under OLC, every accessed node requires its own version read and validation, incurring more atomic operations than in the B-tree.

TPC-C benchmark. Table 5.2 shows that the OLC-B-skiplist achieves 1.9× and 5.4× speedup over the RW-B-skiplist and Folly, respectively, on the TPC-C benchmark. Furthermore, it achieves about 1.1× speedup over the RW-B++^{+}-tree and 0.9× the throughput of the OLC-B++^{+}-tree. We found that the TPC-C benchmark contains about 90% reads, which favors the B+-tree-based indices, as reflected in the results of the read-heavy YCSB workloads B and C.

SystemThroughput (txns/s)Throughput relative to OLC-BSL
OLC-BSL5.77E41.00
RW-BSL3.05E40.53
FLY-SL1.06E40.18
RW-B+T^{\mathrm{T}}5.03E40.87
OLC-B+T^{\mathrm{T}}6.28E41.09

Table 5.2. Throughput (transactions/s) of the tested systems on the TPC-C benchmark (about 90% reads).

Deletes. Overall, we find the OLC-B-skiplist achieves significantly higher delete throughput than the baselines on the delete-heavy workload. The OLC-B+-tree does not support deletion, so we omit it from this discussion. For 50%/50% deletes/finds, the OLC-B-skiplist achieves 1.6×, 35×, and 116× higher throughput than the RW-B-skiplist, Folly, and RW-B+-tree, respectively. The RW-B+-tree suffers most under deletes because its OCC protocol relinquishes all locks and retries under write locks on each conflicting operation. For 5%/95% deletes/finds, the margins narrow to 0.9×, 4×, and 5× the throughput of the RW-B-skiplist, Folly, and RW-B+-tree, respectively. Just as in the YCSB workloads, the OLC-B-skiplist is well-suited to write-heavy workloads because the hybrid scheme only requires write locks starting from the promotion level.

Latency.

We report latency at 128 threads across four percentiles (50th, 90th, 99th, and 99.9th). Figure 5.2 shows workloads A and C; we summarize the remaining workloads in the text. Latency complements throughput by revealing tail behavior: two systems with equal throughput may differ substantially in latency variance.

Latency at different percentiles for uniform and zipfian YCSB workloads

Figure 5.2. Latency at different percentiles on uniform and zipfian YCSB workloads on 128 threads.

Across all four percentiles, for the load phase, the OLC-B-skiplist achieves around 1.2–13× lower latency than the RW-B-skiplist, 2.8–3.7× lower than Folly, and 1.3–13× lower than the RW-B+-tree, but 1.3–1.4× higher latency than the OLC-B+-tree. On point-operation workloads (A, B, and C), it achieves around 0.9–1.7× lower latency than the RW-B-skiplist, 2.6–3.8× lower than Folly, 0.8–6× lower than the RW-B+-tree, and up to 1.6× higher latency than the OLC-B+-tree. On range-query workload E, it achieves around 0.9–1.2× lower latency than the RW-B-skiplist, 8–12× lower than Folly, and 0.7–2.9× lower than the RW-B+-tree.

Between workloads A and C, relative performance is similar except for the RW-B+-tree. Its latency increases significantly above the 90th percentile on workload A

Strong scaling on uniform YCSB workload C

Figure 5.3. Strong scaling on uniform YCSB workload C (100% finds).

Strong scaling on the uniform YCSB load phase

Figure 5.4. Strong scaling on the uniform YCSB load phase (100% inserts).

but remains competitive on workload C. The RW-B+-tree’s OCC protocol retries with write locks; as the insert fraction grows, more retries inflate tail latency. The B-skip lists avoid this because the promotion level is known before traversal, so retries require no harsher locking.

On zipfian workloads, we found that all systems have lower latencies than on uniform workloads, and the relative performance between systems stays the same.

Strong scaling.

Figures 1.2, 5.3, and 5.4 report scaling on uniform workloads A and C, and the load phase, respectively, from 1 to 128 threads. All systems achieve speedup with increasing thread count.

On workload A, the OLC-B-skiplist and Folly achieve around 74× and 68× speedups, respectively, while the RW-B-skiplist, RW-B+-tree, and OLC-B+-tree lag behind at 45×, 34×, and 43×. The OLC-B-skiplist scales better because it eliminates the memory-access bottlenecks of the RW-B-skiplist and RW-B+-tree. On workload C, without insertions, the gap closes and all systems achieve greater speedups: 81×, 70×, 88×, 74×, and 64× for the OLC-B-skiplist, RW-B-skiplist, Folly, RW-B+-tree, and OLC-B+-tree, respectively.

On the load phase, we find that the OLC-B-skiplist and Folly achieve 57× and 60× speedup, respectively, far ahead of the RW-B-skiplist, RW-B+\mathrm{B}^{+}-tree, and OLC-B+\mathrm{B}^{+}-tree, which achieve only 22×22\times, 12×12\times, and 15×15\times speedup, respectively. This scaling gap comes from the cost of writing to shared node state in the different structures. The RW-lock-based structures write to the reader count in shared mode, invalidating the line in other cores’ caches. The OLC-B+\mathrm{B}^{+}-tree mitigates the issue by avoiding writes in shared mode, but splits eagerly and top-down: at every full node along an insert path, it write-locks that node and its parent, splits, and restarts the operation from the root. In contrast, the OLC-B-skiplist fixes its promotion height by an independent coin flip before the descent begins, so it write-locks only from the promotion level down and never restarts to split.

Related work.

We survey related work on optimistic concurrent skiplists and blocked skiplists. Section 1 discusses existing OLC-based structures.

Optimistic concurrent skiplists. The skiplist’s randomized structure admits elegant lock-based and lock-free CC protocols [18, 30, 19, 11, 12].

The closest method is the optimistic skiplist of Herlihy et al. [18, 19], which underlies Folly [1]. It traverses without acquiring locks and validates at the target node. The OLC-B-skiplist inherits this simplicity while improving locality and performance.

Concurrent blocked skiplists. Prior work improves the cache-friendliness of concurrent skiplists [35, 28] but often requires periodic restructuring of the upper levels, increasing tail latency. ESL [28] inserts elements only into the bottom level and updates upper index levels asynchronously. CSSL [33] and PI [35] periodically rebuild the upper levels, blocking reads and writes during restructuring. S3 [39] adaptively chooses guard entries with a neural model, abandoning the skiplist’s probabilistic guarantees.

We instead preserve the original B-skiplist structure to retain its simplicity and probabilistic guarantees.

Conclusion.

This paper presents the optimistic B-skiplist, a scalable concurrent in-memory index that combines the cache-friendly node layout of the B-skiplist with OLC. The optimistic B-skiplist preserves the skiplist’s simple structure while eliminating the space and cache-invalidation overheads of the partitioned RW locks in the RW-lock-based B-skiplist.

Our evaluation shows that on read-heavy workloads, the OLC-B-skiplist achieves higher throughput than the tested skiplists and competitive throughput with the tested B-trees. On write-heavy workloads, the OLC-B-skiplist achieves 1.21.2–4.4×4.4\times higher throughput over all tested indices, making it well-suited for write-heavy applications such as databases and key-value stores.

We plan to integrate the OLC-B-skiplist into key-value stores such as RocksDB [32] and LevelDB [26] to measure end-to-end application impact. The B-skiplist’s simple design, strong theoretical guarantees, and OLC-based CC make it an ideal replacement for traditional skiplists in modern key-value stores.

References

  1. [1]folly. https://github.com/facebook/folly. Last accessed 2/26/25.
  2. [2]ParallelTools. https://github.com/wheatman/ParallelTools. Last accessed 1/16/25.
  3. [3]A. Aggarwal and J. S. Vitter, The input/output complexity of sorting and related problems, Communications of the ACM, 31 (1988), pp. 1116–1127.DOI
  4. [4]R. Bayer and E. M. McCreight, Organization and maintenance of large ordered indexes, Acta Informatica, 1 (1972), pp. 173–189.
  5. [5]R. Bayer and M. Schkolnick, Concurrency of operations on b-trees, Acta informatica, 9 (1977), pp. 1–21.DOI
  6. [6]N. G. Bronson, J. Casper, H. Chafi, and K. Olukotun, A practical concurrent binary search tree, ACM Sigplan Notices, 45 (2010), pp. 257–268.
  7. [7]S. K. Cha, S. Hwang, K. Kim, and K. Kwon, Cache-conscious concurrency control of main-memory indexes on shared-memory multiprocessor systems, in VLDB, vol. 1, 2001, pp. 181–190.
  8. [8]B. F. Cooper, A. Silberstein, E. Tam, R. Ramakrishnan, and R. Sears, Benchmarking cloud serving systems with ycsb, in SoCC, 2010, pp. 143–154.DOI
  9. [9]T. Cory, N. Sulimany, and E. Petrank, Skiplists with foresight: Skipping cache misses, arXiv preprint arXiv:2606.13321, (2026).arxiv.org/abs/2606.13321
  10. [10]P.-J. Courtois, F. Heymans, and D. L. Parnas, Concurrent control with “readers” and “writers”, Communications of the ACM, 14 (1971), pp. 667–668.
  11. [11]M. Fomitchev and E. Ruppert, Lock-free linked lists and skip lists, in PODC, 2004, pp. 50–59.DOI
  12. [12]K. Fraser, Practical lock-freedom, tech. report, University of Cambridge, Computer Laboratory, 2004.
  13. [13]D. Golovin, The b-skip-list: A simpler uniquely represented alternative to b-trees, arXiv preprint arXiv:1005.0662, (2010).arxiv.org/abs/1005.0662
  14. [14]G. Graefe, Modern b-tree techniques, Foundations and Trends in Databases, 3 (2011), pp. 203–402.
  15. [15]R. Guerraoui and V. Trigonakis, Optimistic concurrency with optik, ACM SIGPLAN Notices, 51 (2016), pp. 1–12.
  16. [17]HBase. https://hbase.apache.org/. Last accessed 10/20/2022.
  17. [18]M. Herlihy, Y. Lev, V. Luchangco, and N. Shavit, A provably correct scalable concurrent skip list, in OPODIS, vol. 103, 2006.
  18. [19]M. Herlihy, Y. Lev, V. Luchangco, and N. Shavit, A simple optimistic skiplist algorithm, in SIROCCO, Springer, 2007, pp. 124–138.DOI
  19. [20]M. Herlihy, N. Shavit, V. Luchangco, and M. Spear, The art of multiprocessor programming, Newnes, 2020.
  20. [21]H. Kung and J. T. Robinson, On optimistic methods for concurrency control, ACM Transactions on Database Systems (TODS), 6 (1981), pp. 213–226.DOI
  21. [22]S. K. Lee, J. Mohan, S. Kashyap, T. Kim, and V. Chidambaram, RECIPE: Converting Concurrent DRAM Indexes to Persistent-Memory Indexes, in SOSP, Ontario, Canada, October 2019, p. 462–477.DOI
  22. [23]V. Leis, M. Haubenschchild, and T. Neumann, Optimistic lock coupling: A scalable and efficient general-purpose synchronization method., IEEE Data Eng. Bull., 42 (2019), pp. 73–84.
  23. [24]V. Leis, F. Scheibner, A. Kemper, and T. Neumann, The art of practical synchronization, in Proceedings of the 12th International Workshop on Data Management on New Hardware, 2016, pp. 1–8.DOI
  24. [25]S. T. Leutenegger and D. Dias, A modeling study of the tpc-c benchmark, ACM Sigmod Record, 22 (1993), pp. 22–31.
  25. [26]LEVELDB. https://github.com/google/leveldb. Last accessed 10/20/2022.
  26. [27]Y. Luo, S. Hao, B. Wheatman, P. Pandey, and H. Xu, Bridging cache-friendliness and concurrency: A locality-optimized in-memory b-skiplist, in ICPP, 2025, pp. 218–227.DOI
  27. [28]Y. Na, B. Koo, T. Park, J. Park, and W.-H. Kim, ESL: A high-performance skiplist with express lane, Applied Sciences, 13 (2023), p. 9925.DOI
  28. [29]B. Nichols, D. Buttlar, J. Farrell, and J. Farrell, Pthreads programming: A POSIX standard for better multiprocessing, ” O’Reilly Media, Inc.”, 1996.
  29. [30]W. Pugh, Concurrent maintenance of skip lists, Citeseer, 1990.
  30. [31]W. Pugh, Skip lists: a probabilistic alternative to balanced trees, Communications of the ACM, 33 (1990), pp. 668–676.
  31. [32]RocksDB. http://rocksdb.org/. Last accessed 10/20/2022.
  32. [33]S. Sprenger, S. Zeuch, and U. Leser, Cache-sensitive skip list: Efficient range queries on modern CPUs, in Data Management on New Hardware, Springer, 2016, pp. 1–17.DOI
  33. [34]Z. Wang, A. Pavlo, H. Lim, V. Leis, H. Zhang, M. Kaminsky, and D. G. Andersen, Building a bw-tree takes more than just buzz words, in Proceedings of the 2018 International Conference on Management of Data, 2018, pp. 473–488.DOI
  34. [35]Z. Xie, Q. Cai, H. Jagadish, B. C. Ooi, and W.-F. Wong, Parallelizing skip lists for in-memory multi-core database systems, in ICDE, IEEE, 2017, pp. 119–122.DOI
  35. [36]H. Xu, A. Li, B. Wheatman, M. Marneni, and P. Pandey, Bp-tree: Overcoming the point-range operation tradeoff for in-memory b-trees, Proc. VLDB Endow., 16 (2023), p. 2976–2989.
  36. [37]YCSB, Core workloads. https://github.com/brianfrankcooper/YCSB/wiki/Core-Workloads. Last accessed 2/15/2023.
  37. [38]X. Yu, G. Bezerra, A. Pavlo, S. Devadas, and M. Stonebraker, Staring into the abyss: An evaluation of concurrency control with one thousand cores, (2014).
  38. [39]J. Zhang, S. Wu, Z. Tan, G. Chen, Z. Cheng, W. Cao, Y. Gao, and X. Feng, S3: a scalable in-memory skip-list index for key-value store, Proceedings of the VLDB Endowment, 12 (2019), pp. 2183–2194.

Paper details

vlnc:W_ayqhyfp8
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 1

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents