Towards Efficient Key-Value Storage on Key-Value SSDs = 키-밸류 SSD 상에서의 효율적인 키-밸류 스토리지

다국어 초록 (Multilingual Abstract)

Key-value SSDs (KVSSDs) represent a radical shift in the storage stack design; instead of maintaining an index for finding key-value data
inside the host system, an index is maintained inside the disk itself.
The goal of key-value SSDs is noble; eliminate data transfer to and from the host system for key-value pair indexing.
However, currently available KVSSDs support a limited feature set, and run slower than modern block devices.

Despite their lower speed, KVSSDs present us with a new, powerful interface; one that can find and clean data at our command,
inside the disk itself, and without copies to and from the host system.

This work first introduces Dotori, a KVSSD-based key-value store that introduces a new KVSSD-specific index called the OAK-Tree, which uses
the KVSSDs ability to place and find data for us to greatly reduce the penalty of index persistence.

Then, we focus on a major downside of some KVSSDs; small value support. We solve this problem at the flash translation layer, obviating the
need for users to maintain a host side index for efficient small value performance alone. We call this flash translation layer \textit{Plus}.

The combination of Dotori in the host system and Plus in the KVSSD results in a robust and efficient KVSSD KV storage system that
touches both the top and the bottom of the storage stack.

국문 초록 (Abstract)

디스크 내에서 키-밸류 데이터를 찾기 위한 인덱스를 유지하는 대신 호스트 시스템 내에서 인덱스를 유지하는 키-밸류 SSD (KVSSDs)는 스토리지 스택 설계에서 급진적인 변화를 나타냅니다. 키-밸류 SSD의 목표는 고귀하며, 키-밸류 쌍 인덱싱을 위해 호스트 시스템으로의 데이터 전송을 제거하는 것입니다. 그러나 현재 이용 가능한 KVSSD는 제한된 기능 세트를 지원하며 현대 블록 장치보다 속도가 느립니다.

느린 속도에도 불구하고 KVSSD는 강력한 인터페이스를 제공합니다. 이는 호스트 시스템으로의 복사 없이 디스크 내부에서 데이터 찾기와 정리를 할 수 있습니다.

이 연구는 먼저 Dotori를 소개합니다. 이는 KVSSD 기반 키-밸류 저장소로, KVSSD의 인덱스 유지 비용을 크게 줄이기 위해 KVSSD의 데이터 배치 및 찾기 능력을 사용하는 OAK-Tree라는 새로운 KVSSD 전용 인덱스를 도입합니다.

그 후, 몇몇 KVSSD의 주요 단점인 작은 밸류 지원에 집중합니다. 우리는 이 문제를 플래시 변환 계층에서 해결하여 사용자가 효율적인 작은 밸류 성능을 위해 호스트 측 인덱스를 유지할 필요가 없도록 합니다. 우리는 이 플래시 변환 계층을 \textit{Plus}라고 부릅니다.

호스트 시스템의 Dotori와 KVSSD의 Plus의 조합은 스토리지 스택의 상단과 하단 모두에 걸친 견고하고 효율적인 KVSSD 키-밸류 저장 시스템을 제공합니다.

목차 (Table of Contents)

• Abstract i
• Acknowledgements 1
• Chapter 1 Introduction 3
• 1.1 Thesis Organization 4
• 1.2 Contributions 5
• Chapter 2 Dotori: A Key-Value SSD Based KV Store 6
• 2.1 Introduction 6
• 2.2 KVSSDs and the KV Interface 8
• 2.2.1 The KV Interface 8
• 2.2.2 Why is the KV Interface Better for KV Stores? 9
• 2.2.3 KVSSD Performance Characteristics 12
• 2.2.4 The Different Types of KVSSD 14
• 2.2.5 Discussion 15
• 2.3 Dotori 16
• 2.3.1 Overview 16
• 2.3.2 Indexing 17
• 2.3.3 Read and Write Paths 23
• 2.3.4 Dotori Features 25
• 2.4 Evaluation 31
• 2.4.1 Experiment Setup 31
• 2.4.2 OAK-Tree Performance 33
• 2.4.3 Dotori Performance 36
• 2.4.4 Tradeoffs and Limitations 41
• 2.5 Discussion 44
• 2.6 Related Work 45
• 2.7 Conclusion 47
• Chapter 3 A Hash-Based Key-Value SSD FTL With Efficient Small-Value Support 48
• 3.1 Introduction 48
• 3.2 NVMeVirt 51
• 3.3 Demand Based KVSSD FTL 52
• 3.3.1 Original Implementation 52
• 3.4 Plus 55
• 3.4.1 Plus Part One - Enabling Smaller Grains 55
• 3.4.2 Plus Part Two - Reduced Mapping Table Size 58
• 3.5 Evaluation 60
• 3.5.1 Machine and NVMeVirt Setup 60
• 3.5.2 Workloads 61
• 3.5.3 CPU Adjustments 61
• 3.5.4 YCSB 62
• 3.6 Plus Tradeoffs 67
• 3.7 Related Work 68
• 3.8 Conclusion 69
• Chapter 4 Conclusion 70
• 4.1 Summary 70
• 요약 72

참고문헌 (Reference)

1. Berkeley db. in, M. I. Seltzer, K. Bostic and, M. A. Olson, USENIX Annual Technical Conference, FREENIX Track, pp. 183–191, , 1999

2. Kv-ssd:What is it good for?, J. Bhimani, A. Maruf, M. P. Saha, B. S. Kim and, in 2021 58th ACM/IEEE Design Automation Conference (DAC), pp. 1105–1110, IEEE, , 2021

3. DotoriA key-value ssd based kv store, J. Shim, S.-H. Kim and, C. Duffy, J.-S. Kim, Proceedings of the VLDB Endowment, vol. 16, no. 6, pp. 1560– 1572, 2023, , 2023

4. Kvell+Snapshot isolation without snapshots, B. Lepers, W. Zwaenepoel, O. Balmau, K. Gupta and, 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI), pp. 425–441, , 2020

5. Benchmarking cloud serving systems with ycsb, A. Silberstein, E. Tam, R. Sears, R. Ramakrishnan and, B. F. Cooper, Proceedings of the 1st ACM symposium on Cloud computing, pp. 143–154, , 2010

6. KAMLA flexible high-performance key-value SSD, H.-W. Tseng, Y. Jin, S. Swanson, Y. Papakonstantinou and, in 2017 IEEE International Symposium on High Performance Computer Architecture (HPCA), pp. 373–384, IEEE, , 2017

7. Optimizing space amplification in rocksdb. in, T. Savor and, S. Dong, M. Strum, M. Callaghan, L. Galanis, D. Borthakur, CIDR, vol. 3, p. 3, , 2017

8. DynamoAmazons highly available key-value store, D. Hastorun, M. Jampani, G. Kakulapati, A. Pilchin, A. Lakshman, W. Vogels, G. DeCandia, S. Sivasubramanian, P. Vosshall and, vol. 41, no. 6, pp. 205–220, , 2007

9. HyperdexA distributed searchable key-value store, E. G. Sirer, B. Wong and, R. Escriva, Proceedings of the ACM SIGCOMM 2012 conference on Applications, technologies, architectures, and protocols for computer communication, pp. 25–36, , 2012

10. The log-structured merge-bush the wacky continuum, S. Idreos, N. Dayan and, Proceedings of the 2019 International Conference on Management of Data, pp. 449–466, , 2019

11. BetrfsA right-optimized writeoptimized file system, J. Esmet, W. Jannen, A. Akshintala, P. Reddy, P. Pandey, A. Mittal, Y. Zhan, J. Yuan, Y. Jiao, L. Walsh, et al., in 13th USENIX Conference on File and Storage Technologies (FAST), pp. 301–315, 2015., , 2015

12. Understanding manycore scalability of file systems, S. Kashyap, T. Kim, C. Min, S. Maass and, 2016 USENIX Annual Technical Conference (USENIX ATC 16), pp. 71–85, , 2016

13. Modernizing file system through in-storage indexing, J. Park, S. Lee, J. Koo, J. Song, J. Im, B. S. Kim and, E. Lee, 15th USENIX Symposium on Operating Systems Design and Implementation (OSDI), pp. 75–92, , 2021

14. RhikReconfigurable hash-based indexing for kvssd in, J. Bhimani, M. P. Saha, B. S. Kim, H. S. Gunawi and, Proceedings of the 32nd International Symposium on High-Performance Parallel and Distributed Computing, pp. 319–320, 2023, , 2023

15. Excessive ssd-internal parallelism considered harmful, J. Choi and, B. S. Kim, S. Pei, X. Zhang, in Proceedings of the 15th ACM Workshop on Hot Topics in Storage and File Systems, pp. 65–72, 2023, , 2023

16. Workload analysis of a large-scale key-value store in, B. Atikoglu, Y. Xu, M. Paleczny, E. Frachtenberg, S. Jiang and, Proceedings of the 12th ACM SIGMETRICS/PERFORMANCE joint international conference on Measurement and Modeling of Computer Systems, pp. 53–64, , 2012

17. AtlasBaidus key-value storage system for cloud data in, S. Jiang, C. Cui and, S. Lin, L. Yang, J. Cong, Z. Hou, C. Lai, G. Sun, 2015 31st Symposium on Mass Storage Systems and Technologies (MSST), pp. 1–14, IEEE, , 2015

18. NVMKVA scalable lightweight ftl-aware key-value store in, R. Rangaswami, S. Sundararaman, L. Marmol, N. Talagala and, 2015 USENIX Annual Technical Conference (USENIX ATC), pp. 207–219, , 2015

19. Apache flinkStream and batch processing in a single engine, A. Katsifodimos, V. Markl, S. Ewen, S. Haridi and, P. Carbone, K. Tzoumas, Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, vol. 36, no. 4, , 2015

20. KvrangedbRange queries for a hash-based key–value device, N. Reddy and, J. Lee, B. Settlemyer, F. Wen, Q. Zheng, P. Gratz, M. Qin, ACM Transactions on Storage, vol. 19, no. 3, pp. 1–21, 2023, , 2023

21. Reaping the performance of fast nvm storage with udepot in, K. Kourtis, N. Ioannou and, I. Koltsidas, 17th USENIX Conference on File and Storage Technologies (FAST 19), pp. 1–15, , 2019

22. BluecacheA scalable distributed flash-based key-value store, S. Xu et al., PhD thesis Massachusetts Institute of Technology, , 2016

23. FasterA concurrent key-value store with in-place updates in, B. Chandramouli, M. Barnett, J. Levandoski, J. Hunter and, D. Kossmann, G. Prasaad, Proceedings of the 2018 International Conference on Management of Data, pp. 275–290, , 2018

24. LightstoreSoftware-defined networkattached key-value drives, J. Im and, S. Lee, J. Koo, C. Chung, Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 939–953, , 2019

25. NvmevirtA versatile software-defined virtual nvme device in, I. Kang and, J.-S. Kim, J. Shim, E. Lee, S.-H. Kim, S. Jeong, 21st USENIX Conference on File and Storage Technologies (FAST 23), pp. 379–394, 2023, , 2023

26. WisckeySeparating keys from values in ssd-conscious storage, H. Gopalakrishnan, T. S. Pillai, A. C. Arpaci-Dusseau and, R. H. Arpaci-Dusseau, L. Lu, ACM Transactions on Storage (TOS), vol. 13, no. 1, pp. 1–28, , 2017

27. Transaction support using compound commands in key-value ssds, J. Kim, K. Jeong and, S.-H. Kim, J.-S. Kim, 11th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage), , 2019

28. al. PinkHigh-speed in-storage keyvalue store with bounded tails, J. Im, C. Chung, J. Bae, S. Lee et, in 2020 USENIX Annual Technical Conference (USENIX ATC), pp. 173–187, , 2020

29. LSB-Treea log-structured b-tree index structure for NAND flash SSDs, D.-H. Lee, B.-k. Kim and, Design Automation for Embedded Systems, vol. 19, no. 1, pp. 77–100, , 2015

30. Storage infrastructure behind facebook messagesUsing hbase at scale., K. Ranganathan, M. Bautin, L. Tang and, G. J. Chen, P. Damania, N. Spiegelberg, M. Vaidya, K. Muthukkaruppan, P. Khemani, A. S. Aiyer, IEEE Data Eng. Bull., vol. 35, no. 2, pp. 4–13, 2012., , 2012

31. ForestdbA fast key-value storage system for variable-length string keys, C. Seo, R. Mayuram, J.-S. Ahn, R. Yaseen, S. Maeng, J.-S. Kim and, IEEE Transactions on Computers, vol. 65, no. 3, pp. 902–915, , 2015

32. SpandbA fastcost-effective lsm-tree based kv store on hybrid storage in, Y. Xu, C. Li, X. Ma and, H. Chen, C. Ruan, 19th USENIX Conference on File and Storage Technologies (FAST 21), pp. 17–32, , 2021

33. SpdkA development kit to build high performance storage applications in, B. Walker, C. Liu, D. Verkamp, V. Verma and, J. Stern, G. Cao, L. E. Paul, J. R. Harris, C. Chang, Z. Yang, 2017 IEEE International Conference on Cloud Computing Technology and Science (CloudCom), pp. 154–161, IEEE, , 2017

34. SILKPreventing latency spikes in log-structured merge keyvalue stores in, F. Dinu, O. Balmau, D. Didona, K. Gupta, R. Chandhiramoorthi and, W. Zwaenepoel, 2019 USENIX Annual Technical Conference (USENIX ATC), pp. 753–766, , 2019

35. Towards building a high-performance scale-in key-value storage system in, Y.-s. Kee, Y. Kang, R. Pitchumani, P. Mishra, D. D. Lee, J. Lee and, F. Londono, S. Oh, Proceedings of the 12th ACM International Conference on Systems and Storage, pp. 144–154, , 2019

36. ilsm-ssdAn intelligent lsm-tree based key-value ssd for data analytics in, Y. Kim, S. Park, D. Park, K. Park, C.-G. Lee, W. Chung and, J. Noh, H. Kang, 2019 IEEE 27th International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems (MASCOTS), pp. 384–395, IEEE, 2019., , 2019

37. Kv-csdA hardware-accelerated keyvalue store for data-intensive applications in, D. Bonnie, B. Settlemyer, Q. Zheng, G. Grider, Y. Kim, S. Yang, W. Chung and, J. Lee, I. Park, D. Manno, 2023 IEEE International Conference on Cluster Computing (CLUSTER), pp. 132–144, IEEE, , 2023

38. PebblesdbBuilding key-value stores using fragmented log-structured merge trees, R. Kadekodi, I. Abraham, V. Chidambaram and, P. Raju, in Proceedings of the 26th Symposium on Operating Systems Principles (OSDI), pp. 497–514, , 2017

39. Characterizing modeling and benchmarking rocksdb key-value workloads at facebook in, S. Dong, Z. Cao, D. H. Du, S. Vemuri and, 18th USENIX Conference on File and Storage Technologies (FAST), pp. 209–223, , 2020

40. Empowering storage systems research with nvmevirtA comprehensive nvme device emulator, I. Kang and, S.-H. Kim, S. Jeong, E. Lee, J.-S. Kim, J. Shim, ACM Transactions on Storage, vol. 19, no. 4, pp. 1–26, 2023, , 2023

41. Isolating namespace and performance in key-value ssds for multi-tenant environments in, Y. Kim, D. Min and, Proceedings of the 13th ACM Workshop on Hot Topics in Storage and File Systems, pp. 8–13, , 2021

42. NvmedirectA user-space i/o framework for application-specific optimization on nvme ssds, H.-J. Kim, Y.-S. Lee and, J.-S. Kim, 8th USENIX Workshop on Hot Topics in Storage and File Systems (HotStorage),, , 2016

43. X-engineAn optimized storage engine for large-scale e-commerce transaction processing in, G. Huang, W. Cao and, T. Zhang, D. He, F. Li, Q. Li, Y. Wang, X. Cheng, S. Wang, J. Wang, Proceedings of the 2019 International Conference on Management of Data, pp. 651–665, , 2019

44. TRIADCreating synergies between memory disk and log in log structured key-value stores in, O. Balmau, A. Arora, P. Konka, K. Gupta and, D. Didona, W. Zwaenepoel, H. Yuan, R. Guerraoui, 2017 USENIX Annual Technical Conference (USENIX ATC), pp. 363–375, , 2017

45. A multi-tenant key-value ssd with secondary index for search query processing and analysis, W. Chung and, S. Lee, D. Min, K. Kim, C. Yun, C. Moon, A. Khan, Y. Kim, ACM Transactions on Embedded Computing Systems, vol. 22, no. 4, pp. 1–27, 2023, , 2023

46. Dftla flash translation layer employing demand-based selective caching of page-level address mappings, A. Gupta, Y. Kim and, B. Urgaonkar, Acm Sigplan Notices, vol. 44, no. 3, pp. 229–240, , 2009

47. What modern nvme storage can do and how to exploit itHigh-performance i/o for high-performance storage engines, V. Leis, G. Haas and, Proceedings of the VLDB Endowment, vol. 16, no. 9, pp. 2090–2102, 2023, , 2090

48. MatrixKVReducing write stalls and write amplification in lsm-tree based KV stores with matrix container in NVM in, J. Wan, X. He, C. Xie and, Y. Zhang, H. Jiang, T. Yao, Q. Cui, L. Tang, 2020 USENIX Annual Technical Conference (USENIX ATC), pp. 17–31, , 2020