Fast scans on key-value stores
Authors:
Open Access
- 1 August 2017
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 10 (11) , 1526-1537
Abstract
Key-Value Stores (KVS) are becoming increasingly popular because they scale up and down elastically, sustain high throughputs for get/put workloads and have low latencies. KVS owe these advantages to their simplicity. This simplicity, however, comes at a cost: It is expensive to process complex, analytical queries on top of a KVS because today's generation of KVS does not support an efficient way to scan the data. The problem is that there are conflicting goals when designing a KVS for analytical queries and for simple get/put workloads: Analytical queries require high locality and a compact representation of data whereas elastic get/put workloads require sparse indexes. This paper shows that it is possible to have it all, with reasonable compromises. We studied the KVS design space and built TellStore, a distributed KVS, that performs almost as well as state-of-the-art KVS for get/put workloads and orders of magnitude better for analytical and mixed workloads. This paper presents the results of comprehensive experiments with an extended version of the YCSB benchmark and a workload from the telecommunication industry.Keywords
This publication has 29 references indexed in Scilit:
- SAP HANA databaseACM SIGMOD Record, 2012
- The case for RAMCloudCommunications of the ACM, 2011
- CassandraACM SIGOPS Operating Systems Review, 2010
- SIMD-scanProceedings of the VLDB Endowment, 2009
- Column-oriented database systemsProceedings of the VLDB Endowment, 2009
- Main-memory scan sharing for multi-core CPUsProceedings of the VLDB Endowment, 2008
- Non-blocking Hashtables with Open Addressing2005
- The log-structured merge-tree (LSM-tree)Acta Informatica, 1996
- A critique of ANSI SQL isolation levelsACM SIGMOD Record, 1995
- The design and implementation of a log-structured file systemACM Transactions on Computer Systems, 1992