Source-linked AI summary
Wormhole: A Fast Ordered Index for In-memory Data Management
Xingbo Wu, Fan Ni, Song Jiang
TL;DR
In-memory systems need ordered indexes for range operations, but conventional ordered indexes incur lookup costs tied to the number of keys. Wormhole combines trie, hash-table, and B+ tree techniques to achieve O(logL) lookup while retaining comparable space efficiency, and it substantially outperforms several representative indexes.
Problem
Ordered indexes support range operations but have O(logN) lookup cost, making access expensive for indexes containing billions of keys.
Method
Wormhole combines a trie, hash table, and B+ tree to make ordered-index lookup cost O(logL) while supporting common index operations.
Results
Wormhole improves key lookup throughput by up to 8.4× over skip list, 4.9× over B+ tree, 4.3× over ART, and 6.6× over Masstree.
Takeaways & Limitations
Wormhole provides quick ordered access for very-large-scale key-value stores while maintaining performance for insertion, deletion, and range queries that is higher than or comparable to other indexes.
Takeaways & Limitations
The composite trie-based design can still require O(L) search time in the worst case before the hash-table technique reduces the cost to O(logL).
Abstract
from arXiv · showhide
In-memory data management systems, such as key-value stores, have become an essential infrastructure in today's big-data processing and cloud computing. They rely on efficient index structures to access data. While unordered indexes, such as hash tables, can perform point search with O(1) time, they cannot be used in many scenarios where range queries must be supported. Many ordered indexes, such as B+ tree and skip list, have a O(log N) lookup cost, where N is number of keys in an index. For an ordered index hosting billions of keys, it may take more than 30 key-comparisons in a lookup, which is an order of magnitude more expensive than that on a hash table. With availability of large memory and fast network in today's data centers, this O(log N) time is taking a heavy toll on applications that rely on ordered indexes. In this paper we introduce a new ordered index structure, named Wormhole, that takes O(log L) worst-case time for looking up a key with a length of L. The low cost is achieved by simultaneously leveraging strengths of three indexing structures, namely hash table, prefix tree, and B+ tree, to orchestrate a single fast ordered index. Wormhole's range operations can be performed by a linear scan of a list after an initial lookup. This improvement of access efficiency does not come at a price of compromised space efficiency. Instead, Wormhole's index space is comparable to those of B+ tree and skip list. Experiment results show that Wormhole outperforms skip list, B+ tree, ART, and Masstree by up to 8.4x, 4.9x, 4.3x, and 6.6x in terms of key lookup throughput, respectively.
1 Introduction
In-memory systems make index operations a major cost, while ordered indexes sacrifice hash-table lookup speed to support range queries. Wormhole combines trie, hash-table, and B+ tree strengths to provide faster ordered access without compromising space efficiency.
- Motivation: 14–94% of query execution time in today’s in-memory databases is reportedly consumed by index operations.Removing expensive I/O from the critical path makes index efficiency a major system concern.
- Motivation: Ordered indexes support range operations but require O(logN) key comparisons, reaching about 30 or more comparisons for billions of keys.Large index footprints can also increase working-set size and reduce CPU-cache effectiveness.
- Motivation: Tries make search cost depend on key length L rather than index size N, enabling faster lookup for workloads with short keys.For 4-byte integer keys represented as four byte tokens, search cost is bounded by four.
- Contribution: Wormhole supports lookup, insertion, deletion, and range queries with O(logL) memory accesses, while using space comparable to a B+ tree and often less than a trie.With reasonably bounded keys such as 1000 bytes, its lookup cost can be considered O(1).
- Method: Wormhole combines B+ tree space efficiency, trie search independent of store size, and hash-table O(1) search to construct one ordered index.It replaces the non-leaf B+ tree section with a trie and uses a hash table to reduce trie lookup to O(logL).
- Evaluation: Wormhole improves key lookup throughput by up to 8.4× over skip list, 4.9× over B+ tree, 4.3× over ART, and 6.6× over Masstree.When range queries are unnecessary, its point-lookup throughput reaches 30–92% of a highly optimized Cuckoo hash table.
2 The Wormhole Data Structure
Wormhole evolves a B+ tree by replacing its MetaTree with a trie and then accelerating trie navigation with a hash table. The resulting LeafList–MetaTrieHT structure supports ordered operations with O(logL) lookup cost while retaining comparable space efficiency.
- Background: Lookup in the B+ Tree: B+ tree lookup cost is dominated by its MetaTree, which grows as O(logN) with the number of indexed keys.Search within a bounded-size leaf takes O(1), so the MetaTree determines the major search cost.
- Background: Lookup in the B+ Tree: Replacing the MetaTree with a hash table gives O(1) search but cannot preserve sorted insertion or support range queries with absent boundary keys.Examples include searching between “Brown” and “John” or for keys with prefix “J”.
- Replacing the MetaTree with a Trie: MetaTrie replaces the MetaTree while using anchor keys to map LeafList nodes and preserve ordered navigation between adjacent leaves.Anchor keys satisfy ordering and prefix conditions; the prefix condition ensures each anchor corresponds to a leaf node.
- Replacing the MetaTree with a Trie: The composite LeafList–MetaTrie design is more space-efficient than a conventional trie, but its worst-case lookup remains O(L) for long search keys.Multiple keys occupy each leaf node, and anchors are usually shorter than the keys they index.
- Accelerating Search with a Hash Table: Hashing all anchor prefixes enables binary search for the longest matching prefix in O(log(min(Lanc,Lkey))) time.MetaTrieHT stores trie nodes as hash items, while bitmaps locate siblings of unmatched tokens in O(1) during the second search phase.
- Accelerating Search with a Hash Table: Wormhole’s LeafList and MetaTrieHT support lookup, insertion, deletion, and range search with O(logL) lookup cost and space comparable to a B+ tree.Wormhole has the same number of leaf nodes as a B+ tree, while its internal-node space determines their relative cost; concurrency uses leaf locks plus a MetaTrieHT mutex.
3 Optimization and Enhancement
Wormhole optimizes MetaTrieHT and leaf-node operations to reduce hashing, memory accesses, comparisons, and insertion overhead while preserving correctness for arbitrary key tokens.
- MetaTrieHT optimizations: Incremental hashing reduces the hashing cost of prefixes by reusing previously computed values for extended strings.The implementation uses CRC-32c, while the optimized hashing cost is described as comparable to a hash-table lookup.
- MetaTrieHT optimizations: Eight prefix entries fit in a 64-byte hash slot, each storing a 16-bit tag and a 48-bit pointer to the original prefix.This layout targets cache misses caused by pointer dereferences and comparisons involving long prefixes.
- MetaTrieHT optimizations: Tag-only matching usually avoids full prefix comparisons, with a final comparison detecting false positives and restarting the search when necessary.For 16-bit tags and 1024-byte keys, the reported error probability is 0.0153%.
- Leaf-node optimizations: Leaf nodes use compact tag arrays so searches compare tags first and read original keys only after a tag match.The tags are stored in ascending hash order, reducing memory references during key search.
- Leaf-node optimizations: Newly inserted keys can be appended unsorted and batch-sorted later when a range search or node split reaches the leaf.Delayed sorting amortizes the cost of ordered insertions across multiple appended keys.
- Arbitrary key tokens: Fat leaf nodes preserve correctness when no valid split anchor exists, and are expected to have virtually no impact on real datasets.With maximal node size N, the case requires at least N + 1 keys sharing a prefix and differing in trailing zeroes; N is suggested as 64 or 128.
4 Evaluation
Experiments compare Wormhole with representative ordered indexes across lookup, networked, mixed-operation, insertion, range, memory, and key-structure workloads. Wormhole generally leads on lookup throughput, while its advantage narrows for range scans and longer keys or anchors.
- Lookup performance: Wormhole’s 16-thread lookup throughput reaches 19.5 MOPS, 43% higher than ART, while all five indexes scale well.With one thread, Wormhole achieves 1.266 MOPS, 52% above ART’s 0.834 MOPS; its thread-unsafe variant reaches 21.2 MOPS.
- Lookup performance: 1.3× to 4.2×: Wormhole improves lookup throughput over the best competing index across eight keysets.Masstree and ART vary more with key length, whereas Wormhole is governed by log(min(Lanc,Lkey)).
- Lookup performance: At least 1.7×: Wormhole outperforms competing indexes on URL keys despite their approximately 40-byte average anchors.Long common prefixes increase Wormhole’s anchor lengths, but do not eliminate its throughput advantage in this workload.
- Comparing with hash tables: 31% to 67%: Wormhole’s throughput is about this fraction of the hash table’s on the first seven keysets, while it approaches the hash table on K10.K10’s 1 KB keys make full key accesses dominate both indexes, producing similar throughput.
- Comparing with hash tables: 78% to 40%: with 512-byte keys, long anchors reduce Wormhole’s throughput relative to the hash table as anchor-trie accesses increase.For 512-byte keys, the MetaTrieHT’s longest-prefix matching can require log2 512 = 9 memory accesses.
- Performance of other operations: 1.05× to 1.59×: Wormhole’s range-query improvement over B+ tree is smaller because sequential scanning dominates after the initial lookup.Masstree performs much worse on ranges because scanning its trie requires frequent pointer chasing.
5 Related Work
Prior work improves ordered-index performance through concurrency and caching, while trie-based designs reduce dependence on index size but face space or access-cost trade-offs. Wormhole combines related techniques and also targets workloads with little locality and write operations.
- Comparison-based indexes: Comparison-based indexes such as B-trees and skip lists remain common, but their O(logN) lookup cost motivates parallelism and caching optimizations.Examples include latch-free B+ tree operations in Bwtree.
- Trie-based indexes: ART reduces trie space adaptively, whereas Masstree increases fanout with B+ trees at trie nodes, creating different lookup-cost trade-offs.Masstree reduces trie height but may make node access slow because a node can require a large B+ tree.
- Caching and writes: Caching improves lookup for workloads with strong locality but is ineffective for cold data, where Wormhole instead reduces DRAM accesses through its index structure.Wormhole also supports consistently low-cost writes through fast leaf identification and hashed-key sorting.
- Caching and writes: Buffered designs such as Bε-Tree and FloDB reduce write costs but add lookup or range-query overheads that Wormhole avoids through low-cost lookup.FloDB must fully flush its hash table before serving a range operation, potentially imposing long delays.
- Concurrency: Wormhole uses fine-grained locking, RCU, and version numbers for thread safety, while leaving potentially more efficient concurrency control for future work.Its thread-safe version is only slightly slower than the thread-unsafe version.
6 Conclusion
Wormhole is presented as an ordered key-value index with O(logL) lookup cost, improving access for large indexes while retaining broad operation and space efficiency. Extensive evaluation reports higher or comparable performance across operations and lookup-throughput gains over several alternatives.
- Conclusion: Wormhole achieves O(logL) lookup cost, improving asymptotically over the O(logN) or O(L) costs of other ordered indexes when L is much smaller than N.The paper identifies this as the first ordered key-value index with the O(logL) lookup cost.
- Conclusion: Lookup throughput improves by up to 8.4×, 4.9×, 4.3×, and 6.6× versus skip list, B+ tree, ART, and Masstree, respectively.These are reported key lookup throughput comparisons.
- Conclusion: Insertion, deletion, and range-query performance is higher than or comparable to that of other indexes.The conclusion reports this across the listed additional operations.
- Conclusion: Wormhole’s space demand is as low as that of a B+ tree.The conclusion presents this as a space-efficiency result alongside the operation-performance findings.