More Web Proxy on the site http://driver.im/

research-article

Public Access

Wormhole: A Fast Ordered Index for In-memory Data Management

Authors:

Song JiangAuthors Info & Claims

EuroSys '19: Proceedings of the Fourteenth EuroSys Conference 2019

Article No.: 18, Pages 1 - 16

https://doi.org/10.1145/3302424.3303955

Published: 25 March 2019 Publication History

Abstract

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.

References

[1]

Berk Atikoglu, Yuehai Xu, Eitan Frachtenberg, Song Jiang, and Mike Paleczny. 2012. Workload Analysis of a Large-scale Key-value Store. In Proceedings of the 12th ACM SIGMETRICS/PERFORMANCE Joint International Conference on Measurement and Modeling of Computer Systems (SIGMETRICS '12). ACM, New York, NY, USA, 53--64.

Digital Library

[2]

Oana Balmau, Rachid Guerraoui, Vasileios Trigonakis, and Igor Zablotchi. 2017. FloDB: Unlocking Memory in Persistent Key-Value Stores. In Proceedings of the Twelfth European Conference on Computer Systems (EuroSys '17). ACM, New York, NY, USA, 80--94.

Digital Library

[3]

Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, and Bradley C. Kuszmaul. 2005. Concurrent Cache-oblivious B-trees. In Proceedings of the Seventeenth Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '05). ACM, New York, NY, USA, 228--237.

Digital Library

[4]

Timo Bingmann. 2013. STX B+ Tree C++ Template Classes. https://panthema.net/2007/stx-btree/.

[5]

Anastasia Braginsky and Erez Petrank. 2012. A Lockfree B+Tree. In Proceedings of the Twenty-fourth Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '12). ACM, New York, NY, USA, 58--67.

Digital Library

[6]

Alex D. Breslow, Dong Ping Zhang, Joseph L. Greathouse, Nuwan Jayasena, and Dean M. Tullsen. 2016. Horton Tables: Fast Hash Tables for In-memory Data-intensive Computing. In Proceedings of the 2016 USENIX Conference on Usenix Annual Technical Conference (USENIX ATC '16). USENIX Association, Berkeley, CA, USA, 281--294. http://dl.acm.org/citation.cfm?id=3026959.3026986

Digital Library

[7]

Gerth Stolting Brodal and Rolf Fagerberg. 2003. Lower Bounds for External Memory Dictionaries. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '03). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 546--554.

Digital Library

[8]

Douglas Comer. 1979. Ubiquitous B-Tree. ACM Comput. Surv. 11, 2 (June 1979), 121--137.

Digital Library

[9]

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms, Third Edition (3rd ed.). The MIT Press.

Digital Library

[10]

Bin Fan, David G. Andersen, and Michael Kaminsky. 2013. MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing. In Proceedings of the 10th USENIX Conference on Networked Systems Design and Implementation (NSDI'13). USENIX Association, Berkeley, CA, USA, 371--384.

Digital Library

[11]

Mikhail Fomitchev and Eric Ruppert. 2004. Lockfree Linked Lists and Skip Lists. In Proceedings of the Twenty-third Annual ACM Symposium on Principles of Distributed Computing (PODC '04). ACM, New York, NY, USA, 50--59.

Digital Library

[12]

Bingsheng He and Jeffrey Xu Yu. 2011. High-throughput Transaction Executions on Graphics Processors. Proc. VLDB Endow. 4, 5 (Feb. 2011), 314--325.

Digital Library

[13]

Max Heimel, Michael Saecker, Holger Pirk, Stefan Manegold, and Volker Markl. 2013. Hardware-oblivious Parallelism for In-memory Column-stores. Proc. VLDB Endow. 6, 9 (July 2013), 709--720.

Digital Library

[14]

Danny Hendler, Itai Incze, Nir Shavit, and Moran Tzafrir. 2010. Flat Combining and the Synchronization-parallelism Tradeoff. In Proceedings of the Twenty-second Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '10). ACM, New York, NY, USA, 355--364.

Digital Library

[15]

Maurice Herlihy and J. Eliot B. Moss. 1993. Transactional Memory: Architectural Support for Lockfree Data Structures. In Proceedings of the 20th Annual International Symposium on Computer Architecture (ISCA '93). ACM, New York, NY, USA, 289--300.

Digital Library

[16]

Changkyu Kim, Jatin Chhugani, Nadathur Satish, Eric Sedlar, Anthony D. Nguyen, Tim Kaldewey, Victor W. Lee, Scott A. Brandt, and Pradeep Dubey. 2010. FAST: Fast Architecture Sensitive Tree Search on Modern CPUs and GPUs. In Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data (SIGMOD '10). ACM, New York, NY, USA, 339--350.

Digital Library

[17]

Onur Kocberber, Boris Grot, Javier Picorel, Babak Falsafi, Kevin Lim, and Parthasarathy Ranganathan. 2013. Meet the Walkers: Accelerating Index Traversals for In-memory Databases. In Proceedings of the 46th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO-46). ACM, New York, NY, USA, 468--479.

Digital Library

[18]

Viktor Leis, Alfons Kemper, and Thomas Neumann. 2013. The Adaptive Radix Tree: ARTful Indexing for Main-memory Databases. In Proceedings of the 2013 IEEE International Conference on Data Engineering (ICDE 2013) (ICDE '13). IEEE Computer Society, Washington, DC, USA, 38--49.

Digital Library

[19]

Justin J. Levandoski, David B. Lomet, and Sudipta Sengupta. 2013. The Bw-Tree: A B-tree for New Hardware Platforms. In Proceedings of the 2013 IEEE International Conference on Data Engineering (ICDE 2013) (ICDE '13). IEEE Computer Society, Washington, DC, USA, 302--313.

Digital Library

[20]

Leveldb 2018. LevelDB: A Fast and Lightweight Key/Value Database Library by Google. https://github.com/google/leveldb.

[21]

Sheng Li, Hyeontaek Lim, Victor W. Lee, Jung Ho Ahn, Anuj Kalia, Michael Kaminsky, David G. Andersen, Seongil O, Sukhan Lee, and Pradeep Dubey. 2016. Full-Stack Architecting to Achieve a Billion-Requests-Per-Second Throughput on a Single Key-Value Store Server Platform. ACM Trans. Comput. Syst. 34, 2, Article 5 (April 2016), 30 pages.

Digital Library

[22]

Xiaozhou Li, David G Andersen, Michael Kaminsky, and Michael J Freedman. 2014. Algorithmic improvements for fast concurrent cuckoo hashing. In Proceedings of the Ninth European Conference on Computer Systems. ACM, 27.

Digital Library

[23]

libart 2018. A C99 implementation of the Adaptive Radix Tree. https://github.com/armon/libart.

[24]

libcuckoo 2018. A high-performance, concurrent hash table. https://github.com/efficient/libcuckoo.

[25]

lmdb 2017. Symas Lightning Memory-mapped Database. http://www.lmdb.tech/doc/.

[26]

Yandong Mao, Eddie Kohler, and Robert Tappan Morris. 2012. Cache Craftiness for Fast Multicore Key-value Storage. In Proceedings of the 7th ACM European Conference on Computer Systems (EuroSys '12). ACM, New York, NY, USA, 183--196.

Digital Library

[27]

Masstree 2018. Beta release of Masstree. https://github.com/kohler/masstree-beta.

[28]

Julian McAuley and Alex Yang. 2016. Addressing Complex and Subjective Product-Related Queries with Customer Reviews. In Proceedings of the 25th International Conference on World Wide Web (WWW '16). International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, Switzerland, 625--635.

Digital Library

[29]

Paul E McKenney, Silas Boyd-Wickizer, and Jonathan Walpole. 2013. RCU usage in the Linux kernel: one decade later. (2013).

[30]

Paul E. Mckenney and John D. Slingwine. 1998. Read-Copy Update: Using Execution History to Solve Concurrency Problems. In Parallel and Distributed Computing and Systems. Las Vegas, NV, 509--518.

[31]

Meme9 2009. 96 million memes from Memetracker. https://snap.stanford.edu/data/memetracker9.html.

[32]

MemSQL 2017. MemSQL. http://www.memsql.com/.

[33]

MongoDB 2017. MongoDB for GIANT Ideas. https://mongodb.com/.

[34]

Aravind Natarajan and Neeraj Mittal. 2014. Fast Concurrent Lockfree Binary Search Trees. In Proceedings of the 19th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP '14). ACM, New York, NY, USA, 317--328.

Digital Library

[35]

Rajesh Nishtala, Hans Fugal, Steven Grimm, Marc Kwiatkowski, Herman Lee, Harry C Li, Ryan McElroy, Mike Paleczny, Daniel Peek, Paul Saab, David Stafford, Tony Tung, and Venkateshwaran Venkataramani. 2013. Scaling Memcache at Facebook. In Presented as part of the 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13). USENIX, Lombard, IL, 385--398.

Digital Library

[36]

William Wesley Peterson and Daniel T Brown. 1961. Cyclic codes for error detection. Proceedings of the IRE 49, 1 (1961), 228--235.

[37]

William Pugh. 1990. Skip Lists: A Probabilistic Alternative to Balanced Trees. Commun. ACM 33, 6 (June 1990), 668--676.

Digital Library

[38]

RDMABENCH 2016. RDMA-bench. https://github.com/efficient/rdma_bench.

[39]

Redis 2017. Redis. http://redis.io/.

[40]

Sepideh Roghanchi, Jakob Eriksson, and Nilanjana Basu. 2017. Ffwd: Delegation is (Much) Faster Than You Think. In Proceedings of the 26th Symposium on Operating Systems Principles (SOSP '17). ACM, New York, NY, USA, 342--358.

Digital Library

[41]

Amirhesam Shahvarani and Hans-Arno Jacobsen. 2016. A Hybrid B+-tree As Solution for In-Memory Indexing on CPU-GPU Heterogeneous Computing Platforms. In Proceedings of the 2016 International Conference on Management of Data (SIGMOD '16). ACM, New York, NY, USA, 1523--1538.

Digital Library

[42]

Nir Shavit and Dan Touitou. 1995. Software Transactional Memory. In Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing (PODC '95). ACM, New York, NY, USA, 204--213.

Digital Library

[43]

SQLite 2017. In-Memory Databases - SQLite. https://sqlite.org/inmemorydb.html.

[44]

urcu 2013. Userspace RCU. https://lwn.net/Articles/573424/.

[45]

Marcel Waldvogel, George Varghese, Jon Turner, and Bernhard Plattner. 1997. Scalable High Speed IP Routing Lookups. In Proceedings of the ACM SIGCOMM '97 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communication (SIGCOMM '97). ACM, New York, NY, USA, 25--36.

Digital Library

[46]

Xingbo Wu, Fan Ni, and Song Jiang. 2017. Search Lookaside Buffer: Efficient Caching for Index Data Structures. In Proceedings of the 2017 Symposium on Cloud Computing (SoCC '17). ACM, New York, NY, USA, 27--39.

Digital Library

[47]

xxHash 2017. xxHash. http://github.com/Cyan4973/xxHash/.

[48]

Kai Zhang, Kaibo Wang, Yuan Yuan, Lei Guo, Rubao Lee, and Xiaodong Zhang. 2015. Mega-KV: A Case for GPUs to Maximize the Throughput of In-memory Key-value Stores. Proc. VLDB Endow. 8, 11 (July 2015), 1226--1237.

Digital Library

Cited By

Kim MHwang JHeo GCho SMahajan DPark J(2024)Accelerating String-Key Learned Index Structures via Memoization-Based Incremental TrainingProceedings of the VLDB Endowment10.14778/3659437.365943917:8(1802-1815)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.14778/3659437.3659439
Zhou WYang S(2024)SLIPP: A Space-Efficient Learned Index for String KeysProceedings of the 2024 6th International Conference on Big-data Service and Intelligent Computation10.1145/3686540.3686550(69-77)Online publication date: 29-May-2024
https://dl.acm.org/doi/10.1145/3686540.3686550
Zhang SQi JYao XBrinkmann A(2024)Hyper: A High-Performance and Memory-Efficient Learned Index via Hybrid ConstructionProceedings of the ACM on Management of Data10.1145/36549482:3(1-26)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654948
Show More Cited By

Recommendations

Wormhole cut-through switching: Flit-level messages interleaving for virtual-channelless network-on-chip

A VLSI microrchitecture of a network-on-chip (NoC) router with a wormhole cut-through switching method is presented in this paper. The main feature of the NoC router is that, the wormhole messages can be interleaved (cut-through) at flit-level in the ...
Performance Evaluation of Switch-Based Wormhole Networks

Multistage interconnection networks (MINs) are a popular class of switch-based network architectures for constructing scalable parallel computers. Four wormhole MINs built from k k switches, where k = 2j for some j, are considered in this paper: ...
The hyperdyadic index and generalized indexing and query with PIQUE
SSDBM '15: Proceedings of the 27th International Conference on Scientific and Statistical Database Management

Many scientists rely on indexing and query to identify trends and anomalies within extreme-scale scientific data. Compressed bitmap indexing (e.g., FastBit) is the go-to indexing method for many scientific datasets and query workloads. Recently, the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EuroSys '19: Proceedings of the Fourteenth EuroSys Conference 2019

March 2019

714 pages

ISBN:9781450362818

DOI:10.1145/3302424

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 March 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article
Research
Refereed limited

Funding Sources

National Science Foundation

Conference

EuroSys '19

Sponsor:

SIGOPS

EuroSys '19: Fourteenth EuroSys Conference 2019

March 25 - 28, 2019

Dresden, Germany

Acceptance Rates

Overall Acceptance Rate 241 of 1,308 submissions, 18%

Upcoming Conference

EuroSys '25

Sponsor:
sigops

Twentieth European Conference on Computer Systems

March 30 - April 3, 2025

Rotterdam , Netherlands

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
1,221
Total Downloads

Downloads (Last 12 months)234
Downloads (Last 6 weeks)38

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kim MHwang JHeo GCho SMahajan DPark J(2024)Accelerating String-Key Learned Index Structures via Memoization-Based Incremental TrainingProceedings of the VLDB Endowment10.14778/3659437.365943917:8(1802-1815)Online publication date: 1-Apr-2024
https://dl.acm.org/doi/10.14778/3659437.3659439
Zhou WYang S(2024)SLIPP: A Space-Efficient Learned Index for String KeysProceedings of the 2024 6th International Conference on Big-data Service and Intelligent Computation10.1145/3686540.3686550(69-77)Online publication date: 29-May-2024
https://dl.acm.org/doi/10.1145/3686540.3686550
Zhang SQi JYao XBrinkmann A(2024)Hyper: A High-Performance and Memory-Efficient Learned Index via Hybrid ConstructionProceedings of the ACM on Management of Data10.1145/36549482:3(1-26)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654948
Nguyen DBeringer LMansky WWang STimany ATraytel DPientka BBlazy S(2024)Compositional Verification of Concurrent C Programs with Search Structure TemplatesProceedings of the 13th ACM SIGPLAN International Conference on Certified Programs and Proofs10.1145/3636501.3636940(60-74)Online publication date: 9-Jan-2024
https://dl.acm.org/doi/10.1145/3636501.3636940
Li PHua YJia JZuo P(2024)A Fast Learned Key-Value Store for Concurrent and Distributed SystemsIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.3327009(1-14)Online publication date: 2024
https://doi.org/10.1109/TKDE.2023.3327009
Ramadhan AChoi MChung YChoi J(2023)An Empirical Study of Segmented Linear Regression Search in LevelDBElectronics10.3390/electronics1204101812:4(1018)Online publication date: 17-Feb-2023
https://doi.org/10.3390/electronics12041018
Sun ZZhou XLi G(2023)Learned Index: A Comprehensive Experimental EvaluationProceedings of the VLDB Endowment10.14778/3594512.359452816:8(1992-2004)Online publication date: 22-Jun-2023
https://dl.acm.org/doi/10.14778/3594512.3594528
Cha HHao XWang TZhang HAkella AYu X(2023)B-hash: An Adaptive Hybrid Index for In-Memory Time-Series DatabasesProceedings of the VLDB Endowment10.14778/3583140.358314316:6(1235-1248)Online publication date: 1-Feb-2023
https://dl.acm.org/doi/10.14778/3583140.3583143
Yang JYoon HYun GNoh SChoi YFedorova ANarayanan DDi Luna GQuerzoni L(2023)DyTIS: A Dynamic Dataset Targeted Index Structure Simultaneously Efficient for Search, Insert, and ScanProceedings of the Eighteenth European Conference on Computer Systems10.1145/3552326.3587434(800-816)Online publication date: 8-May-2023
https://dl.acm.org/doi/10.1145/3552326.3587434
Ge JShi BChai YLuo YGuo YHe YChai Y(2023)Cutting Learned Index into Pieces: An In-depth Inquiry into Updatable Learned Indexes2023 IEEE 39th International Conference on Data Engineering (ICDE)10.1109/ICDE55515.2023.00031(315-327)Online publication date: Apr-2023
https://doi.org/10.1109/ICDE55515.2023.00031
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents