Talk type: Talk

Wait-free data structures and wait-free transactions

  • Talk in English
Presentation pdf

Concurrent data structures are at the heart of most multi-threaded applications, from queues that pass messages between actors, to indexing data structures in Key/Value stores. The Java JDK has had several for many years, and C++ is on track to add a few as well.

The easiest way to implement a concurrent data structure is to take a sequential implementation (single-threaded) and protect its methods with a mutual exclusion lock. This approach is easy enough to be done correctly by a novice software engineer, however, it has low scalability and is subject to large latencies.

Apart from being resilient to failures, lock-free and wait-free data structures can have a better latency profile, but it takes significant expertise to implement or modify them to suit specific application needs. Changing a single line of code in a lock-free data structure is likely to cause it to become incorrect.

What if there was a way to allow a non-expert software developer to design and implement correct wait-free data structures? And what if these data structures could scale, have low tail latency, be resilient to failures and have integrated memory reclamation?

Perhaps surprisingly, at the exception of one of these things, it is possible to have this today using an Universal Construction or a Software Transactional Memory.

In this talk we're going to explain what are and how to use Universal Constructions and Software Transactional Memories, and how we can use their wait-free transactions to make wait-free data structures.

  • #acid
  • #concurrent-data-structures
  • #lock-free
  • #persistent-memory
  • #stm
Talks