Basic Paxos

The Paxos algorithm, when presented in plain English, is very simple.

Paxos有许多变种,一般来说都是指的Basic Paxos,也就是这篇论文里提出来的内容。下面没有特殊说明,都是指的Basic Paxos。

Paxos需要保证的是两个特性。

  1. safety

    • Only a value that has been proposed may be chosen
    • Only a single value is chosen, and
    • A process never learns that a value has been chosen unless it actually has been.
  2. liveness

    • Some proposed value is eventually chosen
    • If a value is chosen, servers eventually learn about it

Paxos和raft一样也划分了三种角色,但是和raft的不同的是一台机器可以同时扮演这三个角色。

  • Proposer

  • Acceptor

  • Learner

Problems

  1. problem1: split votes

    如果acceptor只接受它收到的一个value。那么在多个机器一起提出proposal时,会发生脑裂,导致没有value被选择。

    解决办法:acceptor必须接受多个不同的value

  2. problem2: conflict choise

    如果acceptor接受每个它收到的value,会导致选择多个不同的value。

    一旦某个value被选择之后,后续的proposal必选选择同个value。同时proposal应该带有unique number,acceptor应该拒绝旧的序号

    proposal返回的时候,若已有value被选择,应该将value返回,proposer需要选择最大的accept_num对于的value来发起accept请求

    解决办法:2-phase protocal,并且通过num来拒绝旧的提案。

  3. problem3: livelock

    解决办法: 在重新开始下一轮proposal时,随机设定时间,让其它proposers先完成选择。

Algorithm

  1. phase1
    • proposer 选择一个proposal number,发送prepare rpc请求给所有acceptors(或者大部分),参数为num
    • acceptor在收到proposal req之后会根据num比较,拒绝所有num比已经回复promise小的proposal。同时需要返回已经accept的highest-numbered的value(如果有的话)
  2. phase2
    • proposer收到大多数acceptors的promise之后,开始发送accept request给所有acceptors。参数为proposal numer 和value。value是highest-numbered proposal among the responses,如果没有acceptors没有返回value的话,则可以任意选择,说明之前没有accept的提案。
    • acceptor收到accept request之后,和之前一样比较proposal num,只有比之前promise的num大才会接受

所以acceptor需要持久化 可以允许返回promise的最小proposal number,和accepted proposal number和对应的value。

Reference

[1] Paxos made simple

[2] Implementing Replicated Logs with Paxos. John Ousterhout and Diego Ongaro