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.

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())
);

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.

• 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

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.

Here are some YCSB workload scalability results, measured and plotted using index-bench. We insert 100M random keys of different types with u64 values, and then (for non-load workloads) record the throughput of 100M operations, using the default Zipfian skewness of 0.99 (top 10 keys receive ~17% of requests).

These were run on a Chameleon compute_icelake_r650 instance (example) with 80 physical cores. For reproducibility, we pin threads to cores, interleave memory across NUMA sockets, disable hyper-threading and turbo-boost, and set the CPU scaling governor to performance.

As for baselines, art (using ROWEX), fb_tree, hot, and wormhole are research systems written in C/C++ and integrated (hackily) via cxx. The remainder are published Rust crates (including masstree, which is the Rust port rather than the original).

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.

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.

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.