pipette
ENEnglish

A Simple Optimistic B-Skiplist Algorithm

Jianting Guo, Yicong Luo, Helen Xu

PreprintAfirmaciones fuertes, leer con cuidadoDice ser un gran avance

En palabras de los autores

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 higher throughput over state-of-the-art concurrent skiplist implementations. Furthermore, the optimistic B-skiplist achieves the throughput compared to high-performance optimistic B+-tree implementations based on RW locks and OLC. Finally, the optimistic B-skiplist achieves up to lower latency than concurrent skiplists and tree-based indices, and is within of the latency of the OLC-based B+-tree.

Resultado principalEl resumen no menciona limitaciones.

Apareció: viernes, 30 de octubre. arXiv. Preprint, todavía sin revisión por pares.