tpl_concurrent_hash_map.H File Reference

Sharded concurrent hash map (Aleph::ConcurrentHashMap). More...

#include <array>
#include <memory>
#include <mutex>
#include <optional>
#include <shared_mutex>
#include <type_traits>
#include <utility>
#include <ah-errors.H>
#include <tpl_dynSetHash.H>

Include dependency graph for tpl_concurrent_hash_map.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >
	Sharded concurrent hash map: Shards independently-locked DynMapHashTable partitions, no single global lock. More...
struct	Aleph::ConcurrentHashMap< Key, T, Cmp, Shards >::Shard

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Detailed Description

Sharded concurrent hash map (Aleph::ConcurrentHashMap).

ConcurrentHashMap<Key, T, Cmp, Shards> partitions its key space across a fixed number of independently-locked shards, each an ordinary Aleph::DynMapHashTable<Key, T> protected by its own std::shared_mutex. There is no single global lock: two threads operating on keys that hash to different shards run fully in parallel (including two concurrent writers), and any number of readers within the same shard run concurrently with each other.

This is deliberately the simplest safe design, not a lock-free one: a lock-free hash map needs hazard pointers or epoch-based reclamation to free removed nodes safely, which is substantially harder to get right and verify than sharded locking. Sharding already removes the single global bottleneck that makes Synchronized<DynMapHashTable<...>> (one mutex for the whole table) a poor fit for high-concurrency workloads.

Thread-safety

Every public member function is safe to call concurrently from any number of threads. Internally, each call maps its key to one shard (hash(key) % Shards, computed without locking anything) and then takes only that shard's std::shared_mutex: contains()/find_copy()/ with_value() take a shared (read) lock, insert()/insert_or_assign()/ erase()/with_value_mut() take an exclusive (write) lock. size() and snapshot() visit every shard in turn, each under its own lock.

What size()/snapshot() do not guarantee

Because different shards are locked one at a time rather than all together, size() and snapshot() are consistent per shard, not transactionally consistent across the whole map: a concurrent insert/erase racing with size() may or may not be reflected in the count depending on exactly when it lands relative to which shard size() has already visited. The same applies to snapshot(): it is a union of independent per-shard point-in-time views, not one global linearization point. Neither method blocks other shards while visiting one, so this looseness is the price of not serializing the whole map behind a single lock.

No live iteration

This type intentionally has no begin()/end() or other way to hold an iterator that outlives a single call: an iterator into a shard would either need to keep that shard locked for the iterator's entire lifetime (defeating the purpose of sharding) or risk becoming invalid the moment another thread mutates that shard. Use snapshot() to get an independent, owned copy of the entries instead, or with_value()/ with_value_mut() to operate on one entry while its shard is locked.

References must not escape a lock

with_value()/with_value_mut() invoke the caller's callback while holding the shard's lock and forbid the callback from returning a reference (enforced with a static_assert, mirroring Aleph::Synchronized::with_lock() in concurrency_utils.H). This catches the most common mistake (return v; from a callback taking T&/const T&) at compile time, but – like with_lock() – it cannot detect a callback that captures a pointer/reference to its argument into external state (e.g. a callback that assigns its parameter's address into a variable captured by reference); as with with_lock(), the callback should not do that, since the entry is only guaranteed valid while the shard's lock is held.

Example of use

Aleph::ConcurrentHashMap<std::string, int, Aleph::equal_to<std::string>, 16> cmap;
 
// Thread 1
cmap.insert("apples", 10);
 
// Thread 2 (Runs in parallel without locking Thread 1, if hashes diff shards)
cmap.insert_or_assign("oranges", 20);
 
// Thread 3 (Updates value safely using a lock over the specific shard)
cmap.with_value_mut("apples", [](int& v) { v += 5; });

See also

concurrency_utils.H for Aleph::Synchronized/Aleph::RwSynchronized (single-lock wrappers around an arbitrary type) and Aleph::BoundedChannel (blocking MPMC channel).

tpl_dynSetHash.H for Aleph::DynMapHashTable, used internally as each shard's sequential map implementation.

Author

Leandro Rabindranath Leon

(Documentation & Audit extensions)

Definition in file tpl_concurrent_hash_map.H.