解决什么问题

• 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()，则返回<error>
    • 如果收到的回应数没超过半数，则返回<error>
    • 如果收到超半数不为reject()的回应，根据阶段1b中的返回值
      • 如果所有返回值为accept(null)，则proposer向所有acceptor发送acceptI(n, v)。
      取返回值accept(ProNum_ProVal)，判断v的个数是否超过半数
      • 是 => v被选中，返回<ok，v>
      • 否 => 向所有accetpor发送proposal(n, v)，其中v是所有accept(ProNum_ProVal)中ProNum最大对应的ProVal，n是节点1a中的num。
  b（acceptor做法）：根据节点2a接收到的proposal(n, v) , 判断PreNum和n
  • n<PreNum, 不接受该accept
  • 否则，接收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<n的proposal，从而可以信任查询的结果，然后按照P2c的原则实操。