分布式理论知识学习(拜占庭将军，cap理论，base理论)

大家好，欢迎来到IT知识分享网。

前两天的高德交叉面的时候，面试官把我PUA了，其中问到为啥cap理论中一般只能实现两个？这让我这捉襟见肘的脑容量瞬间爆炸了，赶紧在极客时间上面搞了个分布式理论算法原理与实践课程，来学习一下吧，下面的内容就是学习该课程的相关笔记。

分布式系统里，最重要的事情，就是如何选择或设计适合的算法，解决一致性和可用性相关的问题了。

一、理论篇

1. 拜占庭将军问题

拜占庭帝国想要进攻一个强大的敌人，为此派出了10支军队去包围这个敌人。这个敌人虽不比拜占庭帝国，但也足以抵御5支常规拜占庭军队的同时袭击。基于一些原因，这10支军队不能集合在一起单点突破，必须在分开的包围状态下同时攻击。他们任一支军队单独进攻都毫无胜算，除非有至少6支军队同时袭击才能攻下敌国。他们分散在敌国的四周，依靠通信兵相互通信来协商进攻意向及进攻时间。困扰这些将军的问题是，他们不确定他们中是否有叛徒，叛徒可能擅自变更进攻意向或者进攻时间。在这种状态下，拜占庭将军们能否找到一种分布式的协议来让他们能够远程协商，从而赢取战斗？这就是著名的拜占庭将军问题。（其中不会去考虑通信兵是否会被截获或者无法传达信息等问题，即信道没有问题。有一个相似问题叫两军问题）

• 假设是二忠一叛的情况

解决方法一：口信消息解决拜占庭将军问题

解决办法二：签名消息型拜占庭问题之解

签名消息指的就是带有数字签名的消息，你可以这么理解“数字签名”：类似在纸质合同上进行签名来确认合同内容和证明身份.主要是用消息的摘要算法和非对称加密来实现的。

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

签名消息的拜占庭问题之解，也是需要进行 m+1 轮，从另外一个角度理解：n 位将军，能容忍 (n – 2) 位叛将。

虽然口信消息和签名消息能够在理论上解决这个问题，但是这两个解决方案也都是有局限性的。如果将军书为n,叛将数f,那么算法需要递归协商f+1轮，消息的复杂度为O(n^(f+1))，消息数量指数级暴增。所以这两种算法在实际中难以落地。

2. CAP理论

理论说明

• C：一致性（Consistency）：客户端的每次读操作，不管访问哪个节点，要么读到的都是同一份最新的数据，要么读取失败。一致性强调的不是数据完整，而是各节点间的数据一致。一致性看作是分布式系统对访问本系统的客户端的一种承诺：不管你访问哪个节点，要么我给你返回的都是绝对一致的数据，要么你都读取失败。
• A : 可用性（Availability）：可用性说的是任何来自客户端的请求，不管访问哪个节点，都能得到响应数据，但不保证是同一份最新数据。 这个指标强调的是服务可用，但不保证数据的一致。 可用性是分布式系统对访问本系统的客户端的一种承诺：我尽力给你返回数据，不会不响应你，
• P : 分区容错性（Partition Tolerance）：当节点间出现任意数量的消息丢失或高延迟的时候，系统仍然可以继续提供服务。这个指标，强调的是集群对分区故障的容错能力。 换句话也就是说，分布式系统在告诉访问本系统的客户端：不管我的内部出现什么样的数据同步问题，我会一直运行，提供服务。

CAP 不可能三角

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

CA 模型，在分布式系统中不存在。因为舍弃 P，意味着舍弃分布式系统，就比如单机版关系型数据库 MySQL，如果 MySQL 要考虑主备或集群部署时，它必须考虑 P。

其实，在不存在网络分区的情况下，也就是分布式系统正常运行时（这也是系统在绝大部分时候所处的状态），就是说在不需要 P 时，C 和 A 能够同时保证。只有当发生分区故障的时候，也就是说需要 P 时，才会在 C 和 A 之间做出选择。而且如果各节点数据不一致，影响到了系统运行或业务运行（也就是说会有负面的影响），推荐选择 C，否则选 A。

分布式事务 ACID

一个分布式事务，要么全部执行，要么全部不执行。

二阶段提交协议

• 第一阶段：voting phase 投票阶段
  事务协调者给每个参与者发送Prepare消息，每个参与者要么直接返回失败(如权限验证失败)，要么在本地执行事务，写本地的redo和undo日志，但不提交。
  
• 第二阶段：commit phase 提交阶段
  如果协调者收到了参与者的失败消息或者超时，直接给每个参与者发送回滚(Rollback)消息；否则，发送提交(Commit)消息；参与者根据协调者的指令执行提交或者回滚操作，释放所有事务处理过程中使用的锁资源。(注意:必须在最后阶段释放锁资源)
  

二阶段提交协议，不仅仅是协议，也是一种非常经典的思想。二阶段提交在达成提交操作共识的算法中应用广泛，比如 XA 协议、TCC、Paxos、Raft 等。

幂等性，是指同一操作对同一系统的任意多次执行，所产生的影响均与一次执行的影响相同，不会因为多次执行而产生副作用。常见的实现方法有 Token、索引等。它的本质是通过唯一标识，标记同一操作的方式，来消除多次执行的副作用。

二阶段提交的缺陷

3、数据不一致。在二阶段提交的阶段二中，当协调者向参与者发送commit请求之后，发生了局部网络异常或者在发送commit请求过程中协调者发生了故障，这回导致只有一部分参与者接受到了commit请求。而在这部分参与者接到commit请求之后就会执行commit操作。但是其他部分未接到commit请求的机器则无法执行事务提交。于是整个分布式系统便出现了数据不一致性的现象。

三阶段提交协议

相对于2PC，3PC主要解决的单点故障问题，并减少阻塞，因为一旦参与者无法及时收到来自协调者的信息之后，他会默认执行commit。而不会一直持有事务资源并处于阻塞状态。但是这种机制也会导致数据一致性问题，因为，由于网络原因，协调者发送的abort响应没有及时被参与者接收到，那么参与者在等待超时之后执行了commit操作。这样就和其他接到abort命令并执行回滚的参与者之间存在数据不一致的情况。

BASE理论

BASE的核心就是基本可用（Basically Available）和最终一致性（Eventually consistent）；

软状态（Soft state），软状态描述的是实现服务可用性的时候系统数据的一种过渡状态，也就是说不同节点间，数据副本存在短暂的不一致。
BASE 理论是 CAP 理论中的 AP 的延伸，是对互联网大规模分布式系统的实践总结，强调可用性。几乎所有的互联网后台分布式系统都有 BASE 的支持，这个理论很重要，地位也很高。

基本可用

基本可用是当分布式系统在出现不可预知的故障时，允许损失部分功能的可用性，保障核心功能的可用性。主要有流量削峰、延迟响应、体验降级、过载保护等几种解决方案。
如12306在不同的时间，出售不同区域的票，将访问请求错开，削弱请求峰值。在春运期间，自己提交的购票请求，往往会在队列中排队等待处理，可能几分钟或十几分钟后，系统才开始处理，然后响应处理结果，这就是你熟悉的延迟响应。 体验降级， 比如用小图片来替代原始图片，通过降低图片的清晰度和大小，提升系统的处理能力。过载保护， 比如把接收到的请求放在指定的队列中排队处理，如果请求等待时间超时了（假设是 100ms），这个时候直接拒绝超时请求；比如队列满了之后，就清除队列中一定数量的排队请求，保护系统不过载，实现系统的基本可用。

最终一致性

Reference：

1. 唯识相链2
2. 分布式一致性之两阶段提交协议、三阶提交协议