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

拜占庭将军问题

简介

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

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

问题描述

共识问题

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

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

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

燕，齐将军决定要打秦国

韩国将军想撤退

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

两忠一叛

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

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

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

解决方案

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

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

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

第一轮

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

第二轮

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

忠诚将军先发起命令

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

image-20240528153829489

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

image-20240528153851640

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

通敌国先发送作战命令

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

image-20240528154005852

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

image-20240528154020184

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

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

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

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

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

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

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

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

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

忠诚将军先发起命令

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

image-20240528154102135

通敌国先发起命令

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

image-20240528154123384

签名消息的拜占庭问题之解，也是需要进行 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)两阶段提交。所谓的两个阶段是指：

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

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

2PC第一阶段

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

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

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

image-20240528162359332

2PC第二阶段：正常提交

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

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

image-20240528162426879

2PC第二阶段：异常回滚

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

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

image-20240528162442350

2PC存在的问题

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

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

Base理论

BASE 是指基本可用（Basically Available）、软状态（ Soft State）、最终一致性（ Eventual Consistency），核心思想是即使无法做到强一致性（CAP 的一致性就是强一致性），但应用可以采用适合的方式达到最终一致性。

1. 基本可用（Basically Available）

分布式系统在出现故障时，允许损失部分可用性，即保证核心可用。

2. 软状态（Soft State）

允许系统存在中间状态，而该中间状态不会影响系统整体可用性。这里的中间状态就是 CAP 理论中的数据不一致。

3. 最终一致性（Eventual Consistency）

系统中的所有数据副本经过一定时间后，最终能够达到一致的状态。

BASE 理论本质上是对 CAP 的延伸和补充，更具体地说，是对 CAP 中 AP 方案的一个补充。前面在剖析 CAP 理论时，提到了其实和 BASE 相关的两点：

  • CAP 理论是忽略延时的，而实际应用中延时是无法避免的。
  • AP 方案中牺牲一致性只是指分区期间，而不是永远放弃一致性。

总结，ACID 是数据库事务完整性的理论，CAP 是分布式系统设计理论，BASE 是 CAP 理论中 AP 方案的延伸。

常用的 CP 和 AP 系统：

中间件 CAP 分类 解释
Zookeeper CP 保证一致性，在出现网络分区时可能会牺牲部分可用性，典型的强一致性服务，主要用于分布式协调。
HBase CP 保证强一致性，基于 Google 的 BigTable，适合需要严格一致性的数据存储场景，尤其是大数据处理。
MongoDB CP 默认配置下保证强一致性，但在某些情况下允许配置为 AP 模式，可以根据需要调整一致性和可用性之间的平衡。
Redis (集群模式) CP 在 Redis 的集群模式下，倾向于牺牲可用性以确保数据一致性，特别是使用 WAIT 命令进行同步。
Etcd CP 保证一致性，常用于配置管理、服务发现等场景。牺牲可用性确保一致性，特别适用于分布式系统的关键元数据存储。
MySQL（主从模式） CP 数据库在主从模式下，主要保证数据的一致性，特别是在事务中间，主库和从库数据的一致性更优先。
Cassandra AP 优先保证可用性和分区容忍性，牺牲强一致性，通常提供最终一致性，在大规模高可用的场景中非常合适。
DynamoDB AP 基于 Dynamo 设计，提供高可用性和分区容忍性，牺牲一致性，在高可用环境中保证最终一致性。
Riak AP 类似于 Dynamo 的分布式存储系统，保证高可用和分区容忍性，最终一致性模型。
Couchbase AP 一个 NoSQL 数据库，优先保证可用性和分区容忍性，牺牲强一致性，但提供最终一致性。
Voldemort AP 来自 LinkedIn 的分布式键值存储系统，优先保证可用性和分区容忍性，牺牲强一致性，提供最终一致性。
Kafka AP 在某些配置下更偏向于 AP（高可用性和分区容忍性），但在严格配置下可以更接近 CP，但通常不会牺牲可用性。
ElasticSearch AP 分布式搜索引擎，优先保证可用性和分区容忍性，支持最终一致性，但可能会在网络分区时牺牲一致性。

面试题

分布式和集群的区别

  • 分布式(distributed)是指在多台不同的服务器中部署不同的服务模块，通过远程调用协同工作，对外提供服务。
  • 集群(cluster)是指在多台不同的服务器中部署相同应用或服务模块，构成一个集群，通过负载均衡设备对外提供服务。

柔性事务

柔性事务（Flexible Transaction）是一种弱化了传统数据库事务（ACID）严格要求的事务模型，旨在适应分布式系统中高并发性和可扩展性需求。相比于传统事务严格的原子性、一致性、隔离性和持久性（ACID），柔性事务更注重最终一致性和高可用性，允许在短时间内存在数据不一致，但最终数据会达到一致状态。

参考自：