Scalable Concurrent Containers
A collection of high performance containers and utilities for concurrent and asynchronous programming.
Concurrent and Asynchronous Containers
- HashMap is a concurrent and asynchronous hash map.
- HashSet is a concurrent and asynchronous hash set.
- HashIndex is a read-optimized concurrent and asynchronous hash map.
- TreeIndex is a read-optimized concurrent and asynchronous B+ tree.
- Queue is a concurrent lock-free first-in-first-out queue.
Utilities for Concurrent Programming
- EBR implements epoch-based reclamation.
- LinkedList is a type trait implementing a lock-free concurrent singly linked list.
See Performance for benchmark results for the containers.
HashMap
HashMap is a scalable in-memory unique key-value container that is targeted at highly concurrent write-heavy workloads. It uses EBR for its hash table memory management in order to implement non-blocking resizing and fine-granular locking without static data sharding; it is not a lock-free data structure, and each access to a single key is serialized by a bucket-level mutex. HashMap is optimized for frequently updated large data sets, such as the lock table in database management software.
Examples
A unique key can be inserted along with its corresponding value, and then the inserted entry can be updated, read, and removed synchronously or asynchronously.
use HashMap;
let hashmap: = default;
assert!;
assert_eq!;
assert_eq!;
assert_eq!;
let future_insert = hashmap.insert_async;
let future_remove = hashmap.remove_async;
It supports upsert
as in database management software; it tries to insert the given key-value pair, and if the key exists, it updates the value field with the supplied closure.
use HashMap;
let hashmap: = default;
hashmap.upsert;
assert_eq!;
hashmap.upsert;
assert_eq!;
let future_upsert = hashmap.upsert_async;
There is no method to confine the lifetime of references derived from an Iterator to the Iterator, and it is illegal to let them live as long as the HashMap. Therefore Iterator is not implemented, instead, it provides a number of methods as substitutes for Iterator: for_each
, for_each_async
, scan
, scan_async
, retain
, and retain_async
.
use HashMap;
let hashmap: = default;
assert!;
assert!;
// Inside `for_each`, an `ebr::Barrier` protects the entry array.
let mut acc = 0;
hashmap.for_each;
assert_eq!;
// `for_each` can modify the entries.
assert_eq!;
assert_eq!;
assert!;
// Inside `retain`, an `ebr::Barrier` protects the entry array.
assert_eq!;
// It is possible to scan the entries asynchronously.
let future_scan = hashmap.scan_async;
let future_for_each = hashmap.for_each_async;
HashSet
HashSet is a version of HashMap where the value type is ()
.
Examples
All the HashSet methods do not receive a value argument.
use HashSet;
let hashset: = default;
assert!;
assert!;
assert!;
let future_insert = hashset.insert_async;
let future_remove = hashset.remove_async;
HashIndex
HashIndex is a read-optimized version of HashMap. It applies EBR to its entry management as well, enabling it to perform read operations without blocking or being blocked.
Examples
Its read
method is completely lock-free and does not modify any shared data.
use HashIndex;
let hashindex: = default;
assert!;
assert_eq!;
let future_insert = hashindex.insert_async;
let future_remove = hashindex.remove_if;
An Iterator is implemented for HashIndex, because any derived references can survive as long as the associated ebr::Barrier
lives.
use Barrier;
use HashIndex;
let hashindex: = default;
assert!;
let barrier = new;
// An `ebr::Barrier` has to be supplied to `iter`.
let mut iter = hashindex.iter;
// The derived reference can live as long as `barrier`.
let entry_ref = iter.next.unwrap;
assert_eq!;
drop;
// The entry can be read after `hashindex` is dropped.
assert_eq!;
TreeIndex
TreeIndex is a B+ tree variant optimized for read operations. The ebr
module enables it to implement lock-free read and scan methods.
Examples
Key-value pairs can be inserted, read, and removed, and the read
method is lock-free.
use TreeIndex;
let treeindex: = new;
assert!;
assert_eq!;
assert!;
let future_insert = treeindex.insert_async;
let future_remove = treeindex.remove_if_async;
Key-value pairs can be scanned and the scan
method is lock-free.
use Barrier;
use TreeIndex;
let treeindex: = new;
assert!;
assert!;
assert!;
let barrier = new;
let mut visitor = treeindex.iter;
assert_eq!;
assert_eq!;
assert_eq!;
assert!;
Key-value pairs in a specific range can be scanned.
use Barrier;
use TreeIndex;
let treeindex: = new;
for i in 0..10
let barrier = new;
assert_eq!;
assert_eq!;
assert_eq!;
Queue
Queue is a concurrent lock-free first-in-first-out queue.
Examples
use Queue;
let queue: = default;
queue.push;
assert!;
assert!;
assert_eq!;
assert_eq!;
assert!;
EBR
The ebr
module implements epoch-based reclamation and various types of auxiliary data structures to make use of it. Its epoch-based reclamation algorithm is similar to that implemented in crossbeam_epoch, however users may find it easier to use as the lifetime of an instance is safely managed. For instance, ebr::AtomicArc
and ebr::Arc
hold a strong reference to the underlying instance, and the instance is automatically passed to the garbage collector when the reference count drops to zero.
Examples
The ebr
module can be used without an unsafe
block.
use ;
use Relaxed;
// `atomic_arc` holds a strong reference to `17`.
let atomic_arc: = new;
// `barrier` prevents the garbage collector from dropping reachable instances.
let barrier: Barrier = new;
// `ptr` cannot outlive `barrier`.
let mut ptr: = atomic_arc.load;
assert_eq!;
// `atomic_arc` can be tagged.
atomic_arc.update_tag_if;
// `ptr` is not tagged, so CAS fails.
assert!;
// `ptr` can be tagged.
ptr.set_tag;
// The return value of CAS is a handle to the instance that `atomic_arc` previously owned.
let prev: = atomic_arc.compare_exchange.unwrap.0.unwrap;
assert_eq!;
// `17` will be garbage-collected later.
drop;
// `ebr::AtomicArc` can be converted into `ebr::Arc`.
let arc: = atomic_arc.try_into_arc.unwrap;
assert_eq!;
// `18` will be garbage-collected later.
drop;
// `17` is still valid as `barrier` keeps the garbage collector from dropping it.
assert_eq!;
// Execution of a closure can be deferred until all the current readers are gone.
barrier.defer_execute;
drop;
// The closure will be repeatedly invoked until it returns `true`.
let barrier = new;
let mut data = 3;
barrier.defer_incremental_execute;
drop;
// If the thread is expected to lie dormant for a while, call `suspend()` to allow other threads
// to reclaim its own retired instances.
suspend;
LinkedList
LinkedList is a type trait that implements lock-free concurrent singly linked list operations, backed by EBR. It additionally provides support for marking an entry of a linked list to denote a user-defined state.
Examples
use ;
use LinkedList;
use Relaxed;
;
let barrier = new;
let head: L = default;
let tail: = new;
// A new entry is pushed.
assert!;
assert!;
// Users can mark a flag on an entry.
head.mark;
assert!;
// `next_ptr` traverses the linked list.
let next_ptr = head.next_ptr;
assert_eq!;
// Once `tail` is deleted, it becomes invisible.
tail.delete_self;
assert!;
Performance
Comparison with DashMap and flurry.
- Results on Apple M1 (8 cores).
- Results on Intel Xeon (88 cores).
- Interpret the results cautiously as benchmarks do not represent real world workloads.
- HashMap and HashIndex outperform the others according to the benchmark test under highly concurrent workloads.
- The benchmark test a fork of conc-map-bench.