paxos

简述

基于消息传递的分布式系统，不可避免的面临进程被杀死，重启，延迟，丢失，重复等问题，而经典的paxos算法就是用来处理这类问题。paxos能够保证多个节点就某个值的最终达成一致。

角色

proposers：提出议案，议案包括提案编号和提议的值 acceptors：收到提案后可以接受提案，若提案被多数派接受，则该提案获批 learners：只能学习提案

• 每个节点都允许身兼数职

paxos

准备阶段

1. proposer选择一个提案编号n并将prepare请求发送给acceptors
   • Prepare(n)
2. acceptor收到prepare消息后，如果提案的编号大于它已经回复的所有prepare消息(回复消息表示接受accept)，则acceptor将自己上次接受的提案回复给proposer，并承诺不再回复小于n的提案；
   • if has(minProposal) and n > minProposal then minProposal = n and Return(acceptedProposal, acceptedValue)
   • if ! has(minProposal) then minProposal = n and Return(true)

批准阶段

1. 当一个proposer收到了多数acceptors对prepare的回复后，就进入批准阶段。它要向回复prepare请求的acceptors发送accept请求，包括编号n和值value（如果在准备阶段没有收到acceptor回复的value，则可以是任何value）。
   • if received(value) then Accepted(n, value)
   • if ! received(value) then Accepted(n, random)
2. 在不违背自己向其他proposer的承诺的前提下，acceptor收到accept请求后即批准这个请求。
   • if n >= minProposal then acceptedProposal = minProposal = n and acceptedValue = value and return(minProposal)

下图展示了整个算法的过程

实际使用

在实际场景中，分布式系统任意一个值得决议，都需要通过paxos算法过程进行决议并学习通过的提案，这样就带来了比较大的开销，所以拥有改进的multi-paxos，该算法支持一组连续的值被达成一致并学习。 和典型的proxy不同的点在于，multi-proxy通过index参数来控制不同paxos实例间的隔离, 如：

Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  | --- First Request ---
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(N)
   |         |<---------X--X--X       |  |  Promise(N,I,{Va,Vb,Vc})
   |         X--------->|->|->|       |  |  Accept!(N,I,V)
   |         |<---------X--X--X------>|->|  Accepted(N,I,V)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |