290
The algorithm described earlier is thread-safe, but it is not enough to be fault
tolerant on persistent memory. There is a possible persistent memory leak if a program
unexpectedly terminates between the first and fourth steps of our algorithm.
The implementation of pmem::obj::concurrent_map does not use transactions
to support data consistency because transactions do not support isolation and by not
using transactions, it can achieve better performance. For this linked list data structure,
data consistency is maintained because a newly allocated node is always reachable
(to avoid persistent memory leak) and the linked list data structure is always valid. To
support these two properties, persistent thread-local storage is used, which is a member
of the concurrent skip list data structure. Persistent thread-local storage guarantees that
each thread has its own location in persistent memory to assign the result of persistent
memory allocation for the new node.
Figure 14-5 illustrates the approach of this fault-tolerant insert algorithm. When a
thread allocates a new node, the pointer to that node is kept in persistent thread-local
storage, and the node is reachable through this persistent thread-local storage. Then
the algorithm inserts the new node to the skip list by linking it to all layers using the
thread-safe algorithm described earlier. Finally, the pointer in the persistent thread-local
storage is removed because the new node is reachable now via skip list itself. In case of
failure, a special function traverses all nonzero pointers in persistent thread-local storage
and completes the insert operation.
Figure 14-4. Inserting a new node with key=7 into the concurrent skip list
Chapter 14 ConCurrenCy and persistent MeMory
The algorithm described earlier is thread-safe, but it is not enough to be fault
tolerant on persistent memory. There is a possible persistent memory leak if a program
unexpectedly terminates between the first and fourth steps of our algorithm.
The implementation of pmem::obj::concurrent_map does not use transactions
to support data consistency because transactions do not support isolation and by not
using transactions, it can achieve better performance. For this linked list data structure,
data consistency is maintained because a newly allocated node is always reachable
(to avoid persistent memory leak) and the linked list data structure is always valid. To
support these two properties, persistent thread-local storage is used, which is a member
of the concurrent skip list data structure. Persistent thread-local storage guarantees that
each thread has its own location in persistent memory to assign the result of persistent
memory allocation for the new node.
Figure 14-5 illustrates the approach of this fault-tolerant insert algorithm. When a
thread allocates a new node, the pointer to that node is kept in persistent thread-local
storage, and the node is reachable through this persistent thread-local storage. Then
the algorithm inserts the new node to the skip list by linking it to all layers using the
thread-safe algorithm described earlier. Finally, the pointer in the persistent thread-local
storage is removed because the new node is reachable now via skip list itself. In case of
failure, a special function traverses all nonzero pointers in persistent thread-local storage
and completes the insert operation.
Figure 14-4. Inserting a new node with key=7 into the concurrent skip list
Chapter 14 ConCurrenCy and persistent MeMory