research-article

FASTER: A Concurrent Key-Value Store with In-Place Updates

Authors:

Badrish Chandramouli,

Donald Kossmann,

Justin Levandoski,

Mike BarnettAuthors Info & Claims

SIGMOD '18: Proceedings of the 2018 International Conference on Management of Data

Pages 275 - 290

https://doi.org/10.1145/3183713.3196898

Published: 27 May 2018 Publication History

Abstract

Over the last decade, there has been a tremendous growth in data-intensive applications and services in the cloud. Data is created on a variety of edge sources, e.g., devices, browsers, and servers, and processed by cloud applications to gain insights or take decisions. Applications and services either work on collected data, or monitor and process data in real time. These applications are typically update intensive and involve a large amount of state beyond what can fit in main memory. However, they display significant temporal locality in their access pattern. This paper presents FASTER, a new key-value store for point read, blind update, and read-modify-write operations. FASTER combines a highly cache-optimized concurrent hash index with a hybrid log: a concurrent log-structured record store that spans main memory and storage, while supporting fast in-place updates of the hot set in memory. Experiments show that FASTER achieves orders-of-magnitude better throughput - up to 160M operations per second on a single machine - than alternative systems deployed widely today, and exceeds the performance of pure in-memory data structures when the workload fits in memory.

References

[1]

2017. jemalloc. http://jemalloc.net/. (2017). {Online; accessed 30-Oct-2017}.

[2]

Phil Bernstein, Sergey Bykov, Alan Geller, Gabriel Kliot, and Jorgen Thelin. 2014. Orleans: Distributed Virtual Actors for Programmability and Scalability. Technical Report. https://www.microsoft.com/en-us/research/publication/ orleans-distributed-virtual-actors-for-programmability-and-scalability/

[3]

Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes, and Robert E. Gruber. 2008. Bigtable: A Distributed Storage System for Structured Data. ACM Trans. Comput. Syst. 26, 2, Article 4 (June 2008), 26 pages.

Digital Library

[4]

Brian F. Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears. 2010. Benchmarking Cloud Serving Systems with YCSB. In Proceedings of the 1st ACM Symposium on Cloud Computing (SoCC '10). ACM, New York, NY, USA, 143--154.

Digital Library

[5]

Intel Corporation. 2017. Intel Threading Building Blocks. https://www. threadingbuildingblocks.org/. (2017). {Online; accessed 30-Oct-2017}.

[6]

Cristian Diaconu, Craig Freedman, Erik Ismert, Per-Ake Larson, Pravin Mittal, Ryan Stonecipher, Nitin Verma, and Mike Zwilling. 2013. Hekaton: SQL Server's Memory-optimized OLTP Engine. In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data (SIGMOD '13). ACM, New York, NY, USA, 1243--1254.

Digital Library

[7]

Aleksandar Dragojevic, Dushyanth Narayanan, Miguel Castro, and Orion Hodson. 2014. FaRM: Fast Remote Memory, In 11th USENIX Symposium on Networked Systems Design and Implementation (NSDI 2014). https://www.microsoft.com/ en-us/research/publication/farm-fast-remote-memory/

Digital Library

[8]

Facebook. 2017. RocksDB Performance Evaluation. https://github.com/facebook/ rocksdb/wiki/performance-benchmarks. (2017). {Online; accessed 30-Oct-2017}.

[9]

Facebook. 2017. RocksDB Wiki. https://github.com/facebook/rocksdb/wiki. (2017). {Online; accessed 30-Oct-2017}.

[10]

Bin Fan, David G. Andersen, and Michael Kaminsky. 2013. MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing. In Presented as part of the 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI 13). USENIX, Lombard, IL, 371--384. https://www. usenix.org/conference/nsdi13/technical-sessions/presentation/fan

Digital Library

[11]

Apache Software Foundation. 2017. Apache Cassandra. http://cassandra.apache. org/. (2017). {Online; accessed 30-Oct-2017}.

[12]

Apache Software Foundation. 2017. Apache Flink. https://flink.apache.org/. (2017). {Online; accessed 30-Oct-2017}.

[13]

Apache Software Foundation. 2017. Apache Hadoop. http://hadoop.apache.org/. (2017). {Online; accessed 30-Oct-2017}.

[14]

Apache Software Foundation. 2017. Spark State Store: A new framework for state management for computing Streaming Aggregates. https://issues.apache. org/jira/browse/SPARK-13809. (2017). {Online; accessed 30-Oct-2017}.

[15]

Apache Software Foundation. 2017. Trident State Store. http://storm.apache.org/ releases/current/Trident-state.html. (2017). {Online; accessed 30-Oct-2017}.

[16]

Keir Fraser. 2004. Practical Lock-Freedom. Technical Report.

[17]

Google. 2017. Google Cloud Dataflow. https://cloud.google.com/dataflow/. (2017). {Online; accessed 30-Oct-2017}.

[18]

Jim Gray and Goetz Graefe. 1997. The Five-minute Rule Ten Years Later, and Other Computer Storage Rules of Thumb. SIGMOD Rec. 26, 4 (Dec. 1997), 63--68.

Digital Library

[19]

Timothy L. Harris, Keir Fraser, and Ian A. Pratt. 2002. A Practical Multi-Word Compare-and-Swap Operation. In In Proceedings of the 16th International Symposium on Distributed Computing. Springer-Verlag, 265--279.

Digital Library

[20]

Maurice Herlihy, Victor Luchangco, and Mark Moir. 2002. The Repeat Offender Problem: A Mechanism for Supporting Dynamic-Sized, Lock-Free Data Structures. In Proceedings of the 16th International Conference on Distributed Computing (DISC '02). Springer-Verlag, London, UK, UK, 339--353. http://dl.acm.org/citation.cfm? id=645959.676129

Digital Library

[21]

Robert Kallman, Hideaki Kimura, Jonathan Natkins, Andrew Pavlo, Alexander Rasin, Stanley Zdonik, Evan P. C. Jones, Samuel Madden, Michael Stonebraker, Yang Zhang, John Hugg, and Daniel J. Abadi. 2008. H-store: A High-performance, Distributed Main Memory Transaction Processing System. Proc. VLDB Endow. 1, 2 (Aug. 2008), 1496--1499.

Digital Library

[22]

Kangnyeon Kim, Tianzheng Wang, Ryan Johnson, and Ippokratis Pandis. 2016. ERMIA: Fast Memory-Optimized Database System for Heterogeneous Workloads. In Proceedings of the 2016 International Conference on Management of Data (SIGMOD '16). ACM, New York, NY, USA, 1675--1687.

Digital Library

[23]

H. T. Kung and Philip L. Lehman. 1980. Concurrent Manipulation of Binary Search Trees. ACM Trans. Database Syst. 5, 3 (Sept. 1980), 354--382.

Digital Library

[24]

Justin Levandoski, David Lomet, and Sudipta Sengupta. 2013. LLAMA: A Cache/Storage Subsystem for Modern Hardware. Proc. VLDB Endow. 6, 10 (Aug. 2013), 877--888.

Digital Library

[25]

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

[26]

Justin J. Levandoski, David B. Lomet, Sudipta Sengupta, Ryan Stutsman, and Rui Wang. 2015. High Performance Transactions in Deuteronomy. In CIDR 2015, Seventh Biennial Conference on Innovative Data Systems Research, Asilomar, CA, USA, January 4--7, 2015, Online Proceedings. http://cidrdb.org/cidr2015/Papers/ CIDR15_Paper15.pdf

[27]

Hyeontaek Lim, Dongsu Han, David G. Andersen, and Michael Kaminsky. 2014. MICA: A Holistic Approach to Fast In-Memory Key-Value Storage. In 11th USENIX Symposium on Networked Systems Design and Implementation (NSDI 14). USENIX Association, Seattle, WA, 429--444. https://www.usenix.org/conference/nsdi14/ technical-sessions/presentation/lim

Digital Library

[28]

Lin Ma, Joy Arulraj, Sam Zhao, Andrew Pavlo, Subramanya R. Dulloor, Michael J. Giardino, Jeff Parkhurst, Jason L. Gardner, Kshitij Doshi, and Stanley Zdonik. 2016. Larger-than-memory Data Management on Modern Storage Hardware for In-memory OLTP Database Systems. In Proceedings of the 12th International Workshop on Data Management on New Hardware (DaMoN '16). ACM, New York, NY, USA, Article 9, 7 pages.

Digital Library

[29]

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

[30]

Memcached. 2017. https://memcached.org/. (2017). {Online; accessed 30-Oct2017}.

[31]

Maged M. Michael. 2002. Safe Memory Reclamation for Dynamic Lock-free Objects Using Atomic Reads and Writes. In Proceedings of the Twenty-first Annual Symposium on Principles of Distributed Computing (PODC '02). ACM, New York, NY, USA, 21--30.

Digital Library

[32]

C. Mohan, Don Haderle, Bruce Lindsay, Hamid Pirahesh, and Peter Schwarz. 1992. ARIES: A Transaction Recovery Method Supporting Fine-granularity Locking and Partial Rollbacks Using Write-ahead Logging. ACM Trans. Database Syst. 17, 1 (March 1992), 94--162.

Digital Library

[33]

Elizabeth J. O'Neil, Patrick E. O'Neil, and Gerhard Weikum. 1993. The LRU-K Page Replacement Algorithm for Database Disk Buffering. In Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data (SIGMOD '93). ACM, New York, NY, USA, 297--306.

Digital Library

[34]

Patrick O'Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O'Neil. 1996. The Log-structured Merge-tree (LSM-tree). Acta Inf. 33, 4 (June 1996), 351--385.

Digital Library

[35]

Diego Ongaro, Stephen M. Rumble, Ryan Stutsman, John Ousterhout, and Mendel Rosenblum. 2011. Fast Crash Recovery in RAMCloud. In Proceedings of the TwentyThird ACM Symposium on Operating Systems Principles (SOSP '11). ACM, New York, NY, USA, 29--41.

Digital Library

[36]

Redis. 2017. https://redis.io/. (2017). {Online; accessed 30-Oct-2017}.

[37]

Kun Ren, Thaddeus Diamond, Daniel J. Abadi, and Alexander Thomson. 2016. Low-Overhead Asynchronous Checkpointing in Main-Memory Database Systems. In Proceedings of the 2016 International Conference on Management of Data (SIGMOD '16). ACM, New York, NY, USA, 1539--1551.

Digital Library

[38]

Mendel Rosenblum and John K. Ousterhout. 1992. The Design and Implementation of a Log-structured File System. ACM Trans. Comput. Syst. 10, 1 (Feb. 1992), 26--52.

Digital Library

[39]

Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski. 2011. Conflict-free Replicated Data Types. In Proceedings of the 13th International Conference on Stabilization, Safety, and Security of Distributed Systems (SSS'11). Springer-Verlag, Berlin, Heidelberg, 386--400. http://dl.acm.org/citation.cfm?id= 2050613.2050642

[40]

Facebook Open Source. 2017. RocksDB. http://rocksdb.org/. (2017). {Online; accessed 30-Oct-2017}.

[41]

Stephen Tu, Wenting Zheng, Eddie Kohler, Barbara Liskov, and Samuel Madden. 2013. Speedy Transactions in Multicore In-memory Databases. In Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles (SOSP '13). ACM, New York, NY, USA, 18--32.

Digital Library

[42]

Matei Zaharia, Mosharaf Chowdhury, Michael J. Franklin, Scott Shenker, and Ion Stoica. 2010. Spark: Cluster Computing with Working Sets. In Proceedings of the 2Nd USENIX Conference on Hot Topics in Cloud Computing (HotCloud'10). USENIX Association, Berkeley, CA, USA, 10--10. http://dl.acm.org/citation.cfm? id=1863103.1863113

Digital Library

Cited By

Lei HLi CZhou KZhu JYan KXiao FXie MWang JDi S(2024)X-Stor: A Cloud-Native NoSQL Database Service with Multi-Model SupportProceedings of the VLDB Endowment10.14778/3685800.368582417:12(4025-4037)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.14778/3685800.3685824
Dayan NBercea IPagh R(2024)Aleph Filter: To Infinity in Constant TimeProceedings of the VLDB Endowment10.14778/3681954.368202717:11(3644-3656)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3682027
Hao XChandramouli B(2024)Bf-Tree: A Modern Read-Write-Optimized Concurrent Larger-Than-Memory Range IndexProceedings of the VLDB Endowment10.14778/3681954.368201217:11(3442-3455)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3682012
Show More Cited By

Index Terms

FASTER: A Concurrent Key-Value Store with In-Place Updates
1. Information systems
  1. Data management systems
    1. Database management system engines
      1. Parallel and distributed DBMSs
        Key-value stores

Recommendations

LSM-tree managed storage for large-scale key-value store
SoCC '17: Proceedings of the 2017 Symposium on Cloud Computing

Key-value stores are increasingly adopting LSM-trees as their enabling data structure in the backend storage, and persisting their clustered data through a file system. A file system is expected to not only provide file/directory abstraction to organize ...
dCompaction: Delayed Compaction for the LSM-Tree

Key-value (KV) stores have become a backbone of large-scale applications in today's data centers. Write-optimized data structures like the Log-Structured Merge-tree (LSM-tree) and their variants are widely used in KV storage systems like BigTable and ...
MTDB: an LSM-tree-based key-value store using a multi-tree structure to improve read performance
Abstract
Traditional LSM-tree-based key-value storage systems face significant read amplification issues due to the multi-level structure of LSM-tree, the unordered SSTable files in Level 0, and the lack of an in-memory index structure for key-value pairs. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGMOD '18: Proceedings of the 2018 International Conference on Management of Data

May 2018

1874 pages

ISBN:9781450347037

DOI:10.1145/3183713

General Chairs:
Gautam Das
University of Texas at Arlington, USA
,
Christopher Jermaine
Rice University, USA
,
Philip Bernstein
Microsoft Research, USA

Copyright © 2018 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 ACM 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

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 May 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGMOD/PODS '18

Sponsor:

SIGMOD

SIGMOD/PODS '18: International Conference on Management of Data

June 10 - 15, 2018

TX, Houston, USA

Acceptance Rates

SIGMOD '18 Paper Acceptance Rate 90 of 461 submissions, 20%;

Overall Acceptance Rate 785 of 4,003 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

102
Total Citations
View Citations
1,485
Total Downloads

Downloads (Last 12 months)181
Downloads (Last 6 weeks)26

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lei HLi CZhou KZhu JYan KXiao FXie MWang JDi S(2024)X-Stor: A Cloud-Native NoSQL Database Service with Multi-Model SupportProceedings of the VLDB Endowment10.14778/3685800.368582417:12(4025-4037)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.14778/3685800.3685824
Dayan NBercea IPagh R(2024)Aleph Filter: To Infinity in Constant TimeProceedings of the VLDB Endowment10.14778/3681954.368202717:11(3644-3656)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3682027
Hao XChandramouli B(2024)Bf-Tree: A Modern Read-Write-Optimized Concurrent Larger-Than-Memory Range IndexProceedings of the VLDB Endowment10.14778/3681954.368201217:11(3442-3455)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3682012
Zhu ZSaha AAthanassoulis MSarkar S(2024)KVBench: A Key-Value Benchmarking SuiteProceedings of the Tenth International Workshop on Testing Database Systems10.1145/3662165.3662765(9-15)Online publication date: 9-Jun-2024
https://dl.acm.org/doi/10.1145/3662165.3662765
Raman AHuynh ALu JAthanassoulis M(2024)Benchmarking Learned and LSM Indexes for Data SortednessProceedings of the Tenth International Workshop on Testing Database Systems10.1145/3662165.3662764(16-22)Online publication date: 9-Jun-2024
https://dl.acm.org/doi/10.1145/3662165.3662764
Chatterjee SPekala MKruglyak LIdreos S(2024)Limousine: Blending Learned and Classical Indexes to Self-Design Larger-than-Memory Cloud Storage EnginesProceedings of the ACM on Management of Data10.1145/36393022:1(1-28)Online publication date: 26-Mar-2024
https://dl.acm.org/doi/10.1145/3639302
Pandey PFarach-Colton MDayan NZhang HBarcelo PSanchez-Pi NMeliou ASudarshan S(2024)Beyond Bloom: A Tutorial on Future Feature-Rich FiltersCompanion of the 2024 International Conference on Management of Data10.1145/3626246.3654681(636-644)Online publication date: 9-Jun-2024
https://dl.acm.org/doi/10.1145/3626246.3654681
Taleb YMcGehee KYan NWang SMüller SSamuels ABarcelo PSanchez-Pi NMeliou ASudarshan S(2024)Amazon MemoryDB: A Fast and Durable Memory-First Cloud DatabaseCompanion of the 2024 International Conference on Management of Data10.1145/3626246.3653380(309-320)Online publication date: 9-Jun-2024
https://dl.acm.org/doi/10.1145/3626246.3653380
Katsarakis AGavrielatos VNtarmos NMencagli GDazzi PLowenthal DBadia R(2024)DLHT: A Non-blocking Resizable Hashtable with Fast Deletes and Memory-awarenessProceedings of the 33rd International Symposium on High-Performance Parallel and Distributed Computing10.1145/3625549.3658682(186-199)Online publication date: 3-Jun-2024
https://dl.acm.org/doi/10.1145/3625549.3658682
Lee HDathathri RPingali KTsafrir DMusuvathi MGupta RAbu-Ghazaleh N(2024)Kimbap: A Node-Property Map System for Distributed Graph AnalyticsProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 210.1145/3620665.3640421(566-581)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3620665.3640421
Show More Cited By

View Options

Get Access

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents