分布式算法#

拜占庭将军问题是最复杂的分布式故障场景，节点除了故障行为，还有恶意行为。必须使用拜占庭容错算法（BFT），比如在数字货币的区块链技术中。

拜占庭容错算法#

1. 口信消息型拜占庭问题之解#

如果叛将人数为 m，将军人数不能少于 3m + 1 ，那么拜占庭 将军问题就能解决了。

这个算法有个前提，也就是叛将人数 m，或者说能容忍的叛将数 m，是已知的。在这个算法中，叛将数 m 决定递归循环的次数（也就是说，叛将数 m 决定将军们要进行多少轮作战信息协商），即 m+1 轮（所以，你看，只有楚是叛变的，那么就进行了两轮）。

2. 签名消息型拜占庭问题之解#

签名无法伪造，而且对他签名消息的内容进行任何更改都会被发现，这样的话也就会实现无论有多少忠诚的将军和多少叛 将，忠诚的将军们总能达成一致的作战计划，不过也需要进行 m 次协商。

3.PBFT 算 法#

4.PoW 算法#

非拜占庭容错算法#

即故障容错算法（Crash Fault Tolerance，CFT），CFT 解决的是分布式的系统中存在故障，但不存在恶意节点的场景下 的共识问题。 也就是说，这个场景可能会丢失消息，或者有消息重复，但不存在错误消 息，或者伪造消息的情况。常见的算法有 Paxos 算法、Raft 算法、ZAB 协议。

Paxos 算法，最常用的一批共识算法都是基于它改进的。比如，Fast Paxos 算法、 Cheap Paxos 算法、Raft 算法、ZAB 协议等等。

Basic Paxos 算法#

描述的是多节点之间如何就某个值（提案 Value）达成共识；

假设我们要实现一个分布式集群，这个集群是由节点 A、B、C 组成，客户端 1 试图创建值为 3 的 X，客户端 2 试图创建值为 7 的 X，这样要如何达成 共识，实现各节点上 X 值的一致呢？

Raft 算法#

从本质上说，Raft 算法是通过一切以领导者为准的方式，实现一系列值的共识和各节点日志的一致。这句话比较抽象，我来做个比喻，领导者就是 Raft 算法中的霸道总裁，通过霸道的 “一切以我为准” 的方式，决定了 日志中命令的值，也实现了各节点日志的一致。Raft 算法是强领导者模型，集群中只能有一个 “霸道总裁”。

服务节点由三种身份状态

跟随者：就相当于普通群众，默默地接收和处理来自领导者的消息，当等待领导者心跳 信息超时的时候，就主动站出来，推荐自己当候选人。

候选人：候选人将向其他节点发送请求投票（RequestVote）RPC 消息，通知其他节点 来投票，如果赢得了大多数选票，就晋升当领导者。

领导者：蛮不讲理的霸道总裁，一切以我为准，平常的主要工作内容就是 3 部分，处理 写请求、管理日志复制和不断地发送心跳信息，通知其他节点 “我是领导者，我还活 着，你们现在不要发起新的选举，找个新领导者来替代我。

领导者选举过程#

每个节点都有一个随机的超时时间，超过这个时间没有收到领导者心跳信号，节点马上变为候选人，并向其他节点发送选举请求，让他们投票自己做领导者。获得投票过半的节点就是领导者，然后不断向其他节点发送心跳。

节点如何通讯？

在 Raft 算法中，服务器节点间的沟通联络采用的是远程过程调用（RPC），在领导者选举 中，需要用到这样两类的 RPC：

1. 请求投票（RequestVote）RPC，是由候选人在选举期间发起，通知各节点进行投票；

2. 日志复制（AppendEntries）RPC，是由领导者发起，用来复制日志和提供心跳消息。

   我想强调的是，日志复制 RPC 只能由领导者发起，这是实现强领导者模型的关键之一，希 望你能注意这一点，后续能更好地理解日志复制，理解日志的一致是怎么实现的。

什么是任期？

1. 跟随者在等待领导者心跳信息超时后，推举自己为候选人时，会增加自己的任期号，比 如节点 A 的当前任期编号为 0，那么在推举自己为候选人时，会将自己的任期编号增加 为 1。

2. 如果一个服务器节点，发现自己的任期编号比其他节点小，那么它会更新自己的编号到 较大的编号值。比如节点 B 的任期编号是 0，当收到来自节点 A 的请求投票 RPC 消息 时，因为消息中包含了节点 A 的任期编号，且编号为 1，那么节点 B 将把自己的任期编 号更新为 1。

3. 在 Raft 算法中约定，如果一个候选人或者领导者，发现自己的任期编号比其他节点小， 那么它会立即恢复成跟随者状态。比如分区错误恢复后，任期编号为 3 的领导者节点 B，收到来自新领导者的，包含任期编号为 4 的心跳消息，那么节点 B 将立即恢复成跟 随者状态。

4. 还约定如果一个节点接收到一个包含较小的任期编号值的投票请求，那么它会直接拒绝这个请求。比如节点 C 的任期编号为 4，收到包含任期编号为 3 的请求投票 RPC 消息，那它将拒绝这个消息。

5. 任期编号相同时，日志完整性高的跟随者（也就是最后一条日志项对应的任期编号值 更大，索引号更大），拒绝投票给日志完整性低的候选人。

随机超时时间

为了防止同一时间，多个节点同时发起选举，跟随者等待领导者心跳信息超时的时间间隔，是随机的。

当没有候选人赢得过半票数，选举无效了，这时需要等待一个随机时间间隔，也就是 说，等待选举超时的时间间隔，是随机的。

Raft 的日志#

道 Raft 除了能实现一系列值的共识之外，还能实现各节点日志的一致

日志是由日志项组成，日志项是一种数据格式，它主要包含用户指定的数据，也就是指令，比如 set x=3， 还包含一些附加信息，比如索引值（Log index）、任期编号（Term）。

指令：一条由客户端请求指定的、状态机需要执行的指令。你可以将指令理解成客户端 指定的数据。

索引值：日志项对应的整数索引值。它其实就是用来标识日志项的，是一个连续的、单 调递增的整数号码。

任期编号：创建这条日志项的领导者的任期编号。

如何复制日志？#

优化后的二阶段提交

领导者接收到客户端命令，首先，领导者进入第一阶段，通过日志复制（AppendEntries）RPC 消息，将日志项复制到集群其他节点上。 接着，如果领导者接收到大多数的 “复制成功” 响应后，它将日志项提交到它的状态机，并返回成功给客户端。如果领导者没有接收到大多数的 “复制成功” 响应，那么就返回错误给客户端。

学到这里，有同学可能有这样的疑问了，领导者将日志项提交到它的状态机，怎么没通知跟随者提交日志项呢？ 这是 Raft 中的一个优化，领导者不直接发送消息通知其他节点提交指定日志项。因为领导者的日志复制 RPC 消息或心跳消息，包含了当前最大的，将会被提交的日志项索引值。所以通过日志复制 RPC 消息或心跳消息，跟随者就可以知道领导者的日志提交位置信息。 因此，当其他节点接受领导者的心跳消息，或者新的日志复制 RPC 消息后，就会将这条日 志项提交到它的状态机。而这个优化，降低了处理客户端请求的延迟，将二阶段提交优化为 了一段提交，降低了一半的消息延迟

1. 接收到客户端请求后，领导者基于客户端请求中的指令，创建一个新日志项，并附加到本地日志中
2. 领导者通过日志复制 RPC，将新的日志项复制到其他的服务器。
3. 当领导者将日志项，成功复制到大多数的服务器上的时候，领导者会将这条日志项提交到它的状态机中。
4. 领导者将执行的结果返回给客户端。
5. 当跟随者接收到心跳信息，或者新的日志复制 RPC 消息后，如果跟随者发现领导者已经提交了某条日志项，而它还没提交，那么跟随者就将这条日志项提交到本地的状态机中。

如何实现日志的一致？#

如果某些节点出现宕机或者网络故障，日志就会出现不一致。

在 Raft 算法中，领导者通过强制跟随者直接复制自己的日志项，处理不一致日志。也就是 说，Raft 是通过以领导者的日志为准，来实现各节点日志的一致的。需要你注意的是，跟随者中的不一致日志项会被领导者的日志覆盖，而且领导者 从来不会覆盖或者删除自己的日志。

Raft 成员变更#

当往集群增加节点或者减少节点，节点数不同，选举结果可能会不同。

本作品采用《CC 协议》，转载必须注明作者和本文链接