分布式选举算法图文剖析

分布式选举算法图文剖析

🗨

1.概述

  我们在了解分布式选举算法之前,我们需要这样一种算法产生的背景。在一个分布式系统中,因为各种意外的因素,有的服务器可能会崩溃或变得不可靠,它就不能和其他服务器达成一致状态。因而这样就需要一种Consensus协议,来确保服务器的容错性,也就是说即使系统中有一两个服务器节点Crash,也不会影响其处理过程。为了让容错方式达成一致,我们不可能要求所有的服务器节点100%都达成Consensus状态,只要超过半数的大多数服务器节点Consensus即可,假设有N台服务器节点,(N/2)+1 就超过半数,即可代表大多数了。那么,今天笔者给大家分享的就是Raft分布式选举算法。

2.内容

  Raft为了实现Consensus这个目标,这个过程如果选举一样,参选者需要说服大多数服务器节点投票给他,一旦选定后就跟随其操作。在Raft中,任何时候一个服务器节点可以扮演下面角色之一:

  1. Leader:处理所有客户端交互,日志复制等操作,一般一次只有一个Leader。
  2. Follower:类似选民,处于被动状态。
  3. Candidate:类似Proposer,可以被选为一个新的Leader。

  Raft阶段分为两个,首先是选举过程,然后在选举出来的Leader带领下进行相关正常的操作,比如复制等。下面有相关示意图来展示该过程:

2.1 选举请求

  任何一个服务器节点都可以成为一个Candidate,它向其他服务器节点Follower发出要求选举自己的请求,如下图所示:

2.2 应答

  其他服务器应答同意,发出OK。如下图所示:

  需要注意的是,如果在这个过程当中,有一个FollowerCrash掉,没有收到请求选举的要求,因此候选者可以自己选举自己,只要达到 (N/2)+1 的大多数票,候选人还是可以成为Leader的。

2.3 发送指令

  在候选者成为Leader后,它可以向其他Follower节点发送指令,比如进行日志复制,如下图所示:

2.4 Heartbeats

  之后,通过心跳进行日志复制等通知,如下所示:

2.5 Crash

  在运行的过程当中,一旦该集群的Leader当场Crash了,那么Follower中有一个成为候选者,发出投票选举邀请,如下图所示:

2.6 New Leader

  在Follower同意后,其成为Leader,继续承担日志复制等操作动作,如下图所示:

  这里需要注意的是,在整个选举过程当中是有一个时间限制的,如下图所示:

  出现在Split Note的情况,是因为如果同时有两个候选人向其他节点发出投票邀请,这时通过类似的加时赛来解决,两个候选者在一段Timeout,比如100ms互相不服气的等待后,因为双方得到的票数是一样的,一半对一半,那么在100ms后,再由这两个候选者发出投票邀请,这时同时的概率大大降低,那么首先发出邀请投票的候选者得到大多数同意票后,成为Leader,而另外的一个候选者后来发出投票邀请,那些Follower选民已经投票给了第一个候选者,此时不能再投票给它,它就成为落选者了,最后这个落选者也就成为一名普通的Follower了。

3.日志复制案例

  下面通过以日志复制为例子来说明Raft分布式选举算法,假设这里Leader已经选出,这时候客户端发出一个新增的请求,比如日志内容是"smartloli",如下所图所示:

3.1 Append

  在Leader发送的指令下,Follower需要遵循它的指令,都将这个新的日志内容追加到他们各自的日志中:

3.2 Commit

  大多数Follower服务器节点日志写入磁盘文件后,确认追加成功,发出Commited OK,如下图所示:

  再下一个心跳Heartbeats中,Leader会通知所有的Follower更新Commited。对于每个新的日志记录,重复上述操作过程。如果在这个过程当中,发生了网络通信故障,使得Leader不能访问大多数Followers了,那么Leader只能正常更新它能访问的那些Follower服务器节点,而大多数的服务器Follower因为没有了Leader,他们重新选择一个候选者作为Leader,然后这个新的Leader作为代表与外界进行交互,如果外界发送新的请求操作,比如添加新的日志,这个新的Leader就按照上述步骤通知大多数Followers服务器节点,如果这时网络故障修复了,那么原先的Leader就要降级成为Follower,在失联阶段这个老Leader的任何更新都不能算Commit,都要Roll Back,接受新的Leader的新的更新操作。

4.总结

  目前,几乎所有的语言都已经支持Raft分布式选举算法的库了。这里我们通过对分布式选举算法的学习与分析,可以对分布式系统底层选举机制有更好的理解。大家可以去阅读一下Raft算法作者写的论文。另外,Raft的作者有将论文进行整理成了大纲,阅读地址:《Raft论文大纲

5.结束语

  这篇博客就和大家分享到这里,谢谢。


频道:电脑
扫描本文章二维码可手机访问: