Design and Implementation of SCM and SSD Based Key-Value Store

doi:10.3778/j.issn.1002-8331.2008-0467

Abstract

Abstract:

Storage Class Memory（also called Non-Volatile Memory） has many advantages like high throughput and byte-addressability which is beneficial to designing of storage system. In order to combine the merits of SCM and SSD, a hybrid and efficient key value storage system based on SCM and SSD named SSHKV（SCM and SSD Hybrid Key-Value store） is designed. SSHKV stores key and metadata in SCM, and stores value in the SSD by log-structured format to achieve the balance between performance and capacity. Besides, SSHKV adopts strategy called logical space amplification to reduce the valid data migration while Garbage Collection（GC） by mapping the invalid pages which is reclaimed by TRIM instruction to new logical space. According to the evaluation, the random write throughput of SSHKV is 20 times better than LevelDB, a currently popular key-value store engine based on LSM-Tree.

Key words: key-value store, Storage Class Memory（SCM）, solid state storage, Log-Structured Merge Tree（LSM-Tree）

摘要：

具有高性能以及非易失特性的SCM（Storage Class Memory，存储级内存）技术逐渐成熟并开始运用到存储系统设计中，而传统的SSD仍然在存储容量上具有优势，为键值存储系统提供大容量存储的支持。现有键值存储系统不能充分发挥SCM与SSD混合存储架构的优势，需要对数据布局以及系统结构进行重新设计。针对SCM和SSD的特点，设计了基于SCM与SSD的混合式高效键值存储系统（SCM and SSD Hybrid Key-Value store，SSHKV）。SSHKV通过将键值存储中元数据信息存储到SCM中，将数据部分以日志方式存储到SSD中，实现性能与容量的兼顾。在SSD空间管理上，SSHKV采用逻辑空间放大策略，通过重映射TRIM指令释放的无效空间，减小了垃圾回收带来的数据迁移开销。SSHKV基于半异步半同步式IO模型实现，经过对比测试，SSHKV的随机写入性能相较于传统基于LSM-Tree的LevelDB提升了约20倍。

关键词: 键值存储, 存储级内存, 固态存储, 日志结构合并树

ZHAN Ling, ZHANG Yiwen. Design and Implementation of SCM and SSD Based Key-Value Store[J]. Computer Engineering and Applications, 2021, 57(19): 97-103.

詹玲，张艺文. 基于SCM与SSD的混合高效键值存储系统研究[J]. 计算机工程与应用, 2021, 57(19): 97-103.

References

[1] GANTZ J，REINSEL D.The digital universe in 2020：Big data，bigger digital shadows，and biggest growth in the far east[J].IDC iView：IDC Analyze the Future，2012（12）：1-16.
[2] WONG H S P，RAOUX S，KIM S B，et al.Phase change memory[J].Proceedings of the IEEE，2010，98（12）：2201-2227.
[3] BAEK I G，LEE M S，SEO S，et al.Highly scalable nonvolatile resistive memory using simple binary oxide driven by asymmetric unipolar voltage pulses[C]//IEEE International Electron Devices Meeting，2004：587-590.
[4] XIA F，JIANG D，XIONG J，et al.HiKV：A hybrid index key-value store for DRAM-NVM memory systems[C]//2017 USENIX Annual Technical Conference，2017：349-362.
[5] CHANG F，DEAN J，GHEMAWAT S，et al.Bigtable：A distributed storage system for structured data[J].ACM Transactions on Computer Systems（TOCS），2008，26（2）：4.
[6] LevelDB[CP/OL].（2014-08-27）[2020-07-31].https：//github.com/google/leveldb.
[7] LAKSHMAN A，MALIK P.Cassandra：a decentralized structured storage system[J].ACM SIGOPS Operating Systems Review，2010，44（2）：35-40.
[8] GEORGE L.HBase：The definitive guide：random access to your planet-size data[M].[S.l.]：O’Reilly Media，Inc，2011.
[9] RocksDB[CP/OL].（2012-11-30）[2020-07-31].https：//github.com/facebook/rocksdb.
[10] COOPER B F，RAMAKRISHNAN R，SRIVASTAVA U，et al.PNUTS：Yahoo!’s hosted data serving platform[J].Proceedings of the VLDB Endowment，2008，1（2）：1277-1288.
[11] Riak[CP/OL].（2010-04-16）[2020-07-31].https：//github.com/basho/riak_kv.
[12] O’NEIL P，CHENG E，GAWLICK D，et al.The Log-Structured Merge-tree（LSM-tree）[J].Acta Informatica，1996，33（4）：351-385.
[13] LU L，PILLAI T S，GOPALAKRISHNAN H，et al.Wisckey：Separating keys from values in ssd-conscious storage[J].ACM Transactions on Storage（TOS），2017，13（1）：1-28.
[14] CHAN H H W，LIANG C J M，LI Y，et al.HashKV：Enabling efficient updates in {KV} storage via hashing[C]//2018 USENIX Annual Technical Conference，2018：1007-1019.
[15] YAO T，WAN J，HUANG P，et al.A light-weight compaction tree to reduce I/O amplification toward efficient key-value stores[C]//Proceedings of the 33rd International Conference on Massive Storage Systems and Technology，2017.
[16] KANG J U，HYUN J，MAENG H，et al.The multi-streamed solid-state drive[C]//Proceedings of the 6th USENIX Workshop on Hot Topics in Storage and File Systems，2014.
[17] YANG F，DOU K，CHEN S，et al.Optimizing NoSQL DB on flash：A case study of RocksDB[C]//2015 IEEE 12th International Conference on Ubiquitous Intelligence and Computing and 2015 IEEE 12th International Conference on Autonomic and Trusted Computing and 2015 IEEE 15th International Conference on Scalable Computing and Communications and its Associated Workshops，2015：1062-1069.
[18] 刘峪竹.基于SSD的Key-Value系统优化设计与实现[D].长沙：国防科技大学，2014.
LIU Y H.Research and implementation of strategies to optimize the SSD-based Key-Value system[D].Changsha：National University of Defense Technology，2014.
[19] BJ?RLING M.Open-channel solid state drives[J].Vault，2015，12：22.
[20] WANG P，SUN G，JIANG S，et al.An efficient design and implementation of LSM-tree based key-value store on open-channel SSD[C]//Proceedings of the Ninth European Conference on Computer Systems，2014：1-14.
[21] KANNAN S，BHAT N，GAVRILOVSKA A，et al.Redesigning LSMs for nonvolatile memory with NoveLSM[C]//2018 USENIX Annual Technical Conference，2018：993-1005.
[22] KAIYRAKHMET O，LEE S，NAM B，et al.SLM-DB：Single-level key-value store with persistent memory[C]//Proceedings of the 17th USENIX Conference on File and Storage Technologies，2019：191-205.