Distributed Algorithm Basics (IX) - Paxos made simple - 杨一江的博客 | Yi-Jiang...

这是分布式算法笔记的第九章，讲述经典Paxos算法。

Paxos是解决一部环境下的数据强一致性的共识算法，在工业界有着广泛的应用。最早的实现就是Google的chubby系统。目前比较著名的Paxos实现包括zookeeper、DynamoDB以及阿里的X-Paxos。Paxos算法是由Lamport大神提出的，强烈建议大家去看《Paxos Made Simple》这篇文章，Lamport讲的还是比较清楚的，层层深入。也可以结合Yale的讲义。这次笔记就主要围绕着这篇文章，做一个简单的总结。

Paxos Protocol

Paxos是为了解决异步系统的共识问题，本质上是通过足够多的machine来对抗可能发生的failure。由于前面已经证明了纯异步共识算法的不存在性，因此Paxos在节点重启时候需要额外的信息，从而打破这个困局。《Paxos Made Simple》描述的Paxos算法可以总结为

• N/2N/2-resilience
• Support: crush failure, delayed/ missing message
• Proposer (1), acceptor (NN), learner (1)

整个Paxos算法主要由3种agent组成(Proposer, Acceptor and Learner)，但是实际实现的过程中可以不需要严格割裂三者的功能，在一个典型的Replica State Machine案例中，每一个服务器都可以干3个不同agent的功能。

Proposer主要的任务就是分发propose，推动整个系统达成共识。在一个系统中，存在多个proposer可能会影响progress和liveness，因此在初步的Paxos中我们只要求只有一个proposer——这个性质是由leader election算法的liveness来解决——如果出现多个proposer，可以通过类似IP协议的指数随机后退，或者是failure detector来甄别正确的唯一proposer。Proposer重启的时候，需要记住之前最新的进展⟨n,v⟩​。⟨n,v⟩​。

Acceptor就是要求达成共识的对象，故障个数严格小于N/2N/2。需要注意的是，本篇文章中的acceptor是machine (cpu+memory)，本身是可以做出比较复杂的动作（与disk paxos的主要区别）。Acceptor重启的时候，需要记住之前最新的进展⟨nmax,v,nv⟩⟨nmax,v,nv⟩。

Learner是获知当前共识的对象，通常只需要指定一个地位特殊(distinguished)的learner子集（通常为1）作为中继节点，每次当acceptor确认了一个输出之后都会向这些distinguished learners通知，当这些learner收获到超过一半的acceptor的信息之后（达成quorum），distinguished learners通知其他平凡learner。由于learner算法不是重点，因此之后的讨论不再围绕该类agent。Learner的重启只需要求Proposer重发一轮proposal。

具体流程请参考《Paxos Made Simple》原文，这里主要罗列一些重要信息。

• Phase 1
  • prepare⟨n⟩prepare⟨n⟩: ask for promise
  • ack⟨n,v,nv⟩ack⟨n,v,nv⟩
• Phase 2
  • accept⟨n,v⟩accept⟨n,v⟩
  • accepted⟨n,v⟩accepted⟨n,v⟩

Proof: Safety

• Validity: outputoutput来源于input[N]input[N]

  • P1. Acceptor应当接受第一个收到的Proposal
  • P1.a An acceptor can accept a proposal numbered nn iff it has not responded to a prepare request having a number greater than nn.

• Agreement: 共识 vv 一旦达成，今后就一定不会有另外一个output v^≠vv^≠v 成为主流 (chosen)

  • P2 [Global view] If a proposal with value vv is chosen, then every higher-numbered proposal that is chosen has value vv.

  • ⇐⇐P2.a [Acceptor’s view] If a proposal with value v is chosen, then every higher-numbered proposal accepted by any acceptor has value v.

  • ⇐⇐P2.b [Proposer’s view] If a proposal with value v is chosen, then every higher-numbered proposal issued by any proposer has value v.

    • I.H. ∀n′∈[m,n),vm=vn′∀n′∈[m,n),vm=vn′

    • Ind. 这里CC和SS都是关于acceptor的集合

      1. m→C,m+1→C,…,n−1→C(∣C∣≥N/2)m→C,m+1→C,…,n−1→C(∣C∣≥N/2)

      2. S→n(∣S∣≥N/2)S→n(∣S∣≥N/2)

      3. [Quorum.] C∩S≠∅⇒maxnv∣⟨nmax,v,nv⟩∈S≥mC∩S≠∅⇒maxnv∣⟨nmax,v,nv⟩∈S≥m
      4. 根据算法(P2.c)，我们得到标号为nn的proposal对应的vn=vmvn=vm

    □◻

Application

• Replicated State Machine

• Previous
  Distributed Algorithm Basics (VIII) - Fault-Tolerant Consensus