Arctic: A Practical Lock-Free Adaptive Radix Tree

Indexing data structures are vital to the modern systems ecosystem, but there are no indexes that offer high performance, lock freedom, and range scans. Arctic is a lock-free adaptive radix tree that achieves all three: Arctic outcompetes lock-based indexes, including a concurrent hash map, on many YCSB configurations, guarantees non-blocking operation through careful metadata layout and an (eponymous) freezing-based coordination protocol, and offers non-linearizable range and prefix scans. Arctic also contributes a novel safe memory reclamation scheme that uses operation keys to approximate reachable pointers. We integrate Arctic into RocksDB and Turso, improving throughput up to 40% and 12% on their write-heavy benchmarks relative to their default skiplist indexes.