本篇咱们会以拜占庭问题为引，来议论一下关于分布式体系中一同性的问题。
拜占庭问题
拜占庭问题（Byzantine failures）也叫拜占庭将军问题，是由莱斯利兰伯特提出的点对点通讯中的基本问题。意义是在存在音讯丢掉的不牢靠信道上企图经过音讯传递的方法到达一同性是不或许的。
拜占庭问题其本质是一个协议问题，拜占庭帝国戎行的将军们有必要全体一同抉择是否进犯某一支敌军。问题是这些将军在地理上是分隔开来的，并且将军中存在叛徒。叛徒能够恣意举动以到达以下方针：欺骗某些将军采取进攻举动；促进一个不是一切将军都赞同的抉择，假如将军们不希望进攻时促进进攻举动；或许迷惑某些将军，使他们无法做出抉择。假如叛徒到达这些意图之一，则任何进犯举动的成果都是要失利的，只要完全到达一同的尽力才干获得胜利。这时分，在已知有成员谋反的状况下，其他忠诚的将军在不受叛徒的影响下怎么才干到达一同的协议，而拜占庭问题也就此形成。
拜占庭问题能够这样描绘，戎行的几个师驻扎在敌郊外, 每个师都由各自的将军指挥。将军们只能经过信使相互交流，在调查敌情之后，他们有必要制定一个一同的举动计划，如 进攻(Attack) 或许 撤离(Retreat) ，且只要当半数以上的将军一同建议进攻时才干取得胜利。
当三个将军都忠诚时，能够经过投票确定一同的举动计划，图2展现了一种场景，即 General A、B 经过调查敌军军情并结合本身状况判别能够建议进犯，而 General C经过调查敌军军情并结合本身状况判别应当撤离。终究三个将军经过投票表决得到成果为 进攻:撤离 = 2:1，所以将一同建议进攻取得胜利。关于三个将军，每个将军都能履行两种抉择计划（进攻或撤离）的状况下，共存在 6 种不同的场景，图2 是其中一种, 关于其他 5 种场景可简略地推得，经过投票三个将军都将到达一同的举动计划。
当三个将军中存在一个叛徒时，就有或许打乱正常当作战计划。比方图3，当 General C 为叛徒时，他给 General A 和 General B 发送了不同的音讯，在这种场景下 General A 经过投票得到 进攻:撤离 = 1:2，终究将做出撤离当举动计划，General B 经过投票得到 进攻:撤离 = 2:1，终究将作出进攻的举动计划。成果只要General B建议了进攻并战胜。
事实上，关于三个将军中存在一个叛徒的场景，想要总能到达一同的举动计划是不或许的。详细的证明可参看Leslie Lamport的论文。此外，论文中给出了一个愈加普适的定论：假如存在 m 个叛将, 那么至少需求 3m+1 个将军, 才干终究到达一同的举动计划。当然在这篇论文中也给出了解决计划，分别是口信音讯型解决计划（A solution with oral message）和签名音讯型解决计划（A solution with signed message），感兴趣咱们能够去 这篇文章 看看，我这儿不再胪陈。
共同与一同性
上面咱们提到，拜占庭是一个协议共同问题，也便是说让大都人到达一同的意见，即少数人服从大都人。这一术语许多时分会与一同性（Consistency）放在一同评论，而二者的意义并不完全相同。
一同性
一同性（Consistency），早期也叫（Agreement），在分布式体系范畴中是指关于多个服务节点，给定一系列操作，在约好协议的确保下，使得它们对处理成果到达“某种程度”的协同。
理想状况（不考虑节点毛病）下，假如各个服务节点严格遵从相同的处理协议（即构成相同的状况机逻辑），则在给定相同的初始状况和输入序列时，能够确保处理进程中的每个进程的履行成果都相同。因而，传统分布式体系中评论一同性，往往是指在外部恣意建议恳求（如向多个节点发送不同恳求）的状况下，确保体系内大部分节点实践处理恳求序列的一同，即对恳求进行全局排序。
标准来看，分布式体系到达一同性的进程，应该满意：
– 可停止性（Termination）：一同的成果在有限时间内能完结； – 约同性（Agreement）：不同节点终究完结抉择计划的成果是相同的； – 合法性（Validity）：抉择计划的成果有必要是某个节点提出的提案。
要完结理想的严格一同性（Strict Consistency）价值很大。除非体系一切节点都不产生任何毛病，并且节点间通讯没有推迟，此刻整个体系等价于一台机器。实践上，完结较强的一同性要求同步操作，容错性差，一起会献身部分功能和可扩展性。实践体系往往会挑选不同强度的一同性，首要包含强一同性（Strong Consistency）和弱一同性（Weak Consistency）两大类。
一同性的意义比共同广泛，在不同场景（根据业务的数据库、分布式体系等）下意义不同。详细到分布式体系场景下，一同性指的是多个副本对外呈现的状况。如次序一同性、线性一同性，描绘了多节点对数据状况的一同维护才能。而共同，则特指在分布式体系中多个节点之间对某个作业（例如多个业务恳求，先履行谁？）到达一同观点的进程。因而，到达某种共同并不意味着就确保了一同性。
实践中，要确保体系满意不同程度的一同性，往往需求经过共同算法来到达。
共同算法
共同算法解决的是分布式体系对某个提案（Proposal），大部分节点到达一赞同见的进程。提案的意义在分布式体系中非常广泛，如多个事情产生的次序、某个键对应的值、谁是主节点……等等。能够以为任何能够到达一同的信息都是一个提案。
关于分布式体系来讲，各个节点一般都是相同的确定性状况机模型（又称为状况机复制问题，State-Machine Replication），从相同初始状况开端接纳相同次序的指令，则能够确保相同的成果状况。因而，体系中多个节点最关键的是对多个事情的次序进行共同，即排序。
注：计算机国际里选用的是典型的“大都人暴政”，足够简略、高效。
那么到达共同的基本问题就摆在了面前：
– 首要，怎么提出一个待共同的提案？如经过令牌传递、随机选取、权重比较、求解难题等； – 其次，怎么让多个节点对该提案到达共同（赞同或回绝），如投票、规则验证等。
理论上，假如分布式体系中各节点都能以非常“理想”的功能（瞬间响应、超高吞吐）安稳运行，节点之间通讯瞬时送达（如量子纠缠），则完结共同进程并不非常困难，简略地经过广播进行瞬时投票和应对即可。
惋惜的是，实践中这样的“理想”体系并不存在。不同节点之间通讯存在推迟（光速物理束缚、通讯处理推迟），并且恣意环节都或许存在毛病（体系规划越大，产生毛病或许性越高）。如通讯网络会产生中止、节点会产生毛病、乃至存在被入侵的节点故意伪造音讯，损坏正常的共同进程。
一般地，把呈现毛病（Crash 或 Fail-stop，即不响应）但不会伪造信息的状况称为“非拜占庭过错（Non-Byzantine Fault）”或“毛病过错（Crash Fault）”；伪造信息恶意响应的状况称为“拜占庭过错”（Byzantine Fault），对应节点为拜占庭节点。显然，后者场景中由于存在“捣乱者”更难到达共同。
此外，任何处理都需求本钱，共同也是如此。当存在必定信任前提（如接入节点都经过验证、节点功能安稳、安全确保很高）时，到达共同相对简单，共同功能也较高；反之在不可信的场景下，到达共同很难，需求支付较大本钱（如时间、经济、安全等），并且功能往往较差（如作业量证明算法）。
注：非拜占庭场景的典型例子是经过报数来计算人数，即使偶有抵触（如两人一起报一个数）也能很快解决；拜占庭场景的一个常见例子是“杀人游戏”，当参加者众多时很难快速到达共同。
当然，共同问题的最坏状况便是永久达不成共同，这也便是共同问题的理论界限，即使在网络通讯牢靠的状况下，一个可扩展的分布式体系的共同问题通用解法的下限是——没有下限（无解）。
这个定论，被成为“FLP不或许原理”。该原理及其重要，能够看做是分布式范畴里的“测不准原理”。
注：不光分布式体系范畴，实践上许多范畴都存在相似测不准原理的束缚，或许阐明国际本源就存在束缚。
FLP 不或许原理 与 CAP 原理
FLP不或许原理
FLP 不或许原理：在网络牢靠、但答应节点失效（即使只要一个）的最小化异步模型体系中，不存在一个能够解决一同性问题的确定性共同算法（No completely asynchronous consensus protocol can tolerate even a single unannounced process death）。
提出并证明该定理的论文《Impossibility of Distributed Consensus with One Faulty Process》是由 Fischer、Lynch 和 Patterson 三位科学家于 1985 年发表，该论文后来获得了 Dijkstra（便是创造最短路径算法的那位计算机科学家）奖。
FLP 不或许原理告知咱们，不要浪费时间去企图为异步分布式体系规划面向恣意场景的共同算法。
FLP 不或许原理实践上阐明关于答应节点失效状况下，朴实异步体系无法确保共同在有限时间内完结。即使关于非拜占庭过错的前提下，包含 Paxos、Raft 等算法也都存在无法到达共同的极点状况，只是在工程实践中这种状况呈现的概率很小。
那么，这是否意味着研讨共同算法压根没有意义？
不用如此悲观。学术研讨，往往考虑的是数学和物理意义上理想化的景象，许多时分实践国际要安稳得多（感谢这个国际如此鲁棒！）。比方，呈现了几回失利的场景，你重试几回说不定就成功了。遇事不决，直接重启！
科学告知你，什么是不或许的；工程则告知你，支付一些价值，能够把它变成可行。
这便是科学和工程不同的魅力。FLP 不或许原理告知咱们不用浪费时间去追求完美的共同计划，而要根据实践状况规划可行的工程计划。
那么，退一步讲，在支付一些价值的状况下，共同能做到多好？
回答这一问题的是另一个很知名的原理：CAP 原理。
注：科学告知你去赌场是愚笨的，由于终究总会输钱；工程则告知你，假如你愿意承受终究输钱的危险，中间说不定能偶尔小赢几笔呢！
CAP 原理
CAP 原理：分布式体系无法一起确保一同性（Consistency）、可用性（Availability）和分区容忍性（Partition），规划中往往需求弱化对某个特性的需求。该原理以为，分布式体系最多只能确保三项特性中的两项。
一同性、可用性和分区容忍性的详细意义如下：
– 一同性（Consistency）：任何业务应该都是原子的，一切副本上的状况都是业务成功提交后的成果，并保持强一同； – 可用性（Availability）：体系（非失利节点）能在有限时间内完结对操作恳求的应对； – 分区容忍性（Partition）：体系中的网络或许产生分区毛病（成为多个子网，乃至呈现节点上线和下线），即节点之间的通讯无法确保。而网络毛病不应该影响到体系正常服务。
比较直观的了解，当网络或许呈现分区时，体系时无法一起确保一同性和可用性的。要么，节点收到恳求后由于没有得到其它节点的承认而不应对（献身可用性），要么节点只能应对非一同的成果（献身一同性）。由于大部分时分网络被以为是牢靠的，因而体系能够供给一同牢靠的服务；当网络不牢靠时，体系要么献身掉一同性（大都），要么献身掉可用性。
留意：网络分区是或许存在的，呈现分区状况后很或许会导致产生“脑裂“现象。
关于不同的使用场景，咱们在规划体系时，也必定要考虑到对某项特性进行弱化（弱化而非抛弃）：
– 弱化一同性：对成果一同性不灵敏的使用，能够答应在新版本上线后过一段时间才终究更新成功，期间不确保一同性。比方网站的静态页面的内容，实时性较弱的查询类数据库等。简略分布式同步协议如 Gossip，以及 CouchDB 、Cassandra 数据库等，都为此规划。
– 弱化可用性：对成果一同性很灵敏的使用，例如银行取款机，当体系呈现毛病时会回绝服务。MongoDB、Redis、MapReduce 等均为此规划。Paxos、Raft 等共同算法，也是首要处理这种状况。
– 弱化分区容忍性：实践中，网络分区呈现概率较小，但很难完全避免。两阶段的提交算法，某些联系型数据库以及 Zookeeper 首要考虑了这种规划。实践中，网络能够经过双通道等机制增强牢靠性，完结高安稳的网络通讯。
ACID 准则与多阶段提交
ACID 准则
学习过数据库业务的同学对这几个字母应该不生疏，关于分布式体系的业务也是相同的，ACID 是用来描绘一同性的准则，其描绘了分布式数据库需求满意的一同性需求，一起答应支付可用性的价值。
– 原子性（Atomicity）：每次业务都是原子的，业务包含的一切操作，要么全部成功，要么全部失利，一旦有失利，则需求回退到履行业务之前； – 一同性（Consistency）：数据库的状况在业务履行前后的状况是一同和完好的，无中间状况，即只能处于成功业务提交后的状况； – 阻隔型（Isolation）：各种业务能够并发履行，但彼此之间相互不影响。依照标准 SQL 标准，从弱到强能够分为读未提交、读已提交、可重复读和串行化。 – 耐久性（Durability）：状况的改变是耐久的，不会失效。一旦某个业务提交，则它形成的状况变更便是永久的。
与 ACID 相对的一个准则是 eBay 技能专家 Dan Pritchett 提出的 BASE（Basic Availability，Soft-state，Eventual Consistency）准则。BASE 准则面向大型高可用分布式体系，建议献身掉对强一同性的追求，而完结终究一同性，来换取必定的可用性。
注：ACID 和 BASE 在英文平分别是“酸”和“碱”，看似敌对，实则是对 CAP 三特性的不同取舍。
两阶段提交
关于分布式业务一同性研讨成果包含闻名的两阶段提交算法（Two-phase Commit 2PC）和三阶段提交算法（Three-phase Commit，3PC）。
两阶段提交算法最早由 Jim Gray 于 1979 年在论文《Notes on Database Operating Systems》中提出。其基本思想非常简略，既然在分布式场景下，直接提交业务或许呈现各种毛病和抵触，那么可将其分解为预提交和正式提交两个阶段，躲避危险。
– 预提交（PreCommit）：和谐者（Coordinator）建议履行某个业务的履行并等候成果。各参加者（Participant）履行业务但不提交，反应是否能完结，并堵塞等候和谐者指令； – 正式提交（DoCommit）：和谐者假如得到一切参加者的成功答复，则宣布正式提交指令，不然宣布状况回滚指令。
两阶段提交算法由于其简略简单完结的优点，在联系型数据库等体系中被广泛使用。当然其缺点也很明显：
– 第一阶段，各参加者同步堵塞等候时，无法处理恳求，会导致体系功能较差； – 存在和谐者单点毛病问题，最坏状况下和谐者纵使在第二阶段毛病，无法完结提交。 – 或许产生数据不一同的状况。例如第二个阶段时，和谐者将正式提交恳求发给部分参加者后产生毛病。
三阶段提交
三阶段提交算法针对两阶段提交算法第一阶段中参加者堵塞问题进行了优化。详细来说，将预提交阶段进一步拆成两个进程：问询提交和预提交。
完好进程如下：
– 问询提交（CanCommit）：和谐者问询参加者是否能进行某个业务的提交。参加者需求返回答复是否准备好，但无需履行提交，也无需堵塞。这就避免呈现参加者被堵塞的状况； – 预提交（PreCommit）：和谐者检查收集到的答复，假如全部为真，则建议履行业务恳求。各参加参加者（Participant）需求履行业务但不提交，并反应能否完结。留意此刻阐明一切参加者都现已处于准备好状况。； – 正式提交（DoCommit）：和谐者假如得到一切参加者的成功答复，则宣布正式提交恳求，不然宣布状况回滚指令。本阶段时，假如参加者一直收不到恳求，则超时后持续提交。
三阶段提交首要解决了堵塞问题和和谐者单点毛病问题。第三阶段时，假如参加者无法及时收到和谐者的音讯，能够在超时后自动进行提交。可是当和谐者宣布的回滚音讯未被部分参加者收到时，会呈现不一同的状况。
其实，不管两阶段还是三阶段提交，都只是必定程度上缓解了提交抵触的问题，并无法确保体系的一同性。首个有效的共同算法是后来提出的Paxos 算法。
Paxos 算法
1990 年由 Leslie Lamport 在论文《The Part-time Parliament》中提出的 Paxos 共同算法，在工程视点完结了一种最大化确保分布式体系一同性（存在极小的概率无法完结一同）的机制。Paxos 算法本质上与前者相同，被广泛使用在 Chubby、ZooKeeper 这样的分布式体系中。Leslie Lamport 作为分布式体系范畴的早期研讨者，由于相关杰出贡献获得了 2013 年度图灵奖。
论文中为了描绘问题编造了一个虚构故事：在古代爱琴海的 Paxos 岛，议会怎么经过表决来到达共同。议员们经过信使传递音讯来对方案进行表决。但议员或许离开，信使或许走丢，乃至重复传递音讯。
Paxos 是首个得到证明并被广泛使用的共同算法，其原理相似于两阶段提交算法，进行了泛化和扩展，经过音讯传递来逐步消除体系中的不确定状况，作为后来许多共同算法（如 Raft、ZAB 等）的根底。
基本原理
算法中存在三种逻辑人物的节点，在完结中同一节点能够担任多个人物：
– 提案者（Proposer）：提出一个提案，等候咱们同意（Chosen）为抉择（Value）。体系中提案都拥有一个自增的仅有提案号。往往由客户端担任该人物； – 承受者（Acceptor）：担任对提案进行投票，承受（Accept）提案。往往由服务端担任该人物； – 学习者（Learner）：获取同意成果，并帮助传达，不参加投票进程。可为客户端或服务端。
算法需求满意安全性（Safety） 和存活性（Liveness）两方面的束缚要求。实践上这两个根底属性也是大部分分布式算法都该考虑的：
– Safety：确保抉择（Value）成果是对的，无歧义的，不会呈现过错状况。 * 只要是被提案者提出的提案才或许被终究同意；
- 在一次履行中，只同意（chosen）一个终究抉择。被大都承受（accept）的成果成为抉择。
– Liveness：确保抉择进程能在有限时间内完结。
- 抉择总会产生，并且学习者能获得被同意的抉择。
基本思路相似两阶段提交：多个提案者先要争取到提案的权利（得到大大都承受者的支持）；成功的提案者发送提案给一切人进行承认，得到大部分人承认的提案成为同意的抉择。
Paxos 并不确保体系总处在一同的状况。但由于每次到达共同至少有超越一半的节点参加，这样终究整个体系都会获悉共同成果。一个潜在的问题是提案者在提案进程中呈现毛病，这能够经过超时机制来缓解。极为凑巧的状况下，每次新一轮提案的提案者都恰好毛病，又或许两个提案者恰好依次提出更新的提案，则导致活锁，体系会永久无法到达共同（实践产生概率很小）。
Paxos 能确保在超越一半的节点正常作业时，体系总能以较大概率到达共同。读者能够试着自己规划一套非拜占庭容错下根据音讯传递的异步共同计划，会发现在满意各种束缚状况下，算法进程总会非常相似 Paxos 的进程。这也是为何 Google Chubby 的作者 Mike Burrows 说：“这个国际上只要一种一同性算法，那便是 Paxos（There is only one consensus protocol, and that’s Paxos）”。
总结
本文咱们从拜占庭问题聊起，提到了分布式体系的一同性问题。本质上的一同性，其实追求的还是终究一同性，并不存在完美的解决计划，而是在实践各种束缚条件下，往往需求经过献身掉某些需求，来规划出满意特定场景的协议。工程范畴中不少问题都不存在一了百了的通用解法；而实用的解决思路都是合理地在实践需求和条件束缚之间进行灵敏的取舍。
链接
– 拜占庭将军问题： liebing.org.cn/2020/02/14/…
– 拜占庭问题与算法: yeasy.gitbook.io/blockchain_…
– 分布式体系核心技能： yeasy.gitbook.io/blockchain_…
– Paxos 算法与 Raft 算法： yeasy.gitbook.io/blockchain_…
