hashicorp raft 代码分析1 - 选举leader

Raft介绍

Raft是一种一致性算法,一致性算法的作用是将几个机器看成一个整体,即使其中的某台或者某几台机器发生故障,整个系统仍能正常工作。在Raft出现之前Paxos几乎是一致性算法的代名词。Ceph就使用Paxos算法同步各个节点的状态。虽然Raft和Paxos的作用相同,但是Raft算法更容易理解和实现,可以给学习一致性算法带来极大的方便。hashicorp的raft实现在各个开源项目中有着广泛应用,比如influxdb,consul。这里分析的代码是基于commit id: 9c733b2b

Raft只有三种节点:follower,candidate和leader。leader节点接收来自client的请求,接收到的请求以Log形式会被储存在本节点并分发到follower节点,如果整个集群中有半数以上节点已经存储了这个Log Entry,那么这个Log Entry就算提交(commit)成功了。Commit成功的Log Entry会被Apply到一个FSM(有限状态机)。FSM的任何一个状态都能通过Apply之前所有的Log Entry而获得,所以即便有节点因为故障而离开集群一段时间,在这个节点恢复时可以Apply它缺失的Log Entry而重新与其他节点保持一致。如果无限制保存Log Entry会需要无限大的磁盘空间,Raft提供Snapshot机制解决这个问题。Snapshot将当前FSM中需要保护的状态保存下来,然后删除这个状态之前的Log Entry,如果出现follower短暂故障而恢复,leader只需要先让follower install leader的最新snapshot,然后再将这个snapshot之后的Log Entry发送给这个follower就可以使其状态与leader保持一致。

完整的Raft协议可以查看这里

选举Leader过程

Raft集群中leader负责接收客户端发来的请求并把这些请求保存和分发到follower,作用至关重要,是集群和外界通信的唯一节点。各个Raft节点通过投票选出leader,每个节点在一个Term中只能投一票,获得半数以上票数的node胜出。这也意味着一个集群中最好有奇数个node。下图为集群启动后的选举过程。

+----1----+      +-----2-----+      +----3-----+
| Follower|      | Follower  |      | Follower |
+---------+      +-----------+      +----------+
                       | (A)
+----1----+      +-----2-----+      +----3-----+
|         |<-(B)-|           |-(B)->|          |
| Follower|      | Candidate |      | Follower |
|         |-(C)->|           |<-(C)-|          |
+---------+      +-----------+      +----------+
                       |(D)
+----1----+       +----2-----+      +----3-----+
|         |<-(E)--|          |-(E)->|          |
| Follower|       |  Leader  |      | Follower |
|         |-(F)-->|          |<-(F)-|          |
+---------+       +----------+      +----------+
  • 系统启动时node 1,2,3都是follower。
  • A: node 2的计时器第一个timeout,因为系统现在没有leader所以node 2在设置时间内没有跟其他节点通讯过。node 2将自己的角色变成Candidate。
  • B: node 2首先将自己的Term加1,并且给自己投上一票,然后将这个Term 放到RequestVote的RPC请求中,发送给node 1和node 3。
  • C: node 1和node 3收到RPC请求后,检查以下几个条件是否都成立,如果是那么他们就可以把自己的一票投给node 2,并且更新自己的Term为最新值。
    • C.1 自己没有leader。
    • C.2 自己当前Term小于收到的RPC Term。
    • C.3 在这个Term中没有把票投给其他node。
    • C.4 自己的Index小于RPC请求中的Index。
  • D: node 2根据步骤C中的response检查自己的得票总数,如果超过半数就把自己的角色变成Leader。(如果在规定时间内没有得到足够票数的话,则启动新一轮投票。)
  • E: node 2成为Leader后开始发送AppendEtries RPC给node 1和node 3。
  • F: node 1和node 3接收到AppendEtries后记录node 2为最新的leader,返回RPC response给node 2。

这个过程中大家可能会有疑问启动过程中会不会出现几个node同时变成Candidate呢?这种情况是可能的,但是很少发生。因为从follower到candidat的时间是由两部分相加组成的,1. 一个可以设置的固定时间, 2. 一个随机时间。由于第二部部分的存在同时变成candidate的可能性很小。当然这也不代表着不可能,如果candidate在等待时间内无法得到足够的票数就会进入下一轮投票。由于candidate等待投票结果的时间也是由一个固定时间和一个随机时间相加而得,所以同一时间内进入下一轮投票的可能性也很小。这两个时间可以保证Raft集群可以很快选举出一个Leader。

选举Leader的代码流程

raft.Raft是这个库的主要数据结构记录着raft的各个节点,自己当前状态等。raft.Raft创建过程中会启动三个主要的后台go routines,分别是

  • run: 根据自己的角色(Leader, Candidate, Follower)执行对应的操作。
  • runFSM: 调用FSM接口
  • runSnapshots: 执行快照操作

选举Leader主要集中在(*Raft).run中。三种角色分别对应函数(*Raft).runFollower,(*Raft).runCandidate,(*Raft).runLeader。

三种角色共用一个(*Raft).processRPC函数用于处理RPC,RPC就三种类型:Raft.AppendEntriesRequest, Raft.RequestVoteRequest, Raft.InstallSnapshotRequest。选举Leader过程会使用前两个RPC请求。下面简单介绍RPC的调用流程。

RPC调用流程

RPC调用的过程如下图所示。

+-------------------Node 1 (Leader)---------------+   +--------------------Node 2-------------------------+
|+--------------+            +--------------+     |   |  +--------------+            +--------------+     |
||Raft          |            |Network       |     |   |  |Network       |            |Raft          |     |
||              |            |Transform     |     |   |  |Transform     |            |              |     |
||              |            |              |     |   |  |  +-----------|            |------+       |     |
||              |---RPC----->|              |-----+---+->|  |consumeCh  |---RPC----->|rpcCh |       |     |
||              |            |              |<----+---+--|  +-----------|            |------+       |     |
||              |            |              |     |   |  |              |            |---------+    |     |
||              |<-Respond---|              |     |   |  |              |<-Respond---|         |    |     |
||              |            |              |     |   |  |              |            |---------+    |     |
|+--------------+            +--------------+     |   |  +--------------+            +--------------+     |
+-------------------------------------------------+   +---------------------------------------------------+

Node1(Leader)要发送一个AppendEtries RPC给node 2需要经过如下步骤。

  • Node 1的Raft构造一个raft.AppendEtriesRequest,通过Transform.AppendEntries传递给Transform。
  • Transform定义了传输层的接口,比如AppendEntries就是接口的一部分。raft.NetworkTransport是基于网络传输的Transform实现。
  • 传输层将RPC请求编码后通过网络将RPC请求发送给Node 2的传输层。
  • Node 2的传输层将RPC请求放入consumeCh(在Raft中这个channel的变量名为rpcCh)channel中。
  • Node 2的Raft从rpcCh channel中取出请求,处理后调用(*RPC).Respond将请求返回给Node 2的传输层。
  • RPC的response最终返回到Node 1的raft.Raft。

总结

本文是Hashicorp raft协议实现分析的第一部分,主要分析了Raft集群中Leader的选举,还简单介绍了RPC的调用过程。

comments powered by Disqus