Introduction Wormhole4j is a Java implementation of the Wormhole index, an ordered in-memory data structure from the EuroSys '19 paper, "Wormhole: A Fast Ordered Index for In-memory Data." By using the strengths of hash tables, prefix trees, and B+ trees, it achieves a worst-case lookup complexity of O(log L) , where L is the length of the key. This makes it very fast for both point lookups and range scans. While earlier versions of the library were fast, they only worked in single-threaded environments. Most high-performance systems today need thread safety and concurrency. Version 0.3.0 fixes this. This post describes how we designed the concurrency model, how we verified it, and what the benchmarks show. Why Concurrent Ordered Indexes Are Hard Designing a concurrent ordered index is much harder than a concurrent hash map. In a hash map, keys are independent. In an ordered index, keys are linked in a specific sequence to allow range scans.…