Raft 选举机制

基本概念

Raft透过选举领袖（英语：leader）的方式做共识算法，Raft是一个共识算法，取代Paxos。Raft的目标是提供更好理解的算法，并且证明可以提供与Paxos相同的容错性以及性能。

在Raft集群（英语：Raft cluster）里，服务器可能会是这三种身份其中一个：领袖（英语：leader）、追随者（英语：follower），或是候选人（英语：candidate）。在正常情况下只会有一个领袖，其他都是追随者。而领袖会负责所有外部的请求，如果不是领袖的机器收到时，请求会被导到领袖。

通常领袖会借由固定时间发送消息，也就是“心跳（英语：heartbeat），让追随者知道集群的领袖还在运作。而每个追随者都会设计逾时机制（英语：timeout），当超过一定时间没有收到心跳（通常是150 ms或300 ms），集群就会进入选举状态。

Raft将问题拆成数个子问题分开解决，让人更容易了解：

• 领袖选举（英语：Leader Election）
• 记录复写（英语：Log Replication）
• 安全性（英语：Safety）

选举过程

1. 初始状态：当一个Raft集群启动时，所有的节点都处于初始状态，没有领导者。每个节点可以是以下三种状态之一：领导者（leader）、跟随者（follower）或候选人（candidate）。
2. 选举超时（Election Timeout）：在Raft中，时间被分割为连续的小段称为任期（term）。每个节点都有一个选举超时时间范围，在该时间范围内没有收到来自领导者的心跳消息，节点就会认为当前的领导者失效，触发选举过程。
3. 候选人状态：当节点的选举超时时间到达时，它将转变为候选人状态并开始选举过程。候选人会增加当前的任期号，并向其他节点发送请求投票的消息。
4. 请求投票（Request Vote）：候选人向其他节点发送请求投票的消息，请求其他节点投票支持自己成为领导者。消息中包含候选人的任期号、候选人的ID等信息。
5. 投票响应：收到请求投票消息的节点将根据一定的规则判断是否投票给候选人。节点会比较候选人的任期号和自己的任期号，如果候选人的任期号更大，并且在投票前没有投给其他候选人，就会投票给该候选人。
6. 选举胜利：如果候选人收到了大多数节点的投票，即获得了多数选票，那么它将成为新的领导者。候选人会向其他节点发送领导者的消息，以宣告自己的胜利。
7. 领导者的心跳：一旦成为领导者，它将定期发送心跳消息给其他节点，以维持自己的领导地位。这些心跳消息也用于告知其他节点当前的任期号。
8. 选举冲突：如果有多个候选人同时开始选举过程，可能出现选举冲突的情况。当多个候选人的任期号相同并且收到的投票数都不足以获胜时，它们将在下一个任期继续选举过程，直到有一个候选人获得多数选票。

通过以上的选举过程，Raft算法保证了在分布式系统中选出一个唯一的领导者，以便协调系统中的操作。选举过程中的任期号和投票机制确保了选举的正确性和一致性。当领导者失效时，其他节点可以及时地发现并重新选举出新的领导者，从而保证系统的可用性和稳定性。

CAP定理（Partition-tolerant, Available, Consistent）

在理论计算机科学中，CAP定理（CAP theorem），又被称作布鲁尔定理（Brewer's theorem），它指出对于一个分布式计算系统来说，不可能同时满足以下三点：

• 一致性（Consistency） （等同于所有节点访问同一份最新的数据副本）
• 可用性（Availability）（每次请求都能获取到非错的响应——但是不保证获取的数据为最新数据）
• 分区容错性（Partition tolerance）（以实际效果而言，分区相当于对通信的时限要求。系统如果不能在时限内达成数据一致性，就意味着发生了分区的情况，必须就当前操作在C和A之间做出选择。）

根据定理，分布式系统只能满足三项中的两项而不可能满足全部三项。理解CAP理论的最简单方式是想象两个节点分处分区两侧。允许至少一个节点更新状态会导致数据不一致，即丧失了C性质。如果为了保证数据一致性，将分区一侧的节点设置为不可用，那么又丧失了A性质。除非两个节点可以互相通信，才能既保证C又保证A，这又会导致丧失P性质。

Raft 遵循 可用性（Availability）和一致性（Consistency）

1. 可用性（Availability）：Raft算法确保了系统的可用性，即在任何时刻都能够响应客户端的请求。当领导者失效时，Raft算法会启动选举过程，尽快选出新的领导者，以保持系统的可用性。即使在网络分区（Partition）的情况下，Raft算法也能够继续运行并选出新的领导者。
2. 一致性（Consistency）：Raft算法通过选举过程来确保系统的一致性。在Raft中，只有获得大多数节点的支持（多数原则）的候选人才能成为领导者。这样做可以保证系统中的大多数节点达成一致，从而确保数据的一致性。当新的领导者选举出来后，它会通过心跳消息向其他节点发送自己的任期号，使系统中的节点保持一致。

PAC定理指出，在分布式系统中，无法同时满足网络分区（Partition）发生时的可用性、一致性和分区容忍（Partition-tolerance）。Raft算法通过在网络分区恢复后重新选举领导者来保证分区容忍性，同时强调了可用性和一致性的重要性。