一致性算法之Raft算法_raft一致性算法

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

raft先选举出leader,leader负责接收所有客户端更新请求和数据同步，leader故障会重新进行选举

leader选举

日志复制

动画演示，很形象：Raft

leader election:

follow在约定时间内没有收到来自leader的心跳（挂了或者没有leader）就主动发起选举。假设100ms超时，有123，3个follower,这时候就看谁快达到超时，谁就先成为候选人。

自己节点先建个队伍，切换到候选人状态--》投自己一票--》给其他节点发送选举请求–》等待回复

1：收到超过半数以上的票（包括自己）则成为leader--》给所有节点发送消息，告知自己是leader

2：被告知已经有人当选leader，切换回follower

3：时间内没有达成条件，保持候选人状态，重新选举（避免平票情况，所以尽量选择奇数机器）

投票规则：

一个任期内，单一节点只能投一票

候选人知道的信息不能比自己少（降低同步数据的成本）

先到先得的原则，满足条件，谁快谁能先被投票

log Replication:

leader负责处理客户端的一切请求，并保证leader和follow按照同样的顺序执行请求，以保证数据一致。

共识算法：相同的初始状态+相同的输入 = 相同的结果

怎么保证同样的顺序那，使用本地时间会有很大的风险，所以使用replicate log来实现。

 

日志提交类似2PC，只不过只要保证半数以上的回复即可。

 

raft实现的是最终一致性，leader通过不断给follower发log entries，直到所有消息一致。

这里只要半数响应，leader就会响应客户端，最终还会将日志应用到状态机，真正影响节点的状态。

只能有一个leader，有多个leader就会出现脑裂，会导致数据覆盖丢失。

raft是怎么保证的：

1：一个节点某一任期只能投一票

2：只有获得半数以上的才能成为leader

日志匹配（logmatching）：

leader在某一个term只会创建一个log entry,只能追加日志，不能修改删除，如下

 

这里面a-f几种follow与leader不一致的情况，多少，或者某一段的多或少。

不一致时，leader会强制follow复制自己的log

leader会自己维护一个indexNext数组，比如现在index是12，那初始化记录的就是12+1

先看follower的12一致吗，不一致就返回false，index-1,直到一致。比如f,到index=3才一致，然后强制同步后面的日志

A leader任职期间的日志一定会出现在后面的日志里，因为：

日志只有多数复制成功才commit

一个节点只有得到多数的投票才能任职，并且投票的前提是自己的日志比投票者新。

脑裂情况：

 

1-5，之前1是leader,但是因为网络异常，3-5与1-2无法联系，导致3-5选出来3是leader ,那就有1，3两个leader.

写请求：这时假设有请求前来，给到leader 1，因为1只能联系到1-2，总共5个节点，所以不满足半数，所以1会给客户端返回半数，

读请求：比如写到了3，读到了1，那么1其实是落后的，为避免这种情况。leader需要check自己是否过时，办法就是与过半数节点通信（存在效率问题）

leader-》follower 

收到更高term的消息，或者无法与半数以上节点通信，自动转换

 

上图是一个较为复杂的情况。1代表term1，2代表term2.

在时刻(a), s1是leader，在term2提交的日志只赋值到了s1 s2两个节点就crash了。

在时刻（b), s5成为了term 3的leader，日志只赋值到了s5，然后crash。

然后在(c)时刻，s1又成为了term 4的leader，开始赋值日志，于是把term2的日志复制到了s3，此刻，可以看出term2对应的日志已经被复制到了majority，因此是committed，可以被状态机应用。

不幸的是，接下来（d）时刻，s1又crash了，s5重新当选，然后将term3的日志复制到所有节点，这就出现了一种奇怪的现象：被复制到大多数节点（或者说可能已经应用）的日志被回滚。

究其根本，是因为term4时的leader s1在（C）时刻提交了之前term2任期的日志。为了杜绝这种情况的发生：

为了防止某些意外情况，leader在任职期间，不会提交前任的日志，而是通过提交当前时期的日志顺带提交之前的日志。如果没有客户端请求，就提交一个空的log请求

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

 

总结：

  raft将共识问题分解成两个相对独立的问题，leader election，log replication。流程是先选举出leader，然后leader负责复制、提交log（log中包含command）

  为了在任何异常情况下系统不出错，即满足safety属性，对leader election，log replication两个子问题有诸多约束

leader election约束：

• 同一任期内最多只能投一票，先来先得
• 选举人必须比自己知道的更多（比较term，log index）

log replication约束：

• 一个log被复制到大多数节点，就是committed，保证不会回滚
• leader一定包含最新的committed log，因此leader只会追加日志，不会删除覆盖日志
• 不同节点，某个位置上日志相同，那么这个位置之前的所有日志一定是相同的

异常分析：leader挂掉的几种情况：

1. 数据到达 Leader 节点前

这个阶段 Leader 挂掉不影响一致性，不多说。

2. 数据到达 Leader 节点，但未复制到 Follower 节点

这个阶段 Leader 挂掉，数据属于未提交状态，Client 不会收到成功会重试。Follower 节点上没有该数据，重新选主后 Client 重试重新提交可成功。

原来的 Leader 节点恢复后作为 Follower 加入集群重新从当前任期的新 Leader 处同步数据，强制保持和 Leader 数据一致

 

3. 数据到达 Leader 节点，成功复制到 Follower 所有节点，但还未向 Leader 响应接收

这个阶段 Leader 挂掉，虽然数据在 Follower 节点处于未提交状态（Uncommitted）但保持一致，重新选出 Leader 后可完成数据提交，此时 Client 由于不知到底提交成功没有，可重试提交。针对这种情况 Raft 要求 RPC 请求实现幂等性，也就是要实现内部去重机制。

 

4. 数据到达 Leader 节点，成功复制到 Follower 部分节点，但还未向 Leader 响应接收

这个阶段 Leader 挂掉，数据在 Follower 节点处于未提交状态（Uncommitted）且不一致，Raft 协议要求投票只能投给拥有最新数据的节点。所以拥有最新数据的节点会被选为 Leader 再强制同步数据到 Follower，数据不会丢失并最终一致。

 

5. 数据到达 Leader 节点，成功复制到 Follower 所有或多数节点，数据在 Leader 处于已提交状态，但在 Follower 处于未提交状态

这个阶段 Leader 挂掉，重新选出新 Leader 后的处理流程和阶段 3 一样。

6. 数据到达 Leader 节点，成功复制到 Follower 所有或多数节点，数据在所有节点都处于已提交状态，但还未响应 Client

 

这个阶段 Leader 挂掉，Cluster 内部数据其实已经是一致的，Client 重复重试基于幂等策略对一致性无影响。