Raft论文总结

简介

如何多快好省的对大规模数据集进行存储和计算?

解决

1. 更好的机器
2. 更多的机器

问题

1. 不断垂直扩展机器，升到一定配置之后就不能升级了。升级机器的配置带来的提升与付出的价格不匹配。瓶颈是在与硬件和对成本的控制
2. MapReduce 中使用一些廉价的机器组成一个集群处理大规模的数据，这也会引出一个问题。如何保证多个机器之间的同步，如何解决机器间的网络问题。对于网络通信有三种：写入成功，写入失败，消息丢掉（无法判断消息丢失还是延迟）

如何让跨网络的机器之间协调工作？

1. 状态立即一致
2. 状态的最终一致

如何应对网络不可靠以及节点的实效？

1. 可读写
2. 可读
3. 不可用

• 组织机器使其状态最终一致性并允许局部失败的算法称为一致性算法。（共识算法）
• Paxos 算法由来已久，目前是功能和性能最完善的一致性算法，然而他难以理解和实现。raft简化了Paxos，它是以易于理解为首要目标，尽量提供与Paxos一样的功能与性能 Paxos Raft ZAB 的比较
• 保证最终一致性 三个结点，ABC，A结点依次应用3456 ，BC结点也要依次应用3456。

复制状态机

1. Client 将操作发送到Leader结点，
2. Leader 将同步请求发送到其余的结点，将操作记录到日志中
3. 专门的状态机会将日志应用到server

• 每一个日志都按照相同的顺序包含相同指令，所有的服务器都执行相同的指令序列。状态机是确认的，每一次执行操作都产生相同的状态和序列。
• 任务就变成了保证日志复制的一致性。
• 一致性算法的目标就是保证集群中所有的状态一致，节点要执行的指令可以分为两种，读和写。只有写的指令才会改变结点的状态，因此为了保证集群各个节点状态的一致，就必须将写指令同步给所有节点。
• 理想状态下，我们期望任意节点发生写命令都会立即在其他节点上变更状态，这其中没有任何时延，所有节点都好像是同一个节点（像单机）一样被变更状态。
• 网络延迟要远远慢于内存操作，写入命令不可能被同时执行，因此如果在不同节点发生不同写命令，那么早其他节点上这些写命令被应用的顺序很可能完全不同。
• 如果我们不要所有节点的写命令立即被执行，而仅仅是保证所有的写命令在所在节点上按照相同的顺序最终被执行？仅允许一个节点处理写命令，所有节点维护一份顺序一致的日志。
• 日志的顺序以及对应对应序号的日志操作都是相同的。

一致性要解决的问题

1. 输入：写入命令
2. 输出：所有节点最终处于相同的状态
3. 约束
4. 网络不确定性：在非拜占庭情况下(非受信网络)，出现网络 分区、冗余、丢失、乱序 等问题下要保证正确。
5. 基本可用性：集群大部分节点能够保持相互通信，那么集群就应该能够正确响应客户端
6. 不依赖时序：不依赖物理时钟或者极端的消息延迟来保证一致性。不能依靠给消息时间戳来保证消息的顺序。零点飘逸
7. 快速响应：对客户端请求的响应不能依赖集群中最慢的节点

一个可行解

• 初始化时候有一个leader 节点，负责发送日志到其他追随者，并决定日志的顺序
• 读请求到来时，任意节点都可读，写请求需要重定向到leader节点
• 领导者先写入自己的日志，然后同步给半数以上节点，跟随者表示ok了，领导者才提交日志。（有点类似先commit 再push）
• 日志最终由领导者先按照顺序应用于状态机，其他跟随者随机应用到状态机
• 当领导者崩溃之后，其他跟随者通过心跳感知并选举出新的leader继续集群的正常运转
• 当有新节点加入或者退出集群，需要将配置信息同步给整个集群

Raft 的详细实现

状态机

raft 中有三个角色(状态)，三个角色可以进行一些切换，每一个状态都有不同的数据结构 所有的节点在启动的时候都是Follower，会启动一个心跳计时器，如果心跳计时器超时了，那么就会变为Candiate状态，变成之后会立即向其他结点发送投票请求进行投票，同时也会启动一个选举超时计时器。 如果收到半数以上人数的票就会变为leader，成为leader之后发送心跳和同步日志，启动一个定时器，每隔一段时间给follower发送心跳。 如果始终没有收到足够的选票，这时候选举定时器超时，就会更新自己的状态为候选人重新发起一轮新的投票过程 如果在等待选票的过程中，收到了leader的心跳请求，就会退回到follower状态。 由于网络分区，集群中又出现了一个leader，这时候网络中就有两个leader，这是分布式系统中一个常见的问题-脑裂。如何避免这个问题呢？给每一个leader都有一个任期term（在心跳中就会同步任期数），如果有两个leader之后就后根据term较大的一个作为新的leader，较小的term的leader就会退回为follower 选举的过程中，超时计时器的时间是固定的，所有的follower变为candidate同时请求选举，可能会有瓜分选票的问题，三个人手上都只有一张选票，没有超过半数，一直选举，一直都没有leader出现，一直都不可写。raft为了避免这个问题，给每个结点选举超时时间设定了一个随机范围，尽量在一次选举中就可以选出leader

数据结构

通用持久性数据（三个状态都有）

• raft 在一个term中一个follower只会投一次票
• log 中包含操作（set，add，是复制状态机可接受的操作），term（写入这个操作的leader的所处的term），以及对应的index

通用易失性数据

• commitIndex的左边的日志是这个server已经提交的日志（已经提交给集群中半数以上的节点）
• lastAppliApplied <= commitIndex ,他们中间可能还有一部分log处于可以应用但是还没有应用的状态。
• raft只保证已提交日志的一致性。lastApplied和commitIndex之间的可能是不一致的。

leader的易失性数据

• 标识同步的状态，还有多少log没有被同步

对于每一个角色，都有不同的定时器，leader是发送心跳的计时器，follower是心跳超时的计时器，candidate是选举超时的计时器

RPC

RPC 的发起者是谁，由谁接受处理它？

• candidate 发起投票选举的RPC 到follower或者candidate
• leader 发起的RPC到follower
  • 日志追加
  • 心跳通知 candidate会将投票选举的RPC发送给它知道的所有的结点

请求投票

什么时候触发？

1. follower变为candidate(follower的心跳计时器超时了)
2. 选举超时

请求(核心)参数

返回值

投票逻辑（候选人）

1. 在转变成候选人后就立即开始选举过程
2. 自增当前的任期号 (currentTerm)
3. 给自己投票(votedFor = 自己的 ID)
4. 重置选举超时计时器
5. 发送请求投票的 RPC 给其他所有服务器（到选举规则了）
6. 如果接收到大多数服务器的选票，那么就变成领导人
7. 如果接收到来自新的领导人的附加日志 RPC，转变成跟随者
8. 如果选举过程超时，再次发起一轮选举

选举的规则（接受到RPC方）

1. 如果term＜ currentTerm返回 false，currentTerm
2. （判断候选人已经提交的的日志是否是足够新的，候选人应该拥有所有的已提交，从建立之初到现在的所有的日志）如果votedFor 为空 或者 等于 candidateld(可能是新一轮投票)，并且比较lastLogTerm和currentTerm
3. lastLogTerm>currentTerm则直接投票
4. 小于则拒绝
5. 等于则比较lastLogIndex 和 log[len(log)-1].idx

日志追加&心跳

触发

1. 客户端发起写请求时
2. 发送心跳时
3. 日志匹配失败时

请求参数

响应值

日志追加（leader）

1. 一旦成为leader：发送空的附加日志RPC(心跳)给所有的follower，在一定空余时间之后不停的重复发送，阻止follower超时
2. 如果接受到来自client的写请求：附加本条目到本地日志中，在条目被应用到状态机后响应client（可选，如果是强一致的，就这样做，如果不是强一致附加到本地日志就可以返回了）
3. 对于follwer，如果leader的最后日志条目的索引值>=nextIndex，那么发送从nextIndex开始的所有日志条目：
4. 如果成功，更新相应追随者的nextIndex和matchIndex
5. 如果因为日志不一致而失败，减少nextIndex 重试(每次减1进行尝试，直到找到和preLogIndex，term匹配的就停止，就可以发送日志了。为什么只匹配到这个就可以认为之前的也一样呢？只要不匹配就往后退，就删除，最后肯定会当index=0的时候一定匹配，那么这时候1也匹配，2也配)
6. 如果存在一个满足 N>commitIndex 的N，并且大多数的matchIndex[i]>=N 成立，并且log[N].term == currentTerm 成立，那么 commitIndex = N (matchIndex 是当前集群同步的进度，N就是超过一半的节点都提交到这个点了，中位数，那么就满足了法定人数，此时更新这个commit就是安全的)

接受日志(follower)

1. 如果leader的term < follower当前的term，返回false,currentTerm
2. 在接受者的日志中，如果能找到一个和preLogIndex以及preLogTerm一样的索引和任期的日志条目，则执行下面操作，否则返回false，
3. 如果一个已经存在的条目和新的条目发生冲突(索引相同，任期不同)，那么就删除这个已经存在的条目以及它之后的所有条目。(五个结点旧的leader和其中一个结点与其他三个结点分区了，网络恢复后，结点A有可能存在没有提交的logEntry)，leader会让删除不是自己任期内的为提交的日志。当前日志未提交，可以强制使follower复制日志和leader一样。
4. 追加日志中尚未存在的任何新条目 5. 如果领导者的(commitIndex)leaderCommit 大于 接收者的commitlndex 则把接收者的commitlndex 重置为 ( leaderCommit 或者是 发来的最新日志条目的索引值取两者 的最小值) ？？？

算法证明

五条公理

选举安全特性

在一个任期内半数以上选票才可以当选，保证每个任期要么0个领导要么1个领导。 normal operation 是有leader的时候 一个term可能也没有leader被选举出来，那么这时候term++，继续选举

日志复制过程的完全匹配

1. 因为 集群在任意时刻最多只能有一个leader存在，leader在一个任期内只会在同一个索引处写入一次日志
2. 又因为 领导者从来不会删除或者覆盖自己的日志，并且日志一旦写入就不允许修改
3. 所以 只要任期和索引相同,那么在任何节点上的日志也都相同
4. 因为 跟随者每次只会从与leader的PreLog匹配处追加日志,如果不匹配 则nextindex -1重试
5. 所以 由递归的性质可知一旦跟随者和leader在PreLog处匹配,那么之前的所有日志就都是匹配的(0 就是空log，是起点，所有的结点都相同)
6. 所以只要把preLog之后的日志全部按此次Leader同步RPC的日志顺序覆盖即可保证 二者的一致性

安全性

每一任的领导者一定会有所有任期内领导者的全部已提交日志吗？

选举限制

选民只会投票给任期比自己大，最后一条日志比自己新(任期大于或者等于时索引更大)的候选人。 但这真的正确吗？

1. 时刻a，S1是任期2的领导人并且向部分节点（S1和S2）复制了2号位置的日志条目，然后宕机​
2. 时刻b，S5获得了S3、S4( S5的日志与S3和S4的一样新，最新的日志的任期号都是1）和自己的选票赢得了选举，成了3号任期的领导人，并且在2号位置上写人了一条任期号为3的日志条目。在新日志条目复制到其他节点之前，S5若机了​
3. 时刻c，S1重启，并且通过S2、S3、S4和自己的选票赢得了选举，成了4号任期的领导人，并且继续向S3复制2号位置的日志。此时，任期2的日志条目已经在大多数节点上完成了复制​ （s3 的4 可能还没有提交）
4. 时刻d，S1发生故障，S5通过S2、S3的选票再次成为领导人（因为S5最后一条日志条目的任期号是3，比S2、S3、S4中任意一个节点上的日志都更加新），任期号为5。然后S5用自己的本地日志夜写了其他节点上的日志​
5. 上面这个例子生动地说明了，即使日志条目被半数以上的节点写盘（复制）了，也并不代表它已经被提交（commited）到Raft集群了——因为一旦某条日志被提交，那么它将永远没法被删除或修改。这个例子同时也说明了，领导人无法单纯地依靠之前任期的日志条目信息判断它的提交状态​
6. 因此，针对以上场景，Raft算法对日志提交条件增加了一个额外的限制：要求Leader在当前任期至少有一条日志被提交，即被超过半数的节点写盘
7. 正如上图中e描述的那样，S1作为Leader，在崩溃之前，将3号位置的日志（任期号为4）在大多数节点上复制了一条日志条目（指的是条目3，term 4），那么即使这时S1若机了，S5也不可能赢得选举一一因为S2和S3最新日志条目的任期号为4，比S5的3要大，S3无法获得超过半数的选票。无法赢得选举，这就意味着2号位置的日志条目不会被覆写

所以新上任的领导者在接受客户端写入命令之前 需要提交一个no-op(空命令)，携带自己任期号的日志复制到大多数集群节点上才能真正的保证选举限制的成立。（相当于不会单独同步Term 2，而是把同步Term2与Term4原子化，不然Term2会被覆盖）

状态机安全性证明（三段论）

1. 定义 A为上个任期最后一条已提交日志，B为当前任期的leader​
2. 因为 A必然同步到了集群中的半数以上节点​
3. 又因为 B只有获得集群中半数以上节点的选票后才能成为leader​
4. 所以 B的选民中必然存在拥有A日志的节点​
5. 又因为 选举限制， B成为leader的前提是比给它投票的所有选民都要新​
6. 所以 B的日志中必然要包含A​
7. 又因为 日志完全匹配规则 如果A被B包含，那么比A小的所有日志都被B包含​
8. 因为 lastApplied <= commitIndex​
9. 又因为 raft保证已提交日志在所有集群节点上的顺序一致​
10. 所以 应用日志必然在在所有节点上顺序一致​
11. 因为 状态机只能按序执行应用日志部分​
12. 得证 状态机在整个集群所有节点上必然 最终一致

状态机安全性证明（反证法）

1. 当日志条目L被同步给半数以上节点时,leaderA会移动commitIndex指针提交日志,此时的日志被提交​
2. 当leader崩溃后, 由一个新节点成为leaderB，假设leaderB是第一个未包含leaderA最后已提交日志的领导者​
3. 选举过程中,只有获得半数以上节点认可才能成为leader,因此至少有一个投票给当前leaderB的节点中含有已经提交的那条日志L。​
4. 那么根据选举限制, 节点只会将选票投给至少与自己一样新的节点​
5. 节点C作为包含leaderA最后提交日志条目的投票者, 如果leaderB与节点C的最后一条日志的任期号一样大时，节点C的条目数一定大于leaderB，因为leaderB是第一个未包含最后一条LeaderA日志的领导者。这与选举限制相矛盾，节点C不会投票给leaderB
6. 如果leaderB最后一条日志的任期号大于节点C最后一条日志的任期号, 那么leaderB的前任领导中必然包含了leaderA已经提交的日志(leaderB是第一个不包含leaderA已提交日志的领导者 这一假设) 根据 日志匹配特性 leaderB也必须包含leaderA最后的已提交日志,这与假设矛盾。​
7. 所以证明 未来所有的领导者必然包含过去领导者已提交的日志,并且日志匹配原则,所有已提交日志的顺序一定是一致的。
8. 又因为 任意节点仅会将已提交日志按顺序应用于自身的状态机,更新lastApplied指针,因此所有节点的状态机都会最终顺序一致。
9. 得证 raft 算法能够保证节点之间的协同工作。

一些额外的资料

一致性介绍

• 弱一致性。在写入之后，访问可能看到，也可能看不到（写入数据）。尽力优化之让其能访问最新数据。这种方式可以 memcached 等系统中看到。弱一致性在 VoIP，视频聊天和实时多人游戏等真实用例中表现不错。打个比方，如果你在通话中丢失信号几秒钟时间，当重新连接时你是听不到这几秒钟所说的话的。
  • 最终一致性。在写入后，访问最终能看到写入数据（通常在数毫秒内）。数据被异步复制。 DNS 和 email 等系统使用的是此种方式。最终一致性在高可用性系统中效果不错。
  • 强一致性。在写入后，访问立即可见。数据被同步复制。 文件系统和关系型数据库（RDBMS）中使用的是此种方式。强一致性在需要记录的系统中运作良好。

脑裂 (split-brain)

原本一个集群，被分成了两个集群，同时出现了两个“大脑”，这就是所谓的“脑裂”现象。 这里的大脑都是被选举出来的，可能由于网络分区的原因，选举的时候。由于原本的一个集群变成了两个，都对外提供服务。 一段时间之后，两个集群之间的数据可能会变得不一致了。 当网络恢复时，就面临着谁当Leader，数据怎么合并，数据冲突怎么解决等问题。

网络分区

在分布式环境下，有时由于网络通讯故障，而不是服务器上的应用故障，导致一些节点认为应用不可用，另外一些节点认为应用仍可用。导致，整个系统在提供服务时，造成了不一致性。由于故障将网络划分为多个区域了。