Raft协议

Raft协议是比paxos协议更容易理解和实现的一种一致性协议。http://thesecretlivesofdata.com/raft/   这个网址动态演示了Raft协议的整个过程。

1:Raft是一个可被理解接受的分布式一致性协议。

 2:什么是分布式一致性协议呢?以一个例子为例

 

 3:假设有一个单节点系统

 

 

4:假设这个节点是个数据库服务器,只存储了一个数据。

 

 5:假设存储的数据是 X

 

 

6: 现在有个客户端可以向这个server发送数据

7:向server端发送了修改数据的请求

 8:在一个节点上,很容易做到数据一致性。

 9:如果有多个节点,又如何让数据保持一致性呢。这就是分布式一致性的问题。

 

 

 10:Raft是一种用于实现分布式一致性的协议。

 

 

 

11:让我们从总体上看一下它是如何工作的。一个节点的状态分为三种:Follower,Candidate,Leader

 

 

 

 12:所有的节点刚开始都是follower的状态。

 

 13:如果follower状态的节点,没有接收到来自leader的信息,那么这个节点就可以变成candidate状态

 

 14:候选者节点会向其他节点发送投票请求。

15:候选者如果得到了大多数节点的投票,这个候选者就变成了leader。

 

 上述过程被称为Leader选举过程。

 

 

 

当leader选举出来之后,对于当前系统的所有写操作都通过leader来完成。如果有客户端请求到follower节点,也会转到leader来。

16:每次的变更,都会在节点上的日志中新增一条记录。

 

 17:这条日志记录当前还是未提交的状态,所以还没有真正的更新节点上的值。

 

 18:leader节点为了提交这条记录,首先把它复制到其它follower节点上去。

 

19:leader节点等待大多数follower节点将这条变更记录写入成功并返回。

 

20:到这里,这条变更记录在leader节点才处于提交状态,节点的状态记录为 “5”,写入内存成功。

21:leader节点通知其他follower节点变更记录进行提交。

 

22:当前集群现在对于系统状态而言已经达到了一致性。实际上通过了两个阶段提交uncommit,commit.

 

 上述过程称为日志复制

我们下面详细看下leader的选举过程

23:在Raft协议中有两个超时时间的设置来控制选举。

 

24:第一个是选举超时时间。

 

 

 25:这个选举超时时间是指follower等待变成candidate的时间。

 

 

 26:这个选举超时时间是150ms~300ms之间的随机值。

 

 

 

27:每个节点在election time 内自我选举成candidate,然后开始新一轮的选举投票。候选者会发送投票请求给其他节点,让其他节点投票给自己称为leader。

 

 

 

 

 

28:如果接收到请求的节点在当前周期内还没有进行过投票,那么它就会投票给当前这个candidate。然后receiving节点会重置选举超时时间。一旦candidate接收到大多数节点的投票,它就会变成leader。

 

 

 29:leader 开始向其他follower发送 追加变更记录的信息.

 

 

 30:  这些消息按心跳超时时间作为时间间隔发送到其他节点。

 

 31:follower们也会给每一个消息进行响应。

 

 

 32:直到一个follower停止接收leader发送过来的心跳并变成candidate之后这个选举过程才算结束。注意!follower和leader通信过程中,自我选举也一直都在,只是每次收到leader的心跳之后就被重置了。

         这也是后面leader挂了之后,马上开始election的原因。

 

 33:接下来看下把lader停掉,集群是怎么重新选举的。

34:假设B 原来是leader,突然挂了,也就没法向其他follower节点发送心跳了,正如32步骤中说的那样,另外两个节点一直在进行election term,下图是A节点首先成为了candidate,然后发送投票请求给C,C响应成功,

       A节点就变成了leader。

 

35:下面我们看下投票发生分裂的情况,当集群中投票有多个follower节点同时变成candidate。下面第二个图,A,C节点同时变成candidate,并向其他节点发送vote请求。

 

36:这两个进行election 的节点都收到了两个节点的投票。

 

 

 

 37:两个候选者得到的票数一样,开始下一个周期的投票。

 

等下个周期开始A,C看那个节点先发起投票。最后A得到了大多数票数。

 

 

下面详细说明下  Log Replication的过程

   38:一旦选定了一个leader之后,我们需要复制所有的变更记录到系统的所有节点。

 

 39:复制的这个过程靠leader和follower之间心跳来维持的。

 

 40:过程如下:

1:一个客户端过来向leadeer发送一条信息,新增了5这条数据,在leader这边先写入本地日志set 5。

2: 下次心跳的时候,leader带着这条set 5日志操作向其他follower发送请求。

3:当集群中大多数follower节点ack的时候,leader节点才将这条记录进行commit比如写入磁盘落地等。

4:响应客户端。

41:在上面的基础上增加2的过程如下。

 

Raft协议还可以保证在发生分区的情况下保持系统一致性。

 

 42:假设五个节点发生了分区,其中A,B是一个区的,C,D,E是一个区的

 

 43:分区一单发生C,D,E集群就会开始election term ,假设C节点变成了第二个leader。

 

 

 

 

44: 假设有个客户端来请求B节点进行set 3,但是由于分区的原因B节点不能复制这条变更记录到大多数的节点,所以这条记录一直处于uncommit的状态,也不能给客户端进行响应。

 

 45:假设另外一个分区有一个客户端来进行连接在C节点操作set 8操作,由于C可以复制到大多数节点,所以这个set 8的操作是会成功的。

 

 46:当分区的问题解决之后,B节点会发现比它更高级的election term 也就是C,B就会主动放弃leader成功follower。并且,A,B节点上处于uncommit的记录也会回滚掉,接收新leader发来的log。

 

 

 

 

这样这个集群之间的节点也就处于一致了。

 

对于GIS业务来说,路径规划是非常基础的一个业务,一般公司如果处理,都会直接选择调用已经成熟的第三方的接口,比如高德、百度等。当然其实路径规划的算法非常多,像比较著名的Dijkstra、A*算法等。当然 ...