Scalable Concurrent Containers
A collection of concurrent data structures and building blocks for concurrent programming.
- scc::ebr implements epoch-based reclamation.
- scc::LinkedList is a type trait implementing a wait-free concurrent singly linked list.
- scc::HashMap is a concurrent hash map.
- scc::awaitable::HashMap is a non-blocking awaitable concurrent hash map.
- scc::HashSet is a concurrent hash set based on scc::HashMap.
- scc::HashIndex is a concurrent hash index allowing lock-free read and scan.
- scc::TreeIndex is a concurrent B+ tree allowing lock-free read and scan.
- scc::awaitable::TreeIndex is a non-blocking awaitable concurrent B+ tree.
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!;
LinkedList
LinkedList
is a type trait that implements wait-free concurrent singly linked list operations, backed by EBR
. It additionally provides support for marking an entry of a linked list to indicate that the entry is in 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!;
HashMap
HashMap
is a scalable in-memory unique key-value container that is targeted at highly concurrent heavy workloads. It applies EBR
to its entry array management, thus enabling it to avoid container-level locking and data sharding.
Examples
A unique key can be inserted along with its corresponding value, and then it can be updated, read, and removed.
use HashMap;
let hashmap: = default;
assert!;
assert_eq!;
assert_eq!;
assert_eq!;
It supports upsert
as in database management software; it tries to insert the given key-value pair, and if it fails, it updates the value field with the supplied closure.
use HashMap;
let hashmap: = default;
hashmap.upsert;
assert_eq!;
hashmap.upsert;
assert_eq!;
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
stays valid due to the lack of a global lock. Therefore Iterator
is not implemented, instead, it provides two methods that allow a HashMap
to iterate over its entries: for_each
, and retain
.
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`, a `ebr::Barrier` protects the entry array.
assert_eq!;
Awaitable HashMap
awaitable::HashMap
is a variant of HashMap
tailored to asynchronous code. Methods that access the data do not return the result immediately, instead a future
is returned; in order to get the result, the caller has to await it.
Examples
use HashMap;
let hashmap: = default;
let future_insert = hashmap.insert;
let result = future_insert.await;
HashSet
HashSet
is a variant of HashMap
where the value type is fixed ()
.
Examples
All the HashSet
methods do not receive a value argument.
use HashSet;
let hashset: = default;
assert!;
assert!;
assert!;
The capacity of a HashSet
can be specified.
use HashSet;
use RandomState;
let hashset: = new;
assert_eq!;
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 acquiring locks.
Examples
Its read
method does not modify any shared data.
use HashIndex;
let hashindex: = default;
assert!;
assert_eq!;
An Iterator
is implemented for HashIndex
, because 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.
use TreeIndex;
let treeindex: = new;
assert!;
assert_eq!;
assert!;
Key-value pairs can be scanned.
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!;
Awaitable TreeIndex
WORK-IN-PROGRESS
awaitable::TreeIndex
is a variant of TreeIndex
tailored to asynchronous code. Methods that modify the data do not return the result immediately, instead a future
is returned; in order to get the result, the caller has to await it.
Examples
use TreeIndex;
let treeindex: = default;
let future_insert = treeindex.insert;
let result = future_insert.await;
Performance
Test setup
- OS: SUSE Linux Enterprise Server 15 SP1
- CPU: Intel(R) Xeon(R) CPU E7-8880 v4 @ 2.20GHz x 4
- RAM: 1TB
- Rust: 1.56.0
- SCC: 0.5.8
- HashMap<usize, usize, RandomState> = HashMap::default()
- HashIndex<usize, usize, RandomState> = HashIndex::default()
- TreeIndex<usize, usize> = TreeIndex::default()
Test data
- A disjoint range of
usize
integers is assigned to each thread: 128M integers forHashMap
and 4M for others. - The performance test code asserts the expected outcome of each operation and the post state of the container.
Test workload: local
- Each test is run twice in a single process in order to minimize the effect of page faults as the overhead is unpredictable.
- Insert: each thread inserts its own records.
- Read: each thread reads its own records in the container.
- Scan: each thread scans the entire container once.
- Remove: each thread removes its own records from the container.
- The read/scan/remove data is populated by the insert test.
Test workload: local-remote
- Insert, remove: each thread additionally operates using keys belonging to a randomly chosen remote thread.
- Mixed: each thread performs insert-local -> insert-remote -> read-local -> read-remote -> remove-local -> remove-remote.
Test Results
11 threads | 22 threads | 44 threads | |
---|---|---|---|
InsertL | 169.888s | 182.077s | 208.961s |
ReadL | 104.574s | 112.154s | 118.647s |
ScanL | 29.299s | 60.656s | 125.701s |
RemoveL | 127.436s | 135.593s | 145.353s |
InsertR | 324.540s | 341.395s | 365.969s |
MixedR | 376.788s | 396.557s | 412.073s |
RemoveR | 260.364s | 277.673s | 295.6s |
11 threads | 22 threads | 44 threads | |
---|---|---|---|
InsertL | 4.574s | 4.871s | 6.692s |
ReadL | 2.313s | 2.397s | 2.693s |
ScanL | 0.757s | 1.548s | 3.094s |
RemoveL | 2.858s | 2.927s | 3.603s |
InsertR | 7.554s | 8.434s | 10.151s |
MixedR | 11.321s | 11.697s | 13.955s |
RemoveR | 5.813s | 5.92s | 7.623s |
11 threads | 22 threads | 44 threads | |
---|---|---|---|
InsertL | 5.887s | 10.731s | 15.248s |
ReadL | 1.069s | 1.128s | 1.24s |
ScanL | 11.834s | 26.22s | 56.101s |
RemoveL | 5.06s | 8.964s | 17.051s |
InsertR | 16.986s | 14.763s | 23.677s |
MixedR | 101.077s | 128.350s | 158.627s |
RemoveR | 6.771s | 6.768s | 8.102s |
Changelog
0.6.1
- Partially fix
#66
.
0.6.0
- Asynchronous
HashMap
.
0.5.8
- Optimize
HashMap
andHashSet
. - Fix a problem with the
retain
method erasing some entries satisfying the given predicate.
0.5.7