wxya（个人网站）一致性与共识b
两将军问题 | 拜占庭将军问题与拜占庭容错
两个将军问题 很形象地描述了非拜占庭问题：有两个军队，每个军队都由不同的将领率领，他们袭击一座城市，但只有两军共同发起攻击才能获胜，不幸的他们要派信使协商攻击时间时必须经过敌军阵地并有可能被抓获从而导致消息无法传递到友军。两个将军问题就是讨论在这种情况下如何达成一致的问题。
我们可以设想：将军A派信使1通知将军B，告知一同进攻的时间
- 信使1被抓，导致将军A发起攻击时将军B的军队还在原地，即无法达成一致
- 将军B收到了信使1的通知，但它要确保将军A知道自己收到了，否则可能会是自己发起攻击了而将军A以为自己没有收到而原地不动，所以将军B要派信使2去告知将军A自己确认收到了，但这过程信使2被抓，导致了无法达成一致
- 再往下，将军A收到了信使2的确认通知，但他还要让将军B知道自己收到确认，否则也会出现将军B以为将军A没有收到确认而待在原地，所以这里将军A又要再派信使1告知将军B自己收到确认了，但这又回到一开始，信使1可能被抓
- ……
常用共识算法
对于「非拜占庭容错 Crash Fault Tolerance (CFT)」的情况，已经存在不少经典的算法，包括 Paxos（1990 年）、Raft（2014 年）及其变种等。这类容错算法往往性能比较好，处理较快，容忍不超过一半的故障节点。
对于「拜占庭容错 Byzantine Fault Tolerance（BFT）」的情况，目前有 PBFT（Practical Byzantine Fault Tolerance，1999 年）为代表的确定性系列算法、PoW（1999 年）为代表的概率算法等算法可选。确定性算法一旦达成共识就不可逆转，即共识是最终结果；而概率类算法的共识结果则是临时的，随着时间推移或某种强化，共识结果被推翻的概率越来越小，最终成为事实上结果。拜占庭类容错算法往往性能较差，容忍不超过 1/3 的故障节点。
此外，XFT（Cross Fault Tolerance，2015 年）等最近提出的改进算法可以提供类似 CFT 的处理响应速度，并能在大多数节点正常工作时提供 BFT 保障。Algorand 算法（2017 年）基于 PBFT 进行改进，通过引入可验证随机函数解决了提案选择的问题，理论上可以在容忍拜占庭错误的前提下实现更好的性能（1000+ TPS）。
注：实践中，对客户端来说要拿到共识结果需要自行验证，典型地，可访问足够多个服务节点来比对结果，确保获取结果的准确性。
常见共识算法列举如下：
ㅤ | 拜占庭容错 | 一致性 | 性能 | 可用性（能容忍多大比例的节点出现故障） |
两阶段提交 2PC | 否 | 强一致性 | 低 | 低 |
TCC(try-confirm-cancel) | 否 | 最终一致性 | 低 | 低 |
Paxos | 否 | 强一致性 | 中 | 中 |
ZAB | 否 | 最终一致性 | 中 | 中 |
Raft | 否 | 强一致性 | 中 | 中 |
Gossip | 否 | 最终一致性 | 高 | 高 |
Quorum NWR | 否 | 强一致性 | 中 | 中 |
PBFT | 是 | N/A | 低 | 中 |
PoW | 是 | N/A | 低 | 中 |
PoS | 是 | N/A | 低 | 中 |
是 | N/A | 中 | 中 |
资料
Loading...