Raft 共识算法

分布式一致性

首先从单点系统开始说起，可以把我们的数据库服务器看做是一个单点节点。当客户端发送一次改变到数据库时，一致性是很容易达成的。但是当我们有多个数据库节点时，该如何保证一致性？而 Raft 是一种实现了分布式一致性的协议，每一个节点都属于以下三种状态之一：

• 跟随者状态
• 候选人状态
• 领导者状态

选举

所有节点都从跟随者开始。如果跟随者没有收听到有来自领导者的信息，他们就可以成为候选人，接着候选人将请求来自其他节点的选票，而其他节点将进行投票表决，如果候选人从多数节点中获得了选票，他就成了领导者。

在 Raft 有两个超时设置来控制选举，首先是选举超时，选举超时是一个跟随者等待成为候选人的时间，选举超时随机分为 150ms 和 300ms 之间。选举超时后，跟随者成为候选人，并开始新的选举任期。接着对自己投票，并向其他的节点发送请求投票的信息。如果接收到的节点在这届任期中还没有投票，那么它将为候选对象投票，并重置自己的选举超时。一旦候选人有多数的选票，将成为领导者。领导者开始向其跟随者发送附加条目消息，这些消息是按心跳超时指定的间隔发送的，然后跟随者回复每一次的附加条目信息（同时重置自己的选举超时）。这届选举任期将一直持续到跟随者停止收到心跳请求，达到选举超时后成为候选人为止。

要求多数选票来保证每届任期只能选出一名领导人

如果两个节点同时成为候选人，则可能发生分裂投票。当两个节点都开始在同一届任期中选举，每一个候选人在其他候选人之前达到一个单一节点，若候选人在这届任期中获得了相同的投票数，那么这些节点会等待新的任期，并重试。

日志复制

所有对系统的改变都会经过领导者，每一次改变都将作为一项条目来添加到节点的日志中，此改变条目项在当前未提交，因此也不会更新节点的值。要提交条目，领导者节点首先将条目复制到所有的跟随者节点，然后领导者等待大多数节点写入条目，接着领导者节点会提交该条目并通知跟随者“改变条目已提交”。现在集群已经对系统状态达成一致性。

一旦我们选出了一个领导者，我们就需要将系统的所有更改复制到所有节点。这是通过使用与心跳相同的附加条目消息来完成的。首先，客户端向领导者发送更改请求，这次更改会添加到领导者的日志中，然后在下一次心跳中将更改发送给追随者，一旦大多数跟随者响应，条目就会被提交，然后领导者会响应给客户端。

Raft 甚至可以在面对网络分区时保持一致。

假设当前有 5 个节点（A-E）组成的集群，其中 B 节点是领导者，其他节点是跟随者。当网络分区导致造成 A、B 和 C、D、E 在两个不同的网络，首先 B 仍然是 领导者；C、D 和 E 由于没有收到心跳请求将发生新的一届选举，若 E 成为新一届任期的领导者，此时在集群中的两个网络分区将存在两个领导者。

一个客户端向领导者 B 发送一次更改请求（将值更新为 3），由于 B 节点不能复制到大多数节点，所以它的日志条目保持未提交。另一个客户端向领导者 E 发送一次更改请求（将值更新为 8），这会成功，因为它可以复制到大多数节点。

现在当我们恢复网络分区，B 节点将看到更高的一届选举任期并下台。两个节点 A 和 B 将回滚未提交的条目并匹配新的领导者日志。此时在我们的集群中，日志是一致的。