本次分享的 Paper[1]：《KVSSD：Close integration of LSM trees and flash translation layer for write-efficient KV store》是在 18 年的 Design, Automation & Test in Europe Conference & Exhibition (DATE) 会议上呈现的 KVSSD，作者为：Sung-Ming Wu[2]、Kai-Hsiang Lin[3]、Li-Pin Chang[4]。

这篇 Paper 次要思路是在 SSD 上间接提供 KV 接口，将 LSM Tree 与 FTL 深度联合，从而防止从 LSM Tree，主机文件系统到 FTL 多个软件层的写入放大。跟大家分享这篇 Paper，一方面是蹭一蹭 KV 接口曾经胜利进入 NVMe 2.0 标准被标准化的热点，另一方面是为了和 TiKV / TiDB 的同学探讨将来存储硬件的更多可能性，心愿能带来一些启发。

本文将首先介绍问题的背景，什么是写放大，哪里产生了写放大，而后引出解决方案，介绍 KVSSD 做了哪些优化，之后再介绍 KVSSD 的性能评估数据，以及工业上的停顿。

背景

首先咱们来聊聊背景。这是一个 TiKV 的架构图：

咱们都晓得 TiKV 是一个分布式的 Key-Value 数据库，TiKV 的每一个节点都运行着一个 RocksDB 的实例，就像是这样：

RocksDB 基于 Log-structed merge-tree (LSM) 开发的，LSM tree 是目前业界使用最为宽泛的长久化数据结构之一。咱们要探讨的问题就是 LSM tree 在 SSD 上遇到的写入放大问题及其解决方案。

KV 存储系统中的写放大

从存储的视角来看，一个 KV 存储的软件堆栈大略是这样的：

最顶层是一颗 LSM tree，具体的实现就不开展了。大体的思路是在内存中保护可变的 Memtable，在 SSD 上保护不可变的 SSTable。Memtable 写满后会作为 SSTable 输出存储，而所有的 SSTable 会组合成一颗分层的树，每一层写满后就会向下一层做 compaction。LSM tree 保护过程中产生的 IO 会通过文件系统与 BIO 层的转换落到 SSD 上。

而后看一下文件系统。显然的，文件落到文件系统上必然会有一些额定的开销，比如说咱们须要保护文件的 Metadata。inode、大小、批改工夫、拜访工夫等都须要长久化。此外，文件系统须要可能保障在 crash 的时候不失落曾经写入的数据，所以还须要引入日志，写时复制这样的技术。

而后再来看看 SSD 这一层。一个典型的 NAND Flash 芯片通常由 package、die、plane、block 和 page 组成。package，又叫做 chips，就是咱们能在 SSD 上看到的颗粒。一个 pakage 通常由多层重叠而成，每一层就叫做一颗 die。一颗 die 外面会被划分为多个 plane，而每个 plane 外面会包含一组 Block，每个 Block 又能够进一步细化为 Page。其中 Block 是擦除动作的最小单位，通常是 128KB 到 256KB 不等，而 Page 是读取和写入的最小单位，通常为 2KB 到 32KB 不等。为了保护逻辑地址到物理地址的转换，SSD 中引入了 FTL。此外，FTL 还须要承当垃圾回收，坏块回收，磨损平衡等职责。

咱们晓得 SSD 设施的个性决定了它在写之前必须要进行擦除操作，设施须要将数据全副读到内存中批改并写回。为了平衡芯片损耗与性能，SSD 通常会抉择标记以后 block，寻找新的可用 block 来写入，由 FTL 来执行垃圾回收，这也就是咱们常说的 SSD Trim 过程。

从下面的剖析咱们不难察看到重大的写放大问题：

• LSM tree 的 compaction 过程
• 文件系统本身
• 块申请落到 FTL 上会呈现的 read-modify-write 过程
• FTL 的垃圾回收
• Paper 中没有思考文件系统自身的写放大，只取了剩下三点的乘积作为总体的写入放大率。写入放大显然是个坏东西，既加大了存储设备的磨损，又升高了写入的吞吐，这些因素最终都会反映到用户的总体持有老本上。

如何缓解写放大？

为了解决或者说缓解这个问题，大家提出过很多不同方向的计划。

比如说咱们能够对算法做一些革新，比方 LSM-trie[5]、PebblesDB[6] 或者 WiscKey[7]。WiscKey 大家可能比拟相熟一点，将 LSM tree 中的 Key 和 Value 离开存储，就义范畴查问的性能，来升高写放大。TiKV 的 titan 存储引擎、dgraph 开源的 badger[8] 还有 TiKV 社区孵化中的 Agatedb[9] 都是基于这个思路设计的。

或者咱们也能在文件系统这一层做些事件，比如说专门开发一个面向写办法优化的文件系统，缩小在日志等环节的写入 IO，比如说开启压缩比更高的通明压缩算法，或者面向 KV 的典型负载做一些优化和调参。

然而算法上和软件上的优化究竟还是有极限的，想要冲破就只能不做人啦，间接对硬件下手，从固件的层面进行优化。个别的来说，系统优化都有拆形象和加形象两个方向的优化。拆形象是指咱们去掉现有的形象，将更多的底层细节裸露进去，这样用户能够更自在的依据本人的负载进行针对性优化。加形象是指咱们减少新的形象，屏蔽更多的底层细节，这样能够针对硬件特点做优化。

存储系统的优化也不例外。

拆形象思路的先驱者是 Open-Channel SSD，它的思路是把固件里的 FTL 扬了，让用户本人来实现。这个思路是好的，然而 Open-Channel Spec 只定义了最通用的一部分，具体到厂商而言，他们思考到本人 SSD 的产品个性和商业秘密，往往抉择在兼容 Open-Channel Spec 的同时，再退出一些本人的定义。这就导致至今都没有呈现通用的 Open-Channel SSD 和针对业务的通用 FTL。对用户来说，并不通用的 Open-Channel SSD 带来了更重大的 vendor-lock 问题。所以 Open-Channel SSD 迟迟无奈失去大规模利用。

NVMe 工作组也看到了这样的问题，所以他们消化吸收了 Open-Channel 的精华，提出了 Zoned Namespace (ZNS) 的新个性。ZNS 将一个 namespace 下的逻辑空间地址划分为一个个的 zone，zone 当中只能进行程序写，须要显式的擦除操作能力再次进行笼罩写。通过这种形式 SSD 将内部结构的边界走漏给外界，让用户来实现具体的地址映射，垃圾回收等逻辑。

另一个思路是加形象，既然下层业务做不好这个事件，那就把它加到固件外面，硬件本人做。比如说在固件中间接实现 Key-Value 接口，或者应用计算型 SSD 将更多的计算工作下推到 SSD 上来做。

这里额定插一句感叹，三国演义开篇的“天下大势，分久必合，合久必分”真是太对了。软件定义存储倒退到当初，硬件厂商也不甘于成为纯正的供货商，他们也想退出到产业链上游，获取更多的利润。所以在存算拆散曾经成为大势所趋的时候，业界还孕育着一股存算交融的潮流：通过更正当更标准的形象，充分利用本人软硬一体的劣势，提供在提早和吞吐上更具劣势的产品。比方有音讯称三星开发中的 KVSSD 上搭载的芯片计算能力相当于两三年前的手机芯片。思考到 FPGA 和 ARM 这样精简指令集的芯片的继续倒退，置信这股潮流会带来更多零碎架构上的可能性。

KVSSD 设计

好的，回归正题。这篇 Paper 就是采纳了加形象的路线，在固件中间接实现 Key-Value 接口。

KVSSD 采纳了闪存原生的 LSM tree 实现，叫做 nLSM (NAND-flash-LSM)。nLSM tree 把 FTL 的 L2P(Logical To Physic) 层转换为了 K2P (Key To Physic) 映射，每个树节点都代表一个 SSTable 的 Key 范畴。nLSM tree 将整个闪存破费为元数据区和 KV 区，KV 区中存储排序后的 KV 对，元数据区中的每一页叫做元数据页，只蕴含指向 KV 页和键范畴的指针。

nLSM 使用了如下设计来优化写放大：

K2P Mapping

首先咱们来看一下 K2P 映射的设计。显然的，K2P 的抽象层次比 L2P 高很多，不可能在 SSD 的内存中间接存储所有 Key 对应的物理 Page。所以作者抉择了在 K2P 中应用 Key Range Tree 来存储 彼此不相交的 key-range 到 SSTable 的映射。nLSM tree 应用 Key Range Tree 来找到一个元数据页，而后应用元数据页中的 key range 信息来找到一个 KV 页，而后再从 KV 页中检索指标 KV 对。nLSM tree 给每个 SSTable 调配了一个闪存块，闪存块的大小是 4MB 跟 SSTable 的大小一样大，保障 SSTable 物理上间断且跟页面边界对齐。在 compaction 的时候，nLSM tree 会对旧的 SSTable 进行多向合并排序，并写入新的 SSTable，并抛弃旧的 SSTbale。之后的垃圾回收过程能够间接擦除这些块，不须要进行任何的数据复制。

Remapping Compaction

其次是 Remapping Compaction。

假如咱们当初 Key Range 被划分为 A 到 I 这几个区间。Ta 示意的是 Level i 层的数据，Tb 和 Tc 示意 Level i+1 层的数据，当初咱们要进行 Compaction 的话，就须要以某种模式将 Ta 中的数据塞进 Tb 和 Tc。Tb 和 Tc 组成一一组区间间断的 Key，而 Ta 跟他们都有一些重叠的中央。如果依照传统的形式重写这些 Page 的话，咱们须要写 12 个 KV page，再加上 3 个 metadata page。然而在 Remapping Compaction 中，会抉择从新写 Tx、Ty、Tz 三个 metadata page 别离指向曾经存在的 KV Page。这样就把重写 page 的代价从 15 升高到了 3。

Hot-cold Separation

最初是冷热拆散。显然的，高效的垃圾回收依赖数据分布的特色。如果绝对较冷的数据能散布在一起，防止反复的 gc 热数据，能够极大的升高 gc 的写入放大。在 LSM tree 的写入模型当中，下层总是比上层的数据要小，换句话来说，下层的数据参加 gc 更多、更频繁。不同档次的数据有着不同的生命周期。基于这样的个性，有一个可能优化是在垃圾回收迁徙数据的时候，尽可能的在同一级别的 KV 页中写入数据，这样能保障类似寿命的页面能被分组到类似的区块中。

KVSSD 性能剖析

接下来咱们看看 Paper 的性能剖析环节。这篇 Paper 次要波及三个性能方面的因素：写放大、吞吐和读放大。试验中应用的 SSD 设施是 15GB，5% 是保留空间，page size 是 32KB，block size 是 4MB。试验的办法是应用 blktrace 记录 leveldb 的 block I/O trace 而后在 SSD 模拟器上重放来收集闪存的操作数据。别离比照了

• LSM: 基于 leveldb
• dLSM: 一种 delay compaction 的优化
• lLSM: 一种轻量级 compaction 的优化
• nLSM
• rLSM(-): nLSM with remapping compaction
• rLSM: nLSM with remapping compaction and hot-cold sparation

依据这一组图能够看到，在给定的测试条件下 rLSM 能将写放大升高至原来的 12%，同时将吞吐晋升了 4.47 倍，然而带来了 11% 的读放大。

好，到这里咱们这篇 paper 的整体思路就曾经介绍完了。咱们来回顾一下 KVSSD 的价值，首先最显著的是 KVSSD 能带来更小写入放大，能够进步吞吐，进而升高 TCO，合乎当初业界降本增效的潮流。其次从零碎架构设计的角度上来看，KVSSD 可能进一步的将 I/O Offload 到 SSD 设施上。以 rocksdb 为例，应用 KVSSD 能升高 rocksdb 的 compaction 和 log 开销。此外，SSD 的计算能力实际上是在逐渐晋升的，将来能够在 SSD 中进行压缩，加密，校验等一系列重计算的工作。这些都为架构提供了新的可能性。

KVSSD 在工业上的停顿

最初咱们来看看业界的跟进状况。

在 2019 的 SYSTOR 会议上，三星沿用这一思路，发表了论文 Towards building a high-performance, scale-in key-value storage system[10]，在论文中提到三星与 SNIA 联手制订了 Key Value Storage API 标准，基于现有的 Block SSD 实现了 KV-SSD 的原型：

还发表了公开的 KVSSD 相干的 API 与驱动：

https://github.com/OpenMPDK/K…

依据三星论文中的剖析来看，KV-SSD 展示了十分强的线性扩大能力，随着设施数量的减少，零碎整体的 TPS 成线性增长，根本不受 CPU 的限度，感兴趣的同学能够找来看看。

这里我补充一下，三星的 KV-SSD 跟本次分享的论文只是大体思路雷同，具体的设计和实现上还是有很大差别。

在 2021 年 6 月公布的 NVMe 2.0 标准中，KVSSD 相干的指令集曾经被规范化为 NVMe-KV 指令集，成为新的 I/O 命令集之一，容许应用 Key 而不是 Block 地址来拜访数据。思考到业界对 NVMe 标准的广泛支持，预计齐全反对 NVMe 2.0 的 SSD 很快就有商用的产品上市，心愿大家放弃关注。

Q&A

业界更关怀 ZNS 还是 KVSSD？

ZNS 实现上要比 KVSSD 容易的多，老本也比 KVSSD 更好管制，所以目前业界对 ZNS 还是更热心一点。

KVSSD 冷热拆散的设计是不是会导致 Block 擦写不平衡？

是的，论文外面没有开展阐述相干的细节。依照目前这样的设计的确会导致这个问题，须要在实现的时候讲磨损平衡的问题也思考进来。

KVSSD 须要占用宿主机的内存和 CPU 吗？

不须要，KVSSD 自带独立的内存和解决芯片，不依赖宿主机的资源。这也是应用 KVSSD 的意义之一：咱们能够将这部分的负载 Offload 到 SSD 上，使得繁多宿主机上能够接入更多的设施。

援用链接

[1] IEEE: https://ieeexplore.ieee.org/d…

[2] Sung-Ming Wu: https://ieeexplore.ieee.org/a…

[3] Kai-Hsiang Lin: https://ieeexplore.ieee.org/a…

[4] Li-Pin Chang: https://ieeexplore.ieee.org/a…

[5] LSM-trie: https://www.usenix.org/confer…

[6] PebblesDB: https://www.cs.utexas.edu/~vi…

[7] WiscKey: https://www.usenix.org/confer…

[8] badger: https://github.com/dgraph-io/…

[9] Agatedb: https://github.com/tikv/agatedb

[10] Towards building a high-performance, scale-in key-value storage system: https://dl.acm.org/doi/10.114…

作者

丁皓 青云科技存储工程师