Paxos 案例

时间:2024-07-16 11:27:21
案例:投票选出最新的报价
单个Processor的情况

Processor:小明

Acceptor:审批人1;审批人2;审批人3;

Learner:记录者

业务背景:选出最新的报价

步骤:

  1. 小明:发起两个prepare请求,里面带一个编号,分别给审批人1和审批人2。这一步的目的是看看是否能得到审批人的认可。
  2. 审批人:如果之前没有接收到prepare请求或者已接收到的prepare请求的编号小于当前prepare请求的编号,那么就承诺此编号1。
  3. 小明:获取到多数(超过半数)审批人的认可后,分别发起accept请求,并且附带最新报价“1.5”。
  4. 审批人:判断编号accept请求中的编号(1)是否小于已承诺的编号(1)

        如果小于:则放弃accept请求中的值

                1. 如果大(等)于:同意最新报价“1.5”,并且发送给小明和记录者

                2. 记录者:记录最新报价“1.5”

多个Processor的情况

Processor:小明;小红;

Acceptor:审批人1;审批人2;审批人3;

Learner:记录者

业务背景:选出最新的报价

步骤:

1. 小明:发起prepare请求,附带编号:1

        1.1 发给审批人1:审批人1发现自己从没有接收过请求,所以承认了编号:1,(并承诺再也不会接受编号小于1的请求)

        1.2 发给审批人2:审批人2发现自己已经接收了编号为2的请求,因此不会接受编号为1的请求,因为:2>1

2. 小红:发起prepare请求,附带编号:2

        2.1 发给审批人2:审批人2发现自己从没有接收过请求,所以承认了编号:2(并承诺再也不会接受编号小于2的请求)

        2.2 发给审批人3:审批人3发现自己从没有接收过请求,所以承认了编号:2(并承诺再也不会接受编号小于2的请求)

3. 小红:发起accept请求,附带值:2.5

        3.1 发给审批人2:审批人2并未发现编号大于2的请求,因此接受值:2.5

        3.2 发给审批人3:审批人3并未发现编号大于2的请求,因此接受值:2.5

4. 小明:发起prepare请求,附带编号:3

        4.1 发给审批人1:审批人1发现自己已经接收过请求,但是之前接收到的编号(1)小于当前的编号(3),因此承诺编号:3

        4.2 发给审批人2:审批人1发现自己已经接收过请求,但是之前接收到的编号(2)小于当前的编号(3),3>2,因此承诺编号:3;

5. 小明:发起accept请求,附带值:5.5

        5.1 发给审批人1:审批人1并未发现编号大于3的请求,因此接受值:5.5

        5.2 发给审批人2:审批人2并未发现编号大于3的请求,因此接受值:5.5

最后

1. 审批人1:5.5

2. 审批人2:5.5

3. 审批人3:2.5

由于多数原则,返回值:5.5

死锁的情况(multi-paxos)

Processor:小明;小红;

Acceptor:审批人1;审批人2;审批人3;

Learner:记录者

步骤:

  1. 小明发起prepare请求给审批人1和审批人2,附带编码:1,并得到审批人的承诺
  2. 小红发起prepare请求给审批人1和审批人2,附带编码:2,并得到审批人的承诺
  3. 小明发起accept请求给审批人1和审批人2,附带值:1.5,被审批人忽略,因为:2>1
  4. 小明发起prepare请求给审批人1和审批人2,附带编码:3,并得到审批人的承诺
  5. 小明发起accept请求给审批人1和审批人2,附带值:2.5,被审批人忽略,因为:3>2
  6. ... ... 然后不断循环,形成死锁