Paxos算法
0x00 简介
- 优点：Paxos算法是基于消息传递且具有 高度容错性质 的一种算法，在分布式领域中有非常重要的地位。
- 缺点：工程上难以实现，因此有许多延伸算法，比如Raft。局限于 不存在恶意（corrupt）节点 的系统（即消息可能丢失或者重复，但是无错误消息）。
0x01 主要成分
在Paxos算法中有三个主要的成分：
- Proposer（提案者）—— 提出 准备请求（Prepare） 和 __提案（Proposal）__，其中 提案（Proposal） 等待大家的批准。且每个提案自带一个 __递增的提案号__。一般由客户端担任角色。
- Acceptor（接受者）—— 对 准备请求（Prepare） 和 提案（Proposal） 做出 __响应（Response）__。负责对提案进行投票，接受提案。一般由服务端担任。
- Learner（学习者）—— 获取批准结果，并帮忙传播。客户端和服务端都可担任。
以下规定：
- 一般情况下，每个节点都可以担任多个角色。为了简便起见，这里假设每个成分对应一个节点。
- 每个准备请求包含一个提案号N，记作
P(N)。 - 每个提案包含两个部分：提案号number、提案value。提案记作
P<N, V>。 - Response分为两种，一种是“已经接受过的编号小于N的最大编号”，响应格式记作
R<AcceptN, AcceptV>或者R<null, null>；另一种是error，记作R<error>。
0x02 成分的行为
0x020 Proposer（提案者）
- Proposer提出提案前，首先需要去“学习”已经被钦定或者选定的value。因此需要向半数以上的Acceptor发出P(N)。
- 如果Proposer收到半数以上Acceptor的相应，那么他会选择跟随收到的响应中提案号最大的提案，并向超过半数的Acceptor（不一定是之前的那一批）发出自己的提案。如果所有的响应都为null，那么提出自己的value。
- 若收到的响应未超过半数，则重新发送Prepare请求。
0x021 Acceptor（接受者）
接收者需要记下两个值：1. 已接受的编号最大的提案 <AcceptN, AcceptV>；2. 已响应的请求的最大提案号 ResN。
- 收到 准备请求（Prepare）
- N <= ResN，不响应或者响应
R<error>。 - N > ResN，令ResN = N，响应
R<Pok, AcceptN, AcceptV>或R<Pok, null, null>。
- 收到 提案（Proposal）
- N <= ResN，不响应或者响应
R<error>，不接受此提案。 - N > ResN，接受提案，响应
R<Aok>.
0x022 Learner（学习者）
Learner有三种方案获取value
| 方案一 | 方案二 | 方案三 |
|---|---|---|
| Accepter 接受一个提案就将该提案发给所有的Learner | Accepter 接受一个提案就将该提案发给主Learner，再由主Learner通知其他Learners | Accepter 接受一个提案就将该提案发给一个Learner集合，集合通知集合 |
| Pro：简单 | 通信次数少 | 集合中的Learner越多，可靠性越好 |
| Con：通信次数多 | 主Learner宕机药丸 | 网络复杂 |
0x03 算法流程
0x04 死循环
这样一个场景，两个Proposer争相发出编号依次递增的提案，那么Acceptor将一直无法钦定。最终成为死循环。
解决方案，考虑选取 __leader Proposer__，仅允许leader提出提案。这样一定程度上可以避免死循环的发生。这就是Raft算法的基本思想。
0x05 Raft算法
第一次看完Raft算法，感觉这和自然界种群领袖的诞生方式不谋而合啊！毕竟对羊群、牛群以及个体数量更为众多鱼群来说，没有一种合理的选Leader的方法是很危险的。
Raft算法的核心就是每个节点都能成为 Follower 、 Candidate 或者 Leader 之一，所有的节点由算法选举一个Leader来向其他节点发送命令（选举Leader的好处是能简化同步的复杂性）。其中每个未成为 Leader 的节点都在伺机成为 Candidate 甚至成为新的 __Leader__，就像动物界争夺首领一般。
- Follower —— 首先，所有的节点默认都是 __Follower__，每个节点都有一个计时器，并随机生成范围在150ms到300ms的倒计时。由于随机性，一般情况下只有一个节点率先完成倒计时。
- Candidate —— 完成倒计时的Folloer将升级成为 Candidate ，并立即向其他节点发送投票请求（Requests Votes）。收到 Follower 投票（Votes）的 Candidate 升级成为 __Leader__。
- Leader —— 成为 Leader 以后就会向其他节点发送心跳包（Heart Beats）和数据，以保证整个网络的数据一致。
Raft算法有 个基本过程
推荐一个良心网站，内容充实而生动：Raft——Understandable Distributed Consensus