Wormhole: A Fast Ordered Index for In-memory Data Management
Wormhole: A Fast Ordered Index for In-memory Data Management
复制标题
Wormhole：用于内存数据管理的快速有序索引
DOI：
10.1145/3302424.3303955
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Jiang, Song
中科院分区：
文献类型：
--
作者：
Wu, Xingbo;Ni, Fan;Jiang, Song
内存中的数据管理系统，如键值存储，已经成为当今大数据处理和云计算中必不可少的基础设施。它们依赖于高效的索引结构来访问数据。虽然无序索引（如哈希表）可以在O（1）时间内执行点搜索，但它们不能用于必须支持范围查询的许多场景。许多有序索引，如B+树和跳表，具有O（log N）的查找成本，其中N是索引中的键数。对于托管数十亿个键的有序索引，在查找中可能需要超过30个键比较，这比哈希表上的要昂贵一个数量级。在当今数据中心的大内存和快速网络的可用性，这O（log N）的时间是一个沉重的负担依赖于有序索引的应用程序在本文中，我们介绍了一种新的有序索引结构，命名为Wormhole，需要O（log L）的最坏情况下的时间来查找一个关键字长度为L。低成本是通过同时利用三种索引结构，即哈希表，前缀树，和B+树的优势，编排一个快速有序的索引。虫洞的范围操作可以通过在初始查找之后对列表进行线性扫描来执行。这种访问效率的提高并不以牺牲空间效率为代价。相反，Wormhole的索引空间与B+树和跳跃列表的索引空间相当。实验结果表明，Wormhole算法的密钥查找吞吐量分别是跳表、B+树、ART和Masstree算法的8.4倍、4.9倍、4.3倍和6.6倍。
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.