注：本文内容引用自张洋老师的知乎文章 https://zhuanlan.zhihu.com/p/11148286254，他是一位存储研发专家。
本文主要讨论基于 RAFT 协议实现的分布式存储，其硬盘状态机的实现方法，以及其中遇到的问题和挑战。
下图是 RAFT 论文中关于 RAFT 架构模型的简图。如图所示，系统包含多个客户端和多个服务器，客户端发起命令，例如写数据的请求。服务端将收到的请求先写入到日志区（log）中，待 RAFT 的多数副本都将这条日志持久化以后，再分别写入状态机（state machine）。状态机是这条写请求真正要操作的地方，每一次写请求使得状态机由一个状态改变为另一个状态，因此称为状态机。
通过 RAFT 协议，可以保证不同副本的状态按照相同的顺序变化，因此 RAFT 的多个状态机的数据最终保持一致。而且通过 RAFT 协议的强 Leader 特性，所有的请求都由 Leader 处理，所以任何时刻，只要写入成功的数据，无论 Leader 如何切换，都可以读取到一致的数据。
状态机可以在各种介质上实现，可以是内存，也可以是硬盘。对于分布式存储系统来说，客户端写入的数据最终需要持久化到硬盘上，因此基于 RAFT 实现的分布式存储系统需要实现硬盘状态机。然而，在实现硬盘状态机时，会遇到两个显著的问题：1）RAFT 如何保证能够传递一个完整一致的状态机快照给落后的 Follower ? 2）如何解决写日志和写状态机的双写带来的写放大问题。
首先来看看这篇论文 “CONSENSUS: BRIDGING THEORY AND PRACTICE” 中关于这两个问题的讨论，然后再结合 zStorage 分布式存储系统中的解决方案，对这些问题做一些剖析。
“CONSENSUS: BRIDGING THEORY AND PRACTICE” 这篇论文是 Diego Ongaro 和 John Ousterhout 在原版 RAFT 论文基础上进一步探索分布式共识的扩展性工作。与原版 RAFT 论文（_In Search of an Understandable Consensus Algorithm_）相比，这篇论文多了一些 理论和实际应用之间的桥梁内容。
问题 1：RAFT 如何保证能够传递一个完整一致的状态机快照给落后的 Follower？
随着客户端不断发起请求，RAFT 的日志逐渐积累，因此需要对过时的日志进行删除（compaction）。那么，哪些日志是“过时的日志”呢？如果日志已经成功应用到状态机并完成了持久化，那么这些日志不再被需要，可以安全删除。假设 RAFT Leader 写入了 100 条日志，其中 90 条已经成功应用到状态机，通过 RAFT 的 take snapshot 操作，删除了这 90 条日志。
那么会出现一个问题：一个落后的 Follower 只包含了 80 条日志，不能通过同步 Leader 的日志来恢复。这时需要复制 Leader 通过 take snapshot 形成的状态机快照，这个快照包含了 80 条日志应用后的数据。完成快照同步后，再同步日志，最后 Follower 追上了 Leader，数据达成一致。然而实际上，状态机的数据规模远远大于 80 条日志，可能达到 TB 级别，这对落后 Follower 的数据同步来说是一个重大挑战。
在论文中大致提及到两种方法：一种是基于原地写（write in place）的方法，另外一种是基于追加写（append only）的方法。这两种方法理论上都可以传递完整一致的状态机镜像到落后的 Follower，但也面临着实际的问题。
原地写的方法
原地写的方法的主要问题是：在 RAFT 打快照时，需要同时给状态机打快照，以便可以方便地将某条日志之前的状态机镜像拷贝到落后的 Follower 上。但是在拷贝状态机快照镜像的过程中，可能会有新的用户 I/O 请求需要处理，这样在状态机镜像之外，可能会逐渐积累许多新增数据。论文中认为，这些新增的数据量不会太大，稍后通过同步 RAFT 日志即可。
但是在实际的分布式存储系统中，为了保证可用性，一方面会限制后台数据的流量，这样同步状态机镜像的时间肯定会被拉长。另一方面，在高速 NVME SSD 的加持下，前台用户 I/O 的写入性能可以达到单盘 2GB/s，甚至更高。那么 5~10 分钟就可以写入 1TB 数据，这么短的时间内，Follower 可能还未完成状态机镜像的同步，这时又会积累大量新增数据。这样一来，一方面硬盘空间浪费不小，另一方面 Follower 也很难追上 Leader 的进度，使得集群的可用性无法保证。
zStorage 分布式存储系统，同样基于 RAFT 实现，也采用了硬盘状态机原地写的实现方法：即数据先写到 RAFT 日志，再应用到硬盘状态机。不过当需要通过打快照删除过时的无效日志时，为了避免上述问题，zStorage 并未将状态机整体打一个快照，而是采用了一种新的方法，缓解了空间浪费和集群可用性问题。
在 zStorage 的硬盘状态机实现中，状态机由有限个 4MB 的 chunk 组成。这些 chunk 可以按照一个固定的顺序遍历，也可以认为 chunk 是有序的。简单理解为：chunk0, chunk1, chunk2, chunk3, ….. chunkn。然后在复制状态机到落后的 Follower 时，采用了一种方法：按照 chunk 的先后顺序，先复制一些 chunk 到 Follower，再复制一些日志到 Follower，如此交替进行。在复制过程中，维护一个分界线（chunk id），该分界线之前的部分是已经复制完成的，分界线之后的是未复制完成的。
当有新的 I/O 请求时，分为两种情况讨论：1）I/O 请求落在分界线之前，那么由于分界线之前的部分，Follower 和 Leader 已经一致，可以正常地 append 和 apply。2）I/O 请求落在分界线之后，Follower 只需要 append 日志，可以不 apply 到状态机。随着分界线的后移，稍后会将包含该请求数据的 chunk 复制过来。大致图示如下：
这种复制硬盘状态机的方法，无需对状态机打快照镜像，同时可以细粒度地控制复制 chunk 占用的资源（网络带宽、硬盘带宽等）。因为上述“分界线”一定是逐渐右移，最终肯定会完成复制。而论文中所说的方法，依赖拷贝状态机过程新增数据量的大小，实际上这一点不一定能保证。zStorage 实现的硬盘状态机复制方法，在各种复杂的情境下，都能良好工作。
问题 2：原地写的方式存在双写问题，即先写日志再写状态机，导致的写放大问题，如何解决？
追加写的方法
要解决双写问题，目前看起来比较靠谱的方法是：追加写的方法。通过不断地将数据追加到日志中，不再将数据应用到状态机，而是采用“日志即状态机”的方法。因为所有用户写入的数据都保存在日志中，所以从日志中可以读取到全部的写入数据。不过，随着用户 I/O 对数据的改写，比如原本 offset=1024, len=512 的数据由全 1 改成全 2，这样日志中的数据逐渐会有很多垃圾数据需要清理。
这便是关于日志清理的方法，论文中介绍了两种实现方式：a）直接删除日志中的过时日志，但是这样会形成空洞，导致处理起来非常麻烦。b）状态机自己实现日志记录结构，这样可以使其与 RAFT 日志独立开，模块化效果更好。
目前在 zStorage 中没有实现“日志清理”这种方式。不过我个人感觉，采用类似方法 a 更加适用于 zStorage。那么，要实现“日志清理”的方法，对于 zStorage 来讲，主要有两个改造点：
1）硬盘状态机部分，不再单独记录数据，只记录索引。zStorage 是基于哈希实现的硬盘数据索引，其中 key =（volume id, chunk id），value = 4MB 的 chunk。改造后，由于 chunk 不用记录数据，因此可以减小大小，只记录每个 block（4KB）在日志中的位置。因此，在 RAFT 日志应用时，只需要修改数据指向即可。对于大 I/O 请求来讲，这样有效地减少了写放大问题。
2）重点还是“日志清理”。大致思路是定期扫描日志数据（元数据部分），并询问硬盘状态机，日志是否还被引用。以此为依据清理垃圾数据。随着垃圾的清理，无效的日志 segment 可以整块删除，其他一些 segment 可能会形成空洞，实际有效数据不多，可以合并在一起。“日志清理”这种方式大体可行，但也会有一些负面影响：首先是增加代码流程，会争用 CPU、内存、硬盘等资源；另外，“日志清理”带来的数据搬移也会产生硬盘写 I/O，并且与 I/O 模型密切相关。对于顺序写来说，主要是删除垃圾 segment 带来的开销，影响可控；但对于随机 I/O，会产生大量的数据搬移，如果搬移频率太慢，会导致空间浪费较大；反之，则会增加硬盘 I/O 压力，无法达到减少写放大的目的。
LSM tree 的方法
LSM tree 也是一种追加写的方法。该方法广泛应用于多种开源和商业存储系统，例如：rocksdb、阿里云的 EBS 等。LSM tree 的工作原理大致如下：随着数据的 append 写入，会形成一个个的 segment，在 LSM tree 中被称为 SSTable（硬盘中），内存中为 Memtable。当 Memtable 增长到一定大小后，会进行排序并合并数据，然后写入到盘上的 level0 层。后台会有一个 compaction 任务，定期将 level0 合并排序，放入到 level1 层，以此类推，形成一个树形结构。
越处于上层的数据越新，反之越旧。读取数据时，从新到旧层层查找，直到找到或找不到所需数据。读请求采用如图所示的布隆过滤器（Bloom Filter）进行优化，通过布隆过滤器可以减少很多不必要的查询。LSM tree 实际上与“日志清理”方法类似。这种追加写的方式，在复制 RAFT 快照数据到慢 Follower 时非常自然，因为所有写请求都是追加的。拷贝任何一个时间点之前的数据，都是拷贝不会再被修改的数据，不会有任何冲突。
但是对于 zStorage 来说，LSM tree 相当于是一套全新的本地存储架构，改造跨度相当大，不太切合实际。而针对自身的数据结构，实现一套符合实际的“日志清理”改造，相对来说更加容易。
总结
总体来说，硬盘状态机主要有两种实现方法。一种是原地写的方式，这种方式存在双写问题、写放大问题，并且实现压缩、EC 等特性比较麻烦，加之复制状态机镜像也较为繁琐；另一种是追加写的实现方法，这种方式没有双写问题，但在进行 GC 数据时带来的 I/O 需要谨慎处理，对于实现压缩、EC 以及复制状态机镜像，相对来说更加容易处理。
扩展阅读：《企业存储技术》文章分类索引（微信公众号专辑）》
END
作者：张洋
原文：企业存储技术
推荐阅读
欢迎关注企业存储技术极术专栏，欢迎添加极术小姐姐微信（id:aijishu20)加入技术交流群，请备注研究方向。
