scc (Scalable Concurrent Containers)

A TreeIndex is a B-plus tree variant optimized for read operations. It uses sdd to protect memory used by individual entries, enabling lock-free read access.

Locking Behavior

• Read access: Always lock-free and non-blocking.
• Write access: Lock-free and non-blocking as long as no structural changes (node splits or merges) are required. If a write operation causes a node to split or merge, other write operations on keys in the affected range are blocked.
• Blocking impact: Blocking operations during node splits/merges do not affect read operations.

Entry Lifetime

TreeIndex does not drop removed entries immediately. Entries are dropped only when the leaf node is cleared or split. Consequently, TreeIndex is suboptimal for write-heavy workloads where frequent removals occur.

use scc::TreeIndex;

let treeindex: TreeIndex<u64, u32> = TreeIndex::new();

assert!(treeindex.insert_sync(1, 2).is_ok());

// `peek` and `peek_with` are lock-free.
assert_eq!(treeindex.peek_with(&1, |_, v| *v).unwrap(), 2);
assert!(treeindex.remove_sync(&1));

let future_insert = treeindex.insert_async(2, 3);
let future_remove = treeindex.remove_if_async(&1, |v| *v == 2);

scc::HashIndex is a read-optimized version of HashMap. It uses sdd to protect entry buckets, enabling lock-free read access to individual entries via peek and peek_with.

Important: Entry Lifetime

HashIndex does not drop removed entries immediately. An entry is only dropped when the bucket is accessed again after sdd ensures no potential readers remain. This makes HashIndex unsuitable for write-heavy workloads with large entry sizes.

Iteration

Unlike HashMap, HashIndex implements the standard Iterator trait, but requires an sdd::Guard to be supplied to the iter method.

use scc::HashIndex;
use sdd::Guard;

let hashindex: HashIndex<u64, u32> = HashIndex::default();
assert!(hashindex.insert_sync(1, 0).is_ok());

// Lock-free reads
assert_eq!(hashindex.peek_with(&1, |_, v| *v).unwrap(), 0);

// Updating entries
if let Some(mut o) = hashindex.get_sync(&1) {
    o.update(2); // Create a new version
}

// Standard Iterator usage
let guard = Guard::new();
let mut iter = hashindex.iter(&guard);
let entry_ref = iter.next().unwrap();

use scc::HashIndex;

use sdd::Guard;

let hashindex: HashIndex<u64, u32> = HashIndex::default();

assert!(hashindex.insert_sync(1, 0).is_ok());

// `peek` and `peek_with` are lock-free.
assert_eq!(hashindex.peek_with(&1, |_, v| *v).unwrap(), 0);

let future_insert = hashindex.insert_async(2, 1);
let future_remove = hashindex.remove_if_async(&1, |_| true);

// The `Entry` API of `HashIndex` can update an existing entry.
assert!(hashindex.insert_sync(1, 1).is_ok());

if let Some(mut o) = hashindex.get_sync(&1) {
    // Create a new version of the entry.
    o.update(2);
};

if let Some(mut o) = hashindex.get_sync(&1) {
    // Update the entry in place.
    unsafe { *o.get_mut() = 3; }
};

// An `Iterator` is implemented for `HashIndex`.
let hashindex: HashIndex<u64, u32> = HashIndex::default();
assert!(hashindex.insert_sync(1, 0).is_ok());

// Existing values can be replaced with a new one.
hashindex.get_sync(&1).unwrap().update(1);

let guard = Guard::new();

// An `Guard` has to be supplied to `iter`.
let mut iter = hashindex.iter(&guard);

let entry_ref = iter.next().unwrap();
assert_eq!(iter.next(), None);

Because HashMap cannot implement the standard Iterator trait due to lifetime constraints on Iterator::Item, it provides specialized iteration methods:

Synchronous Iteration

• iter_sync: Returns true if all entries satisfy a predicate.
• retain_sync: Allows modifying or removing entries based on a predicate.
• begin_sync: Returns an OccupiedEntry to start manual iteration.

Asynchronous Iteration

• iter_async: An asynchronous scan over entries.
• begin_async: Returns an asynchronous iterator using the Entry API.

use scc::HashMap;

let hashmap: HashMap<u64, u32> = HashMap::default();
assert!(hashmap.insert_sync(1, 0).is_ok());
assert!(hashmap.insert_sync(2, 1).is_ok());

// Using retain_sync to modify and filter
let mut acc = 0;
hashmap.retain_sync(|k, v_mut| { acc += *k; *v_mut = 2; true });

// Using iter_sync for predicates
assert!(hashmap.insert_sync(3, 2).is_ok());
assert!(!hashmap.iter_sync(|k, _| *k == 3));

// Asynchronous iteration using begin_async
let future_iter = async {
    let mut iter = hashmap.begin_async().await;
    while let Some(entry) = iter {
        assert_eq!(*entry.key(), 1);
        iter = entry.next_async().await;
    }
};

use scc::HashMap;

let hashmap: HashMap<u64, u32> = HashMap::default();

assert!(hashmap.insert_sync(1, 0).is_ok());
assert!(hashmap.insert_sync(2, 1).is_ok());

// Entries can be modified or removed via `retain_sync`.
let mut acc = 0;
hashmap.retain_sync(|k, v_mut| { acc += *k; *v_mut = 2; true });
assert_eq!(acc, 3);
assert_eq!(hashmap.read_sync(&1, |_, v| *v).unwrap(), 2);
assert_eq!(hashmap.read_sync(&2, |_, v| *v).unwrap(), 2);

// `iter_sync` returns `true` when all the entries satisfy the predicate.
assert!(hashmap.insert_sync(3, 2).is_ok());
assert!(!hashmap.iter_sync(|k, _| *k == 3));

// Multiple entries can be removed through `retain_sync`.
hashmap.retain_sync(|k, v| *k == 1 && *v == 2);

// `hash_map::OccupiedEntry` also can return the next closest occupied entry.
let first_entry = hashmap.begin_sync();
assert_eq!(*first_entry.as_ref().unwrap().key(), 1);
let second_entry = first_entry.and_then(|e| e.next_sync());
assert!(second_entry.is_none());

// Asynchronous iteration over entries using `iter_async`.
let future_scan = hashmap.iter_async(|k, v| { println!("{k} {v}"); true });

// Asynchronous iteration over entries using the `Entry` API.
let future_iter = async {
    let mut iter = hashmap.begin_async().await;
    while let Some(entry) = iter {
        assert_eq!(*entry.key(), 1);
        iter = entry.next_async().await;
    }
};

A HashIndex is a concurrent hash map data structure optimized for parallel read operations. It is similar to a standard HashMap but with several key differences:

• Lock-free read: Read and scan operations are never blocked and do not modify shared data.
• Immutability: Data in the container is immutable until it becomes unreachable.
• Linearizability: The linearizability of read operations relies on the CPU architecture.

Key Statistics:

• Expected metadata per key-value pair: 2 bytes.
• Expected atomic write operations per key: 2.
• Expected atomic variables accessed per key: 2.
• Entries managed by a single bucket without a linked list: 32.
• Expected maximum linked list length when resize is triggered: log(capacity) / 8.

Unwind Safety: HashIndex is impervious to out-of-memory errors and panics in user-specified code provided that H::Hasher::hash, K::drop, and V::drop do not panic.

A TreeIndex is a scalable, concurrent B-plus tree optimized for read operations.

Key Characteristics

• Lock-free reads: Read and scan operations are never blocked and do not modify shared data.
• Near lock-free writes: Write operations (insert/remove) do not block unless a structural change (like a node split or merge) is required.
• No busy waiting: Uses wait queues for nodes to avoid spinning.
• Immutability: Data is immutable until it becomes unreachable.

Important Guarantees and Limitations

• Linearizability: TreeIndex methods are linearizable.
• Iterator Non-linearizability: The Iter and Range iterators are not linearizable; they are only guaranteed to observe events that occurred before the first call to Iterator::next.
• Unwind Safety: The container is impervious to panics in user-specified code only if K::drop and V::drop do not panic.
• Async Usage: Avoid using synchronous methods (like insert_sync) inside asynchronous code blocks or poll functions, as this can lead to deadlocks or performance degradation.

The HashMap is a concurrent hash map optimized for parallel write-heavy workloads. It uses a non-sharded design where data is stored in a single array of entry buckets.

Locking Behavior

• Bucket Access: Protected by sdd, allowing lock-free access to bucket arrays.
• Entry Access: Each read/write access to an entry is serialized by a read-write lock in the bucket containing the entry. As the map grows, contention on bucket-level locks decreases.
• Resizing: Resizing is non-blocking and lock-free. It is analogous to pushing a new bucket array onto a lock-free stack. Entries in the old array are incrementally relocated during future accesses, and the old array is dropped once it is empty and unreachable.

Performance and Safety

• Linearizability: All manipulation methods are linearizable.
• No Busy Waiting: The implementation avoids spin locks or hot loops.
• Unwind Safety: The map is impervious to OOM errors and panics provided that H::Hasher::hash, K::drop, and V::drop do not panic.

Important Usage Note

Avoid using blocking methods (like insert_sync) inside asynchronous code blocks or poll functions, as this may lead to deadlocks or performance degradation.