Paxos是一种分布式共识算法，与Raft不同的是: Paxos具体到单个var的一致性，映射到Raft就是单个Entry的一致性问题。这里只记录个人学习Paxos的过程几个关键的点。

Paxos

Paxos算法最重要的就是理解推导过程，通过阅读论文Paxos Made Simple一步一步还是比较容易理解的，以前看过Raft论文对我造成了先入为主的困惑，Raft是多个Entry的分布式共识的解决算法，而Paxos只讨论了单个Var的共识。 Paxos 算法解决的问题是一个分布式系统如何就某个值（决议）达成一致。

Agents(角色)

注: 一个节点不单单只承担一个角色

  • Proposers 提案提交者
  • Acceptors 提案接受者
  • Learners 广播确定的提案

Safety前提

  • 一个Var只有一个Value

  • 只有被确定的Value才会被Learn

推导

背景

Paxos讨论的是单个Var的一致性问题

  • Paxos主要包括三个组件：Proposer，Acceptor和Learner，其中Proposer主动发起投票，Acceptor被动接收投票，并存储提案值，Learner负责将确定的提案广播出去。

推导过程

  1. 最简单的方法，只有一个Acceptor，即所有的Proposer通过抢占式的方式来提交自己的value，最先被提交的提案会最先被接收，但这样如果这个唯一的Acceptor发生宕机或其他错误，后面的操作就无法继续了。

  2. 推翻1的思路，我们采用多个Acceptor的方法，每个Acceptor接受一个Value, 只有当一个提案被超过半数的Accepots接受，这个提案才被确认。这里提出一个条件:

    P1. An acceptor must accept the first proposal that it receives.

    这个条件约束了Acceptor必须接受自己收到的第一个提案, 但这个条件也引发了一个问题，假如一个Acceptor只允许接受一个提案，有可能造成任何一个提案都没有被超过半数的Accepots接受:

    Imgur

    这是就需要允许Acceptor可以接受多个提案，即多个Proposer都可以向Acceptors提交自己的提案，最后再通过确认哪一个提案被超过半数的Acceptors选中来达到需求。

  3. 现在允许多个提案被同时提交，为了满足一致性条件，即Safety，我们需要保证被选择的提案里的Value是一致的, 所以这里引入了一个提案的Number，为了遵守P1约束且保证只有一个提案被选中，这里引出了提案P2:

    P2. If a proposal with value v is chosen, then every higher-numbered proposal that is chosen has value v.

    一个提案想被选中，必须先由Accetors所接受，所以在继续在P2的基础上可以 推导出P2a:

    P2a. If a proposal with value v is chosen, then every higher-numbered proposal accepted by any acceptor has value v.

    即如果一个提案已经被选中了，则后面的具有更高Number的提案必须具有相同的value。这里有一个问题，假如一些Acceptors一开始没有接受过提案，根据P1的约束，它们必须接受自己所收到的第一个提案，而此时它们之前没有接受过任何提案，无法确定这个提案是否符合P2a的约束，所以继续衍生P2a的约束:

    P2b. If a proposal with value v is chosen, then every higher-numbered proposal issued by any proposer has value v.

    因为我们无法控制Accetptors之间对某一个提案Value的限定，所以我们转而要求Proposer对提案的Value做限定, 即假如一个提案已经被Acceptor所接受，后面每一个Proposer提交的提案的value都必须和被接受的提案的value保持一致。

    P2c. For any v and n, if a proposal with value v and number n is issued, then there is a set S consisting of a majority of acceptors such that either (a) no acceptor in S has accepted any proposal numbered less than n, or (b) v is the value of the highest-numbered proposal among all proposals numbered less than n accepted by the acceptors in S.

  4. 为了满足P2c的约束，一个Proposer如果想提交一个Number为n的提案，它必须知道目前Acceptor所接受的提案里是否存在提案号Number小于n的提案，如果Acceptor接受所有的提案都小于n，那么它这个提案号为n的提案将会被大多数Acceptor接受。所以为了简单，Proposer要求Acceptors不得再接受Number小于n的提案，所以Paxos将一个提案的提交分为两个过程:

    • Prepare阶段

      A proposer chooses a new proposal number n and sends a request to each member of some set of acceptors, asking it to respond with:

      ​ (a) A promise never again to accept a proposal numbered less than n, and

      ​ (b) The proposal with the highest number less than n that it has accepted, if any.

      Proposer选择一个新的提案号n发给每一个Acceptor，期待得到Acceptor的以下回应:

      • 承诺不会再接受小于n的提案。
      • 如果存在已经被Accept的提案里提案号最大且小于n的提案，返回给Proposer。

    • Accept阶段

      如果Proposer收到了大多数Acceptor的回复，那么它就可以给Acceptors发送这个提案，假如prepare请求的回复里表示Acceptor之前没有收到过提案，那么Value就是自己本身这个提案自带的，如果Acceptor之前已经收到过提案了，那么Value必须是那个提案里附带的Value, 这个要求是为了满足约束P2b，即后面的提案必须认同前面已经被Accept的Value。

Paxos的算法概述

将上面推导的结论总结一下分为Prepare和Accept阶段。其中Prepare阶段用于block当前未被选中的旧的提案，并发现已经被选中的提案内容, Accept过程用于真正的提案提交:

Phase 1.

  • Proposer选择一个提案号为n的提案发送prepare的请求给Acceptors。
  • Acceptor收到了一个prepare请求且提案号n大于之前回复过的prepare请求，Acceptor就会承诺不会再接受提案号小于n的任何提案，假如之前已经存在Accept的提案，那么Acceptor还会返回自己Accept的最新的提案Value。
  • 假如一个Acceptor收到了一个prepare请求，但这个请求里附带的提案号Number小于之前prepare阶段承诺的，那么它将忽略这个prepare请求。

Phase.2

  • 如果Proposer收到了回复，那么它可以给Acceptors发送这个提案，假如prepare的回复里表示Acceptor之前没有收到过提案，那么Value就是自己本身这个提案自带的，如果Acceptor之前已经收到过提案了，那么value必须是那个提案里附带的Value。
  • 如果一个Acceptor收到了accept请求带有一个提案，假如这个提案号n不小于之前Acceptor在prepare回复中承诺的提案号，那么这个提案将会被Accept。