llf333
0%

Raft博士论文阅读

Posted on In
Symbols count in article: 6.7k Reading time ≈ 24 mins.

Raft基础

CAP理论

①Consistency 一致性：如果系统对一个写操作返回成功，那么之后的读请求都必须读到这个新数据；如果写操作返回失败，那么之后所有的读请求都不能读到这个数据；对于调用者而言数据具有强一致性。

②Availability 可用性：所有读写请求在一定时间内得到响应，不会一直等待

③Partition tolerance 分区容忍性：在网络分区的情况下，被分隔的节点仍然能够正常对外服务

为什么三者只能取其二？

PA：存在网络分区，那么网络中的节点之间就有可能数据不一致；比如往节点A中写入数据，B节点由于网络原因没有同步数据过去，如果此时往B节点读取数据是不能读到数据的，所以在存在网络分区的情况下，这个时候如果系统可用，那么数据是不可能保持一致的。

PC：两个节点网络隔离了，想要保证数据一致性只能等待网络恢复，将数据同步，才能读取到数据；也就是说如果想要保证数据强一致性，那么在等待网络恢复的过程中，是不能对外提供服务的，这个时候系统就不可用。

CA：直接舍弃了分区容忍性，那么就演变成了传统的单机系统。

描述一下Raft是什么？

Raft 是一种为了管理日志复制的分布式共识算法，通常用于维护一个集群中的各个节点的状态一致。维护状态一致的方法通常有两种，第一种比较古老，也比较好理解，就是一个服务器直接向另一个服务器传输当前状态信息，然后接收方进行复制，简单粗暴，很明显的缺点就是这种方法会占用大量带宽。第二种就是使用状态机模型，每个服务器存储顺序相同，内容相同的日志，然后服务器分别执行这些日志的命令，因为初始状态相同，日志的顺序内容相同，所以执行后的最终结果相同，所以保证了各个节点的状态相同。说通俗点，Raft算法就是说明在复制日志时，怎么样维护这个日志的顺序相同和内容相同。

Raft和Paxos的区别？

说实话我也没读过Paxos算法的论文，据我粗浅的了解，Paxos和Raft好像差不多，比如说，同一时刻只有一个合法的Leader，某个Entry需要得到多个follower的赞成才会定下来等，总的来说，Paxos算法已经具备了共识算法的完整性，很多要点都已经说出来了，是很多共识算法的基础，但是在Raft论文中也提了它的缺点，就是说很复杂很难理解，因此Raft就对Paxos算法，或者说是共识算法中的各个要点进行了抽象，分点地对共识算法的各个部分进行了说明，提高了算法的可用性和可扩展性。（像Raft现在就有类似的库，上层想要达成一致，就直接调库就行，而想用Paxos就得自己写，因为它太复杂了，从代码设计的角度来说就是它耦合性太强了，想做到解耦很难。）

Leader选举是如何执行的？

（按时间来描述，说得更清晰）

初始状态，集群中的所有节点都是follower，在Raft中，每个节点等待Leader的心跳的超时时间都是随机的，这样，在节点都是follower的状态下，会有一个节点首先达到超时状态，这时它就会开启一轮选举，自己变成候选人，首先投自己一票，并增加当前的Term，并向其他节点发送选举请求，其他节点给他投票，如果票数超过一半则选举成功。每个节点只能投一票，所有最多只有一个合法的leader被选出来，且选举成功后的leader会定时向follower发heartbeat阻止新一轮的选举。

如果说节点A已经成功了，节点B还在请求选举，如果B在收到投票结果之前收到了A的心跳，那它会转变成follower，如果在收到心跳之前收到了投票结果，节点B也必然是失败的，因为同一任期内一个节点只能投一票，它的票数不够。

随机超时时间也是用来避免无限选举的情况。如果大家的超时时间都是一样的，那么它们会同时成为candidate，那么就很可能你一票我一票，大家都没有超过一半的票，就选不出来，下轮选举并且还有可能这样，所以用随机超时时间。

各类时间的要求：broadcastTime ≪ electionTimeout ≪ MTBF
broadcastTime 指的是RPC往返时间，MTBF指的是平均一个服务器的故障时间。

（这种方法没有加限制仍不严谨：比如一个A当选了，B宕机了，在宕机期间A提交了一些日志，B恢复后又没即使收到A的心跳包，然后B开始选举并当选了，那么B就有可能覆盖A中已经提交的日志。限制是什么呢？candidate发送出去的投票请求消息必须带上其最后一条日志条目的Index与Term；接收者需要判断该Index与Term至少与本地日志的最后一条日志条目一样新，否则不给投票。安全性！）

如何解决日志冲突？如何进行日志复制

Raft日志的两个特点
1、两个entry的index和term相同的话，那么他们包含的command一定是相同的
2、两个entry的index和term相同的话，那么他们在他们之前的entry一定都是相同的。
第一点：leader在给定的term和index上只能创建一个entry，而且entry不被允许修改位置。
第二点：一致性检查

什么是一致性检查？
在AppendEntries中，发送的log除了最新的log，还包含新log之前旧的log（总共就是prevLogIndex之后的所有log），如果旧的日志不一致，这个不一致指的是Index和Term不一致，则follower会拒绝Append请求。

如何解决日志冲突？（如果一个Follower缺了一些日志怎么发现，多了一些怎么发现，错了一些怎么发现等问题）

​ 首先需要明确的是Leader上的允许Commit的日志都是正确的，因为这些日志都得到了超过一半的节点的响应。对于Follower日志的错误，本质就是要把他们强制修改为Leader允许Commit的日志。整体来说，分为两步：

  • 通过AppendEntries 找到日志冲突点，就是follower从哪个位置开始和leader的日志不一致了。
  • leader把follower日志冲突点以后的日志强行刷新成自己的。

​ 具体细节就是leader会向follower不间断的发送AppendEntries请求，如果follower返回false的话，那就证明follower和leader不一致。那么leader发送的AppendEntries就会把 prevLogIndex减1再次发送，直至和follower匹配上。匹配成功以后，通过AppendEntries请求将leader上的entries同步至follower。

（这里使用prevLogIndex和prevLogTerm来检查，其实是只检查某一个具体位置日志是否相同，如果这一个具体位置的日志相同，那么其之前的所有日志都相同，这个可以使用数学归纳法来证明，如果在扩展日志时每次都这么检查，那么就能有这个保证。）

安全性保证

文章中这一章主要是针对两个corner case的限制，完善了raft的安全性。

1、选举限制。

case：A当选了Term为2，B宕机了Term为2，在宕机期间A提交了一些日志，B恢复后又没立即收到A的心跳包，然后B开始选举(Term为3)并当选了，那么B就有可能覆盖A中已经提交的日志

方案：选举的条件加了一个，不单单是没投过就投给它，还要保证candidate的日志至少和接收者的日志一样新。

2、Leader只能提交自己任期内的日志

case：Figure8

方案：Leader只能提交自己任期内的日志，通过这种方式，间接提交当前日志之前其他任期的日志。Raft 的 Figure 8 讲了什么问题？为什么需要 no-op 日志？ - 知乎 (zhihu.com)，为了保证集群的liveness（可用性），一般的方案是Leader每次当选后都需要立即发送一条no-op日志，来确保之前的任期的日志完成提交。

加了这两个限制是否就能够说明Raft是安全的呢？可以。证明，在任期U<T时，U任期内提交的日志一定存在于T任期中。

证明：
1、U提交一个日志了，则说明大多数都提交了一个日志。
2、T选举成功了，则说明大多数都投给了T。
3、那么说明必定有一个节点（记为X）既提交了一个日志，且投给了T。
4、因为X投给了T，所以T任期的Leader日志至少和X一样新。
4.1 如果T和X一样新，因为X有，所以T也一定有。
4.2 如果T比X新，因为X有，根据Log Matching属性，T也一定会有。

日志压缩

随着log数量的增大，log会占用大量空间，并且也会导致重放日志的时间变长。所以Raft需要定期做Snapshot，需要保存的信息：

  • 状态机当前的状态（根据状态机而定）

  • 状态机最后一条应用的 entry 对应的 index 和 term

需要注意的是状态机当前的状态的数据，Raft层是无法进行解析的，比如一个kv数据库，通常是保存各个kv对，这对于Raft层是透明，因此状态机当前状态的保存和解析是交给上层来完成的，Raft层只做到保存这些数据即可。

在安装快照时，是不允许新的log进行apply的，因为快照安装结束后会覆盖该条log。

哪些变量需要持久化？哪些变量不需要持久化？为什么？

需要持久化的：Log，CurrentTerm，Votedfor

  • Log很好理解，因为节点宕机了想要恢复状态，我们必须需要它。

  • Votedfor必须持久化的原因是，假如没有持久化，一个节点给一个服务器投票了，它宕机了，那么它很有可能在重启后给同一任期内的另一个服务器投票，这样就会导致同一任期内可能有两个Leader，也是不行的。

  • CurrentTerm的持久化本质上也是维护一个任期内只有一个Leader。考虑下面情况，假如A是Leader有三条日志，term分别是567，BC只有一条日志是5，假如A永久关闭了，且BC宕机重启，他们会重新选Leader，这时候他们因为不知道CurrentTerm是多少，那么BC的第二条日志的Term可能就会是6，这样在Term为6的任期内就存在了两个Leader。

为什么服务器重启时，commitIndex、lastApplied、nextIndex、matchIndex，可以被丢弃？

  • leader 侧的 commitIndex 是根据 matchIndex 算出来的，每当有一条新的日志追加，传播到多数 follower 时，commitIndex 就重新算出来了。在 follower 侧，重启后初始化为 0，收到 leader 的 appendEntries 心跳，commitIndex 就也跟着得到更新了。

  • lastApplied 按说是要持久的。原论文是假设状态机在内存中，重启后要重新 replay 整个 log 来重建状态，因此当然 lastApplied 得从 0 开始了。然而工程上这种状态机的状态肯定是持久化的，不可能从 0 开始重新跑，这个 lastApplied 就该持久了。不然就得重置状态机，重头开始重放raft日志了。

Raft applyIndex 和 commitIndex 的关系以及区别，是否需要持久化，持久化有什么好处。

commitIndex代表的是可以被提交的最大index，lastApplied(applyindex)代表的是已经被提交给状态机的最大index。applyIndex 持久化对快速重启恢复有帮助。commitIndex持久化一下也能快一些，重启之后不用网络就能直接去异步 apply (applyIndex, commitIndex] 区间的日志了。

集群变更

直接大规模切换的问题

如果一次性变更太多，并且从旧配置直接更换到新配置，那么可能会出现同一任期里有两个Leader的现象，这是不可接受的。

下面说出现的原因：

如图是3个节点的集群扩展到5个节点的集群，Server1和Server2构成Old Conig的quorum，Server3、Server4和Server5构成New Conig的多数quorum，导致决议冲突。据此Raft博士论文中给出了两个方案，单步成员变更和多步成员变更。

这里首先需要说明一下，集群变更其实也是一条日志，一条Config日志。但和普通日志所不同的是，Config日志无需在Commit后才生效，而是出现了就立即生效。为什么？不会出现安全性的问题吗？为什么不保守一点等Commit后才生效？

答：

以下是在OneSizeFitsQuorum/raft-thesis-zh_cn: Raft 博士论文的中文翻译 (github.com)指出的：

服务器总是在其日志中使用最新的配置，而不管是否提交了配置条目。这使得领导者可以很容易地避免重叠的配置更改（上面的第三项），方法是直到之前的更改的条目提交之后才开始新的更改。只有当旧集群的大多数成员都在 Cnew 的规则下运行时，才可以安全地开始另一次成员更改。如果服务器只在了解到 Cnew 已提交时才采用 Cnew，那么 Raft 的领导者将很难知道何时旧集群的大部分已经采用它。它们需要跟踪哪些服务器知道配置更改条目的提交，服务器也需要将它们的提交索引保存到磁盘；Raft 其实不需要这些机制。相反，Raft 的每台服务器只要发现该条目存在于其日志中，就采用 Cnew，并且知道一旦提交了 Cnew 条目，就可以安全地允许进一步的配置更改。不幸的是，这个决定意味着配置更改的日志条目可以被删除（如果领导者发生变化）；在这种情况下，服务器必须准备好返回到其日志中的先前配置。

关于是否正确，我的理解是这样的，Config日志只说明了集群的成员，而不包含状态机命令，如果Config日志直接被应用了，它并不会更改状态机的状态，也就是说Config日志，如果不会影响普通日志的提交，那么它就不会影响系统的正确性。那什么情况下它会影响普通日志的提交，唯一的可能性就是如上所说，新旧集群变更时出现了两个quorum，或者说是同一任期出现两个Leader，这样就导致某些命令被错误地认为被大多数认可了，导致错误。如果能够避免同一任期不可能出现两个Leader的问题（下面的单步成员变更和多步成员变更就是解决这个问题的），那么直接提交Config日志绝对是正确的。当然论文中也提到了，这种没有commit的日志在某一时刻可能被删除，那么节点就必须做到回滚，也就是说还需要保存先前配置的日志。

那么为什么不保守一点等Config日志提交后才生效？我从下面这个博客摘取了一个Case来Raft 成员变更的相关问题 – 沧海月明 (inlighting.org)

如果我们规定成员变更只有 committed 后生效，可能会降低可用性（上面原话中加粗的话也印证了这个Case）。

  • 假设存在A，B，C，D 四个节点，A 为 Leader，D 因为某种原因一直是故障，当前这个集群仍然是能正常工作的，因为满足 3 quorum。
  • Leader A 提出要移除 B 节点，并打算将 Cnew 同步到 A，B，C，D 四个节点上了。此时 B 节点也失联了，导致 Leader A 只能同步 ConfChange 到 A 和 C 两个节点。因为 2 小于 3 quorum，使得这个 ConfChange 无法被 commit，也就无法生效，而此时整个集群只有两个节点，不满足 quorum 条件，无法处理任何请求。

如果我们假设 ConfChange 收到就应用，第二步变为：
Leader A 提出要移除 B 节点，并打算将 Cnew 同步到 A，B，C，D 四个节点上了。此时 B 节点也失联了，导致 Leader A 只能同步 ConfChange 到 A 和 C 两个节点。A，C 立即生效了新配置，此时新的 quorum 大小为 2，集群存在两个活跃节点，故其能正常处理请求，commit 正常推进。

所以在正确的前提下，为了提高可用性，我们可以选择Config日志无需Commit而立即生效。

单步成员变更

参考Raft 成员变更的相关问题 – 沧海月明 (inlighting.org)

多步成员变更

参考Raft 成员变更的相关问题 – 沧海月明 (inlighting.org)

一些学到的优化和理解

下面的内容并非完全是自己的理解，主要是在读别人的资料理解后拼凑的，挂出了主要来源。

领导禅让

有时候，会希望取消当前 leader 的管理权，比如：

  • leader 节点因为运维原因需要重启；
  • 有其他更适合当 leader 的节点，比如在某个地方的中心设立Leader，这样到Follower的RPC时间就会更合理；

直接将 leader 节点停机的话，其他节点会等待 electionTimeout 后进入选举状态， 这期间会集群会停止响应。为了避免这一段不可用的时间，可以采用禅让机制：

  1. leader 停止响应客户端请求，并开始禅让计时；
  2. leader 向 target 节点发起一次日志同步；（保证follower等下的选举能够成功）
  3. leader 向 target 发起一次 TimeoutNowRPC，target 收到该请求后立刻发起一轮投票。

目标服务器也有可能发生故障。在这种情况下，集群必须恢复客户端操作。如果在选举超时后领导权禅让仍未完成，则当前领导将中止禅让并恢复接受客户请求。如果当前领导者弄错了并且目标服务器实际上是可用的，那么在最坏的情况下，此错误将导致一次额外的选举，此后客户端操作会恢复。

来源：OneSizeFitsQuorum/raft-thesis-zh_cn: Raft 博士论文的中文翻译 (github.com)

PreVote

一个暂时脱离集群网络的节点，在重新加入集群后会干扰到集群的运行。
因为当一个节点和集群失去联系后，在等待 electionTimeout 后，它就会增加自己的 term 并发起选举， 因为联系不上其他节点，所以在 electionTimeout 后，它会继续增加自己的 term 并继续发起选举。
一段时间以后，它的 term 就会显著的高于原集群的 term。如果此后该节点重新和集群恢复了联络， 它的高 term 会导致 leader 立刻退位，并重新举行选举。

为了避免这一情形，引入了 Pre-Vote 的机制。在该机制下，一个 candidate 必须在获得了多数赞同的情形下， 才会增加自己的 term。一个节点在满足下述条件时，才会赞同一个 candidate：

  • 该 candidate 的日志足够新；
  • 当前节点已经和 leader 失联（electionTimeout）。

也就是说，candidate 会先发起一轮 Pre-Vote，获得多数同意后，更新自己的 term， 再发起一轮 RequestVoteRPC。

这种情形下，脱离集群的节点，只会不断的发起 Pre-Vote，而不会更新自己的 term。

来源：OneSizeFitsQuorum/raft-thesis-zh_cn: Raft 博士论文的中文翻译 (github.com)

Read Index和Follower Read

针对的是线性一致读的问题。对于读请求，因为读请求不会改变状态机的状态，为了提高效率，一个很自然的想法就是想读请求能不能绕开日志。但是这样直接读，就算是在Leader上读，也会出现问题，比如集群ABCDE，A为Leader，经过某个时候AB和CDE被分区了，CDE中会推出新的Leader并且满足quorum，集群会继续正常执行。此时假如客户端读请求访问到了旧LeaderA，如果单纯粗暴地绕开了日志，直接读，那么就会读到过时的数据，这就违背了线性一致性。对此Raft博士论文里也对这种情况提出了优化，对于Leader采取以下措施：

  1. 记录当前的 commit index，称为 Read Index（如果是刚当选的Leader，还得提前提交一个no-op日志来保证当前的commit index在任期内至少与其他节点一样大）
  2. 向 follower 发起一次心跳，如果大多数节点回复了，那就能确定现在仍然是 leader
  3. 等待自己的状态机至少应用到 Read Index 记录的 Log
  4. 执行读请求，将结果返回给 Client

这样，基于上面的Case，假如读请求读到错误的Leader，则不会得到quorum的同意，拒绝读请求。这种方式相较于将读请求写入日志里，只需要用心跳包来确认此次读请求的合法性，减少了磁盘写入，提高了性能。（这里还可以使用Batch优化，一轮心跳来处理多个读请求）

假如我们想在Follower上实现读数据，因为一个follower可能由于长期宕机导致数据都是旧的，直接读肯定是不行的。

基于上面类似的思路，Follower直接去找Leader要一个Read Index就好了，因为Read Index的日志肯定是合法的。我们还可以将读对于Follower可以采取以下措施：

  1. 当follower收到只读请求后，可以给leader发送一条获取Read Index的消息
  2. 当leader通过心跳广播确认自己是合法的leader后（同上面的1和2）（其实最好是等到3，万一Leader的apply慢于follower的apply，那么就读到了leader状态机中还尚未存在的数据，这种其实也违反了线性一致，但好在是返回最新的数据）
  3. Leader将其记录的Read Index返回给follower
  4. follower等待自己的状态机至少应用到 Read Index 记录的 Log
  5. 执行读请求，将结果返回给 Client

这样的优化，一定程度转移了Leader的负载，也提高了提高系统的读取吞吐量。

来源：

  1. OneSizeFitsQuorum/raft-thesis-zh_cn: Raft 博士论文的中文翻译 (github.com)
  2. TiDB 新特性漫谈：从 Follower Read 说起 - 知乎 (zhihu.com)

Lease Read

ReadIndex虽然提升了只读请求的吞吐量，但是由于其还需要一轮心跳广播，因此只读请求延迟的优化并不明显。

在 Raft 论文里面，提到了一种通过 clock + heartbeat 的 lease read 优化方法。也就是 leader 发送 heartbeat 的时候，会首先记录一个时间点 start，当系统大部分节点都回复了 heartbeat response，那么我们就可以认为 leader 的 lease 有效期可以到 start + election timeout / clock drift bound 这个时间点。当leader持有lease时，leader认为此时其为合法的leader，因此可以直接将其commit index作为Read index。后续的处理流程与ReadIndex相同。

为什么能够这么认为呢？主要是在于 Raft 的选举机制，因为 follower 会在至少 election timeout 的时间之后，才会重新发生选举，所以下一个 leader 选出来的时间一定可以保证大于 start + election timeout / clock drift bound。

虽然采用 lease 的做法很高效，但仍然会面临风险问题，也就是我们有了一个预设的前提，各个服务器的 CPU clock 的时间是准的，即使有误差，也会在一个非常小的 bound 范围里面，如果各个服务器之间 clock 走的频率不一样，有些太快，有些太慢，这套 lease 机制就可能出问题。

来源：

  1. OneSizeFitsQuorum/raft-thesis-zh_cn: Raft 博士论文的中文翻译 (github.com)
  2. TiKV 源码解析系列 - Lease Read (qq.com)

Batch and Pipeline

首先可以做的就是 batch，大家知道，在很多情况下面，使用 batch 能明显提升性能，譬如对于 leveldb的写入来说，我们通常不会每次写入一个值，而是会用一个 WriteBatch 缓存一批修改，然后在整个写入。 对于 Raft 来说，Leader 可以一次收集多个 requests，然后一批发送给 Follower。当然，我们也需要有一个最大发送 size 来限制每次最多可以发送多少数据。

如果只是用 batch，Leader 还是需要等待 Follower 返回才能继续后面的流程，我们这里还可以使用 Pipeline 来进行加速。大家知道，Leader 会维护一个 NextIndex 的变量来表示下一个给 Follower 发送的 log 位置，通常情况下面，只要 Leader 跟 Follower 建立起了连接，我们都会认为网络是稳定互通的。所以当 Leader 给 Follower 发送了一批 log 之后，它可以直接更新 NextIndex，并且立刻发送后面的 log，不需要等待 Follower 的返回。如果网络出现了错误，或者 Follower 返回一些错误，Leader 就需要重新调整 NextIndex，然后重新发送 log 了。

来源：TiKV 源码解析系列 - Raft 的优化 - 知乎 (zhihu.com)

异步Apply

我的6.824其实已经照这么写了，这样可以提升 raft 算法吞吐量。