Paxos原理
参考链接：微信自研生产级paxos类库PhxPaxos实现原理介绍 - 知乎
1 什么是Paxos
1.1 一致性协议
Paxos是一个一致性协议。
1.2 分布式环境
异步通信环境指的是消息在网络传输过程中，可能发生丢失，延迟，乱序现象。
几乎所有分布式环境都是异步通信环境。
Paxos是一个在异步通信环境，并容忍在只有多数派机器存活的情况下，仍然能完成一个一致性写入的协议。
1.3 Acceptor和Proposer
在分布式环境当中，每台机器都要扮演一个角色，严格遵守Paxos协议处理消息，称为Acceptor。同时，发起写入请求的角色称为Proposer。
2 Paxos的作用
2.1 确定一个值
当Paxos协议宣称一个值被确定（Chosen）后，数据Data即被确定而永远不会被改变。
![[0104_01_paxos_1_instance.jpg]]
（协议具体是怎样确定一个值的？）
2.2 确定多个值
上述各Proposer、Acceptor和所服务的Data构成一个集合，称为一个Paxos实例。
一个实例确定一个值，多个实例确定多个值。
![[0104_02_paxos_multi_instances.jpg]]
2.3 有序确定多个值
首先给实例一个编号，定义为i，i从0开始，只增不减，由本机器生成，不依赖网络。其次，我们保证一台机器任一时刻只能有一个实例在工作，这时候Proposer往该机器的写请求都会被当前工作的实例受理。最后，当编号为i的实例获知已经确定好一个值之后，这个实例将会被销毁，进而产生一个编号为i+1的实例。
问题：如果一个机器上实例对应的值已经被确定（如图，对A来说，实例5已经确定），其他机器还没有确定（落后于A），根据上述算法，机器将会停止产生新的实例。
![[0104_03_paxos_unlearned.jpg]]
A上的实例5已经被销毁。怎么办？
2.4 实例的学习
实例已经被销毁，说明值已经确定好了，直接获取其值写入本机即可。执行这个操作的角色称为Learner。
![[0104_04_paxos_learned.jpg]]
比如，B从A学到实例5的值；C从B学到实例3-5的值。
3 Paxos的应用
3.1 状态机
一个请求发给Proposer，Proposer与相同实例i的各Acceptor协同工作，共同完成一值的确定，之后将这个值作为状态机的输入，产生状态转移，最终返回状态转移结果给发起请求者。
![[0104_05_paxos_state_machine.jpg]]
3.2 我们需要多个角色尽量在一起
多台机器的相同编号实例共同构成了一个Paxos group。如下图所示，将请求发给任一机器的Proposer即可。 ![[0104_06_paxos_group.jpg]]
3.2 我们需要严格的落盘
落盘： 将数据写入到磁盘（存储介质）；
刷盘： 并不是每次接收到数据后就将数据写入到磁盘，而是会先写入缓冲区。将缓冲区的数据写入到磁盘的过程，称为刷盘。
每次进行写盘都要附加一个Fsync进行保证。Fsync是一个非常重的操作，也因为这个，Paxos最大的瓶颈也是在写盘上，在工程上，我们需要尽量通过各种手段，去减少Paxos算法所需要的写盘次数。
万一磁盘Fsync之后，仍然丢失或者数据错乱怎么办？这个称之为拜占庭问题，工程上需要一系列的措施检测出这些拜占庭错误，然后选择性的进行数据回滚或者直接丢弃。
3.4 我们需要一个Leader
Paxos使用了一些锁的机制解决同时写入时的冲突。越多的Proposer进行同时写入，冲突的剧烈程度越高，虽然完全不妨碍最终会确定一个值，但是性能上是比较差的。
我们希望有一个Proposer的领导者，优先由他来进行写入，那么当在只有一个Proposer在进行写入的情况下，冲突的概率是极小的，这样性能会得到一个飞跃。Leader的引入，不是为了解决一致性问题，而是为了解决性能问题。
由于Leader解决的是性能问题而非一致性问题，即使Leader出错也不会妨碍正确性，所以我们只需要保证大部分情况下只有一个Proposer在工作就行了，而不用去保证绝对的不允许出现两个Proposer或以上同时工作。
3.3 我们需要状态机记录下来输入过的最大实例编号
状态机输入到的实例的最大编号，和Paxos运行当中认为已经确认好值的实例最大编号应该是一样的。但当机器重启或者进程重启之后，状态机的数据可能会由于自身实现问题，或者磁盘数据丢失而导致回滚，所以提出了一种方法，状态机必须严格记得自己输入过的最大实例编号。
如果状态机输入的最大实例编号为a, Paxos发现已确定的值的实例编号为b，a<b，说明状态机落后了. 这是只要一步步将(a,b]的chosen value输入到状态机，即可将其状态更新到b. 这个过程称为启动重放.
3.4 异步消息处理模型
![[0104_07_paxos_model.jpg]]
分为四个部分：
- Request，即外部请求，这个请求直接输入到Proposer里面，由Proposer尝试完成一个值的确定。
- Network i/o，网络i/o处理，负责paxos内部产生的消息的发送与接收，并且只处理paxos消息，采用私有端口，纯异步，各台机器之前的network i/o模块互相通信。
- Acceptor，Proposer，Learner。用于响应并处理paxos消息。
- State machine，状态机，实例确定的值(chosen value)的应用者。
工作流程：
- 收到Request，由Proposer处理，如需要发送paxos消息，则通过network i/o发送。
- Net work i/o收到paxos消息，根据消息类型选择Acceptor，Proposer，或Leaner处理，如处理后需要发送paxos消息，则通过network i/o发送。
- Proposer通过paxos消息获知chosen value，则输入value到State machine完成状态转移，最终通知Request转移结果，完成一个请求的处理。
- 当paxos完成一个值的确认之后，所有当前实例相关角色状态进行清空并初始化进行下一个编号的实例。
5 生产级的paxos库
5.1 RTT与写盘次数的优化
朴素的Paxos算法需要两个RTT，以及每台机器的三次写盘。 生产级的Paxos算法优化为了一个RTT以及每台机器的一次写盘。
5.2 同时运行多个paxos group
由于实例运行的方式是确保i实例的销毁才能运行i+1实例，这个串行过程对cpu的利用很低。
如图，每个group里面都有完整的paxos逻辑，只需要给paxos消息增加一个group的标识，通过network i/o的处理，将不同group的消息输送到对应的group里面处理。这样我们一台机器只需要一个私有端口，即可完成多个状态机的并行处理。
![[0104_08_multi_paxos_group.jpg]]
5.3 更快地对齐数据
如果机器A的实例编号a落后于机器B的编号b，就要通过Learner学习。学习一个实例的网络延时代价是一个RTT，但当新的数据以一个RTT的代价不断写入时，机器A就很难追上了。
打包学习是一个好的方法，将(a,b]的实例值打包学习。但当落后的数据量大，B打包发送数据需要的网络耗时也变大，在发送数据的过程中，A仍然处于空闲状态。由于paxos另外一个瓶颈在于写盘，如果不能利用这段时间来进行写盘，那性能仍然堪忧。
我们参考流式传输，采用类似的方法实现Learner的边发边学，B机器源源不断的往A机器输送数据，而A机器只需要收到一个实例最小单元的包体，即可立即解开进行学习并完成写盘。
5.4 如何删除Paxos数据
Paxos数据，即通过paxos确认下来的有序的多个值（下称Paxos log）作为状态机的输入，是源源不断的，但磁盘空间是有限的。假设要求每次启动时，定义编号Imax，小于等于Imax的数据都不会被使用，可以删除。但会有如下问题：如果一台机器挂掉了，需要用一台新机器代替，新机器需要通过Learner从其他机器学习并重放所有Paxos log，但其他机器上小于等于Imax的数据都被删除了。
有一个方法：将状态机相关数据全部拷贝到新机，再从Imax启动。但状态机的数据无时无刻不在写入，拷贝一个正在写入的数据，其值是不可预期的。
我们需要的是一个状态机的镜像数据（称为Checkpoint），这个数据在我们需要去拷贝的时候是可以随时停止写入的。可以通过镜像状态机构建。
![[0104_09_checkpoint_data.jpg]]
6 正确性保证
模拟异步通信环境 运行时的对账：CRC32 防止拜占庭问题带来的错误：二次校验，防止磁盘数据被篡改