PaxosLease算法实现——用于Paxos自身选主

这篇文章主要是说明一下PaxosLease的算法,主要是参考了:http://dsdoc.net/paxoslease/index.html

在Paxos中,如果能够选举出一个leader(在Lamport的论文中称之为总统),那么有助于提高投票的成功率。另外这个leader在多个决议的选举中有很重要的作用(要靠他得到决议的连续id)。因此,如何通过某种方法得到一个leader就是PaxosLease所说明的。

首先先说下小秦一开始在思考这个问题上的几个思路以及其中的问题,所有的思考都按照有A、B、C三个主机为前提。

考虑最简单的方法:A、B、C互相发送各自的主机名给所有的主机,所有的主机选取主机名最大的为leader。这里有一个潜在问题:如果B收到了来自A的消息,C收到了来自A的消息,但是B和C没有收到各自的消息,那么B和C就不知道自己是不是主机名最大的主机了。

再来换个思路,既然Paxos可以用于选举某个决议,那么选取一个“我是leader”的主机就行了,这里的“我”指的是投票者的主机名。于是在一开始的时候,大家发起了Paxos的投票,投票结果是“A是leader”。A称为了leader。但是某个时候A宕机了,这个时候B和C再次投票的时候,由于Paxos的强一致性,每次结果依然是“A是leader”。所以在leader宕机的时候,Paxos就没用了。

还有一种思路,比如A、B、C在每次选举leader的时候,都是独立的Paxos实例来选举。实例的id可以认为是时间,如按照小时为单位,第一次是2014022314,第二次是2014022315,每个主机在每个小时的30分发起一次选举,这样每次都能选举出leader,即便leader宕机,下次选举的时候剩余的两台主机依旧可以在下一次Paxos实例选举的时候选出新的leader。但这里有个问题,这个算法要求一个ledaer宕机后要可能要等待一个小时才会有新的leader产生。如果我们缩小单位,比如按照分钟来进行id的编号,那么不同的主机可能存在时钟的误差,这样就会有问题。

现在我们来看下PaxosLease算法,它是基于Paxos的,类似于上面提到的第二个思路,但是他引入了超时时间T。算法流程如下(摘抄自上面的链接):

1.一个请求者想要获得租约,时长 T < M 。它生成投票编号 [request.ballotNumber],然后发送准备请求给多数派的接受者。 2.接受者,当收到准备请求时,检查 [request.ballotNumber] 是否高于自己在 [state.highestPromised] 里承诺的本地投票编号中的最大值。如果提议请求的投票编号更低则可以丢弃这个消息,或者发送一个响应结果是 拒绝 的准备响应。如果相等或者更高,接受者用 接受 的回答构造一个准备响应,回答中有当前已接受的提案 [state.acceptedProposal] ,提案可以为空。接受者设置已承诺的最高投票编号 [state.highestPromised] 为 请求消息的投票编号 [request.ballotNumber] ,然后把这个准备响应发回给请求者。 3.请求者检查从接受者过来的准备响应。如果有多数派的接受者响应的是空的提案,意味着他们可以接受新的提案,请求者可以提交它自己作为租约的获得者,时长是 T 。请求者启动一个定时器,过期时间是 T 秒,发送提议请求,其中包含了投票编号 和 租约(它自己的 请求者id 和 T )。 4.接受者,当收到提议请求时,检查投票编号 [request.ballotNumber] 是否高于自己在 [state.highestPromised] 里承诺的本地投票编号中的最大值。如果提议请求的投票编号更低则可以丢弃这个消息,或者发送一个响应结果是 拒绝 的提议响应。如果相等或者更高,接受者接受这个提议:启动过期时间T的超时计时,设置它已接受的提案为这个收到的提案(如果还存着前一个提案,丢弃掉)。接受者用 接受 的回答构造一个提议响应,回答中有投票编号 [request.ballotNumber] 。在超时过期后,接受者重置它已接受的提案为 空 。接受者决不重置它的已承诺的最高投票编号,除非在重启的时候。 5.请求者检查提议响应消息。如果有多数派的接受者响应了接受提案,则这个请求者获得了租约直到本地的定时器超时(在第3步中启动)。它收到多数派消息的最后一条的时间点就是它获得租约的时间点,可以切换它的内部状态到“我持有租约”。

其实最简单的理解就是在Lamport的Paxos论文中提到的那个示例表格中的每个框(或者勾、投票)加个超时时间,在超时时间过了后,自动的变为空(或者叉、不投票)。上面第二个思路的‘但是某个时候A宕机了,这个时候B和C再次投票的时候,由于Paxos的强一致性,每次结果依然是“A是leader”。’这个问题,如果在A宕机后经过足够长的时间,Paxos中的一致性的投票的赞成票的状态会在超时后变成不投票,最终会的出现一致性结果依旧没有被选举的情况,此时B和C继续提出投票申请的时候算法就能继续下去了。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*