分布式一致性协议——Paxos 算法

提议 ProposalPID = 0

居民（Islander）

初次搭建集群

PID 与公共PID相同

议员（Senator）

PID = 0S1:PID = 1

PID = 0PID = 1

无主模型——活锁——当有两个 Proposer 依次提出了一系列编号递增的提案，此时就会导致陷入死循环

PID = 0S6:PID = 1

Paxos 小岛（Island）

议员总数Senator Count = 5

投票

Paxos 算法

朝代

PID = 0S3:PID = 1

选好总统后，我们来看看集群是如何工作的：　　情况一：屁民甲(Client)到某个议员(ZK Server)那里询问(Get)某条法令的情况(ZNode的数据)，议员毫不犹豫的拿出他的记事本(local storage)，查阅法令并告诉他结果，同时声明：我的数据不一定是最新的。你想要最新的数据？等着，等我找总统 Sync 一下再告诉你。　　情况二：屁民乙(Client)到某个议员(ZK Server)那里要求政府归还欠他的一万元钱，议员让他在办公室等着，自己将问题反映给了总统，总统询问所有议员的意见，多数议员表示欠屁民的钱一定要还，于是总统发表声明，从国库中拿出一万元还债，国库总资产由100万变成99万。屁民乙拿到钱回去了(Client函数返回)。　　情况三：总统突然挂了，议员接二连三的发现联系不上总统，于是各自发表声明，推选新的总统，总统大选期间政府停业，拒绝屁民的请求。有主模型：- 只能有一个主发送指令、提议- 主——单点故障        - 重新选举，议员会把票投给数字编号和事务编号都大于自己的议员，默认是事务编号最全，数字编号最大的节点        - 数字编号（议员 ID，ZooKeeper 中叫 myid）：为了快速选出总统        - 事务编号（会议 ID）：为了确定谁的数据是最全的- 多主——脑裂        - 过半原则：选主过程中，如果某个议员获得了超过半数的选票，才可以成为主。- 议员同步数据只需要从主节点同步- 节点越多业务能力越强，但是选举速度也会越慢        - 设置新的角色，减少参与选举和投票的人数（例如 ZooKeeper 的 Observer）- 集群可用节点少于二分之一时整个集群不可用，推荐使用基数台服务器搭建集群。

1 元/度

如何选主

对不起，这个提议先前提过了

1 号提议，设定电费 2 元/度

议员总数Senator Count = 6

　　现在看冲突的解决：假设总共有三个议员 S1 ~ S3，S1 和 S2 同时发起了一个提议：1 号提议，设定电费。S1 想设为 1 元/度，S2 想设为 2 元/度。结果 S3 先收到了 S1 的提议，于是他做了和前面同样的操作。紧接着他又收到了 S2 的提议，结果他一查记事本，咦，这个提议的编号小于等于我的当前编号 1，于是他拒绝了这个提议：对不起，这个提议先前提过了。于是 S2 的提议被拒绝，S1 正式发布了提议：1 号提议生效。S2 向 S1 或者 S3 打听并更新了 1 号法令的内容，然后他可以选择继续发起 2 号提议。

1 号提议生效

为了保证数据的完整性

无脑投票给议员 ID 最大的实现快速选主

此时 PID 都为 0

PID = 0

PID = 0S5:PID = 1

投票过半原则

总统（President）

PID = 0S2:PID = 1

无主模型——活锁——每个议员都提出了一个提议，大家相互拒绝其他人的提议从而陷入死循环

解决网络波动带来的脑裂问题

- 有一个叫做 Paxos 的小岛(Island)上面住了一批居民(Islander)；- 岛上面所有的事情由一些特殊的人决定，他们叫做议员(Senator)；- 议员的总数(Senator Count)是确定的，不能更改；- 岛上每次环境事务的变更都需要通过一个提议(Proposal)，每个提议都有一个编号(PID)，这个编号是一直增长的，不能倒退；- 每个提议都需要超过半数((Senator Count)/2 +1)的议员同意才能生效；- 每个议员只会同意大于当前编号的提议，包括已生效的和未生效的；- 如果议员收到小于等于当前编号的提议，他会拒绝，并告知对方：你的提议已经有人提过了。这里的当前编号是每个议员在自己记事本上记录的编号，他会不断更新这个编号；- 整个议会不能保证所有议员记事本上的编号总是相同的；- 现在议会有一个目标：保证所有的议员对于提议都能达成一致的看法。　　现在议会开始运作，所有议员一开始记事本上面记录的编号都是 0。有一个议员发了一个提议：将电费设定为 1 元/度。他首先看了一下记事本，嗯，当前提议编号是 0，那么我的这个提议的编号就是 1，于是他给所有议员发消息：1 号提议，设定电费 1 元/度。其他议员收到消息以后查了一下记事本，哦，当前提议编号是 0，这个提议可接受，于是他记录下这个提议并回复：我接受你的 1 号提议，同时他在记事本上记录：当前提议编号为 1。发起提议的议员收到了超过半数的回复，立即给所有人发通知：1 号提议生效！收到的议员会修改他的记事本，将 1 号提议由记录改成正式的法令，当有人问他电费为多少时，他会查看法令并告诉对方：1 元/度。

冲突的解决

宕机恢复

接受你的提议

方便区分哪个是最新的主实现任何时候都只有一个主

无主模型：- 人人（所有议员）都能发送指令、投票- 投票人数有可能导致分区（分不同的阵营）- 事务编号混乱，每个节点都有可能有自己的提议- 议员同步数据要从多个节点同步（议员下线又重启）

提议 ProposalPID = 1

有一个议员发了一个提议：将电费设定为 1 元/度

有主模型——总统议员

1 号提议，设定电费 1 元/度

PID = 0S4:PID = 1

S2：1 号提议，设定电费 2 元/度

总结

S1：1 号提议，设定电费 1 元/度

发起提议的议员收到了超过半数的回复，立即给所有人发通知：1 号提议生效

- 小岛(Island)：服务器集群。- 议员(Senator)：单台服务器。- 居民(Islander)：客户端。- 议员的总数(Senator Count)是确定的：为了确定半数，总数都不确定半数怎么确定？- 提议(Proposal)：每一次对集群节点数据的修改。- 每个提议都有一个编号(PID)，这个编号是一直增长的：提议的唯一标识。- 每个提议都需要超过半数((Senator Count)/2 +1)的议员同意才能生效：为了数据的最终一致性。- 每个议员只会同意大于当前编号的提议：防止冲突。- 整个议会不能保证所有议员记事本上的编号总是相同的：因为中途可能会有节点故障。- 议会有一个目标：保证所有的议员对于提议都能达成一致的看法（弱一致性——最终一致性）。- 议员发消息 1 号提议，设定电费 1 元/度：前期投票((Senator Count)/2 +1)。- 议员给所有人发通知 1 号提议生效：后期广播(all)。

未有任何提议的情况下

电费多少