Arctic: A Practical Lock-Free Adaptive Radix Tree
Talkat 20th USENIX Symposium on Operating Systems Design and Implementation (OSDI '26) · 2026-07-13..07-15·
summary
Arctic is a lock‑free adaptive radix tree that uses a freezing‑based coordination protocol and edge‑in‑parent layout to perform compress/replace operations with a single 16‑byte CAS, plus a novel hazard keys SMR that reclaims nodes by comparing prefixes to published operation keys. Evaluation on 80 cores with YCSB shows 1.2×–2.8× throughput over the next best index, stable scaling past 80 threads, memory reclamation effective up to Zipf 0.99, and end‑to‑end gains when plugged into RocksDB and Turso (up to 40% and 12%).
AI-written summary · about
chapters (14)
- 0:00Arctic introduction
- 1:04Concurrent index importance
- 2:51Lock freedom vs performance
- 3:36Prefix tree primer
- 5:22Edge compression
- 6:45Node compression
- 8:10Concurrency design impact
- 9:34Memory reclamation challenges
- 11:01Hazard keys for SMR
- 13:13Evaluation setup
- 14:40Read-heavy YCSBA
- 15:01Read-only and scan results
- 15:21Memory usage efficiency
- 16:23Conclusion
related talks
12mROART: Range-query Optimized Persistent ART
20mRRR-SMR: Reduce, Reuse, Recycle: Better Methods for Practical Lock-Free Data Structures
17mA New Radix-Tree Based Memory Storage Engine
01h 13mC++ Memory Model Meets High-Update-Rate Data Structures
50mPostgreSQL meets ART - Using Adaptive Radix Tree to speed up vacuuming
56m“High-Radix Concurrent C++”
29mAccelerating Performance: Mastering RocksDB for High Speed Data Processing
15m"Range as a Key" is the Key! Fast and Compact Cloud Block Store Index with RASK