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*算法等。当然 ...