分布式一致性协议

gossip协议

我们的办公室八卦一般都是从一次交谈开始,只要一个人八卦一下,在有限的时间内办公室的的人都会知道该八卦的信息,这种方式也与病毒传播类似。因此 Gossip也有“病毒感染算法”、“谣言传播算法”之称。

Cassandra,amazon s3,等在使用gossip协议

一般情况是这样的,集群中的节点P随机选择另一个节点Q,两个节点互相交换信息,如果Q有消息需要更新的话,那么Q继续去集群中寻找其他的节点,再次进行信息的交换,就这样一次次的交换,知道所有的节点消息都为最新的位置.

在Q和P的信息交换,一般有以下3种方式:

  1. push:P讲信息推送给Q,Q判断是否比本地信息新,如果是的话,更新本地信息
    if P.value.time>Q..value.time
    Q..value = P.value
  2. pull: P从Q那拉取信息,如果Q的消息比P新,则更新P的消息
    if P.value.time>Q..value.time
    P.value = Q..value
  3. push-pull: P和Q同时进行Push和pull
    if P.value.time>Q..value.time
    Q..value = P.value
    else
    P.value = Q..value

push刚开始传播快,后来慢,pull相反。push-pull模式是最快的

PAXOS协议

Paxos算法分为两个阶段。具体如下:

  • 阶段一:
    (a) Proposer选择一个提案编号N,然后向半数以上的Acceptor发送编号为N的Prepare请求。
    (b) 如果一个Acceptor收到一个编号为N的Prepare请求,且N大于该Acceptor已经响应过的所有Prepare请求的编号,那么它就会将它已经接受过的编号最大的提案(如果有的话)作为响应反馈给Proposer,同时该Acceptor承诺不再接受任何编号小于N的提案。

  • 阶段二:
    (a) 如果Proposer收到半数以上Acceptor对其发出的编号为N的Prepare请求的响应,那么它就会发送一个针对[N,V]提案的Accept请求给半数以上的Acceptor。注意:V就是收到的响应中编号最大的提案的value,如果响应中不包含任何提案,那么V就由Proposer自己决定。
    (b) 如果Acceptor收到一个针对编号为N的提案的Accept请求,只要该Acceptor没有对编号大于N的Prepare请求做出过响应,它就接受该提案。

ZAB协议

设计目标

  • 一致性
  • 有序性:有序性是 Zab 协议与 Paxos 协议的一个核心区别。Zab 的有序性主要表现在两个方面:
    a. 全局有序:如果消息 a 在消息 b 之前被投递,那么在任何一台服务器,消息 a都会在消息 b 之前被投递。
    b. 因果有序:如果消息 a 在消息 b 之前发生(a 导致了 b),并被一起发送,则 a 始终在 b 之前被执行。
  • 容错性:有 2f+1 台服务器,只要有大于等于 f+1 台的服务器正常工作,就能完全正常工作。

协议内容

Zab 协议分为两大块:

  • 广播(boardcast):Zab 协议中,所有的写请求都由 leader 来处理。正常工作状态下,leader 接收请求并通过广播协议来处理。
  • 恢复(recovery):当服务初次启动,或者 leader 节点挂了,系统就会进入恢复模式,直到选出了有合法数量 follower 的新 leader,然后新 leader 负责将整个系统同步到最新状态。

raft协议

leader选举:

leader周期性地heartbeat到所有的follower。follower如果能收到leader发来的消息,那么就保持follower状态。如果follower一段时间收到不消息了,则开始新的选主。

首先当前term计数加1,然后给自己投票并向其它结点发投票请求。直到以下三种情况:

  • 它赢得选举
  • 另一个服务器成为leader
  • 持续一段时间没有主机胜出
    在选主期间,candidate可能收到来自其它自称为leader的写请求,如果该leader的term不小于candidate的当前term,那么candidate承认它是一个合法的leader并回到follower状态,否则拒绝请求。
    如果出现两个candidate得票一样多,则它们都无法获取超过半数投票。这种情况会持续到超时。然后进行新一轮的选举。
    使用随机的选举超时,这样不容易发生上面情况。

日志复制

leader收到client写请求后,先写自己的log,然后发到所有服务器,当确认记录已安全复制后,回应client。 每条日志记录会存命令以及term编号,term编号用于检测日志的不一致。
每个提交的记录都是持久的,并且是最终一致的。当log记录成功复投票请求中包含了这个限制:请求中有关于candidate的log信息制到大多数服务器时,记录被提交。如果投票者的log比它新,则拒绝请求。
冲突解决,leader通过强制follower复制自己的log来处理不一致。

安全

举个例子,一个follower可能一段时间不可用,期间leader持续提交了多次log,然后这个follower被选为leader了,那么它会覆盖掉提交的记录。
所以要限制哪些服务器可以被选为leader。使用投票过程阻止candidate选举中获胜,除非它的log包含了所有已提交的记录。
因为要获得超过半数的投票,那么candidate至少要跟大多数的log一样新。这样它拥有所有提交的记录。投票请求中包含了这个限制:请求中有关于candidate的log信息,如果投票者的log比它新,则拒绝请求。
如果follower或candidate崩溃了,那么发给它的请求会失败,raft将无限次的重试。当它恢复后,会继续收到未完成的请求。如果一个服务器完成了请求但尚未回复,接着crash了,那么它重启后会收到相同的请求。

Loading Disqus comments...
Table of Contents