Pliops XDP(Extreme Data Processor)数据库存储设计的新型加速硬件

0 前言

以色列 公司 Pliops 2021年 VLDB上发表了篇The End of Moore’s Law and the Rise of The Data Processor，介绍他们在 计算硬件领域的新方案。

ps : 这个方案并不是 最近推出的 内核网络协议栈的优化 Express Data Path，虽然名字一样。

其虽然主推的是计算能力（类似的硬件有FPGA/GPU），但是他们做出了对存储工业界来说更为友好的解决方案，那就是 将计算+I/O 整合到了一块，对外提供一个完整的使用方案。这对数据库应用来说，是一个值得尝试的方向。

本文主要是一个粗略的整体方案的介绍，帮助大家快速了解 XDP 解决的核心问题 、 主要的设计原则 、基本的架构。
更多的细节可以参考前面提到的论文。

XDP 的方案设计主要是为数据库存储领域做的，单纯对比 其 和其他加速硬件的计算能力是没有意义的。
先看看 各个数据库引擎底座近些年遇到的一些问题。

1 核心问题

如今我们的计算机硬件 已经不能按照摩尔定律持续增加性能了，不论是计算芯片 还是 存储硬件上的芯片 ，硅基晶体管的大小受限于科技水平已经不能再小了，要不然为什么 Flash-ssd 从 SLC --> TLC --> QLC 这种方式来增加存储容量 而不是让 SLC 更小 来为一个block 放更多的slc（毕竟SLC 性能/准确性更可控 ） 。
当然，也可以更换存储介质，比如 PCM 为存储单元的 3D XPoint，但是成本扛不住啊，而且最后也得受限于微观工艺上的发展。

计算芯片同样的原理，物理CPU上如果能放更多的晶体管，那意味着每一个时钟周期可以参与计算的单元更多，性能自然就上去了。

硬件的微观层面已经到瓶颈了，那这一些方向的探索只能靠科学家去探索了，所以应用层面还需要考虑更多能够保持性能增加的可行方向。硬件加速卡就是一个方向，解放CPU的算力，自己带着自己的 memory/CU 甚至电容器 加入到服务器大家庭，我们的 FPGA / GPU 就在这个大背景下出现了。

那 Pliops XDP 看到了计算领域 已经比较成熟了， 但是计算硬件和存储硬件的结合还是有很多可以做的方向（存储 既有 计算密集型 也有 IO 密集型的场景），他们细致分析了存储领域的一些痛点，做出了XDP。

1.1 引擎的各方面性能受限于数据结构的选择

现如今的存储引擎 主题数据结构形态 不论是LSM-tree/ B-tree/ Hash 都是 index + log，内存中有一部分的数据索引用来加速读性能，内存累积了一部分写入数据会 Flush 到磁盘存储中。

• LSM-tree 引擎的 内存组件设计 是为了提升写性能，将上层的随机写转化为内存的有序结构从而形成顺序写；却牺牲了一部分读性能（Rocksdb 为了提升读性能做了太多的组件设计）和 磁盘空间问题。
• B-tree/B±tree 引擎的 内存组件设计 是为了提升读性能，尤其是对 range Scan 较为友好。但是因为 B-tree 本身模型 in-place update 对写并不友好。而且磁盘利用率并不高（内存page假如16k，写2k 就得分配一个16k 的磁盘block）
• Hash 引擎的内存组件 因为是hash结构，除了scan 性能之外，内存消耗上是一个大问题。

总之，受限于数据结构的选择，存储引擎也分化出了自己的应用场景，而且需要围绕各自索引的劣势只能从软件层来尝试做非常多的设计和探索。受限于 物理服务器的CPU 计算资源 / 内存大小 / IO 性能的影响，软件层的设计只能说是小心翼翼 😐 。

1.2 压缩功能 导致的CPU瓶颈

压缩功能在大集群规模下是必须要有的，显著解决存储成本 以及 磁盘寿命。问题也很明显，CPU 会先成为瓶颈。

1.3 Crash-safe 崩溃异常的无奈选择

因为有一部分数据在内存中，那为了保证存储的可靠性 ，异常恢复是必须要的功能。
这样 WAL / Double-write 就不可避免了，同一份数据的两份存储 造成的 写放大 、空间放大 和 CPU的调度消耗 也是当前引擎设计的无奈之举，且不依赖新硬件的情况下（PMEM）无法解决。

1.4 当前主流 加速硬件 较难满足存储性能提升的要求

前面提到过 主流加速硬件 FPGA / GPU 专为计算方向的性能提升做的，都能提供极致的的并行计算能力，但是并不一定适用于 数据库存储场景。

1. 数据库存储 是计算+IO 一体的， 即使 X-Engine 探索了 FPGA off-load compaction 的方案，尝试释放 compaction 需要的算力到 FPGA 上，但是 IO 问题解决不了，走内核协议栈该有的读写放大一分不少，且整体的TCO 收益很难说（毕竟 compaction 的调度是在 update-heavy 场景，且 FPGA的成本可一点不低）。
2. 主流加速硬件的接入复杂度，FPGA 的使用有自己的编程语言，毕竟内部的 host-memory 和 CU 的调度都是没有 像传统 服务器 os 的，内部的内存管理和计算资源的调度都得自己写代码（还是专有语言），不论是前期的设计 还是中期的开发 以及 后期的调试 复杂度还是非常高的（需要懂引擎 且 有相关领域的资深经验 才能保证性能 以及 最重要的稳定性问题）。

这个痛点对与大多数的做数据库内核的同学来说要求着实有点高。

2 XDP 设计原则

XDP 看到了这一些问题 ，希望能从一个 计算 + IO 的 软硬结合的 全局设计来解决上面的问题。

主要的两个展望是：

1. Using Compute to Solve Non-Compute Problems. 希望能通过较多的计算能力解决一些之前引擎受限于算力的问题。
2. A Unified Box，希望能提供一套即插即用的硬件解决方案，而不需要用户过多的参与到硬件本身的编程细节上。

XDP 主要的探索方向在如下几个方面：

2.1 数据结构上的优化

XDP 这里软件层 实现了 index + log 的架构，内存中是 Partial sorted Hash 索引，并且写入是 Append-only 方式 来保证维持磁盘的寿命和写性能。
存在的问题也很明显，索引对内存的占用问题。传统机器受限于 CPU 资源问题，对于索引压缩总是畏首畏尾。
XDP 大手一挥，不用担心计算问题，只要内存占有能降下来，随便设计，就有了下面的方案：

1. 用户 key 的 会生成一个定长的hash值(16B)，每一个hash-bucket 用 Trie 存储不同 Hash 值之间的差异bit。 论文中展开的细节是 DHT(Delta hash table)
2. 内存中的数据会在flush到磁盘之前进行排序，保证对磁盘的写入是顺序写
3. 密集hash 索引(dense hash map) 用来解决冲突。

以上三种都是 CPU密集型的实现，需要大量得消耗计算资源。但是XDP 有自己的计算卡，不用担心，只要 内存问题解决了就是好事。

2.2 解决 压缩引入的CPU消耗

压缩这个方向不言而喻，直接挑压缩比最高的算法，有的是计算资源。
所以 XDP 选择了 ZSTD 算法，保证了数据的最高压缩比，降低磁盘存储成本 而不用担心 IO 问题。

2.3 异常恢复的设计

XDP 可以自己管理 ssd，所以提供了可选的 RAID 方案设计，这样不用担心 ssd 硬件异常导致的服务可用性问题。
更主要的是 XDP 提供了 capacitor-backed 备用电容器，用户的更新数据放在 XDP内部的 SRAM上 不用担心机器宕机之后的数据丢失问题，电容器提供的电量能保证 SRAM的 用户数据持久化到磁盘。

这也就意味着，我们的存储 crash-safe 设计 不需要考虑 WAL/ Double write这样的问题 来降低引擎性能了，只需要有数据 塞到XDP就好了。

2.4 易于集成

XDP 甚至考虑到了用户接口问题，提供了广泛使用的 K/V 接口 以及 Block Interface(可以格式化文件系统 以及 分布式存储 类似 ceph 这样的应用 直接管理磁盘) 接口。

XDP的 集成不需要消耗系统服务器的计算资源，而且能够提供可选的磁盘使用方案：用户自己通过 os 管理磁盘，另一种通过 XDP 访问磁盘（磁盘内部块设备的调度XDP 自行管理）。

3 XDP 基本架构

XDP 硬件插在 PCIe 插槽上：

接下来看看 XDP 的基本组件，当然里面提到的组件并不是很全，真正使用起来的时候整个服务器也不是严格按照这个来分层，主要是展示 XDP 内用拥有的基础组件，和 server 本有的 memory /cpu 是有差异的。

暴露了两种 用户可通过 XDP 访问的接口，block interface 和 k/v 接口，对大多数场景来说都足够使用了。
而且 其内部有自己的 Memory组件，并且提供了 capacitor-backed，不用担心 有像 DRAM 掉电丢失的问题。

接下来主要看看 XDP 的 HW. indexing 内部调度 I/O 过程的基本架构如下：

• Arrival Buffer 接受最新的写入 和 读取。其内部还有更细粒度的buffer,分别放在 SRAM(xdp 的内存) 和 DRAM上，不过最新的写入都会先放在 SRAM中。达到了一定阈值之后会将 Arrival Buffer中的数据 flush到 block clusters。
• Block clusters XDP 管理 ssd 的组件，将 磁盘块映射为一个个 逻辑 block cluster。通过内存 index 能够找到实际的user key 存放的 block cluster 以及 value 对应的偏移。
• Index，主要的 log+index 架构 中的 hash 索引存放的位置，实现上是一个 DHT(Delta hash table)，内存占用极少。
• GC info，为了保证写性能 以及 flash 磁盘寿命，提供了顺序写入。也就是需要通过 GC来进行过期/删除 数据的清理。GC info 保存了一些GC调度的元数据。GC的过程 就和 LSM-tree compaction 过程一样，从磁盘读数据，排序，写入新数据到磁盘，多了一个回插index的过程。
• GC buffers，将GC 后新的 k/v 数据先缓存到 DRAM中，回插到index 中 标识当前GC Task完成之后再清理。

知道这几个组件大概的用途，其实对其软件架构的设计就很清楚了（索引为 hash 形态的 log-structure Merged 结构）。

写入的路径很简单：
上图中的 1 --> 2 --> 3

读路径也很简单：
A --> B --> C

GC 的过程：
5 --> 6 —> 7 —>8

因为它现在将这个软件形态集成到了他们的内部 k/v Library中，且 Flush 和 GC都会排序（因为不缺，又不占有CPU的，又能提升写性能，减少写放大），他们眼光长远得集成了 ZNS(zone namespace ssd)，因为 ZNS 对顺序写非常友好，像Zenfs 的应用就是很好得将 rocksdb 的 compaction 和 SSD 内部的 GC机制结合起来，极大得减少了SSD 内部 FTL 引入的写放大，提升Flash寿命。

关于ZNS的介绍，可以参考:ZNS: 解决传统SSD问题的高性能存储栈设计（fs–＞io–＞device）。

关于 index 内部的 DHT 设计提一下，利用不缺算力的优势如何优化索引对内存的消耗：
index 存放的是 hkey，其形态如下：

对输入的 user_key 通过murmur hash 生成一个 128bits 16B 的hash值，取前i 个bits 作为bucket id，j bits 作为 lslot id，剩下的作为指纹标识。
lslots 的 bits 假如是 11，则表示是第三个slot，lslot 和 bucket其实就是做了一个二级hash，也就是密集索引，消耗cpu，但足够均匀。 每一个slot 有一个int 成员和pointer，标识映射到当前slot 的user_key有多少个 以及 lslots耗尽之后通过链表扩展一个bucket内部的slots个数。

如下案例：

假如 i, j都是2，则对于输入的hash值前四个bits 且 1011 ，则表示当前 user_key被映射到了10 即 第3个bucket 的 11 第四个slot，里面有1个 use_key。

继续向下看，剩下的 128 -i -j bits 用来作为具体user_key 的指纹数值。
存储的时候仅仅会保存增量指纹之间的差异，核心目标是最少内存占用的情况下 保证读时的唯一性。

比如对于 e1–e5 这 5个 user_key 的指纹数值，取的是前6个bits。当然，这里是因为6个bits 已经能够两两区分他们之间的差异了，实际可能需要更多的bits，也就需要拿更多的bits进行 Trie的构造了。
将 entry 之间的差异 逐个插入 Trie 树中：
比如 e1 和 e2 之间的差异是到 下标为2 的位置 010 和 011 有差异，则会在 e1,e2的公共索引节点标识其差异下标所在位置 idx 2。
同理，e1 和 e3 再 idx 0 位置就有差异，构造的过程就将 e3 放在右子树中。右子树中的 idx 5是 对比 e3,e5时 发现在 下标为 5的位置才有差异 添加进来的。

这样整个 Delta Trie 就构造好了，这个过程对于所有属于当前 slot的 entry都要先收集最大的差异bits，再构造Trie，整个过程会有极多的计算资源的消耗，但都被财大气粗的 计算硬件包揽。优势就是 极大得节省了存储空间。

不过Trie 的Scan 性能可能并不会友好，但是不需要 server 的 CPU参与，这就是最大的优势了。

4 总结

总的来说 XDP 计算硬件 结合了 IO 链路所展示基本解决方案 让我们看到了存储和新硬件结合的曙光。当然，其方案内部的设计 复杂度是非常高的（尤其是对磁盘的管理 – os 是 generic block layer --> io sheduler --> block layer，它现在要自己管理）。