一文读懂Raft共识算法

@(Raft共识算法)[CAP定理|Paxos|解读Raft]

1. CAP定理含义
- 1.1 CAP不能同时做到
- 1.2 一致性和可用性的矛盾
2. 放弃CAP定义
3. Paxos算法简介
4. 解读RAFT

1. CAP定理含义

1998年，加州大学的计算机科学家 Eric Brewer 提出，分布式系统有三个指标：

Consistency ：一致性
Availability ：可用性
Partition tolerance ：分区容错

首字母缩写简称： CAP

Eric Brewer 说，这三个指标不可能同时做到。这个结论就叫做 CAP 定理。

1.1 CAP不能同时做到

大多数分布式系统都分布在多个子网络。每个子网络就叫做一个区（partition）。分区容错的意思是，区间通信可能失败。比如，一台服务器放在中国，另一台服务器放在美国，这就是两个区，它们之间可能无法通信。一般来说，分区容错无法避免。

1.2 一致性和可用性的矛盾

要保证多个节点的一致性，当一个节点在写入数据的时候，其他节点就需要锁定，等待数据同步完成。这时，就不能保证其他节点的可用性。
如果各个节点同时可读写数据，保证了节点的可用性，就不能保证各个节点之间数据一致性。
因此，一致性和可用性是矛盾的。

2. 放弃CAP定义

放弃CAP	说明
放弃C （弱化一致性）	要求高可用性并允许分区容错，则需要弱化一致性。因为一旦一个节点或分区发生故障失去联系，为了保证高可用性，每个节点只能使用本地数据库提供服务，但这样会导致各个节点的数据不一致。这种情况一般是对一致性不敏感的应用，可以允许在新版本上线后过一段时间才最终更新完成，期间不保证一致。例如NoSQL、DNS、web缓存都属于此类
放弃A （弱化可用性）	那么每个请求都需要在server之间保持强一致性，而分区的出现会导致节点之间数据同步时间延长，但是CP是可以保证的。例如对一致性比较敏感的应用，例如ATM机、电子支付等，当系统出现故障时，直接拒绝服务
放弃P （弱化分区容错性）	如果要保证C（强一致性）和A（可用性），则无法保证分区容错性。但是分布式系统是无法避免分区的，两阶段的提交算法（如ZooKeeper等）主要考虑了这种设计

3. Paxos算法简介

Paxos算法的目的是为了解决分布式环境下一致性的问题

多个节点并发操作数据，如何保证在读写过程中数据的一致性，并且解决方案要能适应分布式环境下的不可靠性。

3.1 Paxos两个组件

Proposer：提议发起者，处理客户端请求，将客户端的请求发送到集群中，以便决定这个值是否可以被批准
Acceptor：提议批准者，负责处理接收到的提议，他们的回复就是一次投票。会存储一些状态来决定是否接收一个值

3.2 Paxos两个原则

安全原则：保证不能做错的事
- 针对某个实例的表决只能有一个值被批准，不能出现一个被批准的值被另一个值覆盖的情况
- 每个节点只能学习到已经被批准的值，不能学习没有被批准的值
存活原则：只要有多数服务器存活并且彼此间可以通信，最终都要做到的下列事情
- 最终会批准某个被提议的值
- 一个值被批准了，其他服务器最终会学习到这个值

3.3 Paxos细节和资料

4. 解读RAFT

4.1 什么是RAFT

raft是工程上使用较为广泛的强一致性、去中心化、高可用的分布式协议。

raft是一个共识算法（consensus algorithm），所谓共识，就是多个节点对某个事情达成一致的看法，即使是在部分节点故障、网络延时、网络分割的情况下。这些年最为火热的加密货币（比特币、区块链）就需要共识算法，而在分布式系统中，共识算法更多用于提高系统的容错性，比如分布式存储中的复制集（replication）。raft协议就是一种leader-based的共识算法，与之相应的是leaderless的共识算法。

Raft is a consensus algorithm for managing a replicated log

业界最著名的一致性算法就是大名鼎鼎的Paxos（Chubby的作者曾说过：世上只有一种一致性算法，就是Paxos）。但Paxos是出了名的难懂，而Raft正是为了探索一种更易于理解的一致性算法而产生的。

4.2 RAFT名词解释

Leader Election（选举）：Raft通过选举Leader并由Leader节点负责管理日志复制来实现多副本的一致性。
- Leader：负责接收客户端的请求，将日志复制到其他节点并告知其他节点何时应用这些日志是安全的
- Candidate：候选人，用于选举Leader的一种角色
- Follower：跟随者，类似于人民群众，负责响应来自Leader或者Candidate的请求
Term（任期）：类似总统当选后每4年一个任期，Raft把时间切割为任意长度的任期，每个任期都有一个任期号，采用连续的整数
Log replication（复制日志集）：Leader复制日志集到Follower
Heart Beat（心跳）：Leader会不停的给Follower发心跳消息，表明自己的存活状态。在一段时间内如果没有收到来自leader的心跳，从follower切换到candidate，发起选举。

4.3 Leader Election 选举

Raft协议中，任一节点时刻处于三个状态中：Leader、Follower、Candidate。

所有节点初始状态都是Follower
超时时间内没有收到Leader的心跳，则转换为Candidate发起选举
Candidate收到大多数节点的选票则转换为Leader
Candidate发现Leader或者收到更高任期的请求则转换为Follower
Leader在收到更高任期的请求后转换为Follower

4.4 选举过程

如果follower在election timeout内没有收到来自leader的心跳，（也许此时还没有选出leader，大家都在等；也许leader挂了；也许只是leader与该follower之间网络故障），则会主动发起选举。
步骤如下：

增加节点本地的 current term ，切换到Candidate状态
投自己一票
并行给其他节点发送 RequestVote RPCs
等待其他节点的回复

在这个过程中，根据来自其他节点的消息，可能出现三种结果：

收到majority（大多数）的投票（含自己的一票），则赢得选举，成为Leader
被告知别人已当选，那么自行切换到follower
一段时间内没有收到majority投票，则保持candidate状态，重新发出选举

4.5 投票规则

在任一任期内，单个节点最多只能投一票
候选人知道的信息不能比自己的少（这一部分，后面介绍log replication和safety的时候会详细介绍）
first-come-first-served 先来先得

4.6 结果分析

结果一：赢得了选举之后，新的leader会立刻给所有节点发消息，广而告之，避免其余节点触发新的选举

结果二：

例如有节点A、B、C， A、B同时触发选举。
A和B同时向其他节点发送RequestVite[A->B,A->C],[B->A,B->C]。
假设C先收到A的请求，C给A投了一票，当C收到B的请求的时候，因为已经给A投过票了，因此就不会给B投票。
同时，A和B不会给对方投票。最终，A获得自己和C的投票一共2票胜出，成功当选Leader。
A胜出后，给B和C发送心跳
B节点发现A的Term不低于自己，知道已经有Leader产生了，于是切换为Follower

结果三：

例如有节点A、B、C、D，A、B同时触发选举
如果C、D各投A、B一票的化，就会出现A、B Split Vote（平票）
直到超时重新发起选举

因此： raft引入了randomized election timeouts来处理平票情况。同时，leader-based 共识算法中，节点的数目都是奇数个，尽量保证majority的出现。

4.4. Term 任期

从上面选举阶段可以看出，哪个节点做leader是大家投票选举出来的，每个Leader工作一段时间，然后选出新的Leader继续负责。这根民主社会的选举很像，每一届新的履职期称之为一届任期，在Raft协议中，也是这样的，对应的术语叫Term。

4.5. Log Replication 日志复制

当Leader产生之后，系统就可以处理客户端发来的请求了。客户端的一切请求都发送到Leader，由Leader来调度和处理这些请求，并且将请求和执行顺序告知Follower，保证与Follower的状态一致性。

4.5.1 Replicated State Machines 复制状态机

If two identical(完全相同的), deterministic（确定的） processes begin in the same state and get the same inputs in the same order, they will produce the same output and end in the same state.

即： 相同的初识状态 + 相同的输入 = 相同的结束状态

在raft中，leader将客户端请求（command）封装到一个个log entry，将这些log entries复制（replicate）到所有follower节点，然后大家按相同顺序应用（apply）log entry中的command，达到状态的一致。

4.5.2 完整流程

Leader append log entry ：Leader封装Command到Log Entry中
Leader issue AppendEntries RPC in parallel ： Leader同时将AppendEntries通过RPC方式告知所有Follower
Leader wait for majority response ： Leader等到大多数Follower的返回
Leader apply entry to state machine ： Leader通过复制状态机执行Entry里面的Command
Leader reply to client ： Leader返回客户端处理结果
Leader notify follower apply log ： Leader通知所有Follower执行Entry里面的Command

4.5.3 日志形式

The leader decides when it is safe to apply a log entry to the state machines; such an entry is called committed. Raft guarantees that committed entries are durable and will eventually be executed by all of the available state machines. A log entry is committed once the leader that created the entry has replicated it on a majority of the servers

不难看到:

logs由顺序编号的log entry组成
每个log entry除了包含command，还包含产生该log entry时的leader term
从上图可以看到，五个节点的日志并不完全一致，raft算法为了保证高可用，并不是强一致性，而是最终一致性
leader会不断尝试给follower发log entries，直到所有节点的log entries都相同。

在上面的流程中，leader只需要日志被复制到大多数节点即可向客户端返回。一旦向客户端返回成功消息，那么系统就必须保证log（其实是log所包含的command）在任何异常的情况下都不会发生回滚。

这里有两个词：

commit（committed）: 指日志被复制到了大多数节点后日志的状态
apply (applied)，指节点将日志应用到状态机，真正影响到节点状态

4.6 Safty安全性

4.6.1 Safety And Liveness

在分布式系统的算法和设计中，safety和liveness是2个非常重要的属性：

safety ： something “bad” will never happen
liveness ： something “good” will must happen (but we don’t know when)

在任何系统模型下，都需要满足safety属性，即在任何情况下，系统都不能出现不可逆的错误，也不能向客户端返回错误的内容。比如，raft保证被复制到大多数节点的日志不会被回滚，那么就是safety属性。而raft最终会让所有节点状态一致，这属于liveness属性

4.6.2 Election safety 选举安全性

选举安全性：
即任一任期内最多一个leader被选出

这一点非常重要，在一个复制集中任何时刻只能有一个leader。系统中同时有多余一个Leader，被称之为脑裂（brain split），这是非常严重的问题，会导致数据的覆盖丢失。

在raft中，两点保证了这个属性：

一个节点某一任期内最多只能投一票；
只有获得majority投票的节点才会成为leader。

因此，某一任期内一定只有一个leader。

4.6.3 Log Matching 日志匹配

两个节点上的某个log entry的log index相同且term相同，那么在该index之前的所有log entry应该都是相同的。

首先，leader在某一term的任一位置只会创建一个log entry，且log entry是append-only
其次，consistency check。leader在AppendEntries中包含最新log entry之前的一个log 的term和index
如果follower在对应的term index找不到日志，那么就会告知leader不一致
在没有异常的情况下，log matching是很容易满足的，但如果出现了node crash，情况就会变得复杂

如下图：

上图为某个Follower的6中状态

leader、follower都可能crash，那么follower维护的日志与leader相比可能出现以下情况：

比leader日志少，如上图中的ab
比leader日志多，如上图中的cd
某些位置比leader多，某些日志比leader少，如ef

当出现了leader与follower不一致的情况，leader强制follower复制自己的log

To bring a follower’s log into consistency with its own, the leader must find the latest log entry where the two logs agree, delete any entries in the follower’s log after that point, and send the follower all of the leader’s entries after that point.

leader会维护一个nextIndex[]数组，记录了leader可以发送每一个follower的log index，初始化为eader最后一个log index加1

leader选举成功之后会立即给所有follower发送AppendEntries RPC心跳信息，流程如下：

leader 初始化nextIndex[x]为 leader最后一个log index + 1
AppendEntries里prevLogTerm prevLogIndex来自 logs[nextIndex[x] - 1]
如果follower判断prevLogIndex位置的log term不等于prevLogTerm，那么返回 False，否则返回True
leader收到follower的回复，如果返回值是False，则nextIndex[x] -= 1, 跳转到第二步
leader收到follower的回复，如果返回值是True，则同步nextIndex[x]后的所有log entries

4.6.4 Network Partition 网络分区

raft保证Election safety，即一个任期内最多只有一个leader，但在网络分割（network partition）的情况下，可能会出现两个leader，但两个leader所处的任期是不同的。

一个网络中有5个节点： A、B、C、D、E。其中A为Leader，其余都是Follower。

如果当出现网络分区，N1：【A、B】，N2:【C、D、E】

首先N2网络，收不到Leader心跳触发选主，C当选
此时，产生两个主，分别为N1网络的A（Term 1）和N2网络的C（Term 2）
客户端给A发送消息msg1，A由于只能同步数据到B，达不到大多数节点，因此返回错误，msg1数据状态为Uncommitted
当C当选Leader后，客户端给C发送消息msg2，C将消息同步给D和E，满足大多数节点要求，msg2数据就会被Commited
当网络回复后，5个节点再次处于同一个网络，C广播包含Term的AppendEntries到所有节点，包括A和B
A收到C的广播后，发现C的Term高于自己，自动降级为Follower，删除msg1，复制C的日志msg2
这样完成了在 Network Partition 情况下的复制日志，保证了数据的一致性

4.6.5 State Machine Safety 状态机安全性

State Machine Safety: if a server has applied a log entry at a given index to its state machine, no other server will ever apply a different log entry for the same index

如果节点将某一位置的log entry应用Apply到了状态机，那么其他节点在同一位置不能应用不同的日志。简单点来说，所有节点在同一位置（index in log entries）应该应用同样的日志.

反面例子：

a,b,c,d,e 分别为5个不同的时刻，s1,s2,s3,s4,s5分别为5个节点。

时刻a， s1是Term1的leader，当复制Term2日志的时候，只完成了s2的复制的时候 S1 Crash了
时刻b， s5当先Term3的Leader，日志只存在s5，尚未复制到其他节点，s5 Crash了
时刻c, s1当选Term4的Leader, 把Term2的日志复制到了s3，此刻Term2的日志已经Majority了。因此Commit To Apply。
时刻d， s1 Crash，s5重新当选，然后将Term3的日志复制到了所有节点。

此时就出现了：大多数节点Committed日志被回滚。

究其根本，是因为Term4时的Leader s1在（C）时刻提交了之前term2任期的日志

为了杜绝这种情况的发生：

Raft never commits log entries from previous terms by counting replicas.

永远不要commit之前Term时期的日志

Only log entries from the leader’s current term are committed by counting replicas; once an entry from the current term has been committed in this way, then all prior entries are committed indirectly because of the Log Matching Property.

通过提交当前任期的日志的时候“顺手”把之前的日志也提交了

Raft handles this by having each leader commit a blank no-op entry into the log at the start of its term

如果leader被选举后没有收到客户端的请求呢，论文中有提到，在任期开始的时候发立即尝试复制、提交一条空的log

因此，在上图中，不会出现（C）时刻的情况，即Term4任期的leader s1不会复制Term2的日志到s3。而是如同(e)时刻描述的情况，通过复制-提交 Term4的日志顺便提交Term2的日志。如果term4的日志提交成功，那么term2的日志也一定提交成功，此时即使s1 crash，s5也不会重新当选。

4.6.6 Leader Crash Leader宕机

Leader 会一直不停的给Follower发送心跳，如果Follower一段时间没有收到Leader的心跳，则认为Leader Crash了。重新发起选举。

4.7 总结

Raft 是能够实现分布式系统强一致性的算法，每个系统节点有三种状态 Follower，Candidate，Leader。

实现 Raft 算法两个最重要的事是：选主和复制日志

Algorithms are often designed with correctness, efficiency, and/or conciseness as the primary goals. Although
these are all worthy goals, we believe that understandability is just as important

算法以正确性、高效性、简洁性作为主要设计目标。
虽然这些都是很有价值的目标，但这些目标都不会达成直到开发者写出一个可用的实现。
所以我们相信可理解性同样重要。

4.8 参考链接

Raft 官网：https://raft.github.io/
Raft 原理动画：http://thesecretlivesofdata.com/raft/
Raft 图解： https://www.cnblogs.com/mindwind/p/5231986.html
Raft 详解： https://www.cnblogs.com/xybaby/p/10124083.html
Raft Paper： https://web.stanford.edu/~ouster/cgi-bin/papers/raft-atc14

目录CONTENT