Raft共识算法

分布式共识算法 #

首先我们先明确这个问题：为什么需要分布式共识算法？

这就要从当前的分布式系统设计的缺陷来看了，假设我们的集群现在有两个客户端和三个服务端，如下图：

在这个分布式系统的设计中，往往要满足CAP理论，而分布式共识算法解决的就是CAP理论中的一致性问题。整个一致性问题分为三种问题：

顺序一致性
线性一致性
因果一致性

顺序一致性 #

假设执行结果与这些处理器以某一串行顺序执行的结果相同，同时每个处理器内部操作的执行看起来又与程序描述的顺序一致。满足该条件的多处理器系统我们就认为是顺序一致的。实际上，处理器可以看做一个进程或者一个线程，甚至是一个分布式系统。

这句话并不是很好理解，我们看一下分布式系统中顺序一致性的一个例子：

假设客户端A有两条命令：
command1:set(x,1)	//设置x为1
command2:set(x,3)
客户端B有一下两条命令：
command3:get(x)		//得到x的当前值
command4:set(x,4)

那么如果服务端那边收到的节点只要满足command2在command1后面执行并且comand4在command3后面执行我们就认为其满足顺序一致性。

线性一致性 #

线性一致性或称原子一致性或严格一致性，指的是程序在执行顺序组合中存在可线性化点P的执行模型，这意味着一个操作将在程序的调用和返回之间的某个点P生效，之后被系统中并发运行的所有其他线程所感知。

通俗来讲，线性一致性可以说是顺序一致性的升级版。其会有一个全局时钟，假设还是上面发送的命令，只不过加上了时间信息：客户端A发送的命令如下：

[14:01]command1:set(x,1)	//设置x为1
[14:02]command2:set(x,3)

客户端B发送的命令如下：

[14:03]command3:get(x)		//得到x的当前值
[14:04]command4:set(x,4)

注：这里假设时延可能是几分钟级别的，所以有可能是command3在command1之前到

所以，假设初始值x = 0，而我们到达的顺序如下：

command1->command3->command2->command4
command1->command3->command4->command2
...

这个顺序确实是满足顺序一致性，但是我们get(x)获得的值可谓是千奇百怪，可能是0，1，3 。为了解决顺序一致性的不足，所以才提出的线性一致性。其要求命令满足全局时钟的时序性。所以很容易就知道，满足线性一致性的一定满足顺序一致性；相反，满足顺序一致性的不一定会满足线性一致性。

因果一致性 #

线性一致性要求所有线程的操作按照一个绝对的时钟顺序执行，这意味着线性一致性是限制并发的，否则这种顺序性就无法保证。由于在真实环境中很难保证绝对时钟同步，因此线性一致性是一种理论。实现线性一致性的代价也最高，但是实战中可以弱化部分线性一致性：只保证有因果关系的事件的顺序，没有因果关系的事件可以并发执行，其指的是假设有两个事件：A事件和B事件，如果A发生在B后面，那么就称A和B具有因果关系。

拜占庭将军问题 #

拜占庭将军问题是一个协议问题，拜占庭帝国军队的将军们必须全体一致的决定是否攻击某一支敌军。问题是这些将军在地理上是分隔开来的，并且将军中存在叛徒。叛徒可以任意行动以达到以下目标：欺骗某些将军采取进攻行动；促成一个不是所有将军都同意的决定，如当将军们不希望进攻时促成进攻行动；或者迷惑某些将军，使他们无法做出决定。如果叛徒达到了这些目的之一，则任何攻击行动的结果都是注定要失败的，只有完全达成一致的努力才能获得胜利。

含义是在存在消息丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。

Raft共识 #

简介 #

Raft实现一致性的机制是：首先选择一个leader全权负责管理日志复制，leader从客户端接收log entries（日志条目），将它们复制给集群中的其他机器，然后负责告诉它机器什么时候将日志应用于它们的状态机。举个例子，leader可以在无需询问其他server的情况下决定把新entries放在哪个位置，数据永远是从leader流向其他机器（leader的强一致性）。一个leader可以fail或者与其他机器失去连接，这种情况下会有新的leader被选举出来。

在任何时刻，每个server节点有三种状态：leader、candidate、follower。

leader：作为客户端的接收者，接收客户端发送的日志复制请求，并将日志信息复制到follower节点中，维持网络各个节点的状态。
candidate：在leader选举阶段存在的状态，通过任期号term和票数进行领导人身份竞争，获胜者将成为下一任期的领导人。
follower：作为leader节点发送日志复制请求的接收者，与leader节点通信，接收账本信息，并确认账本信息的有效性，完成日志信息的提交和存储。

正常运行时，只有一个leader，其余全是follower。follower是被动的：它们不主动提出请求，只是响应leader和candidate的请求。leader负责处理所有客户端请求（如果客户端先连接某个follower，该follower负责将它重定向到leader）。candidate状态用户选举leader节点。

如何让跨网络机器之间协调一致性？

状态的立即一致性
状态的最终一致性

raft来源于paxos，它简化了paxos，以易于理解为首要目标，尽量提供与paxos一样的功能与性能。

提出问题：

1、输入：写入命令

2、输出：所有节点最终处于相同的状态

2、约束

网络不确定性：在非拜占庭情况下，出现网络分区/冗余/丢失/乱序/ 等问题下要保证正确。

基本可用性：集群中大部分节点能够保持互相通信，那么集群就应该能够正确响应客户端。

不依赖时序：不依赖物理时钟或极端的消息延迟来保证一致性。

快速响应：对客户端请求对响应不能依赖集群中最慢的节点。

一个可行解：

初始化的时候有一个领导节点，负责发送日志到其他跟随者，并决定日志的顺序

当读请求到来时，在任意节点都可以读，而写请求只能重定向到领导者进行

领导者先写人自己的日志，然后同步给半数以上的节点，跟随者表示都OK了，领导者才提交日志

日志最终由领导者先按顺序应用与状态机，其他跟随者随机应用到状态机

当领导者奔溃后，其他跟随者通过心跳感知并选举出新的领导者继续集群的正常运转

当有新的节点加入或推出集群，需要将配置信息同步给整个集群

raft共识算法中不能保证你的命令一定会被执行，如果你的命令还没有从leader结点同步到大多数追随结点的时候就挂掉，命令就不会被执行。

Raft原理 #

基本原理 #

从上面的描述我们可以看到节点的角色不是固定的，其会在三个角色中转换。我们举个例子来说，假设我们有三个节点A、B、C，它们的基本信息如下图中。一开始所有的节点都是follower状态，并且处于时期0这个状态。

注：在Raft算法中，所有节点会被分配不同的超时时间，时间限定在150ms~300ms之间。为什么这么设置是因为如果设置相同的超时时间就会导致所有节点同时过期会导致迟迟选不出leader，看到后面就会明白。

150ms过去之后，A发现怎么leader没跟我联络感情，是不是leader已经寄了？王侯将相宁有种乎！于是A成为候选人给自己投了一票并开创自己的时代时期 1，并给其他还没过期的follower发送信息请求它们支持自己当leader。

节点B和C在收到来自A的消息之后，又没有收到其他要求称王者的信息，于是就选择支持A节点，加入A的时代并刷新自己的剩余时间。

之后 A 得到了超过一半的节点支持，成为leader，并定时给B和C联络联络感情（心跳信息）目的是防止有节点因为长时间收不到开始反叛成candidate。

之后整个分布式集群就可以和客户端开始通信了，客户端会发送消息给leader，之后leader会保证集群的一致性并且当整个集群中的一半节点都完成客户端发送的命令之后才会真正的返回给客户端，表示完成此次命令。

但是这只是个概况，我们还缺了亿点点细节：

选举机制
日志复制

选举机制 #

刚刚我们讲了最普通的一个选举过程，但是我们可能还会遇到一些特殊情况：

新加入节点
leader 掉线
多个follower同时超时

新节点加入 #

当有一个节点加入当前的分布式集群的时候，leader会检测并发现它并给他发送消息。使其加入此分布式集群。

leader 掉线处理 #

假设我们现在的服务器A掉线，由于没有leader维持心跳消息，这个时候服务器B和C会进入超时倒计时的状态。

200ms过去，服务器B开始超时了，这个时候它揭竿而起成为candidate，并向节点C发送消息请求其支持自己成为leader。

之后，在一系列判断条件之后（后面会讲），节点C会回复节点B的请求信息。插句题外话哈，在B还没收到C的回复消息之前，假设A只是刚刚网络不通畅，现在死而复生，给B发送消息了。那么B发现A的时期比自己落后了，这还等什么？！苍天已死，黄天当立，之后反手将其收为小弟。

之后节点B顺利成为leader。

多个 follower 同时掉线 #

现在假设有4个节点：A、B、C、D。其中A和D的超时时间是相同的。

150ms过后，A和D同时成为candidate，争相为了成为leader给B和C发消息。

这个时候有对于B和C有两个选择，一个是它们一起支持两个中的一次，也就是要么支持A要么支持D，这样这样其中一个就会成为leader，我们假设它们两个都支持A。

另外一种选择就是，A和D各的一票支持，它们的支持者跟进它们各自的leader的时期，然后本轮选举结束。

之后50ms过去之后，B的超时时间过期了，其获得candiate的资格，这个时候其会向其他follower发送消息请求支持。

之后A、B、D 因为当前的B也没有支持者，所以就会支持B，B顺利成为leader。

Log Relocation #

在raft集群中，所有日志都必须首先提交至leader节点。leader在每个heartbeat向follower发送AppendEntries RPC同步日志，follower如果发现没问题，复制成功后会给leader一个表示成功的ACK，leader收到超过半数的ACK后应用该日志，返回客户端执行结果。若follower节点宕机、运行缓慢或者丢包，则leader节点会不断重试Ap pendEntries RPC,直到所有follower节点最终都复制所有日志条目。

上述的具体过程如下：

首先有一条 uncommitted 的日志条目提交至 leader 节点。

在下一个 heartbeat，leader 将此条目复制给所有的 follower。

当大多数节点记录此条目之后，leader 节点认定此条目有效，将此条目设定为已提交并存储于本地磁盘。

在下一个 heartbeat，leader 通知所有 follower 提交这一日志条目并存储于各自的磁盘内。

日志复制 #

当我们的集群leader 选举之后。Leader 接收所有客户端请求，然后转化为 log 复制命令，发送通知其他节点完成日志复制请求。每个日志复制请求包括状态机命令 & 任期号，同时还有前一个日志的任期号和日志索引。状态机命令表示客户端请求的数据操作指令，任期号表示 leader 的当前任期，任期也就是上图中的时期。

而当follower 收到日志复制命令会执行处理流程：

follower 会使用前一个日志的任期号和日志索引来对比自己的数据：

如果相同，接收复制请求，回复 ok；
否则回拒绝复制当前日志，回复 error；

leader 收到拒绝复制的回复后，继续发送节点日志复制请求，不过这次会带上更前面的一个日志任期号和索引；

如此循环往复，直到找到一个共同的任期号&日志索引。此时 follower 从这个索引值开始复制，最终和 leader 节点日志保持一致；

日志复制过程中，Leader 会无限重试直到成功。如果超过半数的节点复制日志成功，就可以任务当前数据请求达成了共识，即日志可以 commite 提交了；

注：这里要提到的一点就是，如果follower发现canidate的日志还没有自己的新（索引号没自己大），其是不会支持其成为leader的。

Network Partition 情况下进行复制日志: #

由于网络的隔断，造成集群中多数的节点在一段时间内无法访问到 leader 节点。按照 raft 共识算法，没有 leader 的那一组集群将会通过选举投票出新的 leader，甚至会在两个集群内产生不一致的日志条目。在集群重新完整连通之后，原来的 leader 仍会按照 raft 共识算法从步进数更高的 leader 同步日志并将自己切换为 follower。