Paxos 有点类似我们之前说的 2PC，3PC，但是解决了他们俩的各种硬伤。该算法在很多大厂都得到了工程实践，比如阿里的 OceanBase 的分布式数据库，底层就是使用的 paxos 算法。再比如 Google 的 chubby 分布式锁也是用的这个算法。可见该算法在分布式系统中的地位，甚至于，paxos 就是分布式一致性的代名词。
Paxos 角色
在paxos算法中，分为4种角色：
- Proposer ：信使
- Acceptor：决策者
- Client：产生议题者
- Learner：最终决策学习者
不过为了方便理解，我们将Proposer摘取出来作为算法的主角，其他三者为配角。
Paxos 举例说明
在 Paxos 岛上，有A1, A2, A3, A4, A5 5位议员，就税率问题进行决议，决议结果由少数服从多数来决定。
我们假设几个场景来解释：
场景 1.
（暂且不考虑信使，即不考虑分布式网络问题）
A1 说：税率应该是 10%。而此时只有他一个人提这个建议。如下图：
很完美，没有任何人和他竞争提案，他的这个提案毫无阻挠的通过了。A2 - A5 都会回应他：我们收到了你的提案，等待最终的批准。而 A1 在收到 2 份回复后（加上A1自己，表决结果过半），就可以发布最终的决议：税率定位 10%，不用再讨论了。
场景 2.
现在我们假设在 A1 提出 10% 税率提案的同时, A5 决定将税率定为 20%，如果这个提案要通过侍从送到其他议员的案头，A1 的草案将由 4 位侍从送到 A2-A5 那里。但是侍从不靠谱（代表分布式环境不靠谱），负责 A2 和 A3 的侍从顺利送达，而负责 A4 和 A5 的侍从则开溜了！而 A5 的草案则送到了 A4 和 A3 的手中。
现在，A1 ，A2，A3 收到了 A1 的提案，A3，A4， A5 收到 A5 的提案，按照 Paxos 的协议，A1，A2，A4，A5 4个侍从将接受他们的提案，侍从拿着回复：我已收到你的提案，等待最终批准 回到提案者那里。
而 A3 的行为将决定批准哪一个。当 A3 同时收到了 A1 和 A5 的请求，该如何抉择呢？不同的抉择将会导致不同的结果。
场景 2. 抉择1.
假设 A1 的提案先送到 A3 那里，并且 A3 接受了该提案并回复了侍从。这样，A1 加上 A2 加上 A3，构成了多数派，成功确定了税率为 10%。 而 A5 的侍从由于路上喝酒喝多了，晚到了一天，等他到了，税率已经确定了（决策已经成型），A3 回复 A5：兄弟，你来的太晚了，税率已经定好了，不用折腾了，听 A1 的吧。
场景 2. 抉择2.
依然假设 A1 的提案先送到 A3 处，但是这次 A5 的侍从不是放假了，只是中途耽搁了一会。这次, A3 依然会将"接受"回复给 A1 .但是在决议成型之前它又收到了 A5 的提案。这时协议根据 A5 的身份地位有两种处理方式。
- 当 A5 地位很高，例如 CEO，就回复 A5：我已收到您的提案，等待最终批准，但是您之前有人提出将税率定为10%,请明察。
- 当 A5 没地位，普通码农一个，直接不回复。等待 A1 广播：税率定为 10% 啦！！
场景 2. 抉择3.
在这个情况中，我们将看见，根据提案的时间及提案者的权势决定是否应答是有意义的。在这里，时间和提案者的权势就构成了给提案编号的依据。这样的编号符合"任何两个提案之间构成偏序"的要求。
A1 和 A5 同样提出上述提案，这时 A1 可以正常联系 A2 和 A3，A5 也可以正常联系这两个人。这次 A2 先收到 A1 的提案; A3 则先收到 A5 的提案。而 A5 更有地位。
在这种情况下，已经回答 A1 的 A2 发现有比 A1 更有权势的 A5 提出了税率 20% 的新提案，于是回复A5说：我已收到您的提案，等待最终批准。
而回复 A5 的 A3 发现新的提案者A1是个小人物，没地位不予应答。
此时，A5 得到了 A2，A3 的回复，于是 A5 说：税率定为 20%，别再讨论了。
那 A4 呢？ A4 由于睡过头了(决议已经成型)，迷迷糊糊的说：现有的税率是什么? 如果没有决定，则建议将其定为 15%.
这个时候，其他的议员就告诉他：哥们，已经定为 20% 了，别折腾了。洗洗继续睡吧。
整个过程如下图：
总结
我们可以看到Paxos算法就是少数服从多数，同时，还会根据议员的身份和提案的时间来判断是否需要应答，这个身份其实就是一个编号，是为了防止出现活性导致死循环。
Paxos 的目标：保证最终有一个提案会被选定，当提案被选定后，其他议员最终也能获取到被选定的提案。
Paxos 协议用来解决的问题可以用一句话来简化： 将所有节点都写入同一个值，且被写入后不再更改。
注意：这一切都是在没有 拜占庭将军 问题的基础上建立的，即消息不会被篡改（因为分布式大多在局域网中）。
网友评论