Crate arctic 

This is the original implementation of Arctic: a practical lock-free adaptive radix tree.

The main data structure is ConcurrentMap, which is a thread-safe map that provides lock-free, linearizable writes (e.g., upsert, remove); wait-free, linearizable reads (i.e., get); and wait-free, non-linearizable scans over key ranges and prefixes, in sorted order.

This crate also includes SequentialMap, which shares the same underlying structure as ConcurrentMap, but gives up thread safety in exchange for single threaded performance and a more convenient API. The borrow checker allows us to safely take advantage of both APIs at runtime, via ConcurrentMap::as_sequential.

Examples

use std::thread;

use arctic::ConcurrentMap;
use arctic::Order;

let map = ConcurrentMap::<u64, u64>::default();

thread::scope(|scope| {
    let map = &map;

    // Concurrent writers (with overlapping keys)
    for thread in 0..8 {
        scope.spawn(move || {
            for offset in 0..128 {
                // 0..128, 64..192, ..., 448..576
                map.upsert(thread * 64 + offset, thread);
            }
        });
    }
});

// Ordered iteration over ranges
assert!(
    map.range(5..=102)
        .entries(Order::Ascend)
        .map(|(key, _)| key)
        .eq(5..=102)
);

// Ordered iteration over prefixes
assert!(
    map.prefix(&[0, 0, 0, 0, 0, 0, 2])
        .entries(Order::Descend)
        .map(|(key, _)| key)
        .eq((512..576).rev())
);

Why use this crate?

As far as we know (corrections welcome!), out of all map data structures that (a) are lock-free and (b) support ordered scan operations, ConcurrentMap provides the highest scalability and throughput. In fact, under various conditions (integer keys, skewed requests, update-heavy), we even out-perform data structures without properties (a) and/or (b). Our benchmarking infrastructure is in this repository; users are encouraged to measure performance on their own workloads.

Briefly comparing against some alternative data structures:

• Concurrent hash maps (e.g., DashMap, papaya) have excellent performance, but do not support scan operations.
• Concurrent B+-trees (e.g., scc::TreeIndex) have good performance, but are typically not lock-free.
• Concurrent skiplists (e.g., crossbeam_skiplist) have poor performance on modern hardware (low cache locality), although there are lock-free implementations.

Limitations

• 128-bit atomic support required for good performance (currently using portable-atomic crate)
• SIMD acceleration is hand-written and currently restricted to AVX2
• Theoretically supports big-endian targets, but untested

Correctness

The research paper presents sketch proofs of linearizability and lock-freedom.

More practically, we employ property testing (via proptest) to test edges, node headers, and SIMD algorithms. The state_machine test suite uses proptest-state-machine to ensure ConcurrentMap and SequentialMap match BTreeMap on arbitrary sequences of operations.

The random test suite inserts and removes disjoint sets of keys on each thread. The orthogonal test suite is a WIP attempt to build a concurrent version of the state_machine test. There is some preliminary work on writing shuttle-based tests.

The entire test suite can be run with cargo test --release --features proptest,rand,validate.

Feature flags

Public features.

• smr-hazard, smr-epoch, and smr-seize enable their respective safe memory reclamation (Smr) backends. At least one SMR backend is required to use ConcurrentMap; by default, seize is enabled and used.

Development features. These have no stability guarantees.

• validate enables runtime checks of local invariants.
• stat enables runtime statistic gathering.
• opt-no-* disable optimizations for ablation measurements.
• opt-membarrier enables membarrier for hazard key and seize SMR backends.
• rand enables integration with rand
• shuttle enables integration with the shuttle concurrency testing runtime.
• proptest enables integration with the proptest property testing framework.

Modules

concurrent

Lock-free concurrent implementation of adaptive radix tree.

key

Abstraction over various key types.

sequential

Non-concurrent implementation of adaptive radix tree.

Structs

ConcurrentMap

Lock-free concurrent map that supports lexicographically ordered, non-linearizable range and prefix scans.

SequentialMap

Non-concurrent map that supports lexicographically ordered range and prefix scans.

SequentialSet

Non-concurrent set.

Enums

Order

Key order for scan operations (e.g., concurrent::Shard::entries).

Traits

Key

Byte sequence that can be stored in an adaptive radix tree.

Range

Native range types (.., lower.., ..=upper, lower..=upper) that can be passed as bounds to SequentialMap::range and ConcurrentMap::range.