paxos笔记

发表于

paxos一致性算法笔记

basic paxos算法描述来源

basic paxos

代码描述来源

1
2
3
4
5
6
 proposer        acceptors
     prepare(n) ->
  <- prepare_ok(n, n_a, v_a)
     accept(n, v') ->
  <- accept_ok(n)
     decided(v') ->

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
proposer(v):
  choose n, unique and higher than any n seen so far
  send prepare(n) to all servers including self
  if prepare_ok(n, n_a, v_a) from majority:
    v' = v_a with highest n_a; choose own v otherwise
    send accept(n, v') to all
    if accept_ok(n) from majority:
      send decided(v') to all

acceptor state:
  must persist across reboots
  n_p (highest prepare seen)
  n_a, v_a (highest accept seen)

acceptor's prepare(n) handler:
  if n > n_p
    n_p = n
    reply prepare_ok(n, n_a, v_a)
  else
    reply prepare_reject

acceptor's accept(n, v) handler:
  if n >= n_p
    n_p = n
    n_a = n
    v_a = v
    reply accept_ok(n)
  else
    reply accept_reject

当v_a/n_a达到大多数时，则达成共识，如果只是v_a呢？

如果只有v_a是不够，例子

1
2
3
S1: p10  a10X               p12
S2: p10          p11  a11Y  
S3: p10          p11        p12   a12X

这个例子里X达到大多数了，存在一个反例，使得最后Y达成共识：

1
2
3
S1: p10  a10X               p12   p13   a13Y
S2: p10          p11  a11Y        p13   a13Y
S3: p10          p11        p12   a12X

为什么v_a/n_a达到大多数，这个值就达成共识？

比如a11v达到大多数了，大多数的机器上都有a11v， 那么之后的p，为了达到大多数，一定会发给其中一台，并得到回复11v， 那么11一定是最大的吗？是否存在一台机器有更大的，比如a12w

为了达到a12w，说明p12达到了大多数，那么肯定有台机器曾经都收到了p12和a11，并且都返回成功了

  1. p12 a11v 的顺序

由于先收到p12，所以a11会被拒掉，和假设矛盾，这种情况不存在

  1. a11v p12的顺序

p12将返回11v，那么p12的值w=v，继续推广，即使有a13z，那么z=w=v，说明即使存在更大的p，它的值也是v

为什么需要Prepare？

  1. 阻挡旧的proposal：旧的proposal在accept时失败
  2. 找到（可能）已经chosen的值

后记

basic paxos的描述非常简洁，但效率不高，达成共识需要两个环节， 而且chosen的值首先proposer知道，还需要推给acceptor，又多了一个环节。 也有很多基于basic paxos的变形，multi-paxos、epaxos，不过工业实现上很难写对（正确性）