Consensus Algo of Raft

共识算法之Raft

背景

随着区块链及分布式场景的广泛应用，如何确保服务在出现网络延时、宕机或者作恶等故障情况下仍然能够得到安全一致的世界状态。此时大量的共识机制、共识算法应运而生。我们可以根据可以容忍的故障类型将这些共识算法分成两个大类：

• 宕机容错类算法（crash fault tolerant consensus algorithm），可以容忍网络丢包、时钟漂移、部分节点宕机这种节点为良性的错误。常见算法有Paxos、Raft等。
• 拜占庭容错类算法（byzantine fault tolerant consensus algorithm），可以容忍部分节点任意类型错误，包括节点作恶的情况。常见算法有PBFT、Tbft、中本聪共识等。

本文主要介绍Raft共识算法，由于在考虑到Paxos的难理解性以及该算法在实际工程应用中难以实现的特性，Raft共识算法在保证算法安全、可靠、高效的同时，该算法最大的设计挑战就是可理解性，并且在工程上容易实现。

算法简介

Raft是一种为了管理复制日志的一致性算法。它提供了和Paxos算法相同的功能和性能，但是它的算法结构和Paxos不同，使得Raft算法更加容易理解并且更容易构建实际的系统。为了提升可理解性，Raft将一致性算法分解成了几个关键模块，例如领导人选举、日志复制、日志压缩和安全机制等。Raft算法比Paxos算法更加容易学习。Raft算法还包括一个新的机制来允许集群成员的动态改变，它利用大多数重叠来保证安全性。

特性

• 强领导特性：和其他一致性算法相比，Raft算法使用一种更强的领导能力形式。比如，日志条目只从领导人发送给其他的服务器。这种方式简化了对复制日志的管理并且使得Raft算法更加易于理解。
• 领导选举：Raft算法使用一个随机超时计时器来选举领导人。并且在成为领导人后通过发送心跳信息来显示自己的领导权威。这种方式在解决领导选举冲突的时候会更加简单快捷。
• 集群成员变更：Raft算法使用一种共同一致的方法来处理集群成员变换的问题，在这种方法下，处于调整过程中的两种不同的配置集群中大多数机器会有重叠，这就使得集群在成员变换的时候依然可以正常工作。

注： 通常的一致性算法都具有安全性、一致性及终止性。

复制状态机

Raft一致性算法是基于复制状态机的背景下提出来的。在这种背景下，一组服务器上的状态机产生相同状态的副本。并且在一些机器宕掉的情况下也可以继续运行。复制状态机在分布式系统中被用于解决很多容错的问题。

每一个服务器存储一个包含一系列指令的日志，并且按照日志的顺序进行执行。每一个日志都按照相同的顺序，每一个服务器都执行相同的指令序列。由于每个状态机都是确定的，所以每一个服务器执行日志操作指令都能产生相同的状态。

Leader选举

节点状态

• Leader（领导者）: 正常情况下，集群中只有一个Leader, 负责处理客户端的写请求、日志复制、向Follower定期发送心跳信息。
• Follower (跟随者) : Follower会从Leader接收日志并提交本地日志信息。正常情况下不会主动发出请求；当超过一定时间没有收到来自Leader的心跳信息，就会election time out，成为Candidate。
• Candidate (候选者) : 如果Leader宕机或者断开连接，会选出新的Leader节点。Candidate节点向其他节点发送请求投票的RPC消息，如果赢得了大多数选票，就成为 Leader。
• 

注： 节点之间是通过RPC进行通信。

任期

Term(任期)：时间被划分成一个个的任期，每个任期始于一次选举。在选举成功后，领导人会管理整个集群直到任期结束。有时候选举会失败，那么这个任期就会没有领导人而结束，然后会进入到下一个任期继续选举。任期之间的切换可以在不同的时间不同的服务器上观察到。

选举过程

初始化启动时：所有节点都处于Follower状态，当有节点率先超时时，该节点就会变成Candidate状态。节点的任期会增加同时节点会给集群中的其他节点发送选举投票消息(RequestVote RPC)。当投票数量超过半数节点时，该节点就会变成Leader节点同时该节点会向集群中的其他节点发送心跳(AppendEntries RPCs)，不携带log entries。发送心跳的目的是为了显示自己的领导地位。

上述情况是比较正常的情况，其实当节点处于Candidate时会出现三种情况：

• 该节点赢得大多数投票并成为Leader节点。
• 集群中其他节点赢得大多数投票并成为Leader节点。
• 这一轮中没有节点能胜出然后会进入下一轮选举。

注： 可通过Raft官网动画演示上述几种情况。

日志复制

日志条目

当Leader被选举出来后，它就可以为客户端服务，客户端的每一个请求都包含一条被复制状态机执行的指令。领导人把这条指令作为一条新的日志条目附加到日志中去，然后并行地发起AppendEntries RPCs给其他的服务器，让他们复制这条日志条目。领导人会不断的重复尝试发送请求,直到所有的跟随者都最终存储了所有的日志条目。

日志由有序序号标记的条目组成。每个条目都包含创建时的任期号和一个状态机需要执行的指令。一个条目当可以安全地被应用到状态机中去的时候，就认为是可以提交了。日志的提交是由Leader决定的。

复制过程

• 客户端向Leader节点发送写入指令请求。
• Leader节点将基于指令创建新的日志条目并存入本地日志，与此同时，Leader节点通过AppendEntries RPCs向集群中的其他节点进行日志复制请求。
• Follower节点成功收到日志复制消息后存入本地日志，并应答成功，此时的日志还未真正提交。
• Leader节点收到大多数成功应答后开始将日志指令提交到状态机中执行并反馈给客户端写入成功的响应，于此同时，Leader节点向集群中其他节点发送AppendEntries RPCs时会携带新的leaderCommit，也就是Leader最新提交日志的索引，Follower会根据此信息同步提交本地相同索引日志。
• 当大多数日志条目被成功写入后就称这些日志条目为committed entries.

日志匹配特性

Raft中日志匹配机制是用来维护不同服务器日志之间一致性，可预测性。同时它是安全性保证的重要环节。Raft日志匹配特性如下:

• 如果在不同节点的日志中有两个条目拥有相同的索引及任期号，那么他们就存储了相同的指令。
• 如果在不同节点的日志中有两个条目拥有相同的索引及任期号，那么他们之前的所有日志条目也全部相同。

在Raft算法中，Leader是通过强制Follower直接复制自己的日志来处理不一致问题的。这意味着在Follower中的冲突的日志条目会被Leader的日志覆盖。要使得Follower的日志和自己的日志状态保持一致，Leader必须找到最后两者达成一致的地方，然后删除Follower从那个点之后的所有日志条目，并发送自己在那个点之后的日志给Follower。所有的这些操作都在发送AppendEntries RPCs请求时进行的一致性检查时完成。

安全性

选举限制

如果一个Follower宕机了，同时Leader也已经提交了很多日志指令，然后这个Follower可能会被重新选举成为新的Leader,那么此时新的Leader会如何处理日志复制呢？
由于上面这种情况Raft算法在进行领导选举时会对即将成为Leader的节点做一些限制，具体限制如下：

• 日志条目是单向传送，只能从Leader到Follower。
• 候选人想要赢得选举，必须包含已提交最新的日志条目。
• 如果两份日志最后的条目的任期号不同，那么任期号大的日志更加新。如果两份日志最后的条目任期号相同，那么日志比较长的那个就更加新。

提交前任日志条目

当前Leader并不知道之前的任期里日志是否已经被提交，即使这条日志已经被复制到了多数派的服务器上。根据Raft协议，这条日志是不能被直接提交的。

A leader knows that an entry from its current term is committed once that entry is stored on a majority of the servers. If a leader crashes before committing an entry, future leaders will attempt to finish replicating the entry. However, a leader cannot immediately conclude that an entry from a previous term is committed once it is stored on a majority of servers.

• a: S1是Term:2的Leader，复制了一条日志(Term:2,Index:2)到S2，同时它自己也写了一条日志(Term:2,Index:2)到本地。

• b: S1此时宕机，S5获得S3、S4和S5的投票成为Leader，然后写了一条日志(Term:3,Index:2)到本地，此时日志都并未提交。

• c: S5此时宕机，S1复活并且重新当选Leader(Term:4)，开始继续复制日志(Term:2,Index:2)到多数派服务器上(S1,S2,S3)上。然后又新写入一条日志(Term:4,Index:3)到本地,此时(Term:2,Index:2)和(Term:4,Index:3)上的日志并未提交。

  虽然(Term:2,Index:2)已经完成了多数派的复制，但是这条日志的Term是2，而当前的S1已经是Term:4的Leader，所有还不能直接提交。只有等到提交Term为4时任期内的日志(Term:4,Index:3)完成多数派复制后，才能把(Term:4,Index:3)和之前任期中的Term:2,Index:2）日志一并提交。

• d: 根据c，此时S1宕机，S5当选Leader (Term >= 5,voted fromS2,S3,S4,S5) ，并将日志(Term:3,Index:2)复制到其他所有节点并成功提交。

• e: 根据c，此时(Term4,Index:3)及他前面所有的日志都已经提交了，如果这个时候S1才宕机，那么再重新选举Leader时，只有S2或者S3中的一个才能被选为新的Leader，证明Raft能够保证只要是在当前Term时成功完成多数派复制的日志肯定会被提交，且已提交的日志不可能被覆盖。

但是在分布式系统中，网络不可靠是一个大概率的问题，情况(d)虽然发生的概率不高，但是只要系统运行的时间足够长，这种情况总是可以出现。为了处理(d)这种情况，Raft共识算法永远不会通过计算副本数目的方式去提交一个之前任期内的日志条目。只有领导人当前任期里的日志条目通过计算副本数目可以被提交，一旦当前任期的日志条目以这种方式被提交，那么由于日志匹配特性，之前的日志条目也都会被间接的提交。

本文主要介绍Raft共识算法Leader选举，日志复制以及安全性等方面内容，更多如安全性论证、成员变更、日志压缩等方面内容可参考如下论文：
(1) https://raft.github.io/raft.pdf
(2) https://web.stanford.edu/~ouster/cgi-bin/papers/OngaroPhD.pdf