TY - GEN
T1 - The ART of practical synchronization
AU - Leis, Viktor
AU - Scheibner, Florian
AU - Kemper, Alfons
AU - Neumann, Thomas
N1 - Publisher Copyright:
© 2016 ACM.
PY - 2016/6/26
Y1 - 2016/6/26
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85046397788&partnerID=8YFLogxK
U2 - 10.1145/2933349.2933352
DO - 10.1145/2933349.2933352
M3 - Conference contribution
AN - SCOPUS:85046397788
SN - 9781450343190
T3 - Proceedings of the ACM SIGMOD International Conference on Management of Data
BT - Proceedings of the 12th International Workshop on Data Management on New Hardware, DaMoN 2016
PB - Association for Computing Machinery
T2 - 12th International Workshop on Data Management on New Hardware, DaMoN 2016
Y2 - 26 June 2016 through 1 July 2016
ER -