Paxos Made Simple

Summary

paxos算法的的核心思想是“与其预测未来,不如限制当下”,即通过保证当前的操作,来一步一步达到预期

Theory

要求

Safety:

  • 只有一个被提议的value被选定(validity)
  • 两个不同的进程不能做出不一样的的选择(agreement)

Liveness

  • 最终会有被提议的value被选定
  • 如果一个value被选定,任意进程最终一定会得知这一结果

推导过程

首先设定三个角色 proposers,acceptors,learners。

要想有value被选定,则acceptor必须要接受proposer的提议,于是我们要求

  • P1. 任意acceptor必须接受(accept)它收到的的第一个提议(proposal)

那么问题来了,多个proposers会提议多个value,无法满足safety. 于是我们考虑让acceptor可以接受(accept)多个提议,为了便于区分,我们考虑为提议增加一个total order的序号(proposal number),即提议由proposal number + value组成 但是最终我们是要选定(chosen)一个value的, 于是我们考虑可以接受多个提议,但是我们必须保证这些提议的value都是一样的,于是我们进一步要求:

  • P2. 如果value为v的提议被选定(chosen),则所有number更大的且被选定的提议的value也必须为v

一个提议如果被选定(chosen),那么至少被一个acceptor接受(accepted)过, 所以我们可以通过满足如下条件来达成P2

  • P2a. 如果value为v的提议被选定(chosen),那么所有number更大的且被任意acceptor接受过(accepted)的提议其value也必须是v

考虑一个acceptor c从没有收到提议,此时一个从故障中恢复的proposer发起了一个更高number的提议,且该提议与已经chosen的value不一样。按照P1,c肯定会accept该提议, 这样便违反了2a。于是我们强化一下P2a的要求

  • P2b. 如果value为v的提议被选定(chosen),那么由proposer发起的number更大的提议的value也必须是v

P2b通过限定proposer的动作来满足P2,通过归纳法我们可以得知,只要保证如下规则,就可以满足P2b

  • P2c. 那么对于大多数(majority)acceptors,我们称之为集合S;如果一个提议(n,v)被发起,则要么1成立,要么2成立
    • S中不存在acceptor接受过(accepted) number 小于n的提议
    • v是S接受过的(accepted)所有提议里number小于n的提议中number最大的提议的value

只要满足P2c就可以满足P2b,进而满足P2;至此我们便有了更具体的方式来实现P2c,具体如下:

  1. proposer选择一个proposal number n,然后向每个acceptors发起请求,要求acceptors:
    • 保证不再接受(accept)number小于n的提议,并且
    • 如果已经接受过(accepted)number小于n的提议,则这些提议中number小于n的最大的number以及该提议的value返回给proposer
  2. 如果proposer收到大多数(majority)的acceptors的响应,则proposer可以发起一个序号为number的提议,其value是v
    • v是所有acceptor响应的(mi, vi)中最大的m对应的v
    • 如果没有acceptor响应(mi, vi),则v由proposer自己决定

以上我们称之为PREPARE请求。利用PREPARE请求,我们完成了一个学习的过程,从而实现了P2c; proposal的具体实现我们归纳出来了,对应的acceptor的的要求也很容易得出:

  • 当且仅当(iff)acceptor 没有响应number大于n的prepare请求时,才可以接受(accept)number为n的提议

由于acceptor收到prepare请求后会保证不再接受(accept) proposal number小于n的提议,则acceptor便没有必要再回复proposal number小于n的prepare请求,我们可以直接忽略,或回复error或null使proposer放弃后续提议. 于是我们可以将proposer和acceptor的动作综合起来描述如下:

  • Phase 1
    • proposer生成一个proposer number n,然后发送prepare请求到所有(其实也可以是majority,但越多越能保证收到过半数的回复)acceptors
    • acceptor收到prepare请求后:
      • 如果之前有收到proposal number > n的prepare请求,则直接忽略该prepare请求,否则
      • 回复该prepare请求,同时如果之前有接受(accept)提议,则回复内容中带上接受的提议value和对应该value的最大的proposal number
  • Phase 2
    • proposer收到总数过半(majority)的回复后:
      • 如果所有回复中都没有携带提议value,则proposal自己选择一个提议value
      • 否则从所有回复中选择proposal number最大的的value
      • 向所有(其实也可以是majority,但越多越能保证收到过半数的accept)acceptor发送上述得到的提议value和proposer number n
    • acceptor收到提议请求后:
      • 如果之前没有回复proposal number > n的prepare请求,则接受(accept)该请求

以上可以完成总数过半的acceptor 接受(accept)一个value,但并不代表被chosen,该value被chosen需要:

  • 由learner来找出哪个提议(proposal number + value)被总数过半的的acceptors接受了(accepted),方式有如下:
    • 由接受(accept)提议的acceptor向所有learner发送通知消息,开销 M*N次通信(假设M个接受该提议的acceptor,N个learner)
    • 由接受(accept)提议的acceptor向某个learner发送通知消息,由该learner确定chosen结果后再广而告之,开销M+N次通信
    • 扩大方法二中某个learner为多个learner,适当增加开销,但可以保证可靠性(learner单点问题)

TO BE CONTINUE!

Comments