Paxos算法
解决什么问题
paxos用于确定一个不可变变量的取值。这看似是一个简单的功能，但是分布式系统中时刻伴随着乱序，故障的现象，并且为了提高系统可用率，存储采用多个副本存储，此时确定一个变量的取值就不是一个简单的功能了。
应用
以分布式式存储系统为例，数据的值是可以一直变化的，但是其存储方式可以拆分为不同的变更记录，使用paxos来确定每一次变更的确定性取值。
问题分析：
paxos解决的问题系统抽象：确定一个变量var的取值
系统组成：
系统内部由多个acceptor组成，负责存储和管理var变量。
系统外部由多个proposer组成，负责发起proposal(n，v)，设置变量var的值，其中编号是n，值是v
系统主要要求：
var的取值的一致性，如果var取值没有确定，则系统认为var取值为NULL，一旦系统认为var取值被确定了，var的值不可被更改
额外要求：
多个proposer可能并发调用，并且可以提出不同的取值。
系统能容忍少数（半数以下）accetpor故障。
系统能容忍任意proposer在任何时候发生故障。
当前假设：acceptor不会丢失数据。
统一术语：
val=v被选中 => v被写入超过超半数的acceptor
paxos算法：
acceptor需要存储的元素：
prepare最大num，记为PreNum
已接受的proposal(n, v)中，编号n最大proposal，记为accept(ProNum_ProVal)，没有接受过proposal则记为accept(null)
阶段1：准备阶段
a（proposer做法）：向超过半数的accetpor发送一个num=n的预请求，记为prepare(n)
b（acceptor做法）：acceptor收到prepare(n)后，对比PreNum和n
如果PreNum>n，回复reject()
否则，acceptor接受该prepare(n)，并设置PreNum=n，并返回accept(ProNum_ProVal)或者accept(null)
阶段2：提交阶段
a（proposer做法）：根据阶段1a中的返回值。
如果收到至少一个reject()，则返回
如果收到的回应数没超过半数，则返回
如果收到超半数不为reject()的回应，根据阶段1b中的返回值
如果所有返回值为accept(null)，则proposer向所有acceptor发送acceptI(n, v)。
取返回值accept(ProNum_ProVal)，判断v的个数是否超过半数
是 => v被选中，返回
否 => 向所有accetpor发送proposal(n, v)，其中v是所有accept(ProNum_ProVal)中ProNum最大对应的ProVal，n是节点1a中的num。
b（acceptor做法）：根据节点2a接收到的proposal(n, v) , 判断PreNum和n
n 否则，接收proposal(n, v)，记录accept(n_v)，并广播accept(n_v) 论文的推导过程理解： 多个acceptor存储val，如何才被定义val被选中？ 超过半数acceptor写入成功某个取值v时，称val被选中 => 理论是抽屉原理，两个超半数的acceptor集合必有一个acceptor重合，最先写入超半数acceptor集合成功的val(v)会被选中，后续的超半数集合acceptor必然能获取到该选中的val(v)。 为什么要添加自增编号num? 需要写入超半数acceptor && 容忍半数以下的acceptor故障。acceptor总个数为5，v1、v2写入成功acceptor的数量=2，此时剩下的一个acceptor故障 => 其中一个acceptor必然会写入两次val，写入是通过添加自增编号（规定高阶=>num更大）区分两次，甚至多次写入。 既然一个acceptor会写入多个值，如何确保val的取值不可变？（被选中之后，不在提出写入其他值） 一旦proposer发现val=n的值被选中，则使用已经被选中的val写入acceptor。 更加严苛的做法（找其充分条件，论文中的证明过程就是一步步找满足不可变条件的充分条件，直至工程上容易实现） 假设当num=m时，val=v已经写入超过半数acceptor，有num=n（n>m），proposer写入任意一个acceptor的val都应该是v => 简称P2a 假设当num=m时，val=v已经写入超过半数acceptor，有num=n（n>m），proposer都只能发送proposal(n，v) => 简称P2b 如何确保P2b？ => P2c（最难理解的部分） 在发出proposal(n，v)之前 要么确保超半数acceptor没有接受过任何自增编号小于n的proposal（证明还没有任何va被选中，此时可以v可以是任何值）。 要么确保超半数acceptor所接受的所有proposal中，最大小于n自增编号的proposal对应的val为v （归纳法可证明，如果v已经被超半数acceptor所接受，每次取最大num对应的v，那高阶的proposal的val一定是v） 两阶段提交中的阶段1 prepare解决了什么问题？ 查询是否有val已经被选中 由于proposer的调用会乱序，通过自增编号num=n锁定acceptor，使得acceptor不在接受num 算法每次取acceptor所接受的proposal中编号最大的v来广播，保证了2件事情 在没有选中前快速收敛 选中后取值一致 算法保证了当val=v的值被写入超过半数后，高阶的num对应的val一定是v，所以以下情况不会出: accept1 accept2 accept3 PreNum - - - accept(ProNum_ProVal) accept(1_1) accept(1_1) accept(2_2)