The Log-Structured Merge tree (LSM-tree) transforms random writes into sequential writes to align with the characteristics of external storage devices and has become the core engine of modern key-value stores. However, fundamental issues such as write amplification and periodic performance degradation remain unsolved. Emerging storage devices like Non-Volatile Memory (NVM) and Zoned Namespace SSD (ZNS SSD) exhibit fundamental differences from traditional SSDs in aspects such as byte-addressability and sequential write constraints, making current LSM-trees ill-suited to fully exploit their hardware capabilities. In this paper, we propose ZQuery-LSM-tree, a novel design targeting hybrid storage systems composed of NVM and ZNS SSD. First, to address the high overlap ratio among L0 SSTables in the LSM-tree, we design an L0 layer reconstruction strategy based on extensible hashing, tailored to the sequential write constraint of ZNS SSD. Second, to mitigate write amplification caused by SSTable compaction operations, we propose an SST block construction strategy based on two-level three-bitmap encoding. Third, to alleviate performance degradation from SSTable proliferation in deeper levels, we design a low-I/O compaction strategy. Finally, we implement ZHashKV, a prototype key-value store built on the ZQuery-LSM-tree over hybrid storage media. Extensive evaluations using db_bench and YCSB show that, compared to ListDB, ZHashKV improves random write throughput by up to 38.1% and reduces write amplification by up to 56.8%.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

ZQuery-LSM-Tree for ZNS SSD

  • Tao Cai,
  • Danping Zou,
  • Dejiao Niu,
  • Zihao Yinyi,
  • Qiujing Huang,
  • Yikang Deng

摘要

The Log-Structured Merge tree (LSM-tree) transforms random writes into sequential writes to align with the characteristics of external storage devices and has become the core engine of modern key-value stores. However, fundamental issues such as write amplification and periodic performance degradation remain unsolved. Emerging storage devices like Non-Volatile Memory (NVM) and Zoned Namespace SSD (ZNS SSD) exhibit fundamental differences from traditional SSDs in aspects such as byte-addressability and sequential write constraints, making current LSM-trees ill-suited to fully exploit their hardware capabilities. In this paper, we propose ZQuery-LSM-tree, a novel design targeting hybrid storage systems composed of NVM and ZNS SSD. First, to address the high overlap ratio among L0 SSTables in the LSM-tree, we design an L0 layer reconstruction strategy based on extensible hashing, tailored to the sequential write constraint of ZNS SSD. Second, to mitigate write amplification caused by SSTable compaction operations, we propose an SST block construction strategy based on two-level three-bitmap encoding. Third, to alleviate performance degradation from SSTable proliferation in deeper levels, we design a low-I/O compaction strategy. Finally, we implement ZHashKV, a prototype key-value store built on the ZQuery-LSM-tree over hybrid storage media. Extensive evaluations using db_bench and YCSB show that, compared to ListDB, ZHashKV improves random write throughput by up to 38.1% and reduces write amplification by up to 56.8%.