> For the complete documentation index, see [llms.txt](https://yangsx95.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://yangsx95.gitbook.io/notes/distributed/yi-zhi-xing/gong-shi-suan-fa.md).

# 共识算法

## 拜占庭将军问题

拜占庭将军问题是 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   | 中                   | 中 |