Hi everyone!
We recently published a new lock-free concurrent ordered map called arctic at OSDI '26, a systems research conference, and on crates.io. Some example use cases are memtables in log-structured merge trees, or indexes in databases using multi-version concurrency control. I've been working on this data structure for more than a year, and believe it's now mature enough to be useful to the wider community. (To hopefully disarm AI slop detectors without derailing: I did not and have yet to use LLMs in any capacity, including: brainstorming, testing, benchmarking, or writing code, documentation, or prose).
I'll give my elevator pitch before bringing up some more Rust-specific topics.
Pitch
It's hard to find a concurrent map that is performant, lock-free, and ordered (i.e., supports efficient range scans); it's a fundamentally challenging design space regardless of programming language. If you don't need ordering, there are plenty of fast concurrent hash maps. If you do need ordering, you're typically forced to choose between performance and lock-freedom: most high-performance ordered data structures (e.g., B+-trees) use optimistic lock coupling; most lock-free ordered data structures (e.g., Bw-tree) are slower than their lock-based counterparts.
We claim arctic is the first concurrent map with all three properties (with caveats):
- Provides high throughput and scalability (measured up to 80 physical cores across two sockets) over a variety of workloads and key types[1], consistently beating lock-free ordered maps, frequently beating lock-based ordered maps, and occasionally even beating unordered maps.
- Guarantees lock-free linearizable writes, wait-free linearizable reads, and wait-free non-linearizable[2] range and prefix scans.
- Belongs to the prefix tree or trie family of data structures and therefore orders keys lexicographically[3].
Additionally, arctic requires atomic 16B compare-and-swap for lock-freedom, and currently only supports SIMD acceleration when compiling for AVX-2 targets. Memory overhead varies with the key distribution. Here are some benchmark results from a two socket machine with 80 physical cores; there are more in the arctic repository and index-bench repository.
Details
I'm going to discuss some of the Rust-specific difficult points in arctic's design in the hope that someone will chime in with better ideas. If you're interested in a higher-level understanding of how the data structure works, please refer to our paper.
Type safety
We reuse almost all structural types and traversal logic between the concurrent and sequential map implementations. In tandem with the borrow checker, this allows us to safely expose the sequential API from the concurrent map, provided the caller has an exclusive reference.
The main downside is that this greatly increases the amount of unsafe code: for example, we use NonNull instead of references internally so higher layers can choose between &Atomic<T> vs. &mut T, and similarly assume higher layers handle safe memory reclamation. In particular, one level of abstraction may ensure one safety condition, but everything is marked unsafe as long as any safety condition may not be met. I thought it might be interesting if each unsafe block could define which conditions it assumes, which maybe gets into effect systems.
I also had a hard time with the Key trait. Unlike most maps, prefix trees encode keys in the tree structure rather than storing them explicitly. This means that arctic generally accepts borrowed keys (like &[u8]) when inserting, but needs to reconstruct keys when scanning. However, if the key type itself is borrowed and outlives the map, we'd like to return them directly at their original lifetime rather than reconstructing.
This Key::Insert<'k> associated type is the only way I've figured out how to encode that (a) insertion for owned keys accepts any lifetime for<'a> 'a, while insertion for borrowed keys &'k [u8] only accepts lifetime outliving 'k, while (b) reads for both owned and borrowed keys accept any lifetime for<'a> 'a. But it requires some awkward internal conversion methods to propagate the lifetime between associated types. I think what I was looking for is some notion of a shortest lifetime, such that I could have trait Key<'k>, impl Key<'shortest> for Vec<u8> and impl<'k> Key<'k> for &'k [u8], and have insert take an &'k Key::Borrowed. We're almost there with impl<'a> Key for Vec<u8>, but I think there's no way for the caller to write the type Map<for<'a>: 'a, Vec<u8>, V>, and Map<'static, Vec<u8>, V> is too restrictive.
Finally, I haven't figured out a good way to support user-defined key types.
Pointer provenance
First, arctic assumes pointers are at most 8 bytes, and that we can pack 8B of metadata and an 8B pointer into an AtomicU128. I believe this prevents us from using AtomicPtr, and is fundamentally incompatible with the strict provenance API (because pointers may have arbitrarily sized metadata)?.
Second, slice keys are fine provenance-wise during insertion, as we take subslices. But efficiently reconstructing slice keys of any length requires subtracting the slice length from a pointer near the end of the slice, which is probably a provenance violation? We can't store a pointer to the start of the key + offset + length because we have a limited number of bits to work with[4]. The slices are constrained by the type system (above) to be immutable and outlive the map.
Conclusion
Thanks all for your time 
I've learned a lot from the Rust community and hope somebody finds this work useful. Feel free to ask questions (here or via email), and let me know if you have a use case but require a particular feature--there's a lot on my wishlist.
Throughput is better for integer keys due to (a) denser tree structure and (b) integer-specific prefix matching optimizations; string key performance is dominated by cache misses. Scalability is good for all keys. Scan performance is worse than B+-trees because we do not have sibling pointers and must keep an explicit traversal stack. ↩︎
Scans do satisfy some weaker properties: keys within bounds are seen exactly once in lexicographical order, and all keys within bounds that were inserted before the scan starts, and not removed before the scan ends, will be seen. ↩︎
Does not support arbitrary comparison functions on keys. ↩︎
TODO: handle 57-bit address spaces ↩︎