Lightweight Latches for B-Trees to Cope with High Contention

B-trees are ubiquitous for many users to store and retrieve large amounts of data concurrently. Concurrency control protocols are introduced to guarantee the physical consistency of B-trees and a high degree of parallelism without any deadlocks. Recently, various optimistic protocols like optimistic lock coupling and hybrid locking coupling have been shown to achieve a higher degree of parallelism compared to standard lock-based protocols. However, the overhead of these optimistic approaches increases for workloads with high and skewed contention. These workloads are very common for near-sorted data inputs, e.g., data streams with a certain degree of out-of-order arrivals where insertions hit only a small fraction of the leaves. Based on these optimistic approaches, this paper presents two novel optimistic concurrency protocols designed for workloads with high local contention. In case of conflicts, these protocols offer a substantially lower overhead than their previous optimistic counterparts and, thus, a higher degree of parallelism. The results of a comprehensive experimental performance comparison show the advantages of our proposed protocols as a function of contention.