区块链核心算法之Paxos 算法

首先看一下libpaxos3的代码：

 第一步获取和编译LibPaxos3所需的基本步骤：

运行示例

​什么是Paxos算法

Paxos算法解决的问题是在一个可能发生消息可能会延迟、丢失、重复的分布式系统中如何就某个值达成一致，保证不论发生以上任何异常，都不会破坏决议的一致性。

一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。

一个通用的一致性算法可以应用在许多场景中，是分布式计算中的重要问题。 节点通信存在两种模型：共享内存和消息传递。Paxos算法就是一种基于消息传递模型的一致性算法。

Paxos算法的目的

Paxos算法的目的是为了解决分布式环境下一致性的问题。多个节点并发操纵数据，如何保证在读写过程中数据的一致性，并且解决方案要能适应分布式环境下的不可靠性（系统如何就一个值达到统一）。

Paxos算法中，可分为4种角色：

• Proposer：提议发起者

处理客户端请求，将客户端的请求发送到集群中，以便决定这个值是否可以被批准。

• Acceptor：提议批准者

负责处理接收到的提议，他们的回复就是一次投票。会存储一些状态来决定是否接收一个值。

• Client：产生议题者

Proposer就像Client的使者，由Proposer使者拿着Client的议题去向Acceptor提议，让Acceptor来决策。

• Learner：最终决策学习者

最终学习的目标是Acceptor们最终接受了什么议题？

Paxos算法的原理

例如：公司商定年会举办的地点，每个人都可以提出建议。在现实环境中我们可以在一个会议室共同讨论或在微信群中讨论（基于内存共享方式）；但在基于消息传递的分布式环境中每个人只能通过手机短信与其它人通过。如何在这种会延迟、丢失的环境中确定一个年会举办地点。

Paxos算法是这样解决这个问题：

1. 每个人都可以提出建议、同意建议、接受建议
2. 少数服从多数。只要建议被多数人同意即可确定该建议。

于是确定以下讨论方式：

1）只有被提出来的建议才能被大家同意。

2）最终只能确定一个建议。

3）如果某个人认为大家同意了某 个建议，那么这个建议必须真的是被大家同意的。

算法推论：

情况一：

如果只有一个人提出建议怎么办？如果只有一个建议被提出来那么大家必须同这个建议，因为如果不同意这个建议就无法确定一个年会举办地点。

所以得出这样的结论：

P1:每一个人必须同意他收到的第一个建议。

基于这样的结论会出现以下问题：

张三给王五发短信说：我建议去上海举办年会！

王五给李四发短信说：我建议去广州举办年会！

李四给张三发短信说：我建议去北京举办年会！

根据P1：每个人必须同意他收到的第一个建议，那么张三、李四、王五最终获得的信息是不一致的。

所以再次规定：一个提议必须被大多数人同意才能生效。

那么说明一个人可以同时同意多个建议，如果一个人可以同时同意多个建议最终可能出现拜占庭将军问题导致最终结果不一致。（例如：张三同意到北京举办也同意到广州举办，那么李四将获得2票一票自己的，一票张三的。他会认为自己获得多数人支持所以就确定最终是到北京举办，同理王五也会同时获得2票，也认为大家最终决定到广州举办）

所以要避免出现这种问题，某个人只要同意的多个提议中的内容相同（公司举办的地址）就不会出现这种问题。

最终协商结果是有2票是到同一个地方，这样就可以确认最终举办地！

那么就会引出这样的一个结论：

P2:一旦同意某个建议，那么之后同意的建议中提议公司举办年会的地址必须一致。

问题出来了：如何确定什么是“之前”，什么 是“之后”所以必须为提议分配一个编号，在提议之间建立一个全序关系。

情况二：

当张三、李四、王五三个人确定最终到郑州举办年会后。赵六、孙七2人由于手机没电，没收到通知，当他们2人开机后赵六给孙七发短信提议到海南举办，这个提议是孙七开机后第一次收到的提议，根据P1原则，他必须同意他接收到的第一个提议，所以孙七同意到海南举行年会。但这样就会导致孙七与张三、李四、王五他们确定的举办地点不一致。

为了避免出现以上问题。对P2进行具体说明：

P2a:一旦一个提议被大家同意，那么之后的人再次同意的提议中的公司举办年会的地址必须一致。

也就是说，孙七在开机后同意的第一个提议必须是“到郑州举办”才不会出现信息不一致的现象。但孙七开机后必须得接受第一个提议（P1原则），并且无法干涉提议中的内容（公司举办年会的地址）。所以最好的办法通过某种方式让赵六的提议中的内容与张三、李四同意的地址相同（到郑州举行）。这样孙七同意的第一个提议就是“到郑州举办”

我们再次对P2a进行修改：

P2b:一旦一个提议被大家同意，那么之后的人再次提议，提议中的公司举办年会的地址必须跟之前其它人解决的地址一致。    

如何让刚开机的赵六提议的内容必须与张三、李四、王五讨论出来的一致（到郑州举行）？

我们继续对P2b进行强化修改：

P2c:如果有一个编号为N的提议具有V(提议的内容)，那么存在一个多数派，要么他们中所有人都没有同意编号小于N的任何提议，要么他们已经同意的所有编号小于N的提案中编号最大的那个提案具有V。

要满足P2c的要求，提议人在提议之前，首先要和多数人通信并获得他们进行的最后一次同意的提议。之后根据反馈的信息决定这次提议的内容，形成提议开始投票！

所以整个投票决议分两个阶段：

准备阶段

1、提议人选择一个编号N，并将准备信息发送给多数人。

2、如果收信人收到准备消息后，如果提议的编号大于它已经回复的所有准备信息。那么收信人将自己上次接受的提议内容回复给提议人，并承诺不再回复小于N的提议。

1.同意阶段

1）当一个提议人收到多数人反馈的信息后，就进入同意阶段。它要向反馈给它信息的人再次发送一个请同意该提议的请求。包含编号N和根据P2C决定的提议内容（如果回复中没有反馈他们已经接受过的提议内容，则可以自由决定提议内容）

2）在不违背向其它人承诺的前提下，收到该提议请求后立即同意该请求。

举例说明一下：

假设：只有User1、User2、User3 三个人决定1+1等于几！

2.准备阶段

1.User1提案编号为1 并发送给User2和User3。

因User2和User3根据P2c它们并没有接受过小于编号为1的提案。所以它们可以接受该提议，并反馈给User1不再接受小于编号1的提案。这时User1收到多数人的回复，将进入第2阶段。（如果收到的回复并不能形成多数人，那么将再次进入阶段1）

2.User2提案编号为2 ；并发送给User1和User3。

因User1第一次收到提案，并且根据P2C它并没有同意过小于编号为2的提议，所以它可以接受该提议。User3由于接受过User1编号为1的提案，但User2的提案编号2>1所以User3也可以同意User2的提议，并反馈不再接受小于2的提议。User2也收到多数人的回复，将进行第2阶段。

3.User3提案编号为3；并发送给user1和user2 。

因user1收到user3编号为3的提案>user2编号为2的提案，所以接受user3的提案。

因user2收到User3编号为3的提案>user1 编号为1的提案，所以接受user3的提案。

至些user3也收到多数人回复，将进行第2阶段。

阶段2：

1.user1发送编号为1的提议，提议内容为：1+1=1；并发送给user2和User3。

由于user2已经声明不再接受小于3的提案，所以拒绝user1的提案。

由于User3已经声明不再接受小于2的提案，所以同样拒绝User1的提案。

User1提议被多数人拒绝，再次进入阶段1。

2.user2发送编号为2的提议，提议内容为：1+1=2；并发送给User1和User3

由于User1已经声明不再接受小于3的提案，所以拒绝user2的提议。

由于User3已经声明不再接受小于2的提案，该提案编号=2所以user3同意User2的提议。

但User2并没有获得多数人的同意，所以同样进行阶段1.

3.User3发送编号为3的提议，提议内容为：1+1=3；并发送给User1和User2;

由于user1声明不再接受小于3的提案，所以同意User3的提议。

由于 user2声明不再接受小于3的提案，所以同意User3的提议。

至此最终User3可以获得多数人的同意。

Paxos算法图解：

在实现环境中会通过一次提议，选择一个Leader。后续所有的提议都只能由Leader提出。

原来paxos算法里的角色都是这样的不靠谱，不过没关系，结果靠谱就可以了。该算法就是为了追求结果的一致性。