Raft算法介绍

Mon, Dec 13, 2021 阅读时间 1 分钟

Raft算法介绍

在分布式系统中，为了消除单点故障提高系统可用性，通常会使用副本来进行容错，但这会带来另一个问题，即如何保证多个副本之间的一致性。

强一致性

强一致性不是说所有节点在任意时刻的状态都是一致的，而是指让一个分布式系统看起来好像是个单机一样，所有操作都是原子的，不管什么故障产生，都不会让分布式系统的节点间的数据出现不一致，让应用层可以忽略底层分布式系统之间数据的同步问题，像操作一个单机一样操作这个分布式系统。

共识算法

共识算法就是用来实现强一致性的算法，可以保证在小于一半的节点发生故障时，整个系统依然是正常可用的。

共识算法是强一致性分布式系统的基石，比较有名的就是Zookeeper所使用的Paxos算法，Raft也是共识算法的一种，它是Paxos算法的一个简化版本，更易于理解和实现，被很多的分布式系统使用，比较有名的就是Etcd、Consul，TiKV等，MySQL集群中也使用到了raft算法。

Raft算法的三个核心问题

对于一个基于raft算法的分布式集群来说，当我们通过客户端向集群发起一些读写操作时，首先需要确定的是需要有一个节点对操作进行处理和响应，这个节点被称为是主节点(Leader)，其他节点就叫做从节点(Follower)。Raft算法的第一个核心问题就是选主，需要确定集群中哪个节点作为主节点。

确定了主节点后，主节点就要接收到了客户端的请求，比如接到一个写入数据的操作后，不仅需要将数据保存在本地，还要将数据分发给集群中的其他从属节点。Raft算法需要在保证集群中的大多数节点都接收到了这次操作并且完成同步之后，主节点才可以给客户端操作成功的响应。这个操作分发的过程就是日志复制，即raft算法中主节点是将操作包装成日志的形式发送给所有从节点的。

最后，由于主节点至关重要，同时对于日志的处理也要谨慎小心，为了确保整个集群对外展现出的一致性，在选主和日志复制时需要有一些安全性保证，安全性就是raft算法的第三个核心问题。

选主

Raft的选主就是在raft集群内部通过票选、心跳等机制协调出一个大多数节点都认可的主节点作为集群的leader。

节点角色

Raft集群中会有三种类型的节点：

  • Leader：集群的主节点，是客户端所有请求的真正处理者，接收客户端发起的操作请求，写入本地日志后还要做同步日志到集群其它节点的工作。
  • Follower：集群的从属节点，主要工作就是从 leader 接收更新请求，写入本地日志文件。如果客户端的操作请求发送给了 follower，则会由 follower 重定向给 leader。
  • Candidate：候选者，在选主期间存在的角色，如果 follower 在一定时间内没有收到 leader 的心跳，则判断 leader 可能已经故障，此时启动选主过程（leader election），本节点将切换为candidate角色参与选举。

任期

每一次选主完成之后，都会产生一个任期(term)，直到下一次选主时，该任期结束，每个 term 都有一个严格递增的整数作为标识。

每当candidate触发leader election时都会增加term值，如果一个candidate赢得选举，他将在本term中担任leader的角色。但是并不是每一个term期间都一定存在一个 leader，有时候会由于选举超时导致选不出leader，这时candicate会递增term号并开始新一轮选举。

节点间的RPC方法

Raft集群中节点间的RPC方法只有两个：

  • RequestVote RPCs：用于candidate在选举时给自己拉票。
  • AppendEntries RPCs：用于leader节点向其他节点复制日志，和同步心跳证明自己的存活。

节点的状态转换时机

上图描述了一个节点向各个角色转换的各种场景。接下来我们详细讨论一下：

Follower状态转换过程

Raft的选主基于一种心跳机制，集群中的每个节点在刚刚启动时都是follower身份（starts up这一步），leader节点会周期性的发送心跳包给所有的follower来保持权威。当一个follower在一段时间内没有收到来自leader的心跳包（即选举超时），则它会认为集群中此时没有leader，此时他就会发起选举（times out, starts election这一步），同时这个follower会转换自己的身份到candidate，并将自己的term值加1。

而当集群刚刚启动，所有的节点都是follower节点，自然所有follower都无法收到leader的心跳包，那么如果这个选举超时的时间都是一样的，所以follower节点将会在同时发起选举，那么整个集群都会变得低效，甚至一直都选不出来一个leader，Raft算法通过一个随机定时器，让每个节点的选举超时时间都是一个一定范围内的随机值，以此降低多个节点同时发起选举的可能性。

Candidate状态转换过程

当follower转换成candidate时，会向集群中的其他节点发送RequestVote的RPC请求进行拉票，请求其他节点给自己投票。那么就会有三种可能：

  1. 选举成功

    当candidate收到了集群的超过半数的节点(包括自己)针对同一个term的选票时，他就赢得了这次选举，此时他就立刻将自己的身份转换为leader，并立刻向集群中所有其他节点发送AppendEntries的RPC请求发送自己的心跳包通知所有节点自己成为了leader的同时，维持自己的权威。

    每个节点针对每一个相同的term只会投出一张选票，所有candidate将会按照先到先得的方式，确保只有一个candidate会成为leader。

  2. 选举失败

    当这个candidate在等待其他节点给自己投票时，突然收到了其他节点发给自己的AppendEntries的RPC请求，通知自己他成为了leader，那么这个candidate会检查这个请求中包含的term值，如果他发过来的term值大于等于自己的term，那么该candidate就会认同这个选举结果，并响应心跳；如果说对方的term值比自己小，则就会拒绝承认对方的leader身份，并保持自己的candidate身份。

  3. 选举超时

    最后一种结果就是，这次选举耗时太久，都没有任何一个follower成为了leader，可能是因为多个candidate平分了选票，那么此时candidate在意识到这次选举超时时，会立刻增加自己的term然后重新向所有节点发送RequestVote的RPC请求，开启新一轮的选举。

    这里选举超时时间是随机化的，即如前文所说，每个节点的超时时间都是在一定范围内的随机值，以防止在所有节点一开始时同时发起竞选，可能导致的选票一直被平分从而一直选不出来leader。

Leader状态转换过程

Leader节点如果要转换成其他节点，只能是被动的转换。当leader节点宕机或者断网，此时其他follower节点会重新进行选举并选出一个新的leader，然后一段时间后leader节点恢复后，就会收到新leader节点的心跳包，然后当他发现这个心跳包中的term比自己时，就会心甘情愿的切换成follower开始追随新leader。（discovers server with higher term这一步）

以上就是整个的选主过程，以及节点在各个身份上的转换场景，关于投票等还会有一些限制条件，这部分将会在后面的安全性模块进行描述。

日志复制

当Leader节点被选举出来，它就要完成它的工作，开始接收客户端请求，并将操作内容包装成日志，并通过AppendEntries这个RPC方法发送日志到其他节点上。整个流程如下：

  1. leader接收客户端发来的写数据指令，然后把整条操作指令附加到自己的日志。
  2. 然后leader向其他所有节点发起附加条目的RPC请求AppendEntries RPC，要求其他节点保存这条日志。
  3. 当大部分节点都成功响应了日志复制，leader就会将该日志提交到本地，然后将执行结果返回客户端。

日志复制一致性的保证

每条日志都有自己的整数索引值，表明他在日志文件中的位置，并且日志中也会保存当前的term号。leader在可以提交，并且响应了客户端之后，发送的心跳包会携带当前已经成功复制的日志索引以及term。所有节点中的follower通过心跳包发现日志已经提交，那么他们就会把自己本地的日志也提交（我的理解，提交就是写入磁盘）。

为了保证日志的一致性。term和index作为一条日志的标识，使用term可以保证数据的一致性。raft要求leader在同一个term内针对同一个index只能创建一条日志，并且日志永远不会被修改。并且复制日志的AppendEntries RPC方法，需要携带上一条日志的term和index，如果follower在本地没找到上一条日志，那么会拒绝接收这条新日志。

可能造成日志复制不一致的场景

  1. follower宕机了一段时间，导致follower数据落后于leader。
  2. leader宕机了，但在宕机之前有follower已经收到了复制日志的请求并给出了响应，然后重新选举时另一台没有复制这条日志的follower当选，就造成了follower的日志领先于leader。

raft强制要求follower必须复制leader日志集合来解决日志不一致的问题。leader会先找到和这个follower最后一次一致的地方，然后后续的日志都进行覆盖填写。

安全性

总体而言，raft的安全性保证体现在选举安全，和提交安全上。

选举安全

由于日志复制时，follower要强制复制leader的日志集合来保证一致性，所以leader的日志正确性至关重要，所以在选举时，必须要考量参选的candidate的日志必须得是集群中最完整的。

因此，当candidate在请求投票时会携带自己本地的最新term和index，如果follower发现这个candidate的日志还没自己的新，就会拒绝投票给他。

所以，Candidate 想要赢得选举成为 leader，必须得到集群大多数节点的投票，那么它的日志就一定至少不落后于大多数节点。又因为一条日志只有复制到了大多数节点才能被 commit，因此能赢得选举的 candidate 一定拥有完整的committed的日志。

提交安全

如下是一种错误场景：

  1. S1作为term1和term2的leader，收到用户请求后，将(term2, index2)只复制给了S2，还没复制给S3~S5
  2. S1宕机，然后S5当选为term3的leader，收到用户请求后，保存了(term3, index2)，但是还没有复制给任何节点
  3. S5宕机，S1恢复，并且S1又重新当选为term4的leader，S1当选后会继续将(term2, index2)这条日志复制给S3，此时这条日志已经满足了复制到了大多数节点的要求，于是这条日志可以提交
  4. S1再次宕机，S5又恢复了，并且S5又当选了term5的leader，开始将自己还没复制的(term3, index2)复制给所有节点。则此时就发生了致命错误，根据日志覆盖的原则，(term2, index2)这条已经提交的日志会被(term3, index2)给覆盖掉！

以上场景可能发生在极短的时间里，用户还没有察觉时，就造成了提交的数据被覆写的错误。针对上述场景，raft增加了一条规则：Leader只允许提交当前term的日志。添加了这个限制后，在第三阶段，(term2, index2)这条日志就无法提交，自然也就无法被覆写了。