arctic/lib.rs
1#![warn(missing_docs)]
2
3//! This is the original implementation of
4//! [Arctic: a practical lock-free adaptive radix tree](https://www.usenix.org/conference/osdi26/presentation/ni).
5//!
6//! The main data structure is [`ConcurrentMap`],
7//! which is a thread-safe [map](https://en.wikipedia.org/wiki/Associative_array) that provides
8//! [lock-free](https://en.wikipedia.org/wiki/Non-blocking_algorithm#Lock-freedom),
9//! [linearizable](https://en.wikipedia.org/wiki/Linearizability)
10//! writes (e.g., [`upsert`][ConcurrentMap::upsert], [`remove`][ConcurrentMap::remove]);
11//! [wait-free](https://en.wikipedia.org/wiki/Non-blocking_algorithm#Wait-freedom),
12//! linearizable reads (i.e., [`get`][ConcurrentMap::get]);
13//! and wait-free, **non-linearizable** scans
14//! over key ranges and prefixes, in sorted order.
15//!
16//! This crate also includes [`SequentialMap`], which shares
17//! the same underlying structure as [`ConcurrentMap`], but
18//! gives up thread safety in exchange for single threaded performance
19//! and a more convenient API. The borrow checker allows us to
20//! safely take advantage of both APIs at runtime, via [`ConcurrentMap::as_sequential`].
21//!
22//! # Examples
23//!
24//! ```rust
25//! use std::thread;
26//!
27//! use arctic::ConcurrentMap;
28//! use arctic::Order;
29//!
30//! let map = ConcurrentMap::<u64, u64>::default();
31//!
32//! thread::scope(|scope| {
33//! let map = ↦
34//!
35//! // Concurrent writers (with overlapping keys)
36//! for thread in 0..8 {
37//! scope.spawn(move || {
38//! for offset in 0..128 {
39//! // 0..128, 64..192, ..., 448..576
40//! map.upsert(thread * 64 + offset, thread);
41//! }
42//! });
43//! }
44//! });
45//!
46//! // Ordered iteration over ranges
47//! assert!(
48//! map.range(5..=102)
49//! .entries(Order::Ascend)
50//! .map(|(key, _)| key)
51//! .eq(5..=102)
52//! );
53//!
54//! // Ordered iteration over prefixes
55//! assert!(
56//! map.prefix(&[0, 0, 0, 0, 0, 0, 2])
57//! .entries(Order::Descend)
58//! .map(|(key, _)| key)
59//! .eq((512..576).rev())
60//! );
61//! ```
62//!
63//! # Why use this crate?
64//!
65//! As far as we know (corrections welcome!), out of all map data structures that (a) are lock-free
66//! and (b) support ordered scan operations, [`ConcurrentMap`] provides the highest scalability and throughput.
67//! In fact, under various conditions (integer keys, skewed requests, update-heavy),
68//! we even out-perform data structures without properties (a) and/or (b).
69//! Our benchmarking infrastructure is in [this repository](https://github.com/nwtnni/index-bench);
70//! users are encouraged to measure performance on their own workloads.
71//!
72//! Briefly comparing against some alternative data structures:
73//!
74//! - Concurrent hash maps (e.g., [DashMap](https://github.com/xacrimon/dashmap), [papaya](https://github.com/ibraheemdev/papaya))
75//! have excellent performance, but do not support scan operations.
76//! - Concurrent B+-trees (e.g., [scc::TreeIndex](https://codeberg.org/wvwwvwwv/scalable-concurrent-containers))
77//! have good performance, but are typically not lock-free.
78//! - Concurrent skiplists (e.g., [crossbeam_skiplist](https://github.com/crossbeam-rs/crossbeam/tree/main/crossbeam-skiplist))
79//! have poor performance on modern hardware (low cache locality),
80//! although there are lock-free implementations.
81//!
82//! # Limitations
83//!
84//! - 128-bit atomic support required for good performance (currently using [portable-atomic](https://github.com/taiki-e/portable-atomic) crate)
85//! - SIMD acceleration is hand-written and currently restricted to AVX2
86//! - Theoretically supports big-endian targets, but untested
87//!
88//! # Correctness
89//!
90//! The research paper presents sketch proofs of linearizability and lock-freedom.
91//!
92//! More practically, we employ property testing (via [proptest](https://docs.rs/proptest/latest/proptest/))
93//! to test edges, node headers, and SIMD algorithms. The `state_machine` test suite uses
94//! [proptest-state-machine](https://proptest-rs.github.io/proptest/proptest/state-machine.html)
95//! to ensure [`ConcurrentMap`] and [`SequentialMap`] match [BTreeMap][std::collections::BTreeMap]
96//! on arbitrary sequences of operations.
97//!
98//! The `random` test suite inserts and removes disjoint sets of keys on each thread.
99//! The `orthogonal` test suite is a WIP attempt to build a concurrent version of the
100//! `state_machine` test. There is some preliminary work on writing
101//! [shuttle](https://github.com/awslabs/shuttle)-based tests.
102//!
103//! The entire test suite can be run with `cargo test --release --features proptest,rand,validate`.
104//!
105//! # Feature flags
106//!
107//! **Public features**.
108//! - `smr-hazard`, `smr-epoch`, and `smr-seize` enable their
109//! respective safe memory reclamation ([`Smr`][crate::concurrent::Smr]) backends. At least
110//! one SMR backend is required to use [`ConcurrentMap`]; by
111//! default, seize is enabled and used.
112//!
113//! **Development features**. These have no stability guarantees.
114//!
115//! - `validate` enables runtime checks of local invariants.
116//! - `stat` enables runtime statistic gathering.
117//! - `opt-no-*` disable optimizations for ablation measurements.
118//! - `opt-membarrier` enables [`membarrier`](https://man7.org/linux/man-pages/man2/membarrier.2.html)
119//! for hazard key and seize SMR backends.
120//! - `rand` enables integration with [rand](https://docs.rs/rand/latest/rand/)
121//! - `shuttle` enables integration with the [shuttle](https://docs.rs/shuttle/latest/shuttle/)
122//! concurrency testing runtime.
123//! - `proptest` enables integration with the [proptest](https://docs.rs/proptest/latest/proptest/)
124//! property testing framework.
125
126macro_rules! const_assert_size_align {
127 ($ty:ty, $size:expr, $align:expr) => {
128 #[cfg(not(feature = "shuttle"))]
129 const _: [(); $size] = [(); core::mem::size_of::<$ty>()];
130 #[cfg(not(feature = "shuttle"))]
131 const _: [(); $align] = [(); core::mem::align_of::<$ty>()];
132 };
133}
134
135macro_rules! if_validate {
136 ($if:expr $(, $else:expr)?) => {
137 if cfg!(any(feature = "validate", debug_assertions, test)) {
138 $if
139 }
140 $(else { $else })?
141 };
142}
143
144macro_rules! validate {
145 ($($tt:tt)*) => {
146 if cfg!(any(feature = "validate", debug_assertions, test)) {
147 assert!($($tt)*);
148 }
149 };
150}
151
152macro_rules! validate_eq {
153 ($($tt:tt)*) => {
154 if cfg!(any(feature = "validate", debug_assertions, test)) {
155 assert_eq!($($tt)*);
156 }
157 };
158}
159
160pub mod concurrent;
161pub(crate) mod raw;
162pub mod sequential;
163#[doc(hidden)]
164pub mod stat;
165#[doc(hidden)]
166pub mod sync;
167pub mod topology;
168
169#[doc(inline)]
170pub use raw::Key;
171#[doc(inline)]
172pub use raw::iter::Range;
173#[doc(inline)]
174pub use raw::key;
175
176#[doc(inline)]
177pub use concurrent::Map as ConcurrentMap;
178
179#[doc(inline)]
180pub use sequential::Map as SequentialMap;
181
182#[doc(inline)]
183pub use sequential::Set as SequentialSet;
184
185#[doc(inline)]
186pub use raw::iter::Order;
187
188/// <https://users.rust-lang.org/t/compiler-hint-for-unlikely-likely-for-if-branches/62102/4>
189#[inline]
190#[cold]
191pub(crate) fn cold() {}