Paxos协议

在分布式系统中，节点之间的信息交换有两种方式：一种是通过共享内存共用一份数据；另一种是通过消息投递来完成信息的传递。

Paxos协议用来解决多个节点之间的一致性问题，多个节点之间通过操作日志同步数据，如果只有一个节点为主节点，很容易确保多个节点之间操作日志的一致性，如果主节点出现故障，需要选举出新的主节点，Paxos协议就是用来实现主节点选举的。

使用Paxos协议的前提是不能出现拜占庭将军问题

tips

拜占庭将军问题是一个典故，当时拜占庭罗马帝国国土辽阔，防御敌人的各个军队都分隔很远，将军和将军之间只能靠信差来传消息。在战争时，拜占庭军队内所有将军和副官必须达成共识，决定出是否有赢的机会才会去攻打敌营。但是，在军队中可能有叛徒或者敌军的间谍，扰乱将军们的决定又扰乱整体军队的秩序，使得最终结果并不代表大多数人的意见。这时，在已知有成员谋反的情况下，其余忠诚的将军应该如何不受叛徒的影响达成一致，也就出现了拜占庭将军问题。拜占庭将军问题是一个没有办法保证可信的通信环境的问题，Paxos的前提是有一个可信的通信环境

角色

Paxos分为三个角色

Proposer 提议者，提出议案的角色
Acceptor 接受者，收到议案后进行判断的角色，Acceptor收到议案后要选择是否接受议案，若议案被多数Acceptor接受，则该议案被批准
Learner 只能学习被批准的议案，相当于对通过的议案进行观察的角色

执行过程

如果系统中只有一个proposer(提议者)

批准，proposer(提议者)发送accept消息要求所有其他节点acceptor(接受者)接受某个提议值，acceptor可以接受或者拒绝
确认，如果超过一半的acceptor接受，意味着提议生效，proposer发送acknowledge消息通知所有的acceptor提议生效

但是系统中可能存在多个proposer(提议者)，各自发起不同的提议

准备，proposer(提议者)首先选择一个提议序号n给其他的acceptor节点发送prepare消息，acceptor收到prepare消息后，如果提议序号大于他已回复的所有prepare消息，则acceptor将自己上次接受的提议回复给proposer(提议者)，并承诺不再回复小于n的提议
批准，proposer(提议者)收到了acceptor中的多数派对prepare的回复后，就进入批准阶段，如果之前的prepare阶段acceptor回复了上次接受的建议，那么proposer(提议者)选择其中序号最大的提议值发给acceptor批准；否则proposer(提议者)生成一个新的提议值发给acceptor批准，acceptor在不违背之前在prepare阶段的承诺的前提下，接受这个请求
确认，如果超过一半的acceptor接受，提议值生效，proposer(提议者)发送acknowledge消息通知所有的acceptor提议生效

如果系统中同时有人提议案的话，就会出现碰撞失败，然后双方都需要再次提交，而每次提交都可能会出现编号冲突的问题，就会产生活锁，解决的办法就是在整个集群中设定一个Leader，所有议案由Leader来提，这就使得提议者变成了一个单点，但是新的问题就是如果Leader出现问题怎么办，那就需要重新选出一个Leader

与两阶段提交协议对比

两者的作用其实是不同的

Paxos协议用于保证同一个数据分片的多个副本之间的数据一致性
两阶段提交协议则用于保证属于多个数据分片上的操作的原子性