共识算法

概述

参考：

• 知乎大佬

分布式系统中，如何保证集群中所有节点中的数据完全相同并且能够对某个提案(Proposal)达成一致，是分布式系统正常工作的核心问题，而 共识算法 就是用来保证分布式系统一致性的方法。有时候，共识算法也称为“一致性算法”。

Note： 提案(Proposal) # 在分布式系统中，Proposal 指分布式系统的修改请求，比如当一个客户端将一个数据写入到分布式系统中，负责接收数据的节点就会发起提案，让集群中其余节点写入该数据。

共识算法的实现：

• Paxos #
• ZAB(muti-paxos) #
• Raft(muti-paxos) # Paxos 算法不易实现，Raft 算法是对 Paxos 算法的简化和改进
• Gossip # 这是一个协议，与 Raft 等公式算法不太一样

由于共识算法的特点(下文会详细介绍，可以看完算法介绍再来看这段描述)，所以一般保证一致性的分布式系统的节点数都是都是奇数个。

Raft 算法

参考：

• 动画演示

一个节点一般具有三种状态：

1. Leader # 领导者，负责发出提案
2. ** Candidate** # 候选人，负责争夺 Leader
3. Follower # 追随者，负责同意 Leader 发出的提案

名词解释：

1. voted # 投票
2. term # 期限、任期。用来代指 Leader 产生到结束这一时间段

Leader 的产生

1. 所有节点的初始状态都是以 Follower，并且持有一个定时器(各节点定时器时间随机，以保证不会同时触发选举)。
   1. 该定时器被随机分配在 150ms 和 300ms 之间
2. 如果 Followers 在定时器时间到了，而没有收到 Leader 信息的话。那么 Follower 则声明自己是 Candidate 并参与 Leader 选举(此时为自己投票)，同时将请求发给其他节点来争取他们的投票，若其他节点长时间没有响应 Candidate，将重新发送选举信息。
3. 如果接收投票信息的节点在这个 term 中还没有投过票，那么该节点将对发起该请求的 Candidate 投票，并且该节点重置定时器。
4. Candidate 计算总票数(自己+其他节点)，得票数大于 (n+1)/2 时(n 为节点数，除不开向下取整)，则该 Candidate 将称为第 M 任 Leader (M 任是最新的 term)
   1. Note：这里面所谓的投票与现实意义中的投票不太一样，没有投同意或者不同意这种说法。
   2. 值要对目标投票，目标就会计算一份得票数
5. Leader 在 term 内会不断发送心跳信息给集群内其他节点证明自己还活着，其他节点在收到心跳后会清空自己的定时器并回复 Leader 的心跳。这个机制保证其他节点不会在 Leader 任期内参加 Leader 选举。
6. 当 Leader 节点出现故障而导致 Leader 失联，没有接收到心跳的 Follower 节点将准备成为 Candidate 进入下一轮 Leader 选举(回到步骤 1)。
7. 若出现两个 Candidate 同时选举并获得了相同的票数，那么这两个 Candidate 将随机推迟一段时间后再向其他节点发出投票请求，这保证了再次发送投票请求以后不冲突。

状态复制

1. Leader 负责接收来自 Client 的提案请求。
   1. 比如提案内容是：写入一个数值 5 。
2. 提案内容将包含在 Leader 发出的下一个心跳中。
3. Follower 接收到心跳以后回复 Leader 的心跳
4. Leader 接收到多数 Follower 的回复以后，确认提案并写入自己的存储空间并回复 Client 。
5. Leader 通知 Follower 节点确认提案并向存储空间写入内容，随后所有的节点都拥有相同的数据。
6. 若集群中出现网络异常，导致集群被分割，将出现多个 Leader。(比如 5 节点集群被分割成两个集群，一个 2 节点，一个 3 节点)
7. 被分割出的少数节点的集群将无法达到共识，即脑裂。
   1. 在状态复制时，……….未知
8. 当网络恢复，集群恢复之后，将只听从最新任期 Leader 的指挥，旧 Leader 将
9. …….未知