FAST'20
Teng Zhang, Alibaba Group, Alibaba-Zhejiang University Joint Institute of Frontier Technologies, Zhejiang University; Jianying Wang, Xuntao Cheng, and Hao Xu, Alibaba Group; Nanlong Yu, Alibaba-Zhejiang University Joint Institute of Frontier Technologies, Zhejiang University; Gui Huang, Tieying Zhang, Dengcheng He, Feifei Li, and Wei Cao, Alibaba Group; Zhongdong Huang and Jianling Sun, Alibaba-Zhejiang University Joint Institute of Frontier Technologies, Zhejiang University
FAST最后一篇关于KV的文章，这是阿里与浙大的一个联合实验室做的通过FPGA优化LSM-Tree的compaction开销的一篇文章，主要是说现在存储设备的I/O性能越来越好，这就导致系统性能的瓶颈从IO转移到CPU上，LSM-Tree需要进行耗费大量CPU资源的compaction操作，并且在KV较小的时候CPU开销更大，与前台操作竞争CPU资源，从而影响前台的性能。为了解决这一问题，本文提出通过FPGA这一专用硬件，将compaction操作offload到FPGA上进行，以此来减少compaction争用前台操作的CPU资源而带来的性能问题。
本文的CPU成为瓶颈的背景问题在KVell中也有提到，KVell的做法是干掉了LSM-Tree的结构，换成了内存索引+单层存储的结构。
背景
- 前台的查询与事务操作与后台的compaction操作之间存在资源争用，compaction消耗较多的CPU与IO资源，尤其是在读写混合的workload下，这种争用更加明显。
从上图可以看到，compaction线程数在32左右，系统throughput达到最高，再继续增加线程数反而会使throughput降低，此时compaction线程占用了较高的IO和CPU资源。
因此本文提出通过将compaction移到别的地方做，来缓解CPU资源的压力
Motivation
当前的LSM-Tree based KV store在读写混合workload下性能下降的原因：
- 分散的L0
由于L0的table是直接从memtable dump下来的，所以table之间存在key range的重叠，查找L0需要查找所有的table，当compaction较慢的时候，L0的table堆积，使得查找L0耗时更多，而L0又是最新的数据，往往热度较高，因此对读写混合workload来说，无疑会影响性能。
- 瓶颈的转移
compaction操作主要流程为：decode，merge，encode，本文测试了三个阶段的开销：
从图中可以看出，当KV size较小的时候，消耗CPU资源更多，而当KV size超过128B之后，主要的开销在IO上，即当compaction小KV的时候，性能受CPU限制。
设计实现
本文的实现是集成到阿里另一篇文章提出的一个KV系统——X-engine中的，这篇文章后面再详细看看，根据简单的描述来看，X-engine也是一个类似LevelDB的LSM-Tree结构，但是在实现上做了一定的优化。
本文为了实现FPGA compaction，设计了几个主要的部件，分别是Task Queue，Result Queue，Driver和Compaction Unit。其中Task Queue是接受待处理的compaction任务，Result Queue是接受处理完的comapction结果。
Driver
Driver的主要任务是构建compaction任务，分发任务以及应用compaction结果，分别对应三个线程：builder thread，dispatcher thread以及driver thread。
builder thread将compaction任务切分成大小相近的块，并分别构成Compaction task，这是FPGA处理的基本单位，compaction task中包含了compaction的input数据。同时builder thread还负责检查result queue中任务是否完成，如果完成则将新的数据install到DB。这也是需要CPU的地方。
dispatcher thread将task queue中的task分发到不同的Compaction Unit进行执行，分发的方式是以round-robin的方式进行的。
driver thread是将输入数据传输到FPGA的memory中，并触发开始执行。
为了将数据传输到FPGA，需要使用到PCIe connect，本文定义了两种数据路径，一个是指令路径（Instruction Path），主要用于传输小的、需要经常传输的数据（指令）；另一个是compaction数据路径（Compaction Data Path），用于传输compaction的数据，通过DMA的方式，无CPU参加。
Compaction Unit
Compaction是FPGA上compaction操作的逻辑实现，主要结构包括了Decoder、KV Buffer、Merger以及Encoder。
Decoder用于将输入的数据进行decode操作，处理之后的数据存储到KV Ring Buffer，Ring Buffer中数据超过一半的时候controller触发merger开始处理数据，同时controller会控制merge处理的速度与decoder处理的速度的平衡，处理完的数据写入output buffer并进行encode。
测试
compaction效率测试
比较对象：单线程compaction，FPGA-offloading compaction
测试方法：4000000KV，手动compaction
总体实现2-5倍的性能提升，KV较小的时候offloading开销相对较大，因此KV越大提升越多。
KV Store性能测试
对比对象：X-Engine
测试工具：DBBench
测试方法：278G数据量，70GB cache，8B key， 32B value
对compaction的影响
0-24线程：提升线程数有效减少L0的数据量累计，加快了查找，此时compaction比write慢，增加compaction线程可以提升compaction效率
24-32线程：性能基本不变
32+线程：线程数增加性能下降，原因：1）线程数增加增加了资源的争用；2）过多的线程消耗IO资源
添加FPGA之后的各种参数对比：除了性能提升之外，能耗也有降低。
Read Ratio对性能的影响
DBBench
测试项目：fillrandom，seekrandom while writing，read while writing，update random，read random and write random
测试结果：
fillrandom提升最多，因为大量写会触发更多comapction
YCSB
总来说：offloading主要还是对写性能提升比较多
