OLD VERSION: Scalable and Low Latency Lock-free Data Structures in C++ - Alexander Krizhanovsky

Discover how to implement scalable and low-latency lock-free data structures in C++ for web caching and high-performance computing. Learn about Gadex-3, live-looking, bit operations, atomic operations, memory allocators, and more.

Key takeaways
  • Log-free data structures are designed to operate efficiently in environments where concurrent access and modification of data are common, ensuring data integrity without the need for explicit locking or synchronization mechanisms.

  • The talk focuses on the implementation of scalable and low-latency lock-free data structures in C++, particularly in the context of web caching and high-performance computing.

  • The Gadex-3 data structure is introduced as a foundation for the presented implementations, emphasizing its advantages in terms of cache-consciousness and efficient collision handling.

  • The concept of “live-looking” is discussed, referring to the challenge of maintaining data consistency in the presence of concurrent readers and writers, and various techniques are explored to address this issue.

  • The use of bit operations and atomic operations is highlighted as crucial for achieving high performance and concurrency in log-free data structures.

  • The talk delves into the trade-offs involved in designing log-free data structures, such as the balance between efficiency and memory usage, and the impact of factors like cache line locality and memory fragmentation.

  • The importance of memory allocators in the context of log-free data structures is emphasized, as efficient memory management is essential for achieving scalability and performance.

  • The talk presents a custom data structure developed by the speaker, which combines techniques from Gadex-3 and other approaches to achieve high performance and scalability in specific use cases.

  • The challenges of handling deletions in log-free data structures are discussed, and various techniques for efficient removal of data are explored, including dummy nodes and copy-on-write mechanisms.

  • The talk concludes by highlighting the significance of tail latency in real-world applications and the importance of designing data structures that minimize the impact of tail latency on overall performance.