Paxos核心思想、流程、扩展与思考学习记录


一致性基本内容

基础概念

  • 允许一定数量进程挂掉
  • 达成一致性是指半数以上同意

三大核心要求

  • 合法性(Validity):达成一致性值value必须是由某个进程提出的
  • 共识性(Consensus):一旦就value值达成一致,不能再对另一个value达成一致
  • 可终止性(Termination):一致性总是能达成(非理论定义上,详见FLP问题,简而言之异步环境下任何一致性算法都存在永不终止的可能)

理解本质

  • 一旦提案I达成一致性,任何比该提案ID更大的提案内容都会被“渲染”成提案I的内容,从而实际意义上结束流程。因为任意两个多数集合必然有交集,而达成一致的提案ID一定最大,在下一个提案中选取已回复的最大ID提案就必然会选中已达成一致的提案
  • 从概念上看,对acceptor来说第一个提案无法拒绝,任意ID大于当前已接受提案的新提案也没有理由被拒绝,必须接受
  • 注意一下提案ID与提案的值分离,提案ID是取决于proposer通过某种方式(例如已经得到实现的全局自增id)获得的ID,但其提案值取决于预提案阶段收到的acceptor们的返回值

流程

  • 阶段一 预提案阶段:

    • 提议者Proposer:向接受者Acceptor广播预提案,附带接下来提案Proposal的proposal_id

    • 接受者Acceptor:收到预提案后更新a_proposal_id = max(proposal_id,a_proposal_id),如果预提案的proposal_id>a_proposal_id,Acceptor回复记录的接受过的proposal_id最大的提案,并承诺不再接受比预提案中附带的proposal_id更小的提案

  • 阶段二 提案阶段:

    • 提议者Proposer:等待直到收到大多数接受者对预提案的回复,从所有回复的提案组成的法定数目的提案集合K中挑选proposal_id最大的提案,以该提案的值作为本次提案的值。如果K是空集,那么可以给提案任意赋值。然后把该提案广播给接受者们,提案和预提案共享同一个proposal_id

    • 接受者Acceptor:如果收到的提案的proposal_id>= a.proposal_id,那么接受这个提案,更新a_proposal_id = max(proposal_id,a_proposal_id),更新记录的提案

扩展

理解误区

  • 分清提案预提案两个不同的阶段,预提案阶段不会接受提案,不同的proposer处于不同的阶段,一个proposer获得多数acceptor的响应后结束其预提案阶段
  • 当前整个环境中不同proposer两个阶段混杂进行,而信息是进程间沟通的唯一手段,预提案本质上起了消息传递扩散的作用
  • 算法结果不唯一,时间顺序对结果有很大的影响,一定程度上取决于谁能更快的走完整个流程,即最快争取到半数同意

活锁

  • 流程
1
2
3
4
graph LR
提案i提出 --> 预提案i+1截胡
预提案i+1截胡 --> i=i+1
i=i+1 --> 提案i提出
  • 这一般是纯理论上的问题,实际工程应用上分布式系统应该并不会出现如此“有序”的场景(一环扣一环,卡死提案的通过提交),而且若进程数总量一定,最终递归还是会被停止的?

其他工程实现细节(待补充)

  • 全局唯一自增ID

Written with StackEdit.