分布式存储|阿里技面之raft如何选主大厂面试|raft|raft算法|分布式计

背景一面在考查技术基础首先被问到过raft协议如何选主？主挂了选出的新主如何重新进行日志复制？
raft协议一直都是分布式系统一致性的难点，能讲清楚很不容易，
下面我们就通过现场还原的方式讲讲该如何回答这两个问题的。
现场还原 Q1面试官：那你先说一下raft协议是如何选主吧？
A1 我：为了保证数据一致性，最好的方式是唯一节点去读，唯一节点去写。这样的数据肯定是一致的。但是分布式架构显然不可能一个节点处理。因此raft提出在集群的所有节点中需要有一个节点来充当这个唯一节点，在一段时间内，只有这一个节点负责读写数据，然后其他节点同步数据。这个唯一的节点就叫leader节点，其他负责同步数据的节点叫follower节点，在集群中，还会有其他状态的节点，例如candidate节点，这种节点只有在选主的时候才会涉及。所以三种角色定义如下:
1.跟随者（follower）：相当于普通群众，默默地接收和处理来自领导者的消息，当领导者心跳超时的时候，它就会主动站出来，推荐自己当候选人。
2.候选人（candidate）：将向其它节点发送请求投票（RequestVote）RPC消息，通知其他节点来投票，如果赢得了大多数选票，就晋升位领导者。
3.领导者（leader）：不讲道理的霸道总裁，平常的主要工作内容就是3部分，处理写请求、管理日志复制和不断地发送心跳信息，通知其它结点“我是领导者，不要发起新的选举”。
节点中的主选举和现实生活中的选举十分类似，就是投票，集群中获票数最多的那个，就是leaderer节点。所以为防止出现平局，一般在部署节点的时候，会将节点个数设置为奇数（2n+1）。
那么，这些节点该如何选举呢？我们来看下面这个例子
在集群中，有三个节点A、B、C[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传

文章图片

?
初始状态下，所有节点都是follower，没有leader。过了一段时间A变成了candidate开始发起选举，凭啥A能变成candidate呢？因为如上图可以看到，集群中每个节点都有一个election timeout，它表示选举超时时间。每个节点等待leader节点心跳信息的election timeout都是150ms~300ms的一个随机数，每当节点的election timeout到了就会触发自己成为candidate。A的选举超时时间先到了（150ms）,它会最先因为没有等到leader的心跳信息发生超时。
在这里，只有candidate状态的节点才可以竞选成为leader。B、C这两个follower是没有资格变为leader的。除此以外，每个节点中还有一个字段叫任期编号（term），这个term是一个全局的、连续递增的整数。每进行一次选举term值加1，如果candidate赢得选举，它会称为leader直到任期结束。此时A触发了选举，它就增加自己的term，并推举自己为候选人，先给自己投上一票，然后向其他节点发送请求投票的RPC消息，请它们选举自己为领导者。

文章图片

当B、C接收到A的请求投票RPC消息后，B、C开始投票，此时只有A一个candidate,在term为1的这届任期内目前也还没有进行过投票，那么它将把选票投给节点A，并增加自己的term。

文章图片

如果candidate在选举超时时间内赢得了大多数选票，它将成为本届任期内新的leaderer。节点A当选leader后，为了巩固自己的“统治”，防止任期之间其它节点因为自身的election timeout而触发选举。它将周期性地发送RPC心跳信息。B和C收到心跳消息后，会重置election timeout。心跳检测时间很短，要远远小于选举超时时间election timeout。

文章图片

B和C收到心跳信息后，会发送心跳响应并重置election timeout。

文章图片

假设A发送的心跳检测信息由于网络原因（延迟、丢包等）没有传送到B、C这两个follower节点。B、C刚好election timeout则触发自身选举。此时C修改自身的任期编号term为2，自身状态变为candidate，并且投了自身一票。发起选举。

文章图片

这时候C的任期值term设为2大于A的任期值。在Raft协议中但凡收到任期编号值大于自己的节点，都会更改自身节点的term值并切换为follower并重置自己的election timeout，因此，A直接变成follower。
此外，如果一个节点接收到一个包含较小的term值的请求，那么它会直接拒绝这个要求。举个例子，假如节点C的term为4，当收到包含term为3的请求投票RPC消息，那么节点C会拒绝这个消息。
Q2面试官：回答得挺好，那么刚才你提到部署的时候节点数一般是奇数，那么现在就是偶数个节点怎么办?
A2 我：假如现在变成了四个节点A、B、C、D。A和B同时进入了candidate状态并开始发起选举。如果A和B中任意一个获得了超过半数以上的多数票则变为leader。如果它们两个经过一次选举后得到的票数相同或者都没有超过半数则宣告选举失败并结束。等待A和B这两个节点中任意一个节点的election timeout超时，然后发起新一轮选举。A、B票数相同，则之后等待哪个先超时。假如A先超时，则A发起选举，由于A的term显然是最大的，则A会选为leader。
Q3面试官：那再讲下一般是如何日志复制的呢？
A3我：raft除了可以实现一系列值的共识以外还能够达成各节点日志一致。
副本是以日志的形式存在，日志由日志项组成。日志就好比是数据表，日志项（log entry）就好比是表里面的记录。日志项是一种数据格式，它主要包括用户指定的数据，也就是指令（command）。此外还包含一些附加信息，比如索引值，任期编号。如下图所示

文章图片

指令：客户端请求指定的，状态机需要执行的指令。
索引值：日志项对应的整数索引值。用来标识日志项，是一个连续的、单调递增的整数号码。
任期编号：创建这条日志项的leader的任期编号。
那么如何进行日志复制呢？我们举个例子

首先，接收到客户端的指令后，为该指令创建一个新日志项并追加到本地日志文件中。

文章图片

这里A作为leader，向B、C发送日志复制（Append Entries RPC）请求。这个RPC消息是根据节点不同而消息也不同的。

文章图片

当B、C接收到消息后，把命令成功写入本地日志文件后向A发送信息。

文章图片

A收到大多数follower的回复信息后可以确定一个日志项被safely replicated了，将应用这条日志项到状态机中，将执行结果返回给客户端。如果某个follower遇到异常情况（宕机或者网络丢包），则会一直给这个follower发送日志复制RPC请求。

文章图片
A向B、C这两个follower发送commit成功的通知

文章图片

B和C收到日志复制RPC消息后，它们先commit自己的日志数据，然后再通知A自己已更新结束。

文章图片

到此整个数据同步也就结束了，不过这是一个理想状态下的日志复制过程。在实际环境中，复制日志的时候，你可能会遇到进程崩溃、服务器宕机等问题，这些问题会导致日志不一致。那么在这种情况下
每个节点都有两个索引，一个是当前提交索引值commitIndex,一个是目前数据的最后一行索引值lastAppliedIndex，它表示最后一个应用到状态机的log序号。
leader节点除了需要存储自身节点的commitIndex和lastAppliedIndex之外，还需要知道每个follower的情况。因此,leader多了一张表，这张表记录了所有follower 的存储情况。表有两个属性，一个是nextIndex，每个follower维护一个nextIndex，表示leaderer给每一个follower发送的下一条日志项的索引。另一个是matchIndex记录的是leaderer已知的follower节点的数据。
Q4面试官：换成新主后如何日志达到一致
A4我：首先，leader通过发送日志复制RPC的一致性检查找到follower与自己相同日志项的最大索引值。
然后，leader强制复制follower更新覆盖的不一致日志项。
leader给follower发送日志复制信息中带着(PrevLogTerm， PrevLogEntry)。PrevLogEntry表示当前复制日志项前一条的索引值。
lPrevLogTerm表示当前要复制的日志项前面一条的任期编号。
比如，下图中leader将索引值为8的日志项发送给follower，那么PrevLogTerm值为4，PrevLogEntry为7。

文章图片

leader通过日志复制RPC消息发送当前日志项到follower。比如上图PrevLogEntry值为7，PrevLogTerm值为4。
如果follower在它的日志中，找不到与PrevLogEntry为7，PrecvLogTerm值为4的日志项表示它和leader的日志文件不一致了，那么follower拒绝接受新的日志项，并返回失败信息给leader。
leader递减要复制的日志项的索引值，并发送日志项到follower，既值为（6,3）的日志项。
如果follower在它的日志中找到了PrevLogEntry值为6，PrevLogTerm值为3的日志项，日志复制RPC返回成功，这样leader就知道在PrevLogEntry值为6，PrevLogTerm值为3的位置，follower和leader的日志项相同。
【分布式存储|阿里技面之raft如何选主】leader发送日志复制RPC消息给follower，follower复制并覆盖该索引之后的日志项，最终实现了集群各节点日志的一致。