Badrish Chandramouli
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.
- 2017. jemalloc. http://jemalloc.net/. (2017). {Online; accessed 30-Oct-2017}.Google Scholar
- 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/Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Intel Corporation. 2017. Intel Threading Building Blocks. https://www. threadingbuildingblocks.org/. (2017). {Online; accessed 30-Oct-2017}.Google Scholar
- 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. Google ScholarDigital Library
- 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/ Google ScholarDigital Library
- Facebook. 2017. RocksDB Performance Evaluation. https://github.com/facebook/ rocksdb/wiki/performance-benchmarks. (2017). {Online; accessed 30-Oct-2017}.Google Scholar
- Facebook. 2017. RocksDB Wiki. https://github.com/facebook/rocksdb/wiki. (2017). {Online; accessed 30-Oct-2017}.Google Scholar
- 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 Google ScholarDigital Library
- Apache Software Foundation. 2017. Apache Cassandra. http://cassandra.apache. org/. (2017). {Online; accessed 30-Oct-2017}.Google Scholar
- Apache Software Foundation. 2017. Apache Flink. https://flink.apache.org/. (2017). {Online; accessed 30-Oct-2017}.Google Scholar
- Apache Software Foundation. 2017. Apache Hadoop. http://hadoop.apache.org/. (2017). {Online; accessed 30-Oct-2017}.Google Scholar
- 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}.Google Scholar
- Apache Software Foundation. 2017. Trident State Store. http://storm.apache.org/ releases/current/Trident-state.html. (2017). {Online; accessed 30-Oct-2017}.Google Scholar
- Keir Fraser. 2004. Practical Lock-Freedom. Technical Report.Google Scholar
- Google. 2017. Google Cloud Dataflow. https://cloud.google.com/dataflow/. (2017). {Online; accessed 30-Oct-2017}.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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 Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- H. T. Kung and Philip L. Lehman. 1980. Concurrent Manipulation of Binary Search Trees. ACM Trans. Database Syst. 5, 3 (Sept. 1980), 354--382. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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.pdfGoogle Scholar
- 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 Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Memcached. 2017. https://memcached.org/. (2017). {Online; accessed 30-Oct2017}.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- Redis. 2017. https://redis.io/. (2017). {Online; accessed 30-Oct-2017}.Google Scholar
- 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. Google ScholarDigital Library
- 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. Google ScholarDigital Library
- 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 Google ScholarCross Ref
- Facebook Open Source. 2017. RocksDB. http://rocksdb.org/. (2017). {Online; accessed 30-Oct-2017}.Google Scholar
- 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. Google ScholarDigital Library
- 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 Google ScholarDigital Library
Index Terms
- FASTER: A Concurrent Key-Value Store with In-Place Updates
Recommendations
KVell: the design and implementation of a fast persistent key-value store
SOSP '19: Proceedings of the 27th ACM Symposium on Operating Systems PrinciplesModern block-addressable NVMe SSDs provide much higher bandwidth and similar performance for random and sequential access. Persistent key-value stores (KVs) designed for earlier storage devices, using either Log-Structured Merge (LSM) or B trees, do not ...
LSM-tree managed storage for large-scale key-value store
SoCC '17: Proceedings of the 2017 Symposium on Cloud ComputingKey-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 ...
Comments