291
Erase Operation
The implementation of the erase operation for pmem::obj::concurrent_map is not
thread-safe. This method cannot be called concurrently with other methods of the
concurrent ordered map because this is a memory reclamation problem that is hard to
solve in C++ without a garbage collector. There is a way to logically extract a node from
a skip list in a thread-safe manner, but it is not trivial to detect when it is safe to delete
the removed node because other threads may still have access to the node. There are
possible solutions, such as hazard pointers, but these can impact the performance of the
find and insert operations.
Concurrent Hash Map
The concurrent hash map designed for persistent memory is based on tbb::concurrent_
hash_map that exists in the Intel TBB. The implementation is based on a concurrent hash
table algorithm where elements assigned to buckets based on a hash code are calculated
from a key. In addition to concurrent find, insert, and erase operations, the algorithm
employs concurrent resizing and on-demand per-bucket rehashing.
4
Figure 14-6 illustrates the basic idea of the concurrent hash table. The hash table
consists of an array of buckets, and each bucket consists of a list of nodes and a readwrite lock to control concurrent access by multiple threads.
4
Anton Malakhov. Per-bucket concurrent rehashing algorithms, 2015, arXiv:1509.02235v1;
https://arxiv.org/ftp/arxiv/papers/1509/1509.02235.pdf.
Figure 14-5. Fault-tolerant insert operation using persistent thread-local storage
Chapter 14 ConCurrenCy and persistent MeMory