The ART of practical synchronization - Leis, Viktor; Scheibner, Florian; Kemper, Alfons; Neumann, Thomas (Proceedings of the ACM SIGMOD International Conference on Management of Data, 2016)
The performance of transactional database systems is critically dependent on the efficient synchronization of in-memory data structures. The traditional approach, fine-grained locking, does not scale on modern hardware. Lock-free data structures, in contrast, scale very well but are extremely difficult to implement and often require additional indirections. In this work, we argue for a middle ground, i.e., synchronization protocols that use locking, but only sparingly. We synchronize the Adaptive Radix Tree (ART) using two such protocols, Optimistic Lock Coupling and Read-Optimized Write EXclusion (ROWEX). Both perform and scale very well while being much easier to implement than lock-free techniques.
CRIS-Team Scopus Importer:2021-04-12