【论文阅读】存储在spdk与新硬件设备的探索汇总

穷则软件优化，达的硬件堆积，本文主要介绍存储领域在硬件方向的一些探索。硬件方向的探索又分为大体两块，对现有硬件的性能压榨，以及新硬件设备的创新。对现有硬件的压榨主要是 SPDK RDMA，通过by pass驱动层来最大限度利用硬件的性能。新硬件的探索则包含了傲腾持久化内存和KV-SSD两块。其中持久化内存目前有些云厂商已经投入了使用，KV-SSD 则目前主要还是在学术理论阶段，业界未看到大规模的使用。
以下几篇论文分别介绍了在 SPDK KV-SSD方向的一些研究。
SpanDB: A Fast, Cost-Effective LSM-tree Based KV Store on Hybrid Storage 介绍了在SPDK的探索。
Towards Building a High-Performance, Scale-In Key-Value Storage System 是三星发布的介绍了他们最新的产品KV-SSD的论文，介绍了KVSSD 这种新型存储在kv的应用。
PinK: High-speed In-storage Key-value Store with Bounded Tails 则针对现在一些KVSSD实现的缺点做了优化，提出了一种针对KVSSD 优化的变种LSM 实现。
下文将非常对这三篇论文进行展开做详细的介绍。

本文主要介绍了如何基于 SPDK 构建LSM-tree Based KV Store。传统的kv实现需要通过调用文件系统层最后才会达到磁盘 ，对于 Nvme SSD 这种高性能设备，传统的io链路无法完全发挥硬件的性能，通过SPDK ByPass驱动层直接操作裸盘则可以将硬件性能发挥到极致。

使用SPDK对WAL进行并发写入，可以大大提升写入性能，支持异步请求处理，减少线程切换的开销。测试表明，对于小value写入，绕过ext4文件系统直接通过SPDK进行写入可以降低6.8-12.4倍的延时。由于WAL 处于关键路径上，这会对写入带来严重的性能开销导致性能瓶颈。其次，现在的kv架构都是假设磁盘设备速度较慢，因此设计上通常都嵌入了较高的软件开销，如果基于轮训的机制则会比较浪费cpu周期。本文基于rocksdb做了如下的优化:

多线程排队写入，有队列头部的线程直接获取当前的写入任务进行提交，可以做写入io合并，提升写入性能。如果写请求已经被提交，队列中部的请求发现已经完成写请求后直接返回，无需在进行io操作，通过group write，将大量的小io转化成顺序大io。

随着io设备性能的提升，linux io协议栈的开销变得不可忽视，通过SPDK将 驱动移动用户态，减少了系统调用并且支持zore copy，通过poll的方式而不是中断的方式进行io操作，减少了内核态的切换和io路径锁争用。同时这个章节对 Optane P4800x和P4610 两种设备进行了压测对比，简单列下压测结果。

图3的N 表示 P4610 0表示Optane 3-N 表示3个线程写入，CR=2 表示每个线程同时提交2个请求

可以看出使用多线程的SPDK 可以大大发挥磁盘性能

一旦进程绑定了SPDK，该磁盘就不能被其他进程访问，无论是通过io栈还是spdk。此外绑定cpu核心可以降低io的性能开销。加上polling-based io机制，导致后台的flush和compact线程不适合使用spdk进行读写，因为如果不绑核，会导致 io变慢，如果绑核了，则难以释放cpu空闲资源。

对于rocksdb和leveldb，前台的client写入通常都是同步的，用户同步提交读写请求然后等待io操作完成后返回，这种操作 通常会受限于io的延时导致吞吐的不足，为了提高吞吐，用户通常会设置超过cpu核心数的线程来进行并发的操作。但是对于使用了SPDK 的高速nvme，线程间的同步唤醒往往开销比io请求本身还大，超线程机制会带来额外的开销和降低了cpu的使用率。（好比redis 内存处理足够快，不需要多线程进行处理，多线程主要带来额外的开销争用）

对于一个n-core的机器，spandb配置Nc和线程数用于处理用户请求同时 进行了绑核，剩下的n-Nc个核心则用于处理内部的io请求，分为loggers和workers。loggers用于处理wal的写入 ，workers用于处理后台的flush和compaction以及memtable的读取和更新操作。

后台线程使用Qflush和Qcompact队列进行flush和compact操作，继承于rocksdb的实现，只是改为了直接操作SPDK
使用Qread队列来处理读请求，写请求则被拆分为Qprolog Qlog和Qepilog三个队列

基准压测表明，少数的几个核通过批量提交请求就可以充分利用磁盘的io，因此spandb默认使用了一个logger线程进行wal的写入，该线程数量可以动态在1-3之间调整，根据队列的长度和处理耗时动态调整线程数。对于前后台线程，优先保证前台线程的调度，同时会 监控后台队列的长度，以便在高负载写入的时候即使进行flush和compact。

为了减少对rocksdb本身的改动，抽象了一个TopFS 来管理spdk的相关操作。sst的数据布局与wal类似，也是通过metadata page管理，metadata page为hashtable，key为文件名，内容为文件对应的逻辑页起止id。

传统是kv存储实现，通常是存储引擎暴露kv接口，用户通过kv接口写入数据，key和value通过一定的数据结构被存储到文件里面，从用户调用接口到数据最终落到磁盘的整个流程可以用下图的左边部分来描述。

kv接口将数据写入文件系统，文件系统通过块设备驱动将数据写入磁盘，为了屏蔽磁盘的内部物理结构，文件系统到磁盘其实是通过LBA进行逻辑地址映射的，磁盘内部通过FTL将LBA转化为PBA，同时FTL还承担了磁盘的COW GC功能。可以看到从写入到落盘中间经历了非常多的环节。那么是否可以通过减少这些环节来进行写入流程的优化呢。比如上面提到的SPDK 通过bypaas文件系统少掉了一层文件系统的开销，那么是否还能更近一步呢。这篇论文正是基于这样想法，直接将kv的操作下层到设备层，由设备直接暴露了kv interface，直接bypass了设备层以及LBA到PBA的映射。通过设备内部的FTL ，直接实现了key到NAND location的映射。

设备暴露了put get delete iterate接口，kv请求通过pipeline的流程处理kv请求，固件驱动从磁盘io队列获取请求，然后传递给request handle，request handle再讲请求传递给index manager，index manager先将变长的key散列成定长的key缓存到local hashtable，最后在合并到全局的hashtable完成到磁盘位置offset的映射。同时index manager还会根据key的前4B进行分桶，通过将相同前缀的数据放在一起来实现迭代操作。local hashtable主要是为了提高写入并发减少全局hashtable的锁竞争。

垃圾回收时，垃圾回收器扫描flash中kv数据，然后和 全局hashtable做对比来判断数据的有效性，丢失已经被删除和更新的数据

性能测试部门主要测试了kvssd的cpu开销，在同样的ssd下，kvssd只需要一个线程就能达到与普通ssd8线程一样的io吞吐，同时，随着单机磁盘数量的提升，kvssd拥有更好的线性拓展能力。对于普通的ssd，单机的吞吐受限于cpu无法随着磁盘数量程线性增长，而kvssd由于极低的cpu开销可以提供更高的单机吞吐能力，对于昂贵的机柜资源，如果能在单机插更多的磁盘提供更高的吞吐显然是更经济的。

其实kvssd之所以需要更低的cpu开销，除了bypass了很多层，更重要的部分是他的固件模块其实已经有点类似于一个小型的cpu了，通过把cpu的工作offload到固件本身的做法在业界由来已久，比如将网络包的解析的bypass 内核offload到网卡直接进行。

虽然使用KV-SSD可以带来延迟的降低和吞吐的上升，但是这个降低只是针对平均值，目前现在大多数的KV-SSD的实现都存在一个长尾的问题。最常见的KV-SSD的实现包括hash-based KV-SSD 和LSM-tree Based KV-SSD，但是这两种实现都存在长尾的问题。

此外，控制器内部的DRAM和FLASH 的发展速度也不一样，平均每年DRAM增长1.13倍但是FLASH则增长了1.43倍，随着DRAM的增长，FLASH的需求将越来难以满足使用，因此设计一个减少FLASH使用的数据结果是势在必行的

总体架构的实现如下图，由于pink是LSM 的改进版本，此处会将pink的数据结构和rocksdb进行比较。pink的存储结构可以分为4部分，分别是 SkipList、 levelList 、meta segment 和data segment。

上面提到skiplist和levellist都存在FLASH 当中，那么FLASH 是否有足够的容量容纳这些levellist呢？对于一块4T 的磁盘，假设key value大小分别为32B和1KB，page的大小为16KB，那么对于一个16KB的meta segment，可以容纳的<k,v>pair数量为398个，对于4T的磁盘总共可以存储2^32个1KB大小的数据，也就是总共需要10.8M个meta segment，那么对于levelist来说需要占用的DRAM空间则为（32B+8B）* 10.8M = 432M 的内存空间。显然控制器的DRAM是够用的。

写入流程很简单，用户写入的数据会直接写入到skiplist中，熟悉LSM的人可能发现了，传统的LSM 写入为了保证数据的可靠性，都会先写入WAL 然后在写入内存memtable，但是此处并没有WAL而是直接写入skiplist会不会有问题呢。这个主要得益于磁盘控制器的自带的电容器，通过电容器可以保证断电数据不丢失，因此可以省掉一次的WAL写入

相比写入，读取流程则显得比较繁琐，以下图的查询key(39)为例。

从上面的读流程可以看到，对于极端的情况，一次的查询可能涉及非常多次的FLASH读取，比如上面的流程就需要读取metaPage0 metaPage2以及最终value所在的datapage12。对于level更多的场景需要读取FLASH 的次数将更多。
level Pinning的思路很简单，就是把meta segment尽可能的放在FLASH，这样就可以减少FLASH的读取了。那么问题来了，FLASH能放的下这么多的meta segment么。
同样直接对数据进行分析计算，由于LSM 的指数分层存储机制，每个Ln+1 层的数据都是Ln层的T倍，对于4T的磁盘，实际数据表明总共需要的存储层级为5级，对与L1到L4的层级分别需要的meta segment为0.91MB 50.86MB 2.83GB 161.3GB.由于一块4T的SSD 通常有4G的FLASH，那么显然是可以把L1到L3的meta segment放到FLASH里面的。
把metasegment放到了FLASH里面还带来了一个额外的好处，就是compaction的开销也随之降低的。因为L1到L3的meta 都在FLASH，可以大幅减少compact时meta更新带来的开销。

优化查找路径使用了级联的方法，简单说就是每一层的kv额外存储指向下一层的指针，其实就是类似skiplist的实现。通过级联的方法，当查询一个key的时候可以缩小每次二分查找的边界。查询Ln层的时候，先找到这个key的上下边界，如果Ln不满足，则根据上下边界直接定位到Ln+1 的上下边界，而无需对整个Ln+1进行二分查找。

级联需要额外的8字节指针开销，由于最后一层不需要存储级联指针，因此总共增加的级联指针开销为43.9M， FLASH 依然是够用的。
不过这里有一个问题论文里没说清楚，当Ln+1由于compaction更新以后，如何去更新Ln的级联指针，考虑到由于levellist都在FLASH中，这里去更新上层的级联指针的开销是可以接受的。

简单概括就是硬件加速，把计算逻辑offload到FPGA来实现硬件加速，达则堆积硬件。

gc优化包含meta segment的GC以及data segmetn的GC。

通过metapage的start从levelList中查询是否还有指针指向page，如果没有则直接回收，否则将数据迁移到空闲的page，然后修改levelList中的指针。由于上层的meta可以通过DRAM直接进行复制更新，因此开销是很低的

遍历需要回收的page逐条读取kv信息，根据key查询判断该数据是否还有效，如果失效了直接忽略，否则则需要对该value进行rewrite。对于rewrite，最简单的实现是参考wisckey，直接更新meta 中的value指针，如果meta segment是保存在DRAM中的那没有任何问题，但是如果meta page是在FLASH中的，由于越底层的数据都是旧数据，因此一个data segment的数据在meta 中往往很离散，这时更新meta的指针会带来meta segment的写放大，为了避免这个问题，pink对于存在FLASH的meta segment使用了延时更新，compact的时候直接把kv写入到L0进行覆盖，对于该kv由于读取是从上往下的，因此读取流程不会存在任何问题，metasegment的数据则可以等待meta指针失效的时候进行删除。

新硬件探索，硬件加速是今后存储发展的一个重要方向，同时随着新硬件的出现，现有的数据结构可能并不适合新硬件的的特性。从HDD 到SDD再到NVMe，硬盘性能不断升级，业界也针对SSD做了大量的存储优化。英特尔最新推出的PMEM则对存储又是一次大的革新，对于PMEM现在的文件系统其实已经不太合适了，因此也有针对该方面的优化 Rethinking File Mapping for Persistent Memory 。至于KVSSD，在该几篇论文后目前则又有了一些新的进展，NVMe 2.0 规范已经将KVSSD的指令集规范为NVMe-KV 指令集，因此KV-NVMe应该也不远了。

Reference:

https://github.com/OpenMPDK/KVSSD
Rethinking File Mapping for Persistent Memory
SpanDB: A Fast, Cost-Effective LSM-tree Based KV Store on Hybrid Storage
Towards Building a High-Performance, Scale-In Key-Value Storage System
PinK: High-speed In-storage Key-value Store with Bounded Tails
https://unix.stackexchange.com/questions/106861/what-is-the-relationship-of-inodes-lba-logical-volumes-blocks-and-sectors