SpanDB: A Fast, Cost-Effective LSM-tree Based KV Store on Hybrid Storage 主要探讨了当前新的 NVMe SSD 等快速设备情况下，基于 LSM-tree 的 KV 存储（以 RocksDB 为例）的性能优化问题。
背景
最新的 SATA Revision 3.4 理论带宽上限为 6Gbps，目前的 NVMe SSD 顺序读性能可以轻松超过 2GBps。随着 SSD 技术的发展，现有的基于慢速磁盘设备的存储引擎设计需进行相应的改进。
在慢速设备的时代，我们通常使用多线程技术，采用远多于 CPU 核心数的线程数量，尽可能避免慢速设备造成的较长时间的等待。进入 NVMe SSD 时代，在 SPDK 技术加持下，线程间的同步可能比 IO 本身更耗时。在这种情形下，传统的多线程 IO 技术在 IO 吞吐量、延迟和 CPU 资源利用上都不具备优势。
上图是 Intel Optane P4800X 分别通过 ext4 和 SPDK 进行读写的对比测试，RR、SR、SW 分别代表随机读、顺序读和顺序写。可以看到，在大批量的顺序读场景下，两者性能相当。其余场景 SPDK 性能，尤其是写性能均显著优异于 ext4。
上图是对 SATA SSD 和 NVMe SSD P4800X 的对比 4KB 顺序写入测试，N 代表 I SATA SSD Intel P4610，O 代表 NVMe SSD Intel Optane P4800X，1-N 代表 1 个线程写入 Intel P4610，CR=2 代表每个线程发起 2 个写请求。可以看到，NVMe SSD 可以提供更高的并发能力，多线程下的表现更好。实际上，即便是 NVMe SSD，超过 3 个写入线程并不会带来 IOPS 的提升。
在现有的 LSM-tree 存储引擎的基础之上，针对 NVMe SSD 的特性做了以下几点优化：
- 层次化的存储结构， NVMe SSD 作为 SD(Speed Disk)，SATA SSD 作为 CD(Capacity Disk)。
- 基于 SPDK 技术，结合 polling IO 模式的异步 IO 请求处理，实现对 SD 高效读写。
- 并行 WAL 写入。
- WAL 和顶部 level 数据存储在 SD。并根据 SD-CD 负载情况，动态分布 level 数据。
异步请求处理
如图所示，在一台具有 n 个 CPU 核心的机器上。基于每个线程占用一个 CPU 核心的原则，用户将客户端线程数配置为 N_client，内部线程数为 n - N_cllient。内部线程被划分为 logger 和 worker 两种角色，一个名叫 head-server thread 的管理线程会根据写入强度动态调整不同角色的内部线程数量。
为实现异步请求处理，在 RocksDB 已有的 flush 队列 Q_flush 和 compact 队列 Q_compact 基础上，SpanDB 引入了1个读取队列 Q_read 和3个用于写入的队列 Q_ProLog、Q_Log 和 Q_EpiLog。
读请求
client 线程会首先尝试进行 memtable 读取，如命中则可直接获取返回结果。如未命中，则将读取请求放入到 Q_read 中，随后通过获取请求状态接口获取结果。worker 线程会随后读取并执行 Q_read 中的读请求，并设置读取结果。
写请求
client 线程直接将写请求压入 Q_ProLog 队列，随后通过获取请求状态接口获取结果。worker 线程读取 Q_ProLog 写入请求，序列化得到 WAL entry 并压入到 Q_log。Q_ProLog 队列和 Q_Log 队列是设计用于实现 batched logging。logger 线程会一次性读取 Q_log 队列中所有的请求，执行 group logging，并将写入请求压入到 Q_EpiLog 队列。worker 线程会从 Q_EpiLog 线程读取请求，执行最终的 memtable 更新操作。
负载调度
为减少线程调度的上下文切换造成的不必要资源占用。SpanDB 默认启动 1 个 logger，根据写入负载在 1 - 3 个 logger 间浮动。基于前台任务优先的原则，根据写入队列的请求响应时间，SpanDB 也会控制相应队列的容量上限实现动态负载均衡。
基于 SPDK 的快速日志写入
SpanDB 的 WAL 写入依然采用了 group logging 机制。若干个 logger 线程从 Q_Log 获取能够读取的所有请求，并发地执行写入。
SpanDB 在 SD 的 WAL area 预先分配若干个逻辑 page，每个 page 有一个唯一的 LPN (Log Page Number)。其中一个 page 作为 metadata page。
若干个连续的 page 组成一个 log page group，每个 group 对应一个 memtable，容量足够容纳一个 memtable 的 WAL。当 memtable flush 完成后，log group 将会被回收重用。meta data page 记录每个 log page group 的起始 LPN。
SpanDB 配置了多个 logger 并发写入，每个 logger 有单独的 WAL data buffer。为实现并行写入，每个 logger 通过原子操作分配得到下一个写入位置。当 memtable 写满时，meta data page 会记录其对应的 log page group 结束 LPN。
Speed Disk 承担 LSM-tree 部分 level 负载
SpanDB 将顶部的部分 level 数据迁移到 SD 中，充分利用 SD 的硬件性能。
数据组织
为减少对 RocksDB 代码的侵入，在 SPDK I/O 的基础上，SpanDB 实现了一个简单的文件系统 TopFS。由于 LSM-tree level 的 append only 属性，文件系统的管理也类似于 WAL，由一个 metadata page 和若干个 data page 组成，metadata page 通过 hash table 记录每个文件的起始 LPN。
WAL 写优先
对于 KV 存储引擎，特别是 OLTP 场景，写入延迟对用户较为敏感。为了实现 WAL 优先写入，SpanDB 采取了3个措施：
- 专门的 logger 请求队列
- 将 flush/compaction 默认请求大小从 1MB 减小为 64KB
- 限制 flush/compaction 的 worker 数量
SPDK Cache
SPDK bypass kernel 的特点让 SPDK 无法使用系统的 page cache，无法充分利用局部性原理。在 TopFS 之上，SpanDB 实现了一个自有的 cache。在SpanDB 初始化时，会在 hugepage 中申请一大片内存用作 cache。一个 hash table 用于管理 cache entry，key 是 SST 文件名，value 是该文件包括的 block 对应的 cache entry。
动态 level 布局
head-server thread 监控 SD 的带宽使用情况，基于预设阈值调整 SST 文件的分配。由于顶部的 SST 文件在不停 merge，也为了避免 SD 和 CD 间数据迁移，SpanDB 调整的是新创建 SST 文件的位置。因此，相同 level 的文件可能会分布在不同的设备之上。
性能测试结果
YCSB 测试结果
| YCSB workload | 说明 |
|---|---|
| A | 50/50 reads and writes |
| B | 95/5 reads/write mix |
| E | short ranges of records are queried |
| F | the client will read a record, modify it, and write back the changes |
- 基于文件系统的顺序 log 写入不能充分发挥高端 SSD 的性能
- 除 read intensive 场景外，SpanDB 在不同的硬件组合下均可大幅度提升 IO 吞吐量和降低延迟
- 高端硬件在 SpanDB 上的收益更大
LinkBench 测试结果
SpanDB 相较于 RocksDB 也能显著改善性能，特别是高端硬件能获得更大的性能收益。
