分布式基础理论

人是为了活着本身活着 - 《活着》

拜占庭将军问题

简介

拜占庭错误是莱斯利·兰伯特在《拜占庭将军问题》中提出的一个错误模型，描述了一个完全不可信的场景，除了存在故障行为，还存在恶意行为。顾名思义，拜占庭容错（Byzantine Fault Tolerance，BFT），就是指能容忍拜占庭错误了。莱斯利·兰伯特（ Leslie Lamport ）通过这个比喻，表达了计算机网络中所存在的一致性问题。

非拜占庭容错，又叫故障容错（Crash Fault Tolerance，CFT），解决的是分布式系统中存在故障，但不存在恶意节点的共识问题，比如进程奔溃，服务器硬件故障等等。

问题描述

共识问题

共识难题，也就是如何在可能有误导信息的情况下，采用合适的通讯机制，让多个将军达成共识，制定一致性的作战计划？

李牧作为合纵长，燕，齐，韩三国合纵想要攻打秦国，但是只有3国出半数以上的将军才能打赢秦国。

共识在这里表示的就是三国将军都收到准确的消息，达成一致性决定在某个时间攻打。一般情况下，每国投票，最后少数服从多数即可达成一致决定，例如：

燕，齐将军决定要打秦国

韩国将军想撤退

按照少数服从多数的原则，韩国将军也会出兵攻打秦国。

两忠一叛

可以看到，在正常情况下，信息一致，是能够形成共识的。但是，只要一旦燕，齐国将军有其中一国通秦，就会形成作战计划不一致的问题。例如燕国将军通秦，燕国将军向韩国将军发攻打，给齐国将军发送撤退：

韩国将军收到的信息就是，2攻打：1撤退
齐国将军看到的信息就是，1攻打：2撤退

按照少数服从多数的原则，最终就是韩国将军自己面对秦国，最后败于秦国。这里的问题就出在，其中里面有一国出了叛徒，导致发送了错误的信息。

解决方案

口信消息型拜占庭问题之解

首先，3位将军都分拨一部分军队，由李牧率领，李牧参与作战计划讨论并执行作战指令。这样，3 位将军的作战讨论，就变为了 4位将军的作战讨论，这能够增加讨论中忠诚国家的数量。

然后，4 位将军还约定了，如果没有收到命令，就执行预设的默认命令，比如“撤退”。除此之外，还约定一些流程来发送作战信息、执行作战指令。

第一轮

先发送作战信息的将军作为指挥官，其他的将军作为副官；指挥官将他的作战信息发送给每位副官；每位副官，将从指挥官处收到的作战信息，作为他的作战指令；如果没有收到作战信息，将把默认的“撤退”作为作战指令。

第二轮

除了第一轮的指挥官外，剩余的 3 位将军将分别作为指挥官，向另外 2 位将军发送作战信息；然后，这 3 位将军按照“少数服从多数”，执行收到的作战指令。

忠诚将军先发起命令

假设先由李牧向3个将军发起进攻的命令，在第一轮作战信息协商中，李牧向燕、齐、韩发送作战指令“进攻”。

在第二轮作战信息协商中，燕、齐、韩分别作为指挥官，向另外 2 位发送作战信息“进攻”，因为韩国将军已经通敌了，所以，为了干扰作战计划，韩国将军发送“撤退”作战指令。

最终，齐和燕收到的作战信息都是“进攻、进攻、撤退”，按照原则，齐和燕与李牧一起执行作战指令“进攻”，实现了作战计划的一致性，保证了作战的胜利。

通敌国先发送作战命令

假设先由韩过将军向3个将军发起进攻的命令，在第一轮作战信息协商中，韩国将军向李牧、燕发送作战指令“撤退”，向齐国将军发送作战指令"进攻"。

然后，在第二轮作战信息协商中，李牧、赵、燕分别作为指挥官，向另外两位发送作战信息。.

最终，李牧、燕和齐收到的作战信息都是“撤退、撤退、进攻”，按照原则，李牧、齐和燕一起执行作战指令“撤退”，实现了作战计划的一致性。也就是说，无论叛将楚如何捣乱，李牧、齐和燕，都执行一致的作战计划，保证作战的胜利。

这个解决办法，其实是兰伯特在论文《The Byzantine Generals Problem》中提到的口信消息型拜占庭问题之解：如果叛将人数为 m，将军人数不能少于 3m + 1 ，那么拜占庭将军问题就能解决了。

这个算法有个前提，也就是叛将人数 m，或者说能容忍的叛将数 m，是已知的。在这个算法中，叛将数 m 决定递归循环的次数（也就是说，叛将数 m 决定将军们要进行多少轮作战信息协商），即 m+1 轮（所以，你看，只有魏是叛变的，那么就进行了两轮）。你也可以从另外一个角度理解：n 位将军，最多能容忍 (n - 1) / 3 位叛将。

不过，这个算法虽然能解决拜占庭将军问题，但它有一个限制：如果叛将人数为 m，那么将军总人数必须不小于 3m + 1。

签名消息型拜占庭问题之解

口信消息型需要增加更多的忠诚的将军，签名消息型就是允许在不添加新的将军的前提下，达到最后的一致性。

签名就好比李牧的印章、虎符等信物，并且必须满足以下条件：

忠诚将军的签名无法伪造，而且对他签名消息的内容进行任何更改都会被发现；

任何人都能验证将军签名的真伪。

忠诚将军先发起命令

如果忠诚的将军，比如韩国先发起作战信息协商，一旦齐国修改或伪造收到的作战信息，那么燕国在接收到齐国的作战信息的时候，会发现韩国的作战信息被修改，齐国已叛变，这时他将忽略来自齐国的作战信息，最终执行韩国发送的作战信息。

通敌国先发起命令

如果叛变将军齐先发送误导的作战信息，那么，韩和燕将按照一定规则（比如取中间的指令）在排序后的所有已接收到的指令中（比如撤退、进攻）中选取一个指令，进行执行，最终执行一致的作战计划。

签名消息的拜占庭问题之解，也是需要进行 m+1 轮（其中 m 为叛将数）。你也可以从另外一个角度理解：n 位将军，能容忍 (n - 2) 位叛将（只有一位忠将没有意义，因为此时不需要达成共识了）。可以尝试去思考在2忠2叛的情况，在这里不做过多的赘述。可能你会觉得怎么可能事先知道叛军的，m根本就不知道。记住，轮次是通过n-1次定义的，而不是通过确定的叛军数确定的。

CAP 理论

这个理论就是 CAP 理论，先想下面几个问题：

什么是 CAP，全称是什么，之间的关系是什么？
CAP 之间是什么关系，场景对应是怎样的？
P 跟 A 都保证了可用性，但怎么区分？
如何运用 CAP？

注意，如果是单体系统，不存在什么 CAP 理论，就不存在分区。

属性	全称	中文	描述
C	Consistency	一致性	集群节点要么读到集群最新一致数据，要么全部都返回读取失败。【所有节点访问同一份最新的数据副本】【也叫副本一致性】
A	Availability	可用性	任何来自客户端的请求，不管访问哪个非故障节点，都能得到响应数据，但不保证是同一份最新数据。
P	Partition Tolerance	分区容错性	当节点间出现任意数量的消息丢失或高延迟的时候，系统仍然在继续工作

分区容错性解释：

举个例子，假设我们有一个分布式数据库系统，该系统有三个节点，分别是A、B和C。在正常情况下，这三个节点可以互相通信，共享数据。

现在，假设网络发生了分区，节点A与节点B、C之间的通信被切断，也就是说，A不能与B、C交换信息，但B和C之间的通信仍然正常。

在这种情况下，如果我们的系统能够继续提供服务（也就是说，客户端可以继续从节点A、B、C读取或写入数据），那么我们就说这个系统具有分区容错性。

需要注意的是，分区容错性并不意味着系统的所有功能都能在网络分区时正常工作。例如，在上述例子中，由于A不能与B、C交换信息，所以A可能无法获取到B、C最新的数据更新，这就可能影响到系统的一致性。这就是CAP理论中的一个基本权衡：在网络分区的情况下，系统必须在一致性和可用性之间做出选择。

CAP 不可兼得

因为分区容错性是前提，P一定有。可以这么理解，一个蓄水池，恒水位，有一个出水口和入水口。入水口坏了，你是想要这个蓄水池先供水，还是先保证水位正确，不要触发水位报警。这个蓄水池，肯定不能在没有入水的前提下，还能让水位保持恒定。因此，CAP 是不能兼容的。要想兼容，除非这个系统不需要分区。

CAP 不可兼得最初是埃里克·布鲁尔（Eric Brewer）基于自己的工程实践，提出的一个猜想，后被赛斯·吉尔伯特（Seth Gilbert）和南希·林奇（Nancy Lynch）证明，证明过程可以参考论文《Brewer’s conjecture and the feasibility of consistent, available, partition-tolerant web services》，记住结论就好了。

补充一点：基于证明严谨性的考虑，赛斯·吉尔伯特（Seth Gilbert）和南希·林奇（Nancy Lynch）对指标的含义做了预设和限制，比如，将一致性限制为原子一致性。

如何使用 CAP 理论

有网络交互就一定会有延迟和数据丢失，而这种状况我们必须接受，还必须保证系统不能挂掉。所以就像前面提到的，节点间的分区故障是必然发生的。也就是说，分区容错性 P 是前提，是必须要保证的。

现在就只剩下一致性 C 和可用性 A 可以选择了：要么选择一致性，保证数据正确；要么选择可用性，保证服务可用。

那么 CP 和 AP 的含义是什么呢？

选择了一致性 C ：一定会读到最新的数据，不会读到旧数据，但如果因为消息丢失、延迟过高发生了网络分区，那么这个时候，当集群节点接收到来自客户端的读请求时，为了不破坏一致性，可能会因为无法响应最新数据，而返回出错信息。

选择了可用性 A ：系统将始终处理客户端的查询，返回特定信息，如果发生了网络分区，一些节点将无法返回最新的特定信息，它们将返回自己当前的相对新的信息。

CAP 适用场景

CA：典型的应用是 Etcd，Consul 和 Hbase，Zookeeper

AP：Cassandra 和 DynamoDB，服务注册中心。

ACID理论

**ACID 是数据库管理系统为了保证事务的正确性而提出来的一个理论，**ACID 包含四个约束，分别是：

1.Atomicity（原子性）
一个事务中的所有操作，要么全部完成，要么全部不完成，不会在中间某个环节结束。事务在执行过程中发生错误，会被回滚到事务开始前的状态，就像这个事务从来没有执行过一样。

2.Consistency（一致性）
在事务开始之前和事务结束以后，数据库的完整性没有被破坏。

3.Isolation（隔离性）
数据库允许多个并发事务同时对数据进行读写和修改的能力。隔离性可以防止多个事务并发执行时由于交叉执行而导致数据的不一致。事务隔离分为不同级别，包括读未提交（Read uncommitted）、读提交（read committed）、可重复读（repeatable read）和串行化（Serializable）。

4.Durability（持久性）

事务处理结束后，对数据的修改就是永久的，即便系统故障也不会丢失。

ACID 中的 C 是指数据库的数据完整性，而 CAP 中的 C 是指分布式节点中的数据一致性。ACID 的应用场景是数据库事务，CAP 关注的是分布式系统数据读写。

但是，这只能保证单个节点上操作的 ACID 特性，无法保证节点间操作的 ACID 特性。因此需要掌握分布式事务协议，比如二阶段提交协议和 TCC（Try-Confirm-Cancel）

二阶段提交协议

2PC(tow phase commit)两阶段提交。所谓的两个阶段是指：

第一阶段：准备阶段(投票阶段)
第二阶段：提交阶段（执行阶段）。

我们将提议的节点称为协调者(coordinator)，其他参与决议节点称为参与者(participants, 或cohorts)。

2PC第一阶段

2PC的第一阶段是投票环节，投票由协调者节点发起，可以进一步细分为以下步骤：

事务询问：协调者向所有的参与者发送事务预处理请求，称之为Prepare，并开始等待各参与者的响应。
执行本地事务：各个参与者节点执行本地事务操作,但在执行完成后并不会真正提交数据库本地事务，而是先向协调者报告说：“我这边可以处理了/我这边不能处理”。
各参与者向协调者反馈事务询问的响应：如果参与者成功执行了事务操作，那么就反馈给协调者Yes响应，表示事务可以执行，如果没有参与者成功执行事务，那么就反馈给协调者No响应，表示事务不可以执行。

第一阶段执行完后，会有两种可能。1、所有都返回Yes. 2、有一个或者多个返回No。

2PC第二阶段：正常提交

如果第一阶段所有的参与者都返回Yes，那么我们就可以继续执行2PC第二阶段的正常提交步骤：

协调者节点通知所有的参与者Commit事务请求；
参与者收到Commit请求之后，就会正式执行本地事务Commit操作，并在完成提交之后释放整个事务执行期间占用的事务资源。

2PC第二阶段：异常回滚

如果任何一个参与者向协调者反馈了No响应，或者等待超时之后，协调者尚未收到所有参与者的反馈响应，那么我们就需要执行2PC第二阶段的回滚操作：

协调者节点通知所有的参与者Rollback请求；
参与者收到Rollback请求之后，就会正式执行本地事务Rollback操作，并在完成提交之后释放整个事务执行期间占用的事务资源。

2PC存在的问题

通过上面的演示，很容易想到2pc所带来的缺陷：

性能问题：无论是在第一阶段的过程中,还是在第二阶段,所有的参与者资源和协调者资源都是被锁住的,只有当所有节点准备完毕，事务协调者才会通知进行全局提交，参与者进行本地事务提交后才会释放资源。这样的过程会比较漫长，对性能影响比较大。
单节点故障：由于协调者的重要性，一旦协调者发生故障。参与者会一直阻塞下去。尤其在第二阶段，协调者发生故障，那么所有的参与者还都处于锁定事务资源的状态中，而无法继续完成事务操作。（虽然协调者挂掉，可以重新选举一个协调者，但是无法解决因为协调者宕机导致的参与者处于阻塞状态的问题）。