research-article

Open access

Efficient Compactions between Storage Tiers with PrismDB

Authors:

Michael J. FreedmanAuthors Info & Claims

ASPLOS 2023: Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3

Pages 179 - 193

https://doi.org/10.1145/3582016.3582052

Published: 25 March 2023 Publication History

Abstract

In recent years, emerging storage hardware technologies have focused on divergent goals: better performance or lower cost-per-bit. Correspondingly, data systems that employ these technologies are typically optimized either to be fast (but expensive) or cheap (but slow). We take a different approach: by architecting a storage engine to natively utilize two tiers of fast and low-cost storage technologies, we can achieve a Pareto efficient balance between performance and cost-per-bit.

This paper presents the design and implementation of PrismDB, a novel key-value store that exploits two extreme ends of the spectrum of modern NVMe storage technologies (3D XPoint and QLC NAND) simultaneously. Our key contribution is how to efficiently migrate and compact data between two different storage tiers. Inspired by the classic cost-benefit analysis of log cleaning, we develop a new algorithm for multi-tiered storage compaction that balances the benefit of reclaiming space for hot objects in fast storage with the cost of compaction I/O in slow storage. Compared to the standard use of RocksDB on flash in datacenters today, PrismDB’s average throughput on tiered storage is 3.3× faster, its read tail latency is 2× better, and it is 5× more durable using equivalently-priced hardware.

References

[1]

Shoaib Akram. 2021. Exploiting Intel optane persistent memory for full text search. In Proceedings of the 2021 ACM SIGPLAN International Symposium on Memory Management. 80–93.

Digital Library

[2]

Joy Arulraj and Andrew Pavlo. 2017. How to Build a Non-Volatile Memory Database Management System. In Proc. Intl. Conference on Management of Data (SIGMOD). 6 pages. isbn:978-1-4503-4197-4 https://doi.org/10.1145/3035918.3054780

Digital Library

[3]

Joy Arulraj, Matthew Perron, and Andrew Pavlo. 2016. Write-behind Logging. Proc. VLDB Endowment, 10, 4 (2016), Nov., 12 pages. issn:2150-8097 https://doi.org/10.14778/3025111.3025116

Digital Library

[4]

Jens Axboe. 2017. Flexible I/O Tester. https://github.com/axboe/fio

[5]

Oana Balmau, Diego Didona, Rachid Guerraoui, Willy Zwaenepoel, Huapeng Yuan, Aashray Arora, Karan Gupta, and Pavan Konka. 2017. TRIAD: Creating Synergies Between Memory, Disk and Log in Log Structured Key-Value Stores. In Proc. USENIX Annual Technical Conference (ATC). isbn:978-1-931971-38-6 https://www.usenix.org/conference/atc17/technical-sessions/presentation/balmau

[6]

Oana Balmau, Florin Dinu, Willy Zwaenepoel, Karan Gupta, Ravishankar Chandhiramoorthi, and Diego Didona. 2019. SILK: Preventing Latency Spikes in Log-Structured Merge Key-Value Stores. In Proc. USENIX Annual Technical Conference (ATC). isbn:978-1-939133-03-8 https://www.usenix.org/conference/atc19/presentation/balmau

[7]

Nathan Beckmann, Haoxian Chen, and Asaf Cidon. 2018. LHD: Improving Cache Hit Rate by Maximizing Hit Density. In Proc. USENIX Symposium on Networked Systems Design and Implementation (NSDI). isbn:978-1-939133-01-4 https://www.usenix.org/conference/nsdi18/presentation/beckmann

[8]

Burton H. Bloom. 1970. Space/time trade-offs in hash coding with allowable errors. Commun. ACM.

[9]

Santiago Bock, Bruce R. Childers, Rami Melhem, and Daniel Mossé. 2016. Concurrent Migration of Multiple Pages in software-managed hybrid main memory. In 2016 IEEE 34th International Conference on Computer Design (ICCD). 420–423. https://doi.org/10.1109/ICCD.2016.7753318

[10]

Nathan Bronson, Zach Amsden, George Cabrera, Prasad Chakka, Peter Dimov, Hui Ding, Jack Ferris, Anthony Giardullo, Sachin Kulkarni, Harry Li, Mark Marchukov, Dmitri Petrov, Lovro Puzar, Yee Jiun Song, and Venkat Venkataramani. 2013. TAO: Facebook’s Distributed Data Store for the Social Graph. In Proc. USENIX Annual Technical Conference (ATC). isbn:978-1-931971-01-0

[11]

Zhichao Cao, Siying Dong, Sagar Vemuri, and David H.C. Du. 2020. Characterizing, Modeling, and Benchmarking RocksDB Key-Value Workloads at Facebook. In Proc. USENIX Conference on File and Storage Technologies (FAST). isbn:978-1-939133-12-0 https://www.usenix.org/conference/fast20/presentation/cao-zhichao

[12]

Li-Pin Chang and Tei-Wei Kuo. 2002. An adaptive striping architecture for flash memory storage systems of embedded systems. In Proceedings. Eighth IEEE Real-Time and Embedded Technology and Applications Symposium. 187–196. https://doi.org/10.1109/RTTAS.2002.1137393

[13]

Hao Chen, Chaoyi Ruan, Cheng Li, Xiaosong Ma, and Yinlong Xu. 2021. SpanDB: A Fast, Cost-Effective LSM-tree Based KV Store on Hybrid Storage. In 19th USENIX Conference on File and Storage Technologies (FAST 21). 17–32.

[14]

Asaf Cidon, Assaf Eisenman, Mohammad Alizadeh, and Sachin Katti. 2016. Cliffhanger: Scaling Performance Cliffs in Web Memory Caches. In Proc. USENIX Symposium on Networked Systems Design and Implementation (NSDI). isbn:978-1-931971-29-4 https://www.usenix.org/conference/nsdi16/technical-sessions/presentation/cidon

[15]

Asaf Cidon, Daniel Rushton, Stephen M. Rumble, and Ryan Stutsman. 2017. Memshare: a Dynamic Multi-tenant Key-value Cache. In 2017 USENIX Annual Technical Conference (USENIX ATC 17). USENIX Association, Santa Clara, CA. 321–334. isbn:978-1-931971-38-6 https://www.usenix.org/conference/atc17/technical-sessions/presentation/cidon

Digital Library

[16]

Alexander Conway, Abhishek Gupta, Vijay Chidambaram, Martin Farach-Colton, Richard Spillane, Amy Tai, and Rob Johnson. 2020. SplinterDB: Closing the Bandwidth Gap for NVMe Key-Value Stores. In Proc. USENIX Annual Technical Conference (ATC). isbn:978-1-939133-14-4 https://www.usenix.org/conference/atc20/presentation/conway

[17]

Brian F. Cooper, Adam Silberstein, Erwin Tam, Raghu Ramakrishnan, and Russell Sears. 2010. Benchmarking Cloud Serving Systems with YCSB. In Proc. Symposium on Cloud Computing (SoCC). 12 pages. isbn:9781450300360 https://doi.org/10.1145/1807128.1807152

Digital Library

[18]

Fernando J Corbato. 1968. A paging experiment with the multics system. DTIC Document.

[19]

James C. Corbett, Jeffrey Dean, Michael Epstein, Andrew Fikes, Christopher Frost, JJ Furman, Sanjay Ghemawat, Andrey Gubarev, Christopher Heiser, Peter Hochschild, Wilson Hsieh, Sebastian Kanthak, Eugene Kogan, Hongyi Li, Alexander Lloyd, Sergey Melnik, David Mwaura, David Nagle, Sean Quinlan, Rajesh Rao, Lindsay Rolig, Yasushi Saito, Michal Szymaniak, Christopher Taylor, Ruth Wang, and Dale Woodford. 2012. Spanner: Google’ s Globally-Distributed Database. In 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI 12). Hollywood, CA. 261–264. isbn:978-1-931971-96-6 https://www.usenix.org/conference/osdi12/technical-sessions/presentation/corbett

[20]

Siying Dong, Mark Callaghan, Leonidas Galanis, Dhruba Borthakur, Tony Savor, and Michael Strum. 2017. Optimizing Space Amplification in RocksDB. In Proc. Biennial Conference on Innovative Data Systems Research (CIDR). http://cidrdb.org/cidr2017/papers/p82-dong-cidr17.pdf

[21]

Assaf Eisenman, Asaf Cidon, Evgenya Pergament, Or Haimovich, Ryan Stutsman, Mohammad Alizadeh, and Sachin Katti. 2019. Flashield: a Hybrid Key-value Cache that Controls Flash Write Amplification. In Proc. USENIX Symposium on Networked Systems Design and Implementation (NSDI). isbn:978-1-931971-49-2 https://www.usenix.org/conference/nsdi19/presentation/eisenman

[22]

Assaf Eisenman, Darryl Gardner, Islam AbdelRahman, Jens Axboe, Siying Dong, Kim Hazelwood, Chris Petersen, Asaf Cidon, and Sachin Katti. 2018. Reducing DRAM Footprint with NVM in Facebook. In Proc. EuroSys Conference. Article 42, 13 pages. isbn:978-1-4503-5584-1 https://doi.org/10.1145/3190508.3190524

Digital Library

[23]

Facebook. 2014. RocksDB. https://rocksdb.org

[24]

Bin Fan, David G. Andersen, and Michael Kaminsky. 2013. MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing. In Proc. USENIX Symposium on Networked Systems Design and Implementation (NSDI). 14 pages. http://dl.acm.org/citation.cfm?id=2482626.2482662

[25]

Eran Gilad, Edward Bortnikov, Anastasia Braginsky, Yonatan Gottesman, Eshcar Hillel, Idit Keidar, Nurit Moscovici, and Rana Shahout. 2020. EvenDB: Optimizing Key-Value Storage for Spatial Locality. In Proc. European Conference on Computer Systems (EuroSys). Article 27, 16 pages. isbn:9781450368827 https://doi.org/10.1145/3342195.3387523

Digital Library

[26]

Google. 2011. Google b-tree implementation. https://code.google.com/archive/p/cpp-btree/

[27]

Google. 2011. LevelDB. http://leveldb.org/

[28]

Laura M. Grupp, John D. Davis, and Steven Swanson. 2012. The Bleak Future of NAND Flash Memory. In Proc. USENIX Conference on File and Storage Technologies (FAST). 1 pages. http://dl.acm.org/citation.cfm?id=2208461.2208463

[29]

Intel. [n. d.]. Intel Optane SSD DC P5800X Series. https://ark.intel.com/content/www/us/en/ark/products/201859/intel-optane-ssd-dc-p5800x-series-1-6tb-2-5in-pcie-x4-3d-xpoint.html

[30]

Intel. 2019. Intel Optane memory. https://www.intel.com/content/www/us/en/architecture-and-technology/optane-memory.html

[31]

Intel. 2019. Intel Thread Building Blocks (TBB) library. https://software.intel.com/content/www/us/en/develop/tools/threading-building-blocks.html

[32]

Shehbaz Jaffer, Kaveh Mahdaviani, and Bianca Schroeder. 2020. Rethinking WOM Codes to Enhance the Lifetime in New SSD Generations. In Proc. USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage).

[33]

Olzhas Kaiyrakhmet, Songyi Lee, Beomseok Nam, Sam H Noh, and Young-Ri Choi. 2019. SLM-DB: single-level key-value store with persistent memory. In Proc. USENIX Conference on File and Storage Technologies (FAST).

[34]

Jagadish B. Kotra, Haibo Zhang, Alaa R. Alameldeen, Chris Wilkerson, and Mahmut T. Kandemir. 2018. CHAMELEON: A Dynamically Reconfigurable Heterogeneous Memory System. In 2018 51st Annual IEEE/ACM International Symposium on Microarchitecture (MICRO). 533–545. https://doi.org/10.1109/MICRO.2018.00050

Digital Library

[35]

Kornilios Kourtis, Nikolas Ioannou, and Ioannis Koltsidas. 2019. Reaping the performance of fast NVM storage with uDepot. In Proc. USENIX Conference on File and Storage Technologies (FAST). isbn:978-1-939133-09-0 https://www.usenix.org/conference/fast19/presentation/kourtis

[36]

Youngjin Kwon, Henrique Fingler, Tyler Hunt, Simon Peter, Emmett Witchel, and Thomas Anderson. 2017. Strata: A cross media file system. In Proc. Symposium on Operating Systems Principles (SOSP).

Digital Library

[37]

Hyun-Seob Lee, Hyun-Sik Yun, and Dong-Ho Lee. 2009. HFTL: hybrid flash translation layer based on hot data identification for flash memory. IEEE Transactions on Consumer Electronics, 55, 4 (2009), 2005–2011. https://doi.org/10.1109/TCE.2009.5373762

Digital Library

[38]

Sungjin Lee, Dongkun Shin, Young-Jin Kim, and Jihong Kim. 2008. LAST: Locality-Aware Sector Translation for NAND Flash Memory-Based Storage Systems. SIGOPS Oper. Syst. Rev., 42, 6 (2008), oct, 36–42. issn:0163-5980 https://doi.org/10.1145/1453775.1453783

Digital Library

[39]

Baptiste Lepers, Oana Balmau, Karan Gupta, and Willy Zwaenepoel. 2019. KVell: The Design and Implementation of a Fast Persistent Key-Value Store. In Proc. Symposium on Operating Systems Principles (SOSP). 15 pages. isbn:9781450368735 https://doi.org/10.1145/3341301.3359628

Digital Library

[40]

Wenjie Li, Dejun Jiang, Jin Xiong, and Yungang Bao. 2020. HiLSM: An LSM-Based Key-Value Store for Hybrid NVM-SSD Storage Systems. In Proceedings of the 17th ACM International Conference on Computing Frontiers (CF ’20). Association for Computing Machinery, New York, NY, USA. 208–216. isbn:9781450379564 https://doi.org/10.1145/3387902.3392621

Digital Library

[41]

Yang Li, Saugata Ghose, Jongmoo Choi, Jin Sun, Hui Wang, and Onur Mutlu. 2017. Utility-Based Hybrid Memory Management. In 2017 IEEE International Conference on Cluster Computing (CLUSTER). 152–165. https://doi.org/10.1109/CLUSTER.2017.130

[42]

Siqiang Luo, Subarna Chatterjee, Rafael Ketsetsidis, Niv Dayan, Wilson Qin, and Stratos Idreos. 2020. Rosetta: A Robust Space-Time Optimized Range Filter for Key-Value Stores. In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data (SIGMOD ’20). Association for Computing Machinery, New York, NY, USA. 2071–2086. isbn:9781450367356 https://doi.org/10.1145/3318464.3389731

Digital Library

[43]

Yixin Luo, Yu Cai, Saugata Ghose, Jongmoo Choi, and Onur Mutlu. 2015. WARM: Improving NAND flash memory lifetime with write-hotness aware retention management. In 2015 31st Symposium on Mass Storage Systems and Technologies (MSST). 1–14. https://doi.org/10.1109/MSST.2015.7208284

[44]

Virendra J. Marathe, Margo Seltzer, Steve Byan, and Tim Harris. 2017. Persistent Memcached: Bringing Legacy Code to Byte-addressable Persistent Memory. In Proc. USENIX Conference on Hot Topics in Storage and File Systems (HotStorage). 1 pages. http://dl.acm.org/citation.cfm?id=3154601.3154605

[45]

C Mellor. [n. d.]. Toshiba flashes 100TB QLC flash drive, may go on sale within months. http://www.theregister.co.uk/2016/08/10/toshiba_100tb_qlc_ssd/

[46]

Micron. 2018. The Great Endurance Race: SSDs in One Lane, HDDs in the Other.

[47]

Micron. 2019. QLC NAND Technology. https://www.micron.com/products/nand-flash/qlc-nand

[48]

Michael Mitzenmacher. 2001. The power of two choices in randomized load balancing. IEEE Transactions on Parallel and Distributed Systems, 12, 10 (2001), 1094–1104.

Digital Library

[49]

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 Proc. USENIX Symposium on Networked Systems Design and Implementation (NSDI). isbn:978-1-931971-00-3

[50]

Matheus Almeida Ogleari, Ethan L Miller, and Jishen Zhao. 2018. Steal but no force: Efficient hardware undo+ redo logging for persistent memory systems. In Proc. Intl. Symposium on High Performance Computer Architecture (HPCA).

[51]

S Ohshima and Y Tanaka. [n. d.]. New 3D Flash Technologies Offer Both Low Cost and Low Power Solutions. https://www.flashmemorysummit.com/English/Conference/Keynotes.html

[52]

Patrick O’Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O’Neil. 1996. The log-structured merge-tree (LSM-tree). Acta Informatica, 33, 4 (1996).

[53]

Ivy B. Peng and Jeffrey S. Vetter. 2018. Siena: Exploring the Design Space of Heterogeneous Memory Systems. In SC18: International Conference for High Performance Computing, Networking, Storage and Analysis. 427–440. https://doi.org/10.1109/SC.2018.00036

Digital Library

[54]

Moinuddin K. Qureshi, Vijayalakshmi Srinivasan, and Jude A. Rivers. 2009. Scalable High Performance Main Memory System Using Phase-Change Memory Technology. SIGARCH Comput. Archit. News, 37, 3 (2009), jun, 24–33. issn:0163-5964 https://doi.org/10.1145/1555815.1555760

Digital Library

[55]

Pandian Raju, Rohan Kadekodi, Vijay Chidambaram, and Ittai Abraham. 2017. PebblesDB: Building Key-Value Stores Using Fragmented Log-Structured Merge Trees. In Proc. Symposium on Operating Systems Principles (SOSP). 18 pages. isbn:978-1-4503-5085-3 https://doi.org/10.1145/3132747.3132765

Digital Library

[56]

Luiz E. Ramos, Eugene Gorbatov, and Ricardo Bianchini. 2011. Page Placement in Hybrid Memory Systems. In Proceedings of the International Conference on Supercomputing (ICS ’11). Association for Computing Machinery, New York, NY, USA. 85–95. isbn:9781450301022 https://doi.org/10.1145/1995896.1995911

Digital Library

[57]

Mendel Rosenblum and John K Ousterhout. 1992. The design and implementation of a log-structured file system. ACM Trans. Computer Systems, 10, 1 (1992).

Digital Library

[58]

Stephen M. Rumble, Ankita Kejriwal, and John Ousterhout. 2014. Log-structured Memory for DRAM-based Storage. In 12th USENIX Conference on File and Storage Technologies (FAST 14). USENIX Association, Santa Clara, CA. 1–16. isbn:ISBN 978-1-931971-08-9 https://www.usenix.org/conference/fast14/technical-sessions/presentation/rumble

[59]

Samsung. 2019. Samsung Z-SSD Redefining fast responsiveness. https://www.samsung.com/semiconductor/ssd/z-ssd/

[60]

Zhenyu Song, Daniel S. Berger, Kai Li, and Wyatt Lloyd. 2020. Learning Relaxed Belady for Content Distribution Network Caching. In Proc. USENIX Symposium on Networked Systems Design and Implementation (NSDI). isbn:978-1-939133-13-7 https://www.usenix.org/conference/nsdi20/presentation/song

[61]

Amy Tai, Andrew Kryczka, Shobhit O. Kanaujia, Kyle Jamieson, Michael J. Freedman, and Asaf Cidon. 2019. Who’ s Afraid of Uncorrectable Bit Errors? Online Recovery of Flash Errors with Distributed Redundancy. In Proc. USENIX Annual Technical Conference (ATC). isbn:978-1-939133-03-8 https://www.usenix.org/conference/atc19/presentation/tai

[62]

Billy Tallis. [n. d.]. The Crucial P1 1TB SSD Review: The Other Consumer QLC SSD. https://www.anandtech.com/show/13512/the-crucial-p1-1tb-ssd-review

[63]

Linpeng Tang, Qi Huang, Wyatt Lloyd, Sanjeev Kumar, and Kai Li. 2015. RIPQ: Advanced Photo Caching on Flash for Facebook. In Proc. USENIX Conference on File and Storage Technologies (FAST). isbn:978-1-931971-201 https://www.usenix.org/conference/fast15/technical-sessions/presentation/tang

[64]

Tracking live sst files. [n. d.]. https://github.com/facebook/rocksdb/wiki/How-we-keep-track-of-live-SST-files. https://github.com/facebook/rocksdb/wiki/How-we-keep-track-of-live-SST-files

[65]

Alexander van Renen, Viktor Leis, Alfons Kemper, Thomas Neumann, Takushi Hashida, Kazuichi Oe, Yoshiyasu Doi, Lilian Harada, and Mitsuru Sato. 2018. Managing Non-Volatile Memory in Database Systems. In Proc. Intl. Conference on Management of Data (SIGMOD). 15 pages. isbn:9781450347037 https://doi.org/10.1145/3183713.3196897

Digital Library

[66]

Alexander van Renen, Lukas Vogel, Viktor Leis, Thomas Neumann, and Alfons Kemper. 2019. Persistent Memory I/O Primitives. In Proc. Intl. Workshop on Data Management on New Hardware (DaMoN). Article 12, 7 pages. isbn:9781450368018 https://doi.org/10.1145/3329785.3329930

Digital Library

[67]

Carl Waldspurger, Trausti Saemundsson, Irfan Ahmad, and Nohhyun Park. 2017. Cache Modeling and Optimization using Miniature Simulations. In Proc. USENIX Annual Technical Conference (ATC). isbn:978-1-931971-38-6 https://www.usenix.org/conference/atc17/technical-sessions/presentation/waldspurger

[68]

Carl A. Waldspurger, Nohhyun Park, Alexander Garthwaite, and Irfan Ahmad. 2015. Efficient MRC Construction with SHARDS. In Proc. USENIX Conference on File and Storage Technologies (FAST). isbn:978-1-931971-201 https://www.usenix.org/conference/fast15/technical-sessions/presentation/waldspurger

[69]

Benjamin Walker. 2016. SPDK: Building blocks for scalable, high performance storage applications. In Storage Developer Conference. SNIA.

[70]

Sean Webster. [n. d.]. Intel SSD 660p. https://www.tomshardware.com/reviews/intel-ssd-660p-qlc-nvme,5719.html

[71]

Chin-hsien Wu and Tei-wei Kuo. 2006. An Adaptive Two-Level Management for the Flash Translation Layer in Embedded Systems. In 2006 IEEE/ACM International Conference on Computer Aided Design. 601–606. https://doi.org/10.1109/ICCAD.2006.320107

[72]

Kan Wu, Andrea Arpaci-Dusseau, and Remzi Arpaci-Dusseau. 2019. Towards an Unwritten Contract of Intel Optane SSD. In Proc. USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage). https://www.usenix.org/conference/hotstorage19/presentation/wu-kan

[73]

Kan Wu, Andrea Arpaci-Dusseau, Remzi Arpaci-Dusseau, Rathijit Sen, and Kwanghyun Park. 2019. Exploiting Intel Optane SSD for Microsoft SQL Server. In Proc. Intl. Workshop on Data Management on New Hardware (DaMoN). Article 15, 3 pages. isbn:9781450368018 https://doi.org/10.1145/3329785.3329916

Digital Library

[74]

Kan Wu, Zhihan Guo, Guanzhou Hu, Kaiwei Tu, Ramnatthan Alagappan, Rathijit Sen, Kwanghyun Park, Andrea C. Arpaci-Dusseau, and Remzi H. Arpaci-Dusseau. 2021. The Storage Hierarchy is Not a Hierarchy: Optimizing Caching on Modern Storage Devices with Orthus. In 19th USENIX Conference on File and Storage Technologies (FAST 21). USENIX Association, 307–323. isbn:978-1-939133-20-5 https://www.usenix.org/conference/fast21/presentation/wu-kan

[75]

Fei Xia, Dejun Jiang, Jin Xiong, and Ninghui Sun. 2017. HiKV: A Hybrid Index Key-Value Store for DRAM-NVM Memory Systems. In Proc. USENIX Annual Technical Conference (ATC). isbn:978-1-931971-38-6 https://www.usenix.org/conference/atc17/technical-sessions/presentation/xia

[76]

Juncheng Yang, Yao Yue, and K. V. Rashmi. 2020. A large scale analysis of hundreds of in-memory cache clusters at Twitter. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20). USENIX Association, 191–208. isbn:978-1-939133-19-9 https://www.usenix.org/conference/osdi20/presentation/yang

[77]

Ting Yao, Yiwen Zhang, Jiguang Wan, Qiu Cui, Liu Tang, Hong Jiang, Changsheng Xie, and Xubin He. 2020. MatrixKV: Reducing Write Stalls and Write Amplification in LSM-tree Based KV Stores with Matrix Container in NVM. In Proc. USENIX Annual Technical Conference (ATC). isbn:978-1-939133-14-4 https://www.usenix.org/conference/atc20/presentation/yao

[78]

HanBin Yoon, Justin Meza, Rachata Ausavarungnirun, Rachael A. Harding, and Onur Mutlu. 2012. Row buffer locality aware caching policies for hybrid memories. In 2012 IEEE 30th International Conference on Computer Design (ICCD). 337–344. https://doi.org/10.1109/ICCD.2012.6378661

Digital Library

[79]

Hobin Yoon, Juncheng Yang, Sveinn Fannar Kristjansson, Steinn E. Sigurdarson, Ymir Vigfusson, and Ada Gavrilovska. 2018. Mutant: Balancing Storage Cost and Latency in LSM-Tree Data Stores. In Proc. Symposium on Cloud Computing (SoCC). 12 pages. isbn:9781450360111 https://doi.org/10.1145/3267809.3267846

Digital Library

[80]

Huanchen Zhang, Hyeontaek Lim, Viktor Leis, David G. Andersen, Michael Kaminsky, Kimberly Keeton, and Andrew Pavlo. 2018. SuRF: Practical Range Query Filtering with Fast Succinct Tries. In Proceedings of the 2018 International Conference on Management of Data (SIGMOD ’18). Association for Computing Machinery, New York, NY, USA. 323–336. isbn:9781450347037 https://doi.org/10.1145/3183713.3196931

Digital Library

[81]

Wenshao Zhong, Chen Chen, Xingbo Wu, and Song Jiang. 2021. REMIX: Efficient Range Query for LSM-trees. In 19th USENIX Conference on File and Storage Technologies (FAST 21). USENIX Association, 51–64. isbn:978-1-939133-20-5 https://www.usenix.org/conference/fast21/presentation/zhong

[82]

Xinjing Zhou, Joy Arulraj, Andrew Pavlo, and David Cohen. 2021. Spitfire: A Three-Tier Buffer Manager for Volatile and Non-Volatile Memory. Association for Computing Machinery, New York, NY, USA. 2195–2207. isbn:9781450383431 https://doi.org/10.1145/3448016.3452819

Digital Library

Cited By

Zhou RZhang YLi CZhou KWang PZhang GZhang JZhang G(2024)HyperDB: a Novel Key Value Store for Reducing Background Traffic in Heterogeneous SSD StorageProceedings of the 53rd International Conference on Parallel Processing10.1145/3673038.3673153(453-463)Online publication date: 12-Aug-2024
https://dl.acm.org/doi/10.1145/3673038.3673153

Index Terms

Efficient Compactions between Storage Tiers with PrismDB
1. Computer systems organization
  1. Dependable and fault-tolerant systems and networks
    1. Secondary storage organization
2. Information systems
  1. Data management systems
    1. Data structures
      1. Data layout

Recommendations

gLSM: Using GPGPU to Accelerate Compactions in LSM-tree-based Key-value Stores
Log-structured-merge tree or LSM-tree is a technological underpinning in key-value (KV) stores to support a wide range of performance-critical applications. By conducting data re-organization in the background by virtue of compaction operations, the KV ...
GHStore: A High Performance Global Hash Based Key-Value Store
Database Systems for Advanced Applications
Abstract
Log-Structured Merge tree (LSM-tree) has become the mainstream data structure of persistent key-value (KV) stores, but it suffers from serious write and read amplification. In update intensive workloads, repeated and useless compaction of outdated ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASPLOS 2023: Proceedings of the 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3

March 2023

820 pages

ISBN:9781450399180

DOI:10.1145/3582016

General Chair:
Tor M. Aamodt
University of British Columbia, Canada
,
Program Chairs:
Natalie Enright Jerger
University of Toronto, Canada
,
Michael Swift
University of Wisconsin-Madison, USA

Copyright © 2023 Owner/Author.

This work is licensed under a Creative Commons Attribution 4.0 International License.

Sponsors

In-Cooperation

SIGBED: ACM Special Interest Group on Embedded Systems

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 March 2023

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article

Funding Sources

NSF
ARO

Conference

ASPLOS '23

Sponsor:

ASPLOS '23: 28th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 3

March 25 - 29, 2023

BC, Vancouver, Canada

Acceptance Rates

Overall Acceptance Rate 535 of 2,713 submissions, 20%

Upcoming Conference

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
1,025
Total Downloads

Downloads (Last 12 months)616
Downloads (Last 6 weeks)77

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhou RZhang YLi CZhou KWang PZhang GZhang JZhang G(2024)HyperDB: a Novel Key Value Store for Reducing Background Traffic in Heterogeneous SSD StorageProceedings of the 53rd International Conference on Parallel Processing10.1145/3673038.3673153(453-463)Online publication date: 12-Aug-2024
https://dl.acm.org/doi/10.1145/3673038.3673153

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Table of Contents