Kvrocks 设计与实现
「Kvrocks: 一款开源的企业级磁盘 KV 存储服务」对 Kvrocks 进行了整体性的介绍，本文从关键设计和内部实现来分析，希望对于想知道如何实现磁盘类型 Redis，以及想熟悉 Kvorcks 设计和实现的人带来一些帮助。
内部设计
Kvrocks 在内部设计上主要拆分成几个部分:
- Redis 协议接收和解析模块，负责解析网络请求和解析 Redis 协议，相比 Redis 来说，Kvrocks 在 IO 处理以及命令执行都是多线程模型；
- 数据结构转换模块，负责将 Redis 复杂类型转为 RocksDB 可处理的简单 KV，不同类型在设计上会有一些小差异；
- 数据存储模块，Kvrocks 底层使用 RocksDB 并对其做了不少针对性的性能优化，文章「 Kvrocks 在 RocksDB 上的优化实践」进行了详细说明，感兴趣的同学可以前往阅读；
- 主从复制模块，类似 Redis 的异步复制的方式，每个从库都会创建一个对应的复制线程。在实现方面，使用 RocksDB CheckPoint + WAL 来实现全量和增量同步；
- 集群模块，包含 Redis 集群协议兼容以及在线迁移的功能。这部分没有在上面的架构图中体现，感兴趣可以参考: 「 Kvrocks 集群方案简介」。
下图为 Kvrocks 的整体设计示意图：
除此之外，代码里面还有一些后台线程 (Compaction Checker) 、任务的线程池以及统计功能由于篇幅关系没有体现。
Redis 协议解析
Kvrocks 目前支持的还是 RESP 2 的协议，请求协议解析的相关代码都在 src/redis_request.cc 这个代码文件里面。相比于 Redis 的实现，Kvrocks 并没有自己实现接收和发送网络包逻辑，而直接使用比较成熟 Libevent 网络库，主要的原因多线程场景下，Libevent 的性能已经足够好，瓶颈主要在磁盘 IO, 没必要自己再造轮子。
解析请求的核心代码只是一个几十行代码的状态机，简化后的代码如下:
Status Request::Tokenize(evbuffer *input) {
...
while (true) {
switch (state_) {
case ArrayLen: // 读取协议的元素个数
line = evbuffer_readln(input, &len, EVBUFFER_EOL_CRLF_STRICT);
if (line[0] == '*') {
multi_bulk_len_ = std::stoull(std::string(line + 1, len-1));
state_ = BulkLen;
}
...
break;
case BulkLen: // 读取元素长度
line = evbuffer_readln(input, &len, EVBUFFER_EOL_CRLF_STRICT);
bulk_len_ = std::stoull(std::string(line + 1, len-1));
state_ = BulkData;
break;
case BulkData: // 读取元素数据
char *data = evbuffer_pullup(input, bulk_len_ + 2);
if (--multi_bulk_len_ == 0) {
state_ = ArrayLen;
...
}
state_ = BulkLen;
break;
}
}
}
协议解析的初始化状态是要读取到单个请求的长度，预期是以 * 字符开头，后面跟着请求的元素个数。以 GET test_key 为例，那么第一行数据是 *2\r\n 表示该请求有两个元素。接着，第一个元素 GET 是 3 个字符，表示为 Bulk String 则为 $3\r\nGET\r\n, $ 开头为元素的长度。同理，test_key 则是 $8\r\ntest_key\r\n, 那么完整的请求变成 Redis 协议则是: *2\r\n$3\r\nGET\r\n$8\r\ntest_key\r\n。
src/redis_reply.cc 里面跟请求协议解析过程刚好相反，实现的功能则是把返回给客户端的数据转为 Redis 的协议格式。
数据编码
由于底层存储引擎是 RocksDB， 只提供简单的 Get/Set/Delete 以及 Scan 接口。在接收到请求之后，Kvrocks 需要对 Hash/List/Set/ZSet/Bitmap 等复杂数据结构的请求进行编码，转为简单 RocksDB KV 来进行读写。目前大部分数据都存储在以下两个 Column Family 里面:
- Metadata Column Family，用来存储 Key 的元数据信息。以 Hash 为例，每个 Hash 都会在这个 Metadata Column Family 存储一个元数据的 KV，Key 就是用户请求的 Hash Key，Value 包含：数据类型，版本号，过期时间以及 Hash 的子元素个数
- Subkey Column Famliy, 用来存储 Hash 对应的子元素和对应的值，这个 Column Family 的 Key 组成是: Hash Key + 版本号 + 子字段的 Key，Value 是子元素对应的具体值
整体示意图如下:
版本号是根据当前时间自动创建一个随机递增的数值，目的是为了实现快速删除，避免删除大 Hash 时产生慢请求。比如，第一次写入版本号为 V1， 包含 N 个元素，在删除或者过期之后再重新写入则会产生新的版本号 V2，由于查找时需要先找到当前活跃版本号，再拼接成子元素的 Key 再查找对应的值。相当于老版本的子元素都变成不可见，这些数据会在后台 Compaction 时自动回收，变相实现了异步删除。
假设写入的 hash_key 里面有两个元素 field1 和 field2，那么 Metadata Column Family 里面会写入一条 hash_key 对应的元数据，值会包含几个字段:
- Flags 会标识这个类型为 Hash
- Expired 如果没有过期时间该值为 0，否则就是对应的过期时间绝对值
- Version 每次创建会自动创建的随机递增数值，用来标识当前活跃的版本号
- Size 为当前 Hash 的元素个数
查找时，根据 Hash Key 先在 Metadata Column Family 找到对应的元数据，然后通过 Hash Key + 元数据的版本号 + 子元素的 Key 拼接成为查找的 Key 后从 SubKey Column Family 找到元素值，其他操作也是同理。
更多编码结构可以参考文档: Design Complex Structure On RocksDB[1], 具体代码实现都在 redis_hash.cc 里面，其他数据结构也是同理。其中 Bitmap 为了减少写放大也做了设计上的优化，具体请参考: 「如何基于磁盘 KV 实现 Bitmap」
Lua 和事务
Kvrocks 是目前开源磁盘 Redis 里面同时支持 Lua 和事务的选型，同时在命令支持上也是比较完善。为了简化实现复杂度，Lua 和事务相关命令执行时会限制为类似 Redis 的单线程执行。实现方式是在 Lua 和事务相关执行命令加上全局锁，代码如下:
if (attributes->is_exclusive()) { // 是否为互斥执行命令
exclusivity = svr_->WorkExclusivityGuard();
} else {
concurrency = svr_->WorkConcurrencyGuard();
}
全局锁会导致 Lua 和事务的性能退化为单线程性能，但就如 「Spanner: Google’s Globally-Distributed Database[2]」所说，业务解决性能问题会比解决功能缺失更加简单得多，性能问题业务总有办法去绕过而功能则很难。所以相比于功能完整性来说，少数命令的性能衰退是可接受的。
在 Lua 实现上，为了和 Redis 行为保持一致，Kvrocks 也是选择 Lua 5.1 版本。但实现上有一些差异，Redis 当前版本的 Lua 脚本做不会持久化，重启之后会丢失，而 Kvrocks 会持久化到磁盘且自动同步到从库，具体实现见: PR 363[3] 和 PR 369[4]。此外，在后续计划中，我们会支持设置 Lua 脚本名字的功能并按名字进行调用，类似数据库的存储过程功能，具体讨论见: Issue 485[10]
在事务方面，Kvrocks 目前支持 Multi/Exec 命令，实现也是跟 Redis 类型，对于 Multi 和 Exec 之间的命令先缓存在内存中，收到 Exec 命令之后才开始执行这行命令。目前实现上存在一个小问题是，虽然执行过程中可以保证单线程但写 Batch 不是原子，所以可能在极端场景下，写到一半服务挂了则可能部分 Batch 成功的情况，具体讨论见: Transaction can't guarantee atomicity[5]，目前社区也在跟进和解决这个问题。
存储
除了将复杂数据结构转为简单 KV 的设计之外，需要在存储层面也有很多优化细节需要去做。Kvrocks 底层的单机存储引擎使用的是 RocksDB，相比于 LevelDB 除了性能方面有比较大提升之外，在特性方面也是存储引擎里面最为丰富的，包含 Backup、CheckPoint 以及 Compact Filter 等功能。当然，RocksDB 除了丰富的特性之外，在配置方面也比 LevelDB 复杂不少，需要针对不同业务场景来提供最佳配置也是比较大的挑战。文章「Kvrocks 在 RocksDB 上的优化实践」对于 RocksDB 参数优化进行了详细的说明。除此之外，Kvrocks 在 Compaction 以及 Profiling 部分也做了一些优化:
- 增量 Compaction，之前除了 RocksDB 的自动 Compaction 之外，允许通过配置
compact-cron来配置全量 Compaction 的时机。一般配置在每天流量低峰做一次，这种方式对于小实例问题不大，而对于大实例则对磁盘 IO 会有比较长时间的影响。后面通过支持增量检查 SST 的方式实现增量 Compaction，同时也允许配置检查的时间段，只在低峰时段做增量 Compaction。具体见:compaction-checker-range配置，实现: PR 98 [6] - 动态 Profiling 开关，线上最常见的问题是遇到 RocksDB 有慢请求，如果在非 IO 性能瓶颈的场景很难定位到问题。Kvrocks 支持通过在线配置 profiling 采样的方式来做性能分析，目前支持几个选项:
- profiling-sample-ratio，默认值为 0，不开启采样，取值范围 0-100
- profiling-sample-record-max-len，默认值 256， 只保留最近 N 条采样记录
- profiling-sample-record-threshold-ms，默认 100ms，只保留超过 100ms 的采样记录
- profiling-sample-commands，默认为空，
*表示全部命令都采样，也可以配置多个命令，使用逗号分割
- 动态调整 SST 大小，之前遇到性能毛刺点问题基本都是由于 SST 过大，读取 Filter/Index 过慢导致请求，通过支持根据一段时间写入 KV 大小调整 SST 文件可以有效的缓解该问题。在 2.0.5 版本引入了 Partition Index 功能，不再有类似问题，所以动态调整功能也随之下线
其他比较经常被提到的问题是: 「Kvrocks 过期或者删除数据如何回收？」，这个是通过 RocksDB 支持 Compact Filter 特性，在 Compaction 阶段对这些过期或者删除数据进行回收。
主从复制
上面内容主要是关于如何实现单机版本的磁盘 Redis，而对于分布式服务来说，Kvrocks 另外两个很重要的功能特性是: 集群和复制。由于集群有其他文章专门分享，这里只关注复制部分。在 2.0 版本之前 Kvrocks 使用 RocksDB Backup + WAL 来做全量和增量复制，创建 Backup 时需要拷贝全部的 DB 文件，导致全量同步时磁盘 IO 持续变高，从而影响服务的响应延时。在 2.0 开始使用 CheckPoint 替换 Backup，CheckPoint 在同步目录和 DB 目录在同一个文件系统时会使用硬连接而不是拷贝，所以全量同步创建 CheckPoint 对磁盘 IO 几乎没有影响，同时整个过程的耗时也比创建 Backup 低很多。
整体流程如下:
-
从库启动时，先检查 Auth 和 DB Name 是否正确，DB Name 主要是为了防止从库连错主库而导致数据被覆盖；
-
接着从库发送当前 DB 的 Sequence Number，主库根据 Sequence Number 确认是否可以进行增量同步；
-
如果 Sequence Number 在当前保留的 WAL 范围之内，则允许增量同步，使用 RocksDB 的
GetUpdateSinceAPI 将 Sequence 之后的写入批量同步到从库。否则，进入全量同步 (Full Sync) 流程； -
全量同步过程中，从库先发送 Fetch Meta 来获取 Meta 数据，主库会先创建 CheckPoint，并发送全量同步的 Meta 信息到从库（Meta 主要包含了需要拉取的文件列表）。
-
从库根据 Meta 信息主动批量拉取 CheckPoint 文件，如果已经在从库存在的文件则会跳过。同时，从库拉取文件可能占用比较多的带宽，可以通过配置
max-replication-mb来限制拉取的带宽，默认是不限制； -
全量同步成功之后回到 Step 2，重新尝试增量同步，以此循环直到成功为止。
总结
不管从功能设计还是行为上，Kvrocks 始终以和 Redis 保持一致为目标，致力让用户在体验上和 Redsis 做到完全无缝，但 Kvrocks 也不会受限于 Redis，我们也会根据 Kvrocks 磁盘存储的特性，对部分 Redis 行为进行改进和优化。演进方向上，2021 年已经完成的 Milestone 2.0[7] 是 Kvrocks 功能上的重大里程碑，而 2022 年的 Milestone 3.0[8] 则是在云原生的重要里程碑。我们努力让 Kvrocks 在云上使用、性能以及运维都能够变得更友好。
另外，作为纯开源社区和组织，目标达成完全靠社区贡献者的不懈努力和无私付出，希望有更多人使用、反馈和参与开源社区的建设。而对于我们能做的是如 Code Of Conductor 所提及，保持透明、尊重和友好的社区交流，让每个 PR 都能在社区找到上下文，让每个人都能轻松地参与到社区讨论和贡献，也让每个人的贡献都能被看见。
参考资料
[1] Design Complex Structure On RocksDB: https://github.com/KvrocksLabs/kvrocks/blob/unstable/docs/metadata-design.md
[2] Spanner: Google’s Globally-Distributed Database: https://static.googleusercontent.com/media/research.google.com/en//archive/spanner-osdi2012.pdf
[3] PR 363: https://github.com/KvrocksLabs/kvrocks/pull/363
[4] PR 369: https://github.com/KvrocksLabs/kvrocks/pull/369
[5] Transaction can't guarantee atomicity: https://github.com/KvrocksLabs/kvrocks/issues/487
[6] PR 98: https://github.com/KvrocksLabs/kvrocks/pull/98
[7] 2.0: https://github.com/KvrocksLabs/kvrocks/projects/1
[8] 3.0: https://github.com/KvrocksLabs/kvrocks/projects/2
[9] Code Of Conductor: https://github.com/KvrocksLabs/kvrocks/blob/unstable/CODE_OF_CONDUCT.md
[10] Issue 485: https://github.com/KvrocksLabs/kvrocks/issues/485
