干货分享，忘掉你微信里那些没意义的3点钟区块链社群吧！

WWW.BCFANS.COM 区块链导航专家

2018年春节前后，除了流感，似乎还有一场“传染”。感染者除了精神亢奋，身体还算健康。典型症状是，对着一个叫“区块链”的东西胡言乱语，根本停不下来。

如果你真的对区块链感兴趣，就多研究区块链，而不是买币。区块链是很多技术的混杂，一定不要混在一块，而跟具体区块链技术相关的要素主要有三点：

第一点：共识算法。

第二点：账户模型。

第三点：智能合约。

有人开玩笑说共识算法解决的是 “今天中午吃什么” 的问题？这是一个很贴切的描述。

所谓的分布式共识算法——我有这么多分布式的节点，彼此之间需要网络通信对某个状态达成共识，但彼此之间又不信任。这跟我们在互联网应用做分布式系统有很大的区别。传统的分布式系统节点都部署在自己的机房里，不需要考虑拜占庭错误，你需要考虑的只有丢包、超时、机器 crash 这些问题，用 Paxos 和 Raft 一类的算法就可以了。

今天我们就来浅析一下Paxos算法。

分布式一致性算法

Paxos算法浅析

节点通信存在两种模式，内存共享和消息传递。Paxos是一种基于消息传递的分布式一致性算法，由Leslie Lamport（莱斯利·兰伯特）于1990提出。是目前公认的解决分布式一致性问题的最有效算法之一。

Paxos算法产生的背景

Paxos算法是莱斯利·兰伯特于1990年提出的一种基于消息传递的一致性算法。由于算法难以理解起初并没有引起人们的重视，使Lamport在八年后重新发表到TOCS上。即便如此Paxos算法还是没有得到重视，2001年Lamport用可读性比较强的叙述性语言给出算法描述。可见Lamport对Paxos算法情有独钟。近几年Paxos算法的普遍使用也证明它在分布式一致性算法中的重要地位。06年google的三篇论文初现“云”的端倪，其中的chubby lock服务使用Paxos作为chubby cell中的一致性算法，Paxos的人气从此一路狂飙。

Paxos算法要解决的问题

Paxos 算法是分布式一致性算法，用来解决一个在异步通信的分布式系统如何就某个值(决议)达成一致的问题。此处异步通信是指，消息在网络传输过程中存在丢失、超时、乱序现象。

Paxos算法的前置假设是在节点通信中不存在消息被篡改的问题（即不存在拜占庭将军问题）。

Paxos算法的应用场景

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

概念术语

Proposal：为了就某一个值达成一致而发起的提案，包括提案编号和提案的值。

Proposer：提案发起者，为了就某一个值达成一致，Proposer可以以任意速度、发起任意数量的提案，可以停止或重启。

Acceptor：提案批准者，负责处理接收到的提案，响应、作出承诺、或批准提案。

Learner：提案学习者，可以从Acceptor处获取已被批准的提案。

Paxos算法保证以下三点

1. 只有被提出的提案才能被选定。

2. 只有一个值最终被选定。

3. 如果某个进程认为某个提案被选定了，那么这个提案必须是真的被选定的那个。

约定

Paxos需要遵循如下约定：

1.一个Acceptor必须批准它收到的第一个提案。

2.如果编号为n的提案被批准了，那么所有编号大于n的提案，其值必须与编号为n的提案的值相同。

Paxos算法的两个阶段

阶段一（prepare阶段）：

(a) Proposer选择一个提案编号N，然后向半数以上的Acceptor发送编号为N的Prepare请求。

(b) 如果一个Acceptor收到一个编号为N的Prepare请求，且N大于该Acceptor已经响应过的所有Prepare请求的编号，那么它就会将它已经接受过的编号最大的提案（如果有的话）作为响应反馈给Proposer，同时该Acceptor承诺不再接受任何编号小于N的提案。

阶段二（accept阶段）：

(a) 如果Proposer收到半数以上Acceptor对其发出的编号为N的Prepare请求的响应，那么它就会发送一个针对[N,V]提案的Accept请求给半数以上的Acceptor。注意：V就是收到的响应中编号最大的提案的value，如果响应中不包含任何提案，那么V就由Proposer自己决定。

(b) 如果Acceptor收到一个针对编号为N的提案的Accept请求，只要该Acceptor没有对编号大于N的Prepare请求做出过响应，它就接受该提案。

Learner

一旦Acceptor批准了某个提案，即将该提案发给所有的Learner。为了避免大量通信，Acceptor也可以将批准的提案，发给主Learner，由主Learner分发给其他Learner。考虑到主Learner单点问题，也可以考虑Acceptor将批准的提案，发给主Learner组，由主Learner组分发给其他Learner。

总结

Paxos算法是基于消息传递且具有高度容错特性的一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一。Paxos算法还有其他的优化算法，比如multi-paxos、cheap-paxos、fast-paxso等，在工程实践上的Raft算法其实也是Paxos算法的变种。

优点：Paxos算法是基于消息传递且具有高度容错特性的一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一。

缺点：难以理解、工程实现困难。

加入BCfans电报群，结识区块链爱好者

https://t.me/bcfans