286
To understand the problem with lock-free algorithms, remember that a system
with persistent memory will usually have the virtual memory subsystem divided into
two domains: volatile and persistent (described in Chapter 2). The result of an atomic
operation may only update data in a CPU cache using a cache coherency protocol. There
is no guarantee that the data will be flushed unless an explicit flush operation is called.
CPU caches are only included within the persistence domain on platforms with eADR
support. This is not mandatory for persistent memory. ADR is the minimal platform
requirement for persistent memory, and in that case, CPU caches are not flushed in a
power failure.
Figure 14-2 assumes a system with ADR support. The example shows concurrent
lock-free insert operations to a singly linked list located in persistent memory. Two
threads are trying to insert new nodes to the tail of a linked list using a compare-andexchange (CMPXCHG instruction) operation followed by a cache flush operation (CLWB
instruction). Assume Thread 1 succeeds with its compare-and-exchange, so the change
appears in a volatile domain and becomes visible to the second thread. At this moment,
Thread 1 may be preempted (changes not flushed to a persistent domain), while Thread
2 inserts Node 5 after Node 4 and flushes it to a persistent domain. A possibility for data
inconsistency exists because Thread 2 performed an update based on the data that is not
yet persisted by Thread 1.
Concurrent Data Structures for Persistent Memory
This section describes two concurrent data structures available in the libpmemobj-cpp
library: pmem::obj::concurrent_map and pmem::obj::concurrent_hash_map. Both are
associative data structures composed of a collection of key and value pairs, such that
each possible key appears at most once in the collection. The main difference between
them is that the concurrent hash map is unordered, while the concurrent map is ordered
by keys.
Figure 14-2. Example of a concurrent lock-free insert operation to a singly linked
list located in persistent memory
Chapter 14 ConCurrenCy and persistent MeMory
To understand the problem with lock-free algorithms, remember that a system
with persistent memory will usually have the virtual memory subsystem divided into
two domains: volatile and persistent (described in Chapter 2). The result of an atomic
operation may only update data in a CPU cache using a cache coherency protocol. There
is no guarantee that the data will be flushed unless an explicit flush operation is called.
CPU caches are only included within the persistence domain on platforms with eADR
support. This is not mandatory for persistent memory. ADR is the minimal platform
requirement for persistent memory, and in that case, CPU caches are not flushed in a
power failure.
Figure 14-2 assumes a system with ADR support. The example shows concurrent
lock-free insert operations to a singly linked list located in persistent memory. Two
threads are trying to insert new nodes to the tail of a linked list using a compare-andexchange (CMPXCHG instruction) operation followed by a cache flush operation (CLWB
instruction). Assume Thread 1 succeeds with its compare-and-exchange, so the change
appears in a volatile domain and becomes visible to the second thread. At this moment,
Thread 1 may be preempted (changes not flushed to a persistent domain), while Thread
2 inserts Node 5 after Node 4 and flushes it to a persistent domain. A possibility for data
inconsistency exists because Thread 2 performed an update based on the data that is not
yet persisted by Thread 1.
Concurrent Data Structures for Persistent Memory
This section describes two concurrent data structures available in the libpmemobj-cpp
library: pmem::obj::concurrent_map and pmem::obj::concurrent_hash_map. Both are
associative data structures composed of a collection of key and value pairs, such that
each possible key appears at most once in the collection. The main difference between
them is that the concurrent hash map is unordered, while the concurrent map is ordered
by keys.
Figure 14-2. Example of a concurrent lock-free insert operation to a singly linked
list located in persistent memory
Chapter 14 ConCurrenCy and persistent MeMory