BadgerDB|BadgerDB 原理及分布式数据库的中应用与优化 BadgerDB原理及分布式数据库的中

Part 1 - BadgerDB 设计架构
Badger[1] 是基于论文：WiscKey: Separating Keys from Values inSSD-conscious Storage[2] 的思想利用 Go 语言进行设计实现的。
LSM-Tree 的优势在于将随机写转换为顺序写，将大块的内存连续地写入到磁盘，减少磁盘寻址的时间，同时数据是按照 key 排序，查找起来速度快，同时也带来了写、读放大。LSM-Tree 的这些优化很适用 HDD，但是 SSD 的性能却受到限制（写放大）。因此，Wisckey 提出了一种面向 SSD 的，将 key-value 分离存储的方法。
下面先分析一下 LSM-Tree 写、读放大。写放大主要是因为各个层级之间的 Compaction，当两个层级之间做 Compaction 时，都需要将多个 SSTable 读到内存排序（读放大），然后写到磁盘。读放大主要是在 LSM-Tree 中查找一个 key 时，一般查询流程是 MemTable、Immutable MemTable 以及 SSTable。如果该 key 不存在，虽然 MemTable 和 Immutable MemTable 是内存操作很快，但是在 Level 0 层的 SSTable 中 Key 是全局无序的，可能还有重叠，需要全扫，更高层级的 SSTable 中也需要二分查找，虽然有 bloom filter 但是依旧影响查找的效率。图 1 中展示了 LevelDB 中写、读方法的测试，数据集大小分为 1G 和 100GB，其中 Key 大小为 16B，Value 大小为 1KB。
【BadgerDB|BadgerDB 原理及分布式数据库的中应用与优化】
文章图片

图 1 LevelDB 的写、读方法
Wisckey 提出的优化是：Key-Value 分离存储。LSM-Tree 里面存储的是一个 Key 以及 Value 的地址，Value 本身以 WAL 方式 append 到 Value Log 文件中。这样在做 Compaction 的时候就只需要重写 Key 以及 Value 的地址就可以了，SSD 中数据的分布如图 2 所示。因此，在 Key size 远远小于 Value size 的场景中降低写放大的效果显著。但是当 Value 很小的时候，重写 Value 的开销就很小，Key-Value 分离带来的好处不足以抵消其本身的开销（读写 Key-Value 需要操作不同的文件，在 range query 的场景下，会产生多次的随机 IO ）。

文章图片

图 2 Wisckey 中数据在 SSD 中的分部
基本操作流程：
写流程：先把 Valueappend 到 Value Log（为了便于 GC 操作也会写入 Key），然后把 Key 以及 Value 的地址（）写入 LSM-Tree 的 MemTable 中，然后按照一定策略利用 MinorCompaction 将 MemTable 写入 SSTable。
读流程：先从 LSM-Tree 里面读取 Key 对应 Value 的地址，然后从 ValueLog 读取 Value。
删除流程：只需把 Key 从 LSM-Tree 里面删除，无需操作 ValueLog。Value 由 GC 机制进行处理。
由于 LSM-Tree 做 Compaction 时不需要重写 Value，大大减小了写放大。同时 LSM-Tree 更小，一个 Block 能存储更多的 key，也会相应的降低读放大，能缓存的 Key 以及 Value 地址也更多，缓存命中率更高。
面临的一些挑战：
RangeQuery： Range query 允许用户查询一段有序 range 内的 KV 对，可以对其进行遍历。当发起一次 rangequery 的时候，最终会被转换为对 Value Log 的多次随机读，而对 LSM-Tree 则是顺序读。因此在 Value 小的情况会增加了延迟。
该场景下，Wisckey 会通过充分利用 SSD 并行 I/O 特性，在 range query 时对 Value Log 中的 Value 进行预取缓存。预期缓存对于大范围的 range query 效果比较明显，但是对于小范围的 range query 可能作用不大。根据论文的实验数据如图 3 所示（100GB 的数据集中查询 4GB 数据），当 value 大于 4KB 时，读的性能才体现出来。
BadgerDB|BadgerDB 原理及分布式数据库的中应用与优化
文章图片

图 3 范围查询性能
GC：由于删除操作只会删除 LSM-Tree 里面的 Key 以及 Value 地址，不会删除 ValueLog 的 Value。
如图 4 所示，Wisckey 在 Value Log 中会存储元组（keysize, value size, key, value）同时会存储以及，用来标识最后做 GC 的位置。会从 tail 开始扫描 Value Log，获取 Key-Value。为了不影响在线服务，会每次取出 Value Log 最旧的一部分数据 (MB)，通过读取 LSM-Tree 来验证其有效性，如果过期或者被删除则丢弃；有效则 append 写入到最新的 vlog，然后更新 tail 的值，并删除 tail 之前的数据，通过 fallocate() 释放无效的文件磁盘空间。如图 5 所示，Wisckey 在 GC 是的性能在所有情况下至少比 LevelDB 快 70 倍。
BadgerDB|BadgerDB 原理及分布式数据库的中应用与优化
文章图片

图 4 Wisckey 中 GC 处理的数据结构

文章图片

图 5 Wisckey 的 GC 性能
一致性：Wisckey 是先写入 Value Log，再写入 LSM-Tree，所以会有以下几种失败情况：vLog 写入失败；vLog 写入成功，LSM-Tree 写入失败；vLog 写入成功，LSM-Tree 写入成功后立刻崩溃。
在 Wisckey 中 vLog 写入失败，则 LSM-Tree 肯定写入失败。可能会残留部分 vLog 数据，由 GC 机制来回收。vLog 写入成功，LSM-Tree 写入失败：此时 vLog 的值便成了垃圾数据，会有 GC 机制来回收。vLog 写入成功，LSM-Tree 写入成功后立刻崩溃：Wisckey 中取消了 LSM-Tree 的 WAL，所以写入 LSM-Tree 也仅仅是写入了内存的 MemTable，此时程序或者机器发生崩溃 LSM-Tree 的数据依旧会丢失。Wisckey 的做法是保存元组（key size, value size, key, value）以及在 vLog 中。每次 Open 数据库的时候，读取 vLog 中 head 的值，然后依次读取 head-vLog-offset 之后的记录，并将 Key 以及 Value 地址写入到 LSM-Tree，最后更新 head 的值。如果更新 head 的值发生崩溃也无所谓，只不过再次 Open 数据库的时候多重放一点记录罢了。
Wisckey 中 Key-Value 分离的策略在大 Value 场景下效果显著，但是对于小 Value 性能不如 LSM-Tree。为此在 BadgerDB 中设置一个 Value 阈值，当 Values 大小超过阈值时该 Value 存入 vLog，小于阈值时存入 LSM-Tree。
BadgerDB|BadgerDB 原理及分布式数据库的中应用与优化
文章图片

图 6 BadgerDB 整体架构
BadgerDB 是基于 Wisckey 论文实现的，整体架构类似 LevelDB，具体如图 6 所示，区别就在于去掉了 LSM-Tree 里面的 WAL，用 vLog 代替。在实现上，去掉了 current 文件。
功能特性：
支持常用的 Get、Put、Delete、Batch 等操作。
实现了 SSI 隔离的 Transaction，支持读、写事物。
所有的操作都是以 Transaction 执行的。
支持 MVCC，支持多版本的 Key-Value。
支持对 key 设置 TTL 以及 UserMeta。
所有的 Key 都是有序存储的，支持 Iteration 和 Prefix-Scan。
支持 Key 的 Compaction 以及 Value 的 GC。
Part 2 - 云溪数据库中的 RAFT 算法
云溪数据库是分布式数据库，与 CockroachDB 等一样都是 NewSQL 家族的一员。云溪数据库具备强一致、高可用的分布式架构，能够水平扩展提供企业级的安全特性完全兼容 PostgreSQL 协议，能够为用户提供完整的分布式数据库解决方案。云溪数据库的整体架构如图 7 所示，云溪数据库的强一致性是由 Raft 算法 [3] 保证分布式多副本之间数据强一致性以及外部读写的一致性，简言之云溪数据库中数据会有多个副本，这些副本存放在不同的机器上，当其中一台机器故障宕机后数据库依旧能够对外提供服务。云溪数据库会根据插入数据的键，将数据划分为多个 Range，每个 Range 上的数据都有一个 Raft Group 来维持多个副本之间数据的一致性。因此，准确地说云溪数据库使用的是 Multi-Raft 算法。
BadgerDB|BadgerDB 原理及分布式数据库的中应用与优化
文章图片

图 7 云溪数据库的整体架构
利用单机的 RocksDB，云溪数据库可以将数据快速地存储在磁盘上；利用 Raft 算法，可以快速地将数据复制到多台机器上，以防单机故障。数据的写入是通过 Raft 算法接口写入，而不是直接写 RocksDB。通过 Raft 算法，云溪数据库变成了一个分布式的键值存储系统，不超过集群半数的机器故障宕机完全能够通过 Raft 算法自动把副本补全，可以做到业务对故障无感知。在前期，云溪数据库中 Raft 算法采用的是开源的 etcd-raft 模块 [4]，该模块主要提供如下几点功能：
Leader 选举；
成员变更，可以细分为：增加节点、删除节点、Leader 转移等；
日志复制。
云溪数据库利用 etcd-raft 模块进行数据复制，每条数据操作都最终转化成一条 RaftLog，通过 RaftLog 复制功能，将数据操作安全可靠地同步到 Raft Group 中的每一个节点上。不过在实际操作中，根据 Raft 的协议，只需要同步复制到多数节点，即可安全地认为数据写入成功。
Part 3 - Raft Log 分离与定制存储
在 etcd-raft 模块中，Raft Group 中的 Leader 节点接收客户端发来的 Request，将 Request 封装成 Raft Entry（Raft Log 的基本组成单元）追加到本地，并通过 gRPC 将 Raft Entry 发送给 Raft Group 中其他 Follower 节点，当 Follower 节点收到 Raft Entry 后进行追加、刷盘以及回复处理结果的同时，Leader 将本地 Raft Entry 进行刷盘，两者同步进行。等 Leader 节点收到过半数节点的肯定回复后，提交 Raft Entry 并将其应用到状态机（将 Raft Entry 中包含的业务数据进行持久化），然后将处理结果返回客户端。
从上面的分析中可以看出 RaftLog 在副本之间达成共识、节点重启以及节点故障恢复等环节都起到至关重要的作用，RaftLog 与业务数据共同存储在同一个 RocksDB 中，在查询高峰期必然会发生磁盘 I/O 资源争抢，增加查询等待时延，降低数据库的整体性能。在 TPCC 场景下进行了 Raft Log 与业务数据写入量的测试，测试场景如下：在物理机（CPU：6240 72 核内存:384G 系统硬盘：480G 数据盘：375G+SSD 硬盘:2T*7）上启动单节点云溪数据库服务，系统稳定后 init 6000 仓 TPCC 数据，观察整个过程中业务数据与 Raft Log 写入量的大小，测试结果如表 1 所示。
表 1 TPCC 初始化过程数据量统计
BadgerDB|BadgerDB 原理及分布式数据库的中应用与优化
文章图片

同时开展了 TPCC 场景下针对 Raft Log 各项操作数量的测试，测试场景如下：启动 3 个节点的云溪数据库集群，系统稳定后 init 40 仓 TPCC 数据，观察网关节点在整个初始化过程中 Raft Log 各项操作数量的变化，测试结果如表 2 所示。将 RaftEntryCache 的大小从 16MiB 增加到 1GiB 后，相同场景下 Term 与 Entry 的查询数量下降到 0。
表 2 TPCC 初始化过程 Raft Log 各项操作统计
BadgerDB|BadgerDB 原理及分布式数据库的中应用与优化
文章图片

根据上述测试以及测试结果，可将云溪数据库中 Raft Log 的操作特点总结如下：

在正常运行过程中，插入和删除操作是最多的且数量也很接近，说明 Raft Log 持久化的时间很短。查询 RaftLogSize 也是较为常规操作，其他操作都是在特殊场景下触发的，几乎可以忽略不计。
查询 Term 与查询 Entry 的操作次数取决于 RaftEntryCache 的大小，是由云溪数据库内部实现机制决定的，Entry 和 Term 的查询一般先去 Unstable 中查找，查找不到再去 RaftEntryCache 中查找，还是查找不到就到底层存储中查找。通常情况下 RaftEntryCache 大小设置合理的话可以命中所有查找。
云溪数据库实际运行过程中产生的 Raft Log 比真正持久化的业务数据多很多（5~10 倍），而且只要数据库持续运行（即使没有任何用户查询）就会源源不断的产生 Raft Log。Raft Log 是用户数据的载体，为了保证数据完整性和一致性 Raft Log 必须持久化。
云溪数据库中存储 raft Log 的引擎面临的真正挑战是频繁写入、删除以及短暂的存储给系统带来的性能损耗。

通过对云溪数据库中 Raft Log 操作场景的详细分析，总结 Raft Log 存储引擎应该满足如下特征：
尽可能将待查询数据保存在内存中，减少不必要磁盘 I/O;
写入的数据能够及时落盘，保证故障恢复后数据的完整性和一致性；
能够及时地清理被删除数据或是延迟清理被删除数据，减少不必要的资源占用。
针对这个问题，目前一些主流 DB 的解决方案是：每个 KV 实例中有两个 RocksDB 实例，一个用于存储 Raft 日志（通常被称为 raftdb），另一个用于存储用户数据以及 MVCC 信息（通常被称为 kvdb）。同时，还开发了基于 RocksDB 的高性能单机 Key-Value 存储引擎。在云溪数据库中直接使用 RocksDB 来存储 Raft Log 是不合适的，不能很好地满足 Raft Log 的具体使用场景。RocksDB 内部采用 LSMTree 存储数据，在 Raft Log 频繁写入快速删除并且还会持续进行随机查询的场景下，造成严重读放大和写放大，不能够充分发挥出 RocksDB 的优势，也对系统整体性能造成不利影响。
研发团队在详细调研分析 LevelDB、RocksDB、BadgerDB、FlashKey 以及 Aerospike 等的具体架构与特征后，决定基于 BadgerDB v2.0 的基础上进行定制优化，作为云溪数据库中 Raft Log 的专用存储引擎。Raft Log 定制存储实现了以下基本功能：
Raft Log 的批量写入与持久化；
Raft Log 的顺序删除与延迟 GC；
Raft Log 的迭代查询，包括：RaftLogSize 查询、Term 查询、LastIndex 查询以及 Entry 查询；
相关 Metrics 的可视化；
多引擎场景下的用户数据完整与一致保证策略。
云溪数据库中 RaftLog 定制存储整体部署架构如图 8 所示：

文章图片

图 8 Raft Log 定制存储整体部署架构
部署时 BadgerDB 需要与 RocksDB 并列进行部署，即一个 Node 上部署相等数量的 RocksDB 实例和 BadgerDB 实例（由目前云溪数据库中副本平衡策略所决定）。查询请求的大致处理流程是先将 Raft Log 写入 BadgerDB，等待集群过半数节点达成共识后，再将 Raft Log 应用到状态机，即将 Raft Log 转化成用户数据写入到 RocksDB，用户写入成功后再将 BadgerDB 中已应用的 Raft Log 删除，同时将状态数据更新到 RocksDB 中。
云溪数据库中 Raft Log 定制存储的写、读流程如图 9 所示。

文章图片

图 9 RaftLog 定制存储写、读流程
由于 Raft Log 定制存储采用 Key-Value 分离的策略，完整的 Key-Value 数据首先写入 VLog 并落盘（如果是删除操作则在落盘成功后由 IfDiscardStats 更新内存中维护各 VLog File 的删除数据的统计信息，这些统计信息也会定期落盘。避免了 BadgerDB 中 SSTable 压缩不及时导致统计信息滞后的问题），然后将 Key 以及元数据信息写入 Memtable(skiplist)。将 Level 0 SSTable 放入内存，同时将需要频繁查询的信息（RaftLogSize、Term 等）记录到元数据放入内存，加快随机读取的效率，减少不必要的 I/O。
已删除 Key 的清理依赖 SSTable 的压缩，对应 Value 的清理则需要云溪数据库周期性调用接口，首先根据访问 IfDiscardStats 在内存中维护的 VLog file 的 discardStats，对备选文件进行排序，顺序遍历进行采样，若可以进行 GC 则遍历 VLog File 中的 Entry，同时到 Mentable(或 SSTable) 查看最新元数据信息确定是否需要进行重写，需要重写则写入新的 VLog File，不需要则直接跳过，Raft Log 定制存储中 GC 处理流程如图 10 所示。

文章图片

图 10 RaftLog 定制存储 VLog GC 流程
在将 Raft Log 进行独立储存后，必须要考虑多个存储引擎数据保持一致性的策略。Raft Log 存在的目的是为了保证业务数据的完整，因此在 Raft Log 与业务数据分开存储后不追求两者完全一致，而是 Raft Log 保持一定的 “冗余”。具体策略是每个 range 上先将 AppliedIndex 以及对应的 Term 同步写磁盘，当 RaftLog 积累到一定数量后再去磁盘上读取前面落盘 AppliedIndex 以及对应的 Term 进而生成 TruncateState 进行 RaftLog 的删除。
研发团队完成上述优化后，开展了 “迭代查询性能对比测试” 与 “TPCC 场景性能测试”。在 “迭代查询性能对比测试” 中，测试场景如下：启动单机单节点云溪数据库服务，系统稳定运行后 init 40 仓 TPCC 数据，记录迭代器查询 RaftLogSize 与 Term 的总耗时。Raft Log 分别存储在 RocksDB、BadgerDB 以及 Raft Log 定制存储中，其中 ValueThreshold 设置为 1KB，其他设置均采用默认值。
表 3 迭代查询测试结果汇总

文章图片

从上述测试结果来看，在对 Badger 迭代器进行优化后，针对元数据的迭代查询速率得到大幅提升，相比 RocksDB 迭代查询延迟降低了约 90%。
在 “TPCC 场景性能测试” 中，测试场景如下：在物理机（CPU：6240 72 核内存:384G 系统硬盘：480G 数据盘：375G+SSD 硬盘:2T*7）启动单节点云溪数据库服务，系统稳定后 init 6000 仓 TPCC 数据，观察整个过程中相应监控指标。
表 4 TPCC 压测监控数据汇总表

文章图片

从上述测试结果来看，Raft Log 采用定制存储后，raft Log 提交延迟下降约 60%，raft Log 应用延迟下降约 25%，RocksDB 读放大下降约 60%（高负载），同时没有明显增加资源消耗。
综上，利用键值分离的思想优化 LSM 树，借助索引模块提升迭代查询性能，使用统计前置的策略提升系统 GC 的效率，能够很好满足云溪数据库中 Raft Log 在各种操作场景下的性能要求。
Part 4 - 后续优化
与故障重启有关的状态数据迁移至 BadgerDB，进一步减少 RocksDB 数据的写入量。
利用 RaftLog 与部分状态数据替换 RocksDB 的 WAL，BadgerDB 承担集群故障恢复功能，为后续 RocksDB 进一步优化扫清障碍。
优化 RaftLog 缓存，提升缓存命中率减少非必要的读盘，在将状态数据引入到 BadgerDB 后，进一步优化写入、查询性能优化，例如：并行写 MEMTable 等。
[1] https://dgraph.io/blog/post/b...
[2] https://www.usenix.org/system...
[3] https://raft.github.io/raft.pdf
[4] https://github.com/etcd-io/etcd