注：本文内容引用自张洋老师的知乎文章 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，这样日志中的数据逐渐会有很多垃圾数据需要清理。
