我们认为基于LSM树的NVM KV存储系统的性能瓶颈主要源于数据序列化/反序列化开销，以及内存到磁盘的数据flush和磁盘上的数据合并速度的不平衡。为此，我们提出了一种基于LSM树的新型键值存储系统（名称为MioDB），使用持久性跳表来替代LSM树的盘上数据结构，并设计了四种新技术来充分利用快速NVM。实验研究表明，与最先进的NoveLSM和MatrixKV相比，MioDB表现出更低的长尾延迟和更好的吞吐量。

该成果“Revisiting Log-structured Merging for KV Stores in Hybrid Memory Systems” 发表在CCF列表A类国际学术会议International Conference on Architectural Support for Programming Languages and Operating Systems 2023（ASPLOS’23）上。ASPLOS是计算机系统研究领域顶级国际会议。MioDB代码已发布在实验室的开源社区中。

• 论文链接: https://dl.acm.org/doi/abs/10.1145/3575693.3575715

• 项目链接：https://github.com/CGCL-codes/mioDB

我们通过实验研究发现，使用NVM的基于LSM树的KV存储的性能瓶颈主要源于：(1)跨内存和存储的代价高昂的数据序列化/反序列化；(2)内存到磁盘的数据flush和磁盘上的数据合并速度不平衡。由于写停滞和写放大，它们可能导致不可预测的性能下降。为了解决这些问题，我们提出了一种基于LSM树的新型键值存储系统（MioDB），提倡用字节可寻址的持久性跳表来替代LSM树的盘上数据结构，并设计了四种新技术来充分利用快速NVM。实验研究表明，与最先进的NoveLSM和MatrixKV相比，MioDB的99.9th延迟分别降低了17.1倍和21.7倍，随机写吞吐量分别提高了8.3倍和2.5倍，写放大率分别降低了5倍和4.9倍。

LSM树是一种基于块的写友好型数据结构，在许多流行的 KV 存储中都有实现，例如 LevelDB、RocksDB和 PebblesDB。以典型的LevelDB为例，其在快速易失性DRAM中的排序跳表（称为MemTable）中缓冲KV更新，然后在称为排序字符串表（SSTable）的多级磁盘数据结构中存储KV对。跳表是一种多维链表，无需遍历链表中的所有元素即可实现快速搜索和就地更新。使用跳表来分阶段写入MemTable是基于LSM树的KV存储的常用方案。为实现故障恢复，KV对在写入MemTable之前应首先追加到先写日志（WAL）中。当MemTable已满时，LevelDB会使其不可变，并创建一个新的MemTable。后台线程会将不可变MemTable中的数据flush到磁盘上的SSTable中。通过这种方式，LSM树将随机写入转换为块设备上的批量顺序写入，从而优化了KV存储的写入性能。LSM树中的每一级容量都有限，但下一级包含的SSTable是上一级的10倍。当一个层的大小超过其极限时，SSTables将从层