Paper Info
Title
MV-RLU: Scaling Read-Log-Update with Multi-Versioning
Abstract
This paper presents multi-version read-log-update (MV-RLU), an extension of the read-log-update (RLU) synchronization mechanism. While RLU has many merits including an intuitive programming model and excellent performance for read-mostly workloads, we observed that the performance of RLU significantly drops in workloads with more write operations. The core problem is that RLU manages only two versions. To overcome such limitation, we extend RLU to support multi-versioning and propose new techniques to make multi-versioning efficient. At the core of MV-RLU design is concurrent autonomous garbage collection, which prevents reclaiming invisible versions being a bottleneck, and reduces the version traversal overhead the main overhead of multi-version design. We extensively evaluate MV-RLU with the state-of-the-art synchronization mechanisms, including RCU, RLU, software transactional memory (STM), and lock-free approaches, on concurrent data structures and real-world applications (database concurrency control and in-memory key-value store). Our evaluation results show that MV-RLU significantly outperforms other techniques for a wide range of workloads with varying contention levels and data-set size.
Year
DOI
Venue
2019
10.1145/3297858.3304040
Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems
Keywords
Field
DocType
concurrency control, garbage collection, multi-version, synchronization
Bottleneck,Software transactional memory,Tree traversal,Programming paradigm,Concurrency control,Computer science,Parallel computing,Garbage collection,Concurrent data structure,Software versioning
Conference
ISBN
Citations 
PageRank 
978-1-4503-6240-5
1
0.35
References 
Authors
0
5
Name
Order
Citations
PageRank
Jaeho Kim17612.54
Ajit Mathew211.02
Sanidhya Kashyap312410.92
Madhava Krishnan Ramanathan410.35
Changwoo Min529429.89