Safe Optimistic Concurrency in Modern C++: A Reimplementation of Masstree

Abstract

The memory model introduced in C++11 marked a significant advancement in writing consistent and correct concurrent programs across diverse hardware platforms. However, concerns remain that this progress in portability and safety may have come at the cost of performance. In this thesis, we investigate the performance implications of using C++11-standard concurrency primitives in the context of high-performance data structures. We begin with an overview of the C++11 memory model, focusing on the header and its utilities. We then review recent developments in concurrent key-value stores, with particular attention to their use of synchronization mechanisms. Our primary contribution is a reimplementation of Masstree, a high-performance, tree-based key-value store. This reimplementation is designed to avoid all forms of undefined behavior under the C++11 memory model. This is achieved in spite of Masstree’s reliance on complex, optimistic concurrency techniques. Our implementation closely replicates the behavior of the original beta release by the Masstree authors, which depended on non-standard behaviors for performance. Through analysis of disassembled binaries and performance benchmarks on x86-64 systems, we demonstrate that adopting standard-compliant C++11 concurrency features incurs minimal performance overhead. Our findings suggest that careful engineering using standard tools can yield both correctness and efficiency in concurrent system design.