13 智慧之火：详解分布式容错共识算法
你好，我是郑建勋。
上节课，我们说分布式系统总是需要在可用性和数据一致性之间找到平衡，也就是既要确保当少部分节点发生故障时，程序仍然能够正确且正常地运行，又要保证分布式节点之间对某一事件达成共识。其实这并不是一件容易的事情，好在许多容错共识算法为我们提供了经过检验的解决方案。
可用性衡量了系统面对网络延迟、网络分区、系统故障时的容错能力。显然，如果我们遇到了极端的事件，例如地球毁灭了，我们是无法保证系统可用的。因此，大多数容错共识算法都会有一个前提，也就是至少需要大部分节点是正常的，这样系统才可以正常运行。
此外，大多数容错共识算法还有第二个前提，就像我在上节课提到的，不考虑节点中可能混入了攻击者，这样才能保证系统不会出现拜占庭问题。
而要保证数据一致性，当前比较有名的算法是：Paxos、Raft和Zab。我将其称为分布式容错共识算法，容错代表了在异常情况下仍然具有可用性和正确性，而共识代表的是数据的一致性，它意味着即便是在并发、异常等情况下也能达成共识。
Raft在现代分布式系统中有着重要的地位，K8s和课程中用到的etcd组件底层都采用了Raft算法。这节课，我就以Raft算法为例讲解容错共识算法是如何实现数据的一致性与可用性的。
我们先从与Raft密切相关的Paxos算法开始讲起。
Paxos算法
Paxos算法是历史比较悠久的容错共识算法，他由Lamport在20世纪80年代末期提出。
Paxos算法中的节点分为了3个角色。
- 提议者（proposer）：负责提出一个值。
- 接收者（acceptor）：负责选择一个值。
- 学习者（learner）： 负责学习被选中的值。
简单来说，Paxos算法可分为如下几个过程：
- 提议者选择一个提议编号n，并把prepare请求发送给大多数接收者；
- 接收者回复一个大于等于n的提议编号；
- 提议者收到回复，并记录这些回复中最大的提议编号，然后将被选中的值和这个最大的提议编号作为一个accept请求，发送给对应的接收者；
- 如果一个接收者收到一个编号为n的accept请求，那么除非它已经回复了一个编号比n大的prepare请求，否则它会接受这个提议；
- 当接收者接受一个提议后，它会通知所有的learner这个提议，最终所有的节点都会就一个节点的提议达成一致。
Paxos算法的核心思想是，通过让proposer与大多数acceptor提前进行一次交流，让proposer感知到当前提出的值是否可能被大多数acceptor接收。如果不能被接收，proposer可以改变策略之后（例如增加提议编号，或接收某一个proposer已经提出的值）再继续进行协调，最终让大多数接收者就某一个值达成共识。Paxos通过一个提议编码保证了后面被接收的值一定是编号更大的值，从而实现了写操作的线性一致性。
不过，Paxos算法虽然描述起来非常简单，但是要完全理解它的原理却比较难。并且，Paxos算法的官方描述中缺少对实现细节的诸多定义，导致实践中可以有多种灵活的实现方式。如果你对这个复杂的算法感兴趣的话，可以看看《分布式系统与一致性》这本书的第十章。
Raft算法
总的来说，Paxos理解起来还是比较困难，在工程上也比较难以实现，所以不太常用，Raft算法就是在这一背景下诞生的。Raft算法简单、容易理解、容易实现，已经成为现代多数分布式系统（例如etcd、TiDB）采用的算法。
Raft算法实现了一种复制状态机。每个分布式的状态机中存储了一份包含命令序列的日志文件，这些文件通过复制的形式传播到其他节点中。每个日志包含相同的命令，并且顺序也相同。状态机会按顺序执行这些命令并产生相同的状态，最终所有的状态机都将达到一个确定的最终状态。
在Raft算法中，每一个节点会维护一份复制日志（Replicated Log），复制日志中存储了按顺序排列的条目（Entry），用户执行的每一个操作都会生成日志中的一个条目，稍后这个条目会通过节点之间的交流复制到所有节点上。
如果一个条目是被大多数节点认可的，那么这种条目被称为Committed Entry，这也是节点唯一会执行的条目类型。各个节点只要按顺序执行复制日志中的Committed Entry，最终就会到达相同的状态。这样，即便节点崩溃后苏醒，也可以快速恢复到和其他节点相同的状态。
总结一下Raft算法的核心思想就是，保证每个节点具有相同的复制日志，进而保证所有节点的最终状态是一致的。
基本原理
Raft中的节点有3种状态，领导者（Leader），候选人（Candidate）和跟随者（Follower）。
其中，Leader是大多数的节点选举产生的，并且节点的状态可以随着时间发生变化。某个Leader节点在领导的这段时期被称为任期（Term）。新的Term是从选举Leader时开始增加的，每次Candidate节点开始新的选举，Term都会加1。
如果Candidate选举成为了Leader，意味着它成为了这个Term后续时间的Leader。每一个节点会存储当前的Term，如果某一个节点当前的Term小于其他节点，那么节点会更新自己的Term为已知的最大Term。如果一个Candidate发现自己当前的Term过时了，它会立即变为Follower。
一般情况下（网络分区除外）在一个时刻只会存在一个Leader，其余的节点都是Follower。Leader会处理所有的客户端写请求（如果是客户端写请求到Follower，也会被转发到Leader处理），将操作作为一个Entry追加到复制日志中，并把日志复制到所有节点上。而Candidate则是节点选举时的过渡状态，用于自身拉票选举Leader。
Raft节点之间通过RPC（Remote Prcedure Cal，远程过程调用）来进行通信。Raft论文中指定了两种方法用于节点的通信，其中，RequestVote 方法由Candidate在选举时使用，AppendEntries则是Leader复制log到其他节点时使用，同时也可以用于心跳检测。RPC 方法可以是并发的，且支持失败重试。
Raft算法可以分为三个部分：选举、日志复制和异常处理。下面我们分阶段介绍一下。
选举与任期
在Raft中有一套心跳检测，只要Follower收到来自Leader或者Candidate的信息，它就会保持Follower的状态。但是如果Follower一段时间内没有收到RPC请求（例如可能是Leader挂了），新一轮选举的机会就来了。这时Follower会将当前Term加1并过渡到Candidate状态。它会给自己投票，并发送RequestVote RPC请求给其他的节点进行拉票。
Candidate的状态会持续，直到下面的三种情况发生。
- 如果这个Candidate节点获得了大部分节点的支持，赢得选举变为了Leader。一旦它变为Leader，这个新的Leader节点就会向其他节点发送 AppendEntries RPC， 确认自己Leader的地位，终止选举。
- 如果其他节点成为了Leader。它会收到其他节点的AppendEntries RPC。如果发现其他节点的当前Term比自己的大，则会变为Follower状态。
- 如果有许多节点同时变为了Candidate，则可能会出现一段时间内没有节点能够选举成功的情况，这会导致选举超时。
为了快速解决并修复这第三种情况，Raft规定了每一个Candidate在选举前会重置一个随机的选举超时（Election Timeout）时间，这个随机时间会在一个区间内（例如150-300ms）。
随机时间保证了在大部分情况下，有一个唯一的节点首先选举超时，它会在大部分节点选举超时前发送心跳检测，赢得选举。如果一个Leader在心跳检测中发现另一个节点有更高的Term，它会转变为Follower，否则将一直保持Leader状态。
日志复制（Log Replication）
一个节点成为Leader之后，会开始接受来自客户端的请求。每一个客户端请求都包含一个节点的状态机将要执行的操作（Command）。Leader会将这个操作包装为一个Entry放入到log中，并通过AppendEntries RPC 发送给其他节点，要求其他节点把这个Entry添加到log中。
当Entry被复制到大多数节点之后，也就是被大部分的节点认可之后，这个Entry的状态就变为Committed。Raft算法会保证 Committed Entry 一定能够被所有节点的状态机执行。
一旦Follower通过RPC协议知道某一个Entry被commit了，Follower就可以按顺序执行log中的Committed Entry了。
如图所示，我们可以把log理解为Entry的集合。Entry中包含了Command命令（例如x←3），Entry所在的Term（方框里面的数字），以及每一个Entry的顺序编号（最上面标明的log index，顺序递增）。
但这里还有一个重要的问题，就是Raft节点在日志复制的过程中需要保证日志数据的一致性。要实现这一点，需要确认下面几个关键的属性：
- 如果不同节点的log中的Entry有相同的index和Term, 那么它们存储的一定是相同的Command；
- 如果不同节点的log中的Entry有相同的index和Term，那么这个Entry之前所有的Entry都是相同的。
接下来我们就来看看，Raft算法是怎么在不可靠的分布式环境中保证数据一致性的。
在实际生产过程中，Raft算法可能会因为分布式系统中遇到的难题（例如节点崩溃），出现多种数据不一致的情况。如下所示，a → f分别代表Follower的复制日志中可能遇到的情况，方框中的方格表示当前节点复制日志中每一个Entry对应的Term序号。
a → e的情况你可以想一想什么时候会发生，我在这里重点解释一下f这种情况，因为f看起来是最奇怪的。
f这种情况可能是这样的：f是Term 2的Leader, 它添加Entry到log中之后，Entry还没有复制到其他节点，也就是说，还没等到commit就崩溃了。但是它快速恢复之后又变为了Term 3 的Leader， 再次添加Entry到log之后，没有commit又崩溃了。当f再次苏醒时，世界已然发生了巨变。
所以我们可以看到，在正常的情况下，Raft可以满足上面的两个属性，但是异常情况下，这种情况就可能被打破，出现数据不一致的情况。为了让数据保持最终一致，Raft算法会强制要求Follower的复制日志和Leader的复制日志一致，这样一来，Leader就必须要维护一个Entry index了。在这个Entry index之后的都是和Follower不相同的Entry，在这个Entry之前的都是和Follower一致的Entry。
Leader会为每一个Follower维护一份next index数组，里面标志了将要发送给Follower的下一个Entry的序号。最后，Follower会删除掉所有不同的Entry，并保留和Leader一致的复制日志，这一过程都会通过AppendEntries RPC 执行完毕。
不过，仅仅通过上面的措施还不足以保证数据的一致性。想想下图这个例子：
从这张图可以看出，一个已经被Committed的Entry是有可能被覆盖掉的。例如在a阶段，节点s1成为了Leader，Entry 2还没有成为Committed。在b阶段，s1崩溃，s5成为了Leader ，添加Entry到自己的log中，但是仍然没有commit。在c阶段，s5崩溃，s1成为了Leader，而且在这个过程中Entry 2成为了Committed Entry。接着在d阶段s1崩溃，s5成为了Leader，它会将本已commit的Entry 2给覆盖掉。但我们真正想期望的是e这种情况。
怎么解决这个问题呢？Raft使用了一种简单的方法。Raft为Leader添加了下面几个限制：
- 要成为Leader必须要包含过去所有的Committed Entry；
- Candidate要想成为Leader，必须要经过大部分Follower节点的同意。而当Entry成为Committed Entry时，表明该Entry其实已经存在于大部分节点中了，所以这个Committed Entry 会出现在至少一个Follower节点中。因此我们可以证明，当前Follower节点中，至少有一个节点是包含了上一个Leader节点的所有Committed Entry的。Raft算法规定，只有当一个Follower节点的复制日志是最新的（如果复制日志的Term最大，则其日志最新，如果Term相同，那么越长的复制日志越新），它才可能成为Leader。
总结
在分布式系统中，让大多数节点就某一事件达成一致并不是一件容易的事情，因为会存在网络延迟，节点崩溃等异常情况，而这就是分布式容错共识算法为我们解决的问题。这节课，我们看到了分布式容错共识算法Raft构建复制状态机的过程，看到了它保证数据一致性的方法和在故障情况下的容错能力。
在Raft算法中，写请求具有线性一致性，但是读请求由于Follower节点数据暂时的不一致，可能会读取到过时的数据。因此，Raft保证的是读数据的最终一致性，这是为了性能做的一种妥协。但我们可以在此基础上很容易地实现强一致性的读取，例如将读操作转发到Leader再读取数据。
在容错方面，Raft通过合理的Leader选择以及Leader与Follower之间强制的日志同步，在保证数据正确性的基础上，也能保证当前Leader崩溃、网络分区、网络延迟之后大部分节点仍然能够正常工作。
Raft在工程上实现起来是相对比较容易的。在Raft的论文中对算法的实现细节有详细的描述，感兴趣的话推荐你看看。如果你想实践一下如何把枯燥的论文变为现实，我推荐给你两份资料，一个是MIT的经典分布式课程6.824，他用实验的形式最后用Go语言实现了Raft算法，另外你还可以参考一下etcd对Raft的实现。
思考题
最后，还是给你留两道思考题。
- 就像前面提到的，如果希望具有一致性读，一种手段是将读操作转发到Leader。但是当前的Leader并不一定是真正的Leader，例如，刚好网络分区导致Leader变更，这样的话，我们还是有可能读取到过时的数据。你知道怎么解决这类问题吗？
- Raft节点出现网络分区的情况，由于一部分节点由于无法与Leader取得通信，会一直增加Term号。在网络恢复后，由于这些节点Term号更大，因此会变为Leader。 然而这种处理看起来并不太合理，你知道有什么办法可以解决这个问题吗？
欢迎你在留言区与我交流讨论，我们下节课见！
- Realm 👍（3） 💬（0）
1 猜测一下，在结果返回给请求方之前，查下自己有没有收到新leader的心跳包，有的话，重新向新leader请求最新数据；没有的话，就把结果返回给请求者，这可能也还是有概率拿不到最新数据； 2 要成为 Leader 必须要包含过去所有的 Committed Entry；
2022-11-09 - 志豪 👍（2） 💬（0）
raft算法实践中都是采用单数节点，当网络出现分区，某区域内节点数不过半则区域内的node无法通过选举产生leader，客户端也就无法读取数据；网络恢复后，节点交少的分区域term会小于其他分区域，作为follower加入到集群中，并且复制leader的日志，保持数据一致性
2022-11-30 - 奕 👍（0） 💬（0）
我记得 如果读请求到达 follow 节点，follow会请求 leader 节点 来判断 commit index 是否是最新的， 如果不是就会进行同步，在进行响应
2022-11-17