Paxos 算法是一种提高分布式系统系统容错性的一致性算法 。对于一个一致性算法 有以下特点:
- 在所有被提出的提案中,只有一个会被选定。
- 如果没有提案被选出,就不会有选定的提案。
- 当一个提案被选定后,所有的节点进程都可以获取到被选定的提案信息。
- 一旦 “接受者” 接受了提议,就不能再接受其他提议内容。
算法过程
在该一致性算法中有三种参与角色。分别为 “提议者(Proposer 向 “接受者” 提出提案)”、“接受者(Acceptor 收到 “提议者” 的提议后,向提议者表达自己的意见)”、“学习者(Learner 天被确定后,学习者获取被确定的提议)”
- 第一阶段:因为存在多个 “提议者” ,如果都提出提案,那么 “接受者” 接受谁的不接受谁的?太混乱了。所以要先明确具有领袖权的提议者才有权提出提案。所以规定一些有领导权力的 “提案者” 可以提出提案。 “接受者” 们就主要去处理这个 “提案者” 的提案了。(这样,才可以在提案提出时就尽量让意见统一,谋求尽早形成多数派)。
- 第二阶段:由以上阶段选出来的主 “提议者” 提出提案,“接受者” 反馈意见。如果多数 “接受者” 接受了一个提案(达到半数以上),那么提案就通过了。
提案者选定与意见处理
- 怎么明确意见领袖呢?通过编号。每个“提议者”在第一阶段先报个号,谁的号大,谁就是意见领袖。如果不好理解,可以想象为贿选。每个提议者先拿着钞票贿赂一圈“接受者”,谁给的钱多,第二阶段“接受者”就听谁的。(注:这里和下文提到的“意见领袖”,并不是一个新的角色,而是代表在那一轮贿赂成功的“提议者”。所以,请把意见领袖理解为贿赂中胜出的“提议者”即可)。
- 有个跟选举常识不一样的地方,就是每个 “提案者” 不会执着让自己的提案通过,而是每个 “提案者” 会执着于让提议尽快达成一致意见。所以为了这个目标,如果 “提案者” 在贿赂的时候发现 “接受者” 已经接受了前面意见领袖的提议,即便 “提议者” 贿赂成功,也会默默地把自己提案修改成前面意见领袖的提议(这样就会更快的达到多数派)。
- 钱的多少很重要,若果钱少了,无论第一还是第二阶段 “接受者” 都不会接受,直接拒绝。
- 上面 2 中提到如果 “提案者” 在贿赂的时候发现前面已经有意见领袖的提议,那就将自己的提议默默地改成意见领袖的提议。但是这里有一种情况,如果你是 “提议者” ,在贿赂的时候, “接受者n” 回复你说 “他收到的意见领袖的提案是 方案 n ”,而 “接受者 n + 1” 回复你说 “他收到的意见领袖提议的方案是 n + 1”。这时候我们该怎么办。原则很简单,还是: “钱的多少重要!”,你就判断下 “是接受者 n ” 见过的意见领袖有钱还是 “接受者 n + 1” 见过的领袖提议者有钱。你就把自己的提议改成意见领袖钱多的那个 提议。
- 在整个选举过程中,每个提案者谁先来后到,“接受者” 什么时候收到 “提案者” 的提议是完全不可控的。所以有可能一个意见领袖已经产生了,但是由于这个意见领袖的第二阶段才刚刚开始,很多 “接受者” 还没有收到这个意见领袖的提案。这时候突然来了一个新的土豪 “提案者” ,那么这个土豪也是有可能让自己提案胜出。会出现这样的博弈现象:
- 上一个意见领袖要赶在土豪 “提案者” 贿赂到 “接受者” 前接受自己的提案,否则会因为自己之前贿赂的钱少于土豪被拒绝。
- 土豪 “提案者” 要赶在上一个意见领袖者将提议传达给 “接受者” 前贿赂到 “接受者”,否则土豪 “提议者” 基石贿赂成功,也要默默地将自己的提议改成前任领袖的提议内容。不管怎么样,最终先得到多数 “接受者” 的认可,那么这个提议就胜出了。
总结
- Paxos 算法包括两个阶段:第一阶段主要就是贿赂,还没有提出提议;第二个阶段就是根据第一阶段的结果,明确接受谁的提议,并且明确提议的内容(这个提议可能是贿赂选取胜出的 “提案者” 自己的提议,也可能是前任意见领袖的提议)。
- 编号(贿赂金额大小)很重要,无论哪个阶段,编号小的都会被拒绝。
- 在第一阶段中,一旦 “接受者” 已经接受了前面的意见领袖的提议,后面再来找这个 “接受者” 的 “提议者” ,即便是贿赂胜出,也要老实的把自己的提案内容改成前面领袖提议的内容,这点尤为重要。接着这个 “提案者” 也会在第二阶段提出改变后的提议(为了一件快速达成一致)。如果 “接受者” 之前没有接收过任何提议,那贿赂成功的 “提议者” 就可以提出自己的提议了。
简单示例说明
有两个 “提案者” 和三个 “接受者”
- 首先 “提案者1” 贿赂了 3个 “接受者”。也就是第一阶段
2. 三个 “接受者” 记下贿赂的金额大小,目前只有一个 “提案者” 出价贿赂,因此 $1就是最高的,所以 3 个 “接受者” 返回 “提案者1” 贿赂成功。另外,因为没有任何先前的意见领袖提出提议,因此 “接受者” 们告诉 “提案者1” 之前没有接受过提议,自然也就没有上一个意见领袖贿赂金额了。
3. “提案者1” 准备执行第二阶段: 向 “接受者1” 提出了自己的提议:内容为 1 号提议,并告诉自己之前贿赂的金额$1。
4. “接受者1” 检查了下,目前贿赂的金额就是 $1,于是就接受了 这个提议,并且把 1号提议的内容记录在案。
5. 在 “提议者1” 向 “接受者2”、“接受者3” 发起提议之前,土豪 “提议者2” 出现了,他开始使用 $2贿赂 “接受者1“ 和 “接受者2”。
6. “接受者1” 和 “接受者2” 就被土豪 “提议者2” 收买了,将贿赂金额改成了 $2,但是,不同的是 “接受者1” 告诉响应 “提案者2” ,之前已经接受过 “提案者1” 提出的1号提议了。而 “接受者2” 告诉 “提案者2” 之前没有收到过其他领袖的提议。
7. 这时候 “提案者1” 回神了,他向 “接受者2” 和 “接受者3” 发起 1号内容提议,并且携带之前贿赂过金额 $1的信息。
8. “接受者2” 和 “接受者3” 开始回复:“接受者2” 检查了下自己记录的金额$2,然后便是已经有人出价 $2了,而你之前出的$1,不再接受你的提议。但是 “接受者3” 检查了自己记录的贿赂金额就是$1,于是就接受了这个提议内容,并且把1号提议记录在案。
9. 到这里,“提案者1” 已经获得了两个接受者的赞同,达到了 半数通过的场景。于是 “提案者1” 确定了一号提议内容最终通过。
10. 我们再回到 “提案者2” ,之前贿赂了 “接受者1” 和 “接受者2”,并且被 “接受者1” 告知: “之前已经接受过一号提议了,并且最高金额是$1”。这个时候 “提案者2” 拿到信息后判断一下,目前就是1号提议内容,就默默地把自己的提议内容改成了 1号。然后向 “接受者1” 和 “接受者2” 发起提议,提议内容已经变成 1号。并且携带信息之前已经贿赂过金额 $2。
11. “接受者1” 和 “接受者2” 收到 “提案者2” 的提议后,继续按照之前流程 对比下贿赂金额,记录的是之前贿赂的金额 $2,所以就接受了提议,其实就是 “提案者1” 提出的内容。就这样最终1号提议内容通过。