常见一致性算法

博主： JIeJaitt
发布时间：2023 年 07 月 02 日
100 次浏览
暂无评论
7969字数
分类：理论经验

> 本文由 [简悦 SimpRead](http://ksria.com/simpread/) 转码， 原文地址 [learnku.com](https://learnku.com/articles/63839)

后台服务架构经过了集中式、SOA、微服务和服务网格四个阶段，目前互联网界大都使用微服务和服务网格。服务从集中式、中心化向分布式、去中心化不断演进，服务也变得更灵活，能够自动扩缩容、快速版本迭代等。但是分布式架构也将集中式下一些问题放大，比如通信故障、请求三态（成功、失败、超时）、节点故障等，这些问题会导致一系例数据不一致的问题，也是计算机领域的老大难问题

分布式理论指导

## ACID,CAP 理论和 BASE 理论

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

### ACID

ACID 是传统数据库常用的设计理念，追求强一致性模型。关系数据库的 ACID 模型拥有 高一致性 + 可用性 很难进行分区：

- 原子性：一个事务中所有操作都必须全部完成，要么全部不完成。
- 一致性：在事务开始或结束时，数据库应该在一致状态。
- 隔离层：事务将假定只有它自己在操作数据库，彼此不知晓。(事务隔离级别)
- 持久性：一旦事务完成，就不能返回。

ACID，是指在数据库管理系统（DBMS）中事务所具有的四个特性：原子性（Atomicity）、一致性（Consistency）、隔离性（Isolation，又称独立性）、持久性（Durability）。

问题一：Mysql 怎么保证一致性的？

这个问题分为两个层面来说。
从数据库层面，数据库通过原子性、隔离性、持久性来保证一致性。也就是说 ACID 四大特性之中，C (一致性) 是目的，A (原子性)、I (隔离性)、D (持久性) 是手段，是为了保证一致性，数据库提供的手段。数据库必须要实现 AID 三大特性，才有可能实现一致性。例如，原子性无法保证，显然一致性也无法保证。

但是，如果你在事务里故意写出违反约束的代码，一致性还是无法保证的。例如，你在转账的例子中，你的代码里故意不给 B 账户加钱，那一致性还是无法保证。因此，还必须从应用层角度考虑。

从应用层面，通过代码判断数据库数据是否有效，然后决定回滚还是提交数据！

问题二: Mysql 怎么保证原子性的？
OK，是利用 Innodb 的 undo log。
undo log 名为回滚日志，是实现原子性的关键，当事务回滚时能够撤销所有已经成功执行的 sql 语句，他需要记录你要回滚的相应日志信息。
例如

(1) 当你 delete 一条数据的时候，就需要记录这条数据的信息，回滚的时候，insert 这条旧数据
(2) 当你 update 一条数据的时候，就需要记录之前的旧值，回滚的时候，根据旧值执行 update 操作
(3) 当年 insert 一条数据的时候，就需要这条记录的主键，回滚的时候，根据主键执行 delete 操作
undo log 记录了这些回滚需要的信息，当事务执行失败或调用了 rollback，导致事务需要回滚，便可以利用
问题三: Mysql 怎么保证持久性的？
OK，是利用 Innodb 的 redo log。
正如之前说的，Mysql 是先把磁盘上的数据加载到内存中，在内存中对数据进行修改，再刷回磁盘上。如果此时突然宕机，内存中的数据就会丢失。
怎么解决这个问题？
简单啊，事务提交前直接把数据写入磁盘就行啊。
这么做有什么问题？

只修改一个页面里的一个字节，就要将整个页面刷入磁盘，太浪费资源了。毕竟一个页面 16kb 大小，你只改其中一点点东西，就要将 16kb 的内容刷入磁盘，听着也不合理。
毕竟一个事务里的 SQL 可能牵涉到多个数据页的修改，而这些数据页可能不是相邻的，也就是属于随机 IO。显然操作随机 IO，速度会比较慢。
于是，决定采用 redo log 解决上面的问题。当做数据修改的时候，不仅在内存中操作，还会在 redo log 中记录这次操作。当事务提交的时候，会将 redo log 日志进行刷盘 (redo log 一部分在内存中，一部分在磁盘上)。当数据库宕机重启的时候，会将 redo log 中的内容恢复到数据库中，再根据 undo log 和 binlog 内容决定回滚数据还是提交数据。

采用 redo log 的好处？
其实好处就是将 redo log 进行刷盘比对数据页刷盘效率高，具体表现如下

redo log 体积小，毕竟只记录了哪一页修改了啥，因此体积小，刷盘快。
redo log 是一直往末尾进行追加，属于顺序 IO。效率显然比随机 IO 来的快。
ps: 不想具体去谈 redo log 具体长什么样，因为内容太多了。

问题四: Mysql 怎么保证隔离性的？
OK, 利用的是锁和 MVCC 机制。还是拿转账例子来说明，有一个账户表如下
表名 t_balance

id user_id balance
1 A 200
2 B 0
其中 id 是主键，user_id 为账户名，balance 为余额。还是以转账两次为例

至于 MVCC, 即多版本并发控制 (Multi Version Concurrency Control), 一个行记录数据有多个版本对快照数据，这些快照数据在 undo log 中。
如果一个事务读取的行正在做 DELELE 或者 UPDATE 操作，读取操作不会等行上的锁释放，而是读取该行的快照版本。
由于 MVCC 机制在可重复读 (Repeateable Read) 和读已提交 (Read Commited) 的 MVCC 表现形式不同，就不赘述了。
但是有一点说明一下，在事务隔离级别为读已提交 (Read Commited) 时，一个事务能够读到另一个事务已经提交的数据，是不满足隔离性的。但是当事务隔离级别为可重复读 (Repeateable Read) 中，是满足隔离性的。

### cap[#](#3d791e)

CAP 定理又被成为布鲁尔定理，是加州大学计算机科学家埃里克・布鲁尔提出来的猜想
2000 年 7 月，加州大学伯克利分校的 Eric Brewer 教授在 ACM PODC 会议上提出 CAP 猜想。2 年后，麻省理工学院的 Seth Gilbert 和 Nancy Lynch 从理论上证明了 CAP。之后，CAP 理论正式成为分布式计算领域的公认定理

* C（Consistency 一致性）：所有的节点上的数据时刻保持同步
* A（Availability 可用性）：每个请求都能接受到一个响应，无论响应成功或失败
* P（Partition tolerance 分区容错）：系统应该能持续提供服务，即使系统内部有消息丢失（分区）

存在问题

![](https://cdn.learnku.com/uploads/images/202112/22/20250/cEMgyxbDwx.png!large)

> CAP 理论证明在分布式系统中不能同时满足这三个特征，只能满足其中两点

高可用、数据一致是很多系统设计的目标，但是分区又是不可避免的事情：
CA without P：如果不要求 P（不允许分区），则 C（强一致性）和 A（可用性）是可以保证的。但其实分区不是你想不想的问题，而是始终会存在，因此 CA 的系统更多的是允许分区后各子系统依然保持 CA。
CP without A：如果不要求 A（可用），相当于每个请求都需要在 Server 之间强一致，而 P（分区）会导致同步时间无限延长，如此 CP 也是可以保证的。很多传统的数据库分布式事务都属于这种模式。
AP wihtout C：要高可用并允许分区，则需放弃一致性。一旦分区发生，节点之间可能会失去联系，为了高可用，每个节点只能用本地数据提供服务，而这样会导致全局数据的不一致性。现在众多的 NoSQL 都属于此类。
困惑一

CP：为了实现一致性和分区容忍性必须放弃可用性。

实际应用中，比如系统存在 A、B 两个节点 (或网络分区)，数据写入 A 后，网络发生抖动导致 A、B 通信中断，数据无法写入 B，为了保证数据一致性，系统将无法继续提供服务直到 B 完成写入，AB 达到数据一致的状态。如果 A、B 通信永远不恢复，系统将永远不可用，这在实际应用中不可接受。

困惑二

CA：为了实现一致性和可用性放弃分区容忍性。

是的，实际应用中 CP、CA 本质上没有区别，同样是面对网络抖动问题，为了满足一致性，都会导致系统无法使用。这是因为实际应用中，节点 A 没有办法判断节点 B 是挂掉了、还是无法与其正常通信。于是 CA 和 CP 在不引入第三方组件的情况下都是无法达到的。而这完全是由 C（一致性）导致，所以如果可以在业务上避免对分布式系统的一致性要求那是极好的！
实际应用分析

只求 AP

放弃一致性，保证系统高可用、高扩展性、分区容忍性。系统设计将极大简化，同时保证高可用、高扩展，系统的运维也很方便，最终的结果是从设计、开发、测试、上线、运维都极大的降低了成本。就如 Amazon SQS，的确是不错。

寻求 A、C 折中

网络抖动时，保留一致性，放弃可用性。在一定时间窗口内 (比如 5s)，如果服务依然没有恢复，就放弃一致性，恢复对外提供服务。这种策略在实际应用比较普遍，根据具体的业务场景，设定一个时间窗口，保证系统在可容忍的时间内尽可能保持一致性，如果实在保证不了，那就放弃一致性，继续提供服务。毕竟更多时候，不能提供服务造成的损失要比部分数据不一致造成的损失大很多。更多的时候，我们自然而然的把 failover 逻辑放在系统的终端实现，就如 ActiveMQ 的 failover、RocketMQ 的 rebalance

> 不适用数据库事务架构，

### BASE

BASE 理论解决 CAP 理论提出了分布式系统的一致性和可用性不能兼得的问题。
BASE 理论是对 CAP 理论的延伸，思想是即使无法做到强一致性（CAP 的一致性就是强一致性），但可以采用适当的采取弱一致性，即最终一致性。
BASE 是指基本可用（Basically Available）、软状态（ Soft State）、最终一致性（ Eventual Consistency）。

* 基本可用（Basically Available）
  基本可用是指分布式系统在出现故障的时候，允许损失部分可用性，即保证核心可用。
  电商大促时，为了应对访问量激增，部分用户可能会被引导到降级页面，服务层也可能只提供降级服务。这就是损失部分可用性的体现。(削峰填谷，延迟响应，服务降级)
* 软状态（ Soft State）
  软状态是指允许系统存在中间状态，而该中间状态不会影响系统整体可用性。分布式存储中一般一份数据至少会有三个副本，允许不同节点间副本同步的延时就是软状态的体现。mysql replication 的异步复制也是一种体现。
* 最终一致性（ Eventual Consistency）
  最终一致性是指系统中的所有数据副本经过一定时间后，最终能够达到一致的状态。弱一致性和强一致性相反，最终一致性是弱一致性的一种特殊情况。(写时修复，读时修复)

> 是对 CAP 中 AP 方案的一个补充
> BASE 模型是传统 ACID 模型的反面，不同与 ACID，BASE 强调牺牲高一致性，从而获得可用性，数据**允许在一段时间内的不一致，只要保证最终一致就可以了**。

分布式一致性的 3 种级别：

> 1. **强一致性** ：系统写入了什么，读出来的就是什么。
> 2. **弱一致性** ：不一定可以读取到最新写入的值，也不保证多少时间之后读取到的数据是最新的，只是会尽量保证某个时刻达到数据一致的状态。
> 3. **最终一致性** ：弱一致性的升级版。，系统会保证在一定时间内达到数据一致的状态
>    业界比较推崇是最终一致性级别，但是某些对数据一致要求十分严格的场景比如银行转账还是要保证强一致性。**

![](https://cdn.learnku.com/uploads/images/202112/22/20250/ZUyHDC0DwC.png!large)

### 服务注册中心，是选择 AP 还是选择 CP ？

服务注册中心解决的问题
在讨论 CAP 之前先明确下服务注册中心主要是解决什么问题：一个是服务注册，一个是服务发现。
服务注册：实例将自身服务信息注册到注册中心，这部分信息包括服务的主机 IP 和服务的 Port，以及暴露服务自身状态和访问协议信息等。
服务发现：实例请求注册中心所依赖的服务信息，服务实例通过注册中心，获取到注册到其中的服务实例的信息，通过这些信息去请求它们提供的服务。

![](https://cdn.learnku.com/uploads/images/202112/22/20250/OFId94Uu47.png!large)

zookeeper 选择 CP
zookeep 保证 CP，即任何时刻对 zookeeper 的访问请求能得到一致性的数据结果，同时系统对网络分割具备容错性，但是它不能保证每次服务的可用性。从实际情况来分析，在使用 zookeeper 获取服务列表时，如果 zk 正在选举或者 zk 集群中半数以上的机器不可用，那么将无法获取数据。所以说，zk 不能保证服务可用性。
eureka 选择 AP
eureka 保证 AP，eureka 在设计时优先保证可用性，每一个节点都是平等的，一部分节点挂掉不会影响到正常节点的工作，不会出现类似 zk 的选举 leader 的过程，客户端发现向某个节点注册或连接失败，会自动切换到其他的节点，只要有一台 eureka 存在，就可以保证整个服务处在可用状态，只不过有可能这个服务上的信息并不是最新的信息。
zookeeper 和 eureka 的数据一致性问题
先要明确一点，eureka 的创建初心就是为一个注册中心，但是 zk 更多是作为分布式协调服务的存在，只不过因为它的特性被 dubbo 赋予了注册中心，它的职责更多是保证数据（配置数据，状态数据）在管辖下的所有服务之间保持一致，所有这个就不难理解为何 zk 被设计成 CP 而不是 AP，zk 最核心的算法 ZAB，就是为了解决分布式系统下数据在多个服务之间一致同步的问题。
更深层的原因，zookeeper 是按照 CP 原则构建，也就是说它必须保持每一个节点的数据都保持一致，如果 zookeeper 下节点断开或者集群中出现网络分割（例如交换机的子网间不能互访），那么 zk 会将它们从自己的管理范围中剔除，外界不能访问这些节点，即使这些节点是健康的可以提供正常的服务，所以导致这些节点请求都会丢失。
而 eureka 则完全没有这方面的顾虑，它的节点都是相对独立，不需要考虑数据一致性的问题，这个应该是 eureka 的诞生就是为了注册中心而设计，相对 zk 来说剔除了 leader 节点选取和事务日志极致，这样更有利于维护和保证 eureka 在运行的健壮性。
————————————————

![](https://cdn.learnku.com/uploads/images/202112/22/20250/dEIYQ3giBV.png!large)

小结：服务注册应该选择 AP 还是 CP
对于服务注册来说，针对同一个服务，即使注册中心的不同节点保存的服务注册信息不相同，也并不会造成灾难性的后果，对于服务消费者来说，能消费才是最重要的，就算拿到的数据不是最新的数据，消费者本身也可以进行尝试失败重试。总比为了追求数据的一致性而获取不到实例信息整个服务不可用要好。
所以，对于服务注册来说，可用性比数据一致性更加的重要，选择 AP。

分布式锁，是选择 AP 还是选择 CP ？
这里实现分布式锁的方式选取了三种：

* 基于数据库实现分布式锁

![](https://cdn.learnku.com/uploads/images/202112/22/20250/K74NLtTrMm.png!large)

利用表的 UNIQUE KEY idx_lock (method_lock) 作为唯一主键，当进行上锁时进行 insert 动作，数据库成功录入则以为上锁成功，当数据库报出 Duplicate entry 则表示无法获取该锁。

不过这种方式对于单主却无法自动切换主从的 mysql 来说，基本就无法现实 P 分区容错性，（Mysql 自动主从切换在目前并没有十分完美的解决方案）。可以说这种方式强依赖于数据库的可用性，数据库写操作是一个单点，一旦数据库挂掉，就导致锁的不可用。

* 基于 redis 实现分布式锁
  redis 单线程串行处理天然就是解决串行化问题，用来解决分布式锁是再适合不过。
  为了解决数据库锁的无主从切换的问题，可以选择 redis 集群，或者是 sentinel 哨兵模式，实现主从故障转移，当 master 节点出现故障，哨兵会从 slave 中选取节点，重新变成新的 master 节点。
  哨兵模式故障转移是由 sentinel 集群进行监控判断，当 maser 出现异常即复制中止，重新推选新 slave 成为 master，sentinel 在重新进行选举并不在意主从数据是否复制完毕具备一致性。
  所以 redis 的复制模式是属于 AP 的模式
* 基于 zookeeper 实现分布式锁

分布式事务，是怎么从 ACID 解脱，投身 CAP/BASE
如果说到事务，ACID 是传统数据库常用的设计理念，追求强一致性模型，关系数据库的 ACID 模型拥有高一致性 + 可用性，所以很难进行分区，所以在微服务中 ACID 已经是无法支持，我们还是回到 CAP 去寻求解决方案，不过根据上面的讨论，CAP 定理中，要么只能 CP，要么只能 AP，如果我们追求数据的一致性而忽略可用性这个在微服务中肯定是行不通的，如果我们追求可用性而忽略一致性，那么在一些重要的数据（例如支付，金额）肯定出现漏洞百出，这个也是无法接受。所以我们既要一致性，也要可用性。

最后修改：2023 年 07 月 22 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

常见一致性算法

JIeJaitt • 2023 年 07 月 02 日

> 本文由 [简悦 SimpRead](http://ksria.com/simpread/) 转码， 原文地址 [learnku.com](https://learnku.com/articles/63839)

分布式理论指导

## ACID,CAP 理论和 BASE 理论

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

### ACID

ACID 是传统数据库常用的设计理念，追求强一致性模型。关系数据库的 ACID 模型拥有 高一致性 + 可用性 很难进行分区：

问题一：Mysql 怎么保证一致性的？

从应用层面，通过代码判断数据库数据是否有效，然后决定回滚还是提交数据！

采用 redo log 的好处？
其实好处就是将 redo log 进行刷盘比对数据页刷盘效率高，具体表现如下

问题四: Mysql 怎么保证隔离性的？
OK, 利用的是锁和 MVCC 机制。还是拿转账例子来说明，有一个账户表如下
表名 t_balance

id user_id balance
1 A 200
2 B 0
其中 id 是主键，user_id 为账户名，balance 为余额。还是以转账两次为例

### cap[#](#3d791e)

存在问题

![](https://cdn.learnku.com/uploads/images/202112/22/20250/cEMgyxbDwx.png!large)

> CAP 理论证明在分布式系统中不能同时满足这三个特征，只能满足其中两点

CP：为了实现一致性和分区容忍性必须放弃可用性。

困惑二

CA：为了实现一致性和可用性放弃分区容忍性。

只求 AP

寻求 A、C 折中

> 不适用数据库事务架构，

### BASE

分布式一致性的 3 种级别：

![](https://cdn.learnku.com/uploads/images/202112/22/20250/ZUyHDC0DwC.png!large)

### 服务注册中心，是选择 AP 还是选择 CP ？

![](https://cdn.learnku.com/uploads/images/202112/22/20250/OFId94Uu47.png!large)

![](https://cdn.learnku.com/uploads/images/202112/22/20250/dEIYQ3giBV.png!large)

分布式锁，是选择 AP 还是选择 CP ？
这里实现分布式锁的方式选取了三种：

* 基于数据库实现分布式锁

![](https://cdn.learnku.com/uploads/images/202112/22/20250/K74NLtTrMm.png!large)

常见一致性算法

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

欢迎使用 Typecho

团队项目管理 Git 与 GitHub 使用经验

流媒体视频点播网站 scheduler 调度器模块实现

算法基础之双指针学习笔记

Redis 缓存问题（图解：三种缓存问题）

投顾资产展示接口笔记

牛客网Go语言入门语法题

bench.sh Linux 服务器测速脚本

保证数据的一致性状态的MySQL事务

团队项目管理 Git 与 GitHub 使用经验

常见一致性算法

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

常见一致性算法

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款