分布式一致性协议之Paxos算法

目录

前置知识

问题描述

提案的选定

推导过程

Proposer生成提案

Accpetor批准提案

算法流程

之前文章介绍了2PC和3PC一致性协议，本文将继续介绍另一个Paxos算法

对于分布式一致性算法，有两个最重要的属性：

1. 安全性：指那些需要保证永远都不会发生的事情
2. 活性：指那些最终一定会发生的事情

假设有一组可以提出提案的进程集合，对于一致性算法，要求：

1. 这些提案最终只有一个被选定
2. 当一个提案被选定后，进程可以获取被选定的提案信息

对于Paxos，安全性要求有：

1. 只有被提出提案才能被选定
2. 只有一个值会被选定
3. 如果某个进程认为某个提案被选定了，那这个提案必须真的是被选定的那个

活性要求是：保证最终有一个提案被选定

三种参与角色：

Proposer：提案提出者

Acceptor：提案接受批准者

Learner：只获取最终被批准的提案

提案的选定

规则：Proposer向一个Acceptor集合发送提案，集合中的每个Acceptor都可能会accept（批准）该提案，当有足够多的Acceptor批准该提案的时候，就可以认为这个提案被选定了。

这里的足够多怎么界定呢？

这个“足够多”的集合是所有Acceptor的一个子集，这个可以包含Acceptor集合中的大多数成员，因为任意两个包含大多数Acceptor的子集至少有一个公共成员。（实际就是超过一半的Acceptor批准）

推导过程

在没有失败和消息丢失的情况下，如果我们希望即使在只有一个提案被提出的情况下，仍然可以选定一个提案，这就暗示如下需求：

P1:一个Acceptor必须批准它收到的第一个提案

但这个条件存在问题，即多个提案被不同Proposer同时提出，无法最终确定一个提案

还会出现不同提案被选定的Acceptor集合数量相同，也无法最终确定一个提案

因此，需要在P1的基础上，在加“一个Acceptor必须能够批准不止一个提案”的条件。

这里将每个提案抽象成一个“【编号，Value】”的结构

• 编号是全局唯一的，可以唯一标识一个被Acceptor批准的提案
• 当具有某个Value值的提案被一半以上的Acceptor批准后，我们就认为这个提案被选定了

 我们约定：虽然允许多个提案被选定，但是必须保证被选定的提案都具有相同的Value值，即

P2:如果【M0，V0】的提案被选定了，那么所有编号比M0高的且被选定的提案，Value值都是V0

这里对于P2的证明需要用到数学归纳法，这里不做详述

Proposer生成提案

由于P2条件，Proposer在产生一个编号为Mn的提案时，必须知道当前某一个将要或者已经被半数以上的Acceptor批准的编号小于Mn但最大的提案。并且 Proposer会要求所有的Acceptor都不能再批准任何编号小于Mn的提案。

Prepare请求

Proposer选择一个新的提案编号Mn，然后向某个Acceptor集合发送请求，要求其作出如下响应：

1. 承诺不在接受任何编号小于Mn的提案
2. 如果此Acceptor批准过提案，就返回已经批准的编号小于Mn但最大的提案的Value值

Accept请求

如果Proposer收到一半以上Acceptor的响应结果，那么它就可以产生【Mn，Vn】的提案，这里的Vn是所有响应中编号最大提案的Vaule值，如果大多数Acceptor没有批准过提案，则Vn任意。之后将该提案再次发送给某个Acceptor集合，期望获得批准。

Accpetor批准提案

收到Prepare请求

Acceptor可以在任何时候响应一个prepare请求

收到Accept请求

在不违背承诺的前提下，可以任意响应Accept请求

即一个Acceptor只要未响应过任何编号大于Mn的Prepare请求，则它可以接受这个编号为Mn的提案

算法流程

阶段一
1. Proposer选择一个提案编号Mn，然后向超过半数的Acceptor子集发送编号为Mn的Prepare请求。
2.如果一个Acceptor收到一个编号为Mn的Prepare请求，且编号Mn大于该Acceptor已经响应的所有Prepare请求的编号，那么它就会将它已经批准过的最大编号的提案作为响应反馈给Proposer，同时该Acceptor会承诺不会再批准任何编号小于Mn的提案。

阶段二

1.如果Proposer收到来自半数以上的Acceptor对于其发出的编号为Mn的Prepare请求的响应，那么它就会发送一个【Mn，Vn】提案的Accept请求给Acceptor。Vn的值就是收到的响应中编号最大的提案的值，如果响应中不包含任何提案，那么它就是任意值。
2.如果Acceptor收到这个针对【Mn，Vn】提案的Accept请求，只要该Acceptor尚未对编号大于Mn的Prepare请求做出响应，它就可以通过这个提案。