常见一致性算法

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

分布式理论指导

一、ACID,CAP理论和BASE理论

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

ACID

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

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

ACID，是指在数据库管理系统（DBMS）中事务所具有的四个特性：原子性（Atomicity）、一致性（Consistency）、隔离性（Isolation，又称独立性）、持久性（Durability）。
问题一：Mysql怎么保证一致性的？
OK，这个问题分为两个层面来说。
从数据库层面，数据库通过原子性、隔离性、持久性来保证一致性。也就是说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

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

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

存在问题

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：为了实现一致性和可用性放弃分区容忍性。

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

是的，实际应用中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. 最终一致性 ：弱一致性的升级版。，系统会保证在一定时间内达到数据一致的状态
   业界比较推崇是最终一致性级别，但是某些对数据一致要求十分严格的场景比如银行转账还是要保证强一致性。**

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

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

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在运行的健壮性。
————————————————

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

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

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

利用表的 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，如果我们追求数据的一致性而忽略可用性这个在微服务中肯定是行不通的，如果我们追求可用性而忽略一致性，那么在一些重要的数据（例如支付，金额）肯定出现漏洞百出，这个也是无法接受。所以我们既要一致性，也要可用性。

本作品采用《CC 协议》，转载必须注明作者和本文链接