arctic

This is the original implementation of Arctic: a practical lock-free adaptive radix tree. To the best of our knowledge (corrections welcome!), this is the fastest and most scalable concurrent ordered map to date.

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 access both APIs 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?

Out of all concurrent 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 and our measurements are accessible through the web interface, but 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), and atomic 128-bit compare-and-swap required for lock-freedom.
• Currently tested only on x86-64, but should work on other architectures in theory.

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.

License

Licensed under either of

• Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
• MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.