【论文阅读】FPGA-Accelerated Compactions for LSM-based Key-Value Store

简介

LSM Tree由于其很高的写效率被广泛应用。这种优势主要依赖于后台compaction将随机写转化为了顺序写，并在compaction的过程实现了Garbage Collection的功能。但是随着IO性能的提升，CPU本身成为了查询、合并等功能的瓶颈，特别是KV size较小的时候。本文就提出了将compaction的功能分配给FPGA缓解CPU本身带来的瓶颈。

?上图为使用typical WPI workload(75% point lookups,25% writes,即读密集的负载)所测得的throughput和CPU/IO占用率的图表。可以看到32线程时，吞吐率出现了转折。这是由于前台的查询事务操作和后来的compaction发生了资源竞争。在这种读密集的负载下就显得更加严重。
因此本文提出了将compaction过程下放到FPGA进行完成从而减少资源竞争的情况，主要做了下面工作。

• compaction速度慢导致L0级别过大以及其他问题，这些问题最终会导致LSM-tree KV存储的性能下降。
• 我们在FPGA上设计实现多级压实管道(multistaged compaction pipeline)，支持merge和delete操作。我们引入了异步调度器(驱动程序)来协调CPU和FPGA来转移compaction。
• 我们对FPGA压缩吞吐量进行了建模分析。使用该模型，我们能够预测不同compaction卸载的方案性能。

背景概念和动机

• LSM-Tree
  
• FPGA offloading
  主要有两种方法将FPGA集成到KV Store中。
  一是"bump-in-the-wire"design。这种设计将FPGA放置在CPU和disk之间。这里FPGA相当于一个数据过滤器。这种设计主要发生在所使用的的FPGA片上RAM的资源较少，只能暂时保存小部分的数据量；
  二是作为co-prosessor进行使用。可以直接将包含大量数据的操作放置在FPGA上进行处理。这种方法适用于异步任务，CPU不会因此而失速。

本文采用的就是法2进行集成。

• 动机
  在运行WPI负载的时候会导致性能降落主要是由于下面两个原因：
  problem 1:碎片化的L0
  L0的SST是直接从memtable上dump下来的。所以不可避免的出现key range重叠的情况，查找L0的时候就需要大范围地查找SST。同时当compaction操作较慢的时候，又会导师L0中SST的堆积，更加剧查找L0时候的延迟。加上L0是较新的数据，往往热度较高，从而更加拖慢了LSM-tree的速度。

?problem 2：瓶颈的转移
compaction的步骤主要为：decode，merge，encode，在不同大小的KV对下，其消耗的资源是不同。

从图中可以看出在KV size比较小的时候，主要消耗的是CPU资源。

设计与实现

1.overview

这里表示了compaction转移的示意图，值得注意的是这里使用的LSM-tree based KVS为X-engine。X-engine维护一个全局索引以加速查找。下面是关键组件的主要功能：

Task Queue: 缓存新触发的compaction任务。
Result Queue：缓存已经compaction完毕的KV记录。
driver：管理从host/FPGA传输的数据。
compaction units：进行压缩操作的单元。

2.driver

2.1. Managing Compaction Task

为了顺利将compaction顺利offload到FPGA，CPU端会创建三种线程：

• builder threads：build compaction tasks
• dispatcher threads:dispatch tasks to CUs in FPGA
• driver threads:install compacted data back to the storage

• builder thread
  对于每个compaction，builder thread会将所需的范围分割成大小近似的不同组(group);每个group最终会形成单独的compaction任务。新建任务的时候需要包含下面的元数据：

如果在FPGA的压缩失败时，builder thread就会重新创建一个CPU compaction解体这个任务。

在本文测试中，大概仅仅0.03%的FPGA-Based Compaction任务失败。

• dispatcher thread
  dispatcher消耗task队列，并将任务发送以round-robin的方式发送给FPGA中的CUs。由于compaction tasks是通过分割成相近大小的形式得到的，不同的CU之间会得到相对平衡的负载。
• driver thread
  driver thread将每个compaction task相关的数据传输到FPGA的片上内存，并通知对应的compaction unit开始工作。当有compaction task完成的时候，driver thread就会被中断来执行：将获得的compacted data block传输回host内存中；将completed tasks压入result queue； - 由2.2中 Interruption Mechanism进行完成。

2.2. Instruction and Data Paths
为了使用FPGA进行compaction，通过PCIe将指令和数据进行传输。本文定义了两种通路。如下图所示：

• Instruction Path-用于传输小的，经常使用的数据(指令)
• Compaction Data Path-用来传输用于compaction的数据，使用的是DMA(direct memory access)，无需CPU的参与。
• Memory Management Unit(MMU)-用来申请从device申请空间用来存储到来的数据。

3.compaction unit

主要结构包含：decoder，merger，kv transfer，encoder

• decoder ：对于一个KVS，其中key使用前缀编码来节省空间。所以需要decoder进行译码，之后传输给KV Ring buffer。
• ring buffer：将ring buffer使用三个flag划分状态：FLAG_EMPTY/FLAG_HALF_FULL/FLAG_FULL。如果处于空状态，就持续decode并写入buffer。如果buffer半满之后就将启动Merger开始合并。之后decoder继续解码数据进行写入。值得注意的是，这里将merger和decoder处理的速度进行平衡匹配，这样可以保证数据不会被阻塞
• encoder-编码输出

4.compaction unit的分析模型

evaluation

总结与亮点