共识算法

拜占庭将军问题

拜占庭将军问题是 Leslie Lamport 在《The Byzantine Generals Problem》论文中提出的分布式对等网络通信容错问题，为分布式领域中最复杂、最严格的容错模型；拜占庭将军问题讨论的是允许存在少数节点作恶（消息可能被伪造）场景下的如何达成共识问题。

拜占庭是古代东罗马帝国的首都，由于地域宽广，守卫边境的多个将军（类比系统中的多个节点）需要通过信使来传递消息，达成某些一致决定。但由于将军中可能存在叛徒（类比系统中节点出错），这些叛徒将向不同的将军发送不同的消息，试图干扰共识的达成；拜占庭问题即讨论在此情况下，如何让忠诚的将军们能达成行动的一致。

例如：有9位将军投票，其中1名叛徒。8名忠诚的将军中出现了4人投进攻，4人投撤离的情况。这时候叛徒可能故意给4名投进攻的将领送信表示投票进攻，而给4名投撤离的将领送信表示投撤离。这样一来在4名投进攻的将领看来，投票结果是5人投进攻，从而发起进攻；而在4名投撤离的将军看来则是5人投撤离，军队的一致协同就遭到了破坏。（注意，节点之间通讯投票，不用让国王决定，目的是将军们同时进攻同时撤离）。

更一般地，在已知有 N 个将军谋反的情况下，其余 M 个忠诚的将军在不受叛徒的影响下能否达成共 识？有什么样的前提条件，该如何达成共识？这就是拜占庭将军问题。

如果一个共识算法在一定条件下能够解决拜占庭将军问题，那我们就称这个算法是「拜占庭容错 Byzantine Fault Tolerance（BFT）」算法。反之如果一个共识算法无法接受任何一个节点作恶，那 它就被称为「非拜占庭容错 Crash Fault Tolerance (CFT)」算法。

可以通过简单穷举发现，二忠一叛是无法达成共识的，这个结论结合反证法可证明，拜占庭容错算法 要求叛徒的比例必须低于 1/3。

在该模型下的系统不会对集群中的节点做任何的限制，它们可以向其他节点发送随机数据、错误数据，也可以选择不响应其他节点的请求，这些无法预测的行为使得容错这一问题变得更加复杂。在分布式场景下，拜占庭需求并不多见，一般存在于容易匿名参与的系统（如虚拟币），或者伪造信息会造成巨大损失的情况（如金融系统）。

什么是共识

一致性：含义比共识宽泛，在不同场景（基于事务的数据库、分布式系统等）下意义不同。在分布式系统场景下，一致性指的是多个副本对外呈现的状态。如之前提到的顺序一致性、线性一致性，描述了多节点对数据状态的共同维护能力。

共识：特指在分布式系统中多个节点之间对某个事情达成一致看法的过程。需注意达成某种共识并不意味着就保障了一致性。

共识算法解决了什么问题

共识算法解决的是分布式系统对某个提案（Proposal），大部分节点达成一致意见的过程。提案泛指多个事件发生的顺序、某个键对应的值…对于分布式系而言，各个节点通常都是相同的确定性状态机模型（又称为状态机复制问题，State-Machine Replication），从相同初始状态开始接收相同顺序的指令，则可以保证相同的结果状态。

这里共识算法需要解决两个基本问题：

1. 如何提出一个待共识的提案（令牌传递、随机选取…）

2. 如何让多个节点对提案达成共识（投票、规则验证…）

现实网络环境中存在各种各样的问题，在分布式环境下，共识算法还需要解决如通信问题（网络中断、分区）、节点故障、消息伪造…

共识算法的分类

根据是否允许拜占庭错误（伪造信息恶意响应）的情况，共识算法分为

• Crash Fault Tolerance 崩溃容错 (CFT)

  • 非拜占庭错误共识算法

  • 例如，Paxos、Raft、ZAB…

• Byzantine Fault Tolerance（BFT）

  • PBFT为代表的确定性系列算法

  • 能容忍拜占庭错误的共识算法

  • 例如，PoW算法

常见的共识算法列举

拜占庭容错	一致性	性能	可用性（能容忍多大比例的节点出现故障）
两阶段提交 2PC	否	强一致性	低	低
TCC(try-confirm-cancel)	否	最终一致性	低	低
Paxos	否	强一致性	中	中
ZAB	否	最终一致性	中	中
Raft	否	强一致性	中	中
Gossip	否	最终一致性	高	高
Quorum NWR	否	强一致性	中	中
PBFT	是	N/A	低	中
PoW	是	N/A	低	中
PoS	是	N/A	低	中
PoH	是	N/A	中	中