一、普通 hash 算法 (取模算法)：

        在了解一致性哈希算法之前，我们先了解一下缓存中的一个应用场景，了解了这个应用场景之后，再来理解一致性哈希算法，就容易多了，也更能体现出一致性哈希算法的优点，那么，我们先来描述一下这个经典的分布式缓存的应用场景。

1、普通 hash算法 与 使用场景描述：

        假设我们有三台缓存服务器，用于缓存图片，我们为这三台缓存服务器编号为 0号、1号、2号，现在有3万张图片需要缓存，我们希望这些图片被均匀的缓存到这3台服务器上，以便它们能够分摊缓存的压力。也就是说，我们希望每台服务器能够缓存1万张左右的图片，那么我们应该怎样做呢？常见的做法是对缓存项的键进行哈希，将hash后的结果对缓存服务器的数量进行取模操作，通过取模后的结果，决定缓存项将会缓存在哪一台服务器上

        我们举例说明，以刚才描述的场景为例，假设图片名称是不重复的，那我们就可以使用图片名称作为访问图片的key，使用如下公式，计算出图片应该存放在哪台服务器上。

hash（图片名称）% N

        当我们对同一个图片名称做相同的哈希计算时，得出的结果应该是不变的，如果我们有3台服务器，使用哈希后的结果对3求余，那么余数一定是0、1或者2；如果求余的结果为0， 就把当前图片缓存在0号服务器上，如果余数为1，就缓存在1号服务器上，以此类推；同理，当我们访问任意图片时，只要再次对图片名称进行上述运算，即可得出图片应该存放在哪一台缓存服务器上，我们只要在这一台服务器上查找图片即可，如果图片在对应的服务器上不存在，则证明对应的图片没有被缓存，也不用再去遍历其他缓存服务器了，通过这样的方法，即可将3万张图片随机的分布到3台缓存服务器上了，而且下次访问某张图片时，直接能够判断出该图片应该存在于哪台缓存服务器上，我们暂时称上述算法为 HASH 算法或者取模算法，取模算法的过程可以用下图表示：

 2、普通 hash 算法的缺陷：

        上述HASH算法时，会出现一些缺陷：如果服务器已经不能满足缓存需求，就需要增加服务器数量，假设我们增加了一台缓存服务器，此时如果仍然使用上述方法对同一张图片进行缓存，那么这张图片所在的服务器编号必定与原来3台服务器时所在的服务器编号不同，因为除数由3变为了4，最终导致所有缓存的位置都要发生改变，也就是说，当服务器数量发生改变时，所有缓存在一定时间内是失效的，当应用无法从缓存中获取数据时，则会向后端服务器请求数据；同理，假设突然有一台缓存服务器出现了故障，那么我们则需要将故障机器移除，那么缓存服务器数量从3台变为2台，同样会导致大量缓存在同一时间失效，造成了缓存的雪崩，后端服务器将会承受巨大的压力，整个系统很有可能被压垮。为了解决这种情况，就有了一致性哈希算法。

        

二、一致性哈希算法：

 1、什么是一致性 hash 算法：

        一致性哈希算法也是使用取模的方法，但是取模算法是对服务器的数量进行取模，而一致性哈希算法是对 2^32 取模，具体步骤如下：

• 步骤一：一致性哈希算法将整个哈希值空间按照顺时针方向组织成一个虚拟的圆环，称为 Hash 环；
• 步骤二：接着将各个服务器使用 Hash 函数进行哈希，具体可以选择服务器的IP或主机名作为关键字进行哈希，从而确定每台机器在哈希环上的位置
• 步骤三：最后使用算法定位数据访问到相应服务器：将数据key使用相同的函数Hash计算出哈希值，并确定此数据在环上的位置，从此位置沿环顺时针寻找，第一台遇到的服务器就是其应该定位到的服务器

下面我们使用具体案例说明一下一致性哈希算法的具体流程：

（1）步骤一：哈希环的组织：

        我们将 2^32 想象成一个圆，像钟表一样，钟表的圆可以理解成由60个点组成的圆，而此处我们把这个圆想象成由2^32个点组成的圆，示意图如下：

        圆环的正上方的点代表0，0点右侧的第一个点代表1，以此类推，2、3、4、5、6……直到2^32-1,也就是说0点左侧的第一个点代表2^32-1，我们把这个由 2^32 个点组成的圆环称为hash环。

（2）步骤二：确定服务器在哈希环的位置：

哈希算法：hash（服务器的IP） % 2^32

        上述公式的计算结果一定是 0 到 2^32-1 之间的整数，那么上图中的 hash 环上必定有一个点与这个整数对应，所以我们可以使用这个整数代表服务器，也就是服务器就可以映射到这个环上，假设我们有 ABC 三台服务器，那么它们在哈希环上的示意图如下：

 （3）步骤三：将数据映射到哈希环上：

        我们还是使用图片的名称作为 key，所以我们使用下面算法将图片映射在哈希环上：hash（图片名称） % 2^32，假设我们有4张图片，映射后的示意图如下，其中橘黄色的点表示图片：

        那么，怎么算出上图中的图片应该被缓存到哪一台服务上面呢？我们只要从图片的位置开始，沿顺时针方向遇到的第一个服务器就是图片存放的服务器了。最终，1号、2号图片将会被缓存到服务器A上，3号图片将会被缓存到服务器B上，4号图片将会被缓存到服务器C上。

 2、一致性 hash 算法的优点：

        前面提到，如果简单对服务器数量进行取模，那么当服务器数量发生变化时，会产生缓存的雪崩，从而很有可能导致系统崩溃，而使用一致性哈希算法就可以很好的解决这个问题，因为一致性Hash算法对于节点的增减都只需重定位环空间中的一小部分数据，只有部分缓存会失效，不至于将所有压力都在同一时间集中到后端服务器上，具有较好的容错性和可扩展性。

        假设服务器B出现了故障，需要将服务器B移除，那么移除前后的示意图如下图所示：

        在服务器B未移除时，图片3应该被缓存到服务器B中，可是当服务器B移除以后，按照之前描述的一致性哈希算法的规则，图片3应该被缓存到服务器C中，因为从图片3的位置出发，沿顺时针方向遇到的第一个缓存服务器节点就是服务器C，也就是说，如果服务器B出现故障被移除时，图片3的缓存位置会发生改变，但是，图片4仍然会被缓存到服务器C中，图片1与图片2仍然会被缓存到服务器A中，这与服务器B移除之前并没有任何区别，这就是一致性哈希算法的优点。

 3、hash 环的倾斜与虚拟节点：

        一致性哈希算法在服务节点太少的情况下，容易因为节点分部不均匀而造成数据倾斜问题，也就是被缓存的对象大部分集中缓存在某一台服务器上，从而出现数据分布不均匀的情况，这种情况就称为 hash 环的倾斜。如下图所示：

         hash 环的倾斜在极端情况下，仍然有可能引起系统的崩溃，为了解决这种数据倾斜问题，一致性哈希算法引入了虚拟节点机制，即对每一个服务节点计算多个哈希，每个计算结果位置都放置一个此服务节点，称为虚拟节点，一个实际物理节点可以对应多个虚拟节点，虚拟节点越多，hash环上的节点就越多，缓存被均匀分布的概率就越大，hash环倾斜所带来的影响就越小，同时数据定位算法不变，只是多了一步虚拟节点到实际节点的映射。具体做法可以在服务器ip或主机名的后面增加编号来实现，加入虚拟节点以后的hash环如下：

---

相关阅读：

常见的服务器架构入门：从单体架构、EAI 到 SOA 再到微服务和 ServiceMesh

常见分布式理论（CAP、BASE）和一致性协议（Gosssip协议、Raft一致性算法）

一致性哈希算法原理详解

Nacos注册中心的部署与用法详细介绍

Nacos配置中心用法详细介绍

SpringCloud OpenFeign 远程HTTP服务调用用法与原理

什么是RPC？RPC框架dubbo的核心流程

服务容错设计：流量控制、服务熔断、服务降级

sentinel 限流熔断神器详细介绍

Sentinel 规则持久化到 apollo 配置中心

Sentinel-Dashboard 与 apollo 规则的相互同步

Spring Cloud Gateway 服务网关的部署与使用详细介绍

Spring Cloud Gateway 整合 sentinel 实现流控熔断

Spring Cloud Gateway 整合 knife4j 聚合接口文档

常见分布式事务详解（2PC、3PC、TCC、Saga、本地事务表、MQ事务消息、最大努力通知）

分布式事务Seata原理

RocketMQ事务消息原理

---

 参考文章：https://www.zsythink.net/archives/1182

Redis 拥有高性能的数据读写功能，被我们广泛用在缓存场景，一是能提高业务系统的性能，二是为数据库抵挡了高并发的流量请求。

把 Redis 作为缓存组件，需要防止出现以下问题，否则可能会造成生产事故。

• Redis 缓存满了

• 缓存穿透、缓存击穿、缓存雪崩

• Redis 数据过期了

• Redis 突然变慢了

• Redis 与 MySQL 数据一致性问题

在本文正式开始之前，需要大家先取得以下两点共识： 

• 缓存必须要有过期时间；

• 保证数据库跟缓存的最终一致性即可，不必追求强一致性

1. 什么是数据库与缓存一致性？ 

数据一致性指的是：

• 缓存中存有数据，缓存的数据值 = 数据库中的值；

• 缓存中没有该数据，数据库中的值 = 最新值。

反推缓存与数据库不一致：

• 缓存的数据值 ≠ 数据库中的值；

• 缓存或者数据库存在旧的数据，导致线程读取到旧数据。

为何会出现数据一致性问题呢？

把 Redis 作为缓存的时候，当数据发生改变我们需要双写来保证缓存与数据库的数据一致性。

数据库跟缓存毕竟是两套系统，如果要保证强一致性，势必要引入 2PC 或 Paxos 等分布式一致性协议，或者分布式锁等等。这个在实现上是有难度的，而且一定会对性能有影响。

如果真的对数据的一致性要求这么高，那引入缓存是否真的有必要呢？

2. 缓存的使用策略

在使用缓存时，通常有以下几种缓存使用策略用于提升系统性能：

• Cache-Aside 模式（旁路缓存，业务系统常用）

• Read-Through 模式（直读）

• Write-Through 模式（同步直写）

• Write-Behind 模式

2.1 Cache-Aside (旁路缓存)

所谓「旁路缓存」，就是读取缓存、读取数据库和更新缓存的操作都在应用系统来完成，业务系统最常用的缓存策略。

2.1.1 读取数据

读取数据逻辑如下:

1. 当应用程序需要从数据库读取数据时，先检查缓存数据是否命中；

2. 如果缓存未命中，则查询数据库获取数据。同时将数据写到缓存中，以便后续读取相同数据会命中缓存。最后再把数据返回给调用者；

3. 如果缓存命中，直接返回。

时序图如下：

 

 

优点

• 缓存中仅包含应用程序实际请求的数据，有助于保持缓存大小的成本效益；

• 实现简单，并且能获得性能提升。

实现的伪代码如下：

String cacheKey = "码哥字节";
String cacheValue = redisCache.get(cacheKey)；
//缓存命中
if (cacheValue != null) {
  return cacheValue;
} else {
  //缓存缺失, 从数据库获取数据
  cacheValue = getDataFromDB();
  // 将数据写到缓存中
  redisCache.put(cacheValue)
}

缺点

由于数据仅在缓存未命中后才加载到缓存中，因此初次调用的数据请求响应时间会增加一些开销，因为需要额外的缓存填充和数据库查询耗时。

 2.1.2 更新数据

使用 cache-aside 模式写数据时，如下流程。

1. 写数据到数据库；

2. 将缓存中的数据失效或者更新缓存数据。

使用 cache-aside 时，最常见的写入策略是直接将数据写入数据库，但是缓存可能会与数据库不一致。

我们应该给缓存设置一个过期时间，这个是保证最终一致性的解决方案。

如果过期时间太短，应用程序会不断地从数据库中查询数据。同样，如果过期时间过长，并且更新时没有使缓存失效，缓存的数据很可能是脏数据。

最常用的方式是删除缓存使缓存数据失效。

为啥不是更新缓存呢？

性能问题

当缓存的更新成本很高需要访问多张表联合计算时，建议直接删除缓存，而不是更新缓存数据来保证一致性。

安全问题

在高并发场景下，可能会造成查询查到的数据是旧值，具体原因稍后分析。

2.2 Read-Through 模式（直读）

当缓存未命中，也是从数据库加载数据，同时写到缓存中并返回给应用系统。

虽然 read-through 和 cache-aside 非常相似，在 cache-aside 中应用系统负责从数据库获取数据和填充缓存。

而 Read-Through 将获取数据存储中的值的责任转移到了缓存提供者身上。

Read-Through 实现了关注点分离原则。代码只与缓存交互，由缓存组件来管理自身与数据库之间的数据同步。

2.3 Write-Through 模式（同步直写） 

与 Read-Through 类似，发生写请求时，Write-Through 将写入责任转移到缓存系统，由缓存抽象层来完成缓存数据和数据库数据的更新，时序流程图如下：

Write-Through 的主要好处是应用系统的不需要考虑故障处理和重试逻辑，交给缓存抽象层来管理实现。

优缺点

单独直接使用该策略是没啥意义的，因为该策略要先写缓存，再写数据库，对写入操作带来了额外延迟。

当 Write-Through 与 Read-Through 配合使用，就能充分发挥 Read-Through 的优势，同时还能保证数据一致性，不需要考虑如何将缓存设置失效。

这个策略颠倒了 Cache-Aside 填充缓存的顺序，并不是在缓存未命中后延迟加载到缓存，而是在数据先写缓存，接着由缓存组件将数据写到数据库。

优点

• 缓存与数据库数据总是最新的；

• 查询性能最佳，因为要查询的数据有可能已经被写到缓存中了。

缺点

不经常请求的数据也会写入缓存，从而导致缓存更大、成本更高。

2.4 Write-Behind 模式

这个图一眼看去似乎与 Write-Through 一样，其实不是。区别在于最后一个箭头的箭头：它从实心变为线。

这意味着缓存系统将异步更新数据库数据，应用系统只与缓存系统交互。

应用程序不必等待数据库更新完成，从而提高应用程序性能，因为对数据库的更新是最慢的操作。

这种策略下，缓存与数据库的一致性不强，对一致性高的系统不建议使用。

3. 旁路缓存下的一致性问题分析

业务场景用的最多的就是 Cache-Aside (旁路缓存) 策略，在该策略下，客户端对数据的读取流程是先读取缓存，如果命中则返回；未命中，则从数据库读取并把数据写到缓存中，所以读操作不会导致缓存与数据库的不一致。

重点是写操作，数据库和缓存都需要修改，而两者就会存在一个先后顺序，可能会导致数据不再一致。针对写，我们需要考虑两个问题：

• 先更新缓存还是更新数据库？

• 当数据发生变化时，选择修改缓存（update），还是删除缓存（delete）？

将这两个问题排列组合，会出现四种方案：

• 先更新缓存，再更新数据库；

• 先更新数据库，再更新缓存；

• 先删除缓存，再更新数据库；

• 先更新数据库，再删除缓存。

接下来的分析大家不必死记硬背，关键在于在推演的过程中大家只需要考虑以下两个场景会不会带来严重问题即可：

• 其中第一个操作成功，第二个失败会导致什么问题？

• 在高并发情况下会不会造成读取数据不一致？

为啥不考虑第一个失败，第二个成功的情况呀？

既然第一个都失败了，第二个就不用执行了，直接在第一步返回 50x 等异常信息即可，不会出现不一致问题。

只有第一个成功，第二个失败才让人头痛，想要保证他们的原子性，就涉及到分布式事务的范畴了。

3.1 先更新缓存，再更新数据库

 

如果先更新缓存成功，写数据库失败，就会导致缓存是最新数据，数据库是旧数据，那缓存就是脏数据了。

之后，其他查询立马请求进来的时候就会获取这个数据，而这个数据数据库中却不存在。

数据库都不存在的数据，缓存并返回客户端就毫无意义了。

该方案直接 Pass。

3.2 先更新数据库，再更新缓存

一切正常的情况如下：

1. 先写数据库，成功；

2. 再 update 缓存，成功。

更新缓存失败

这时候我们来推断下，假如这两个操作的原子性被破坏：第一步成功，第二步失败会导致什么问题？

会导致数据库是最新数据，缓存是旧数据，出现一致性问题。

该图与上一个图类似，把 Redis 和 MySQL 的位置对调即可。

高并发场景

谢霸歌经常 996，腰酸脖子疼，bug 越写越多，想去按摩推拿放提升下编程技巧。

疫情影响，单子来之不易，高端会所的技师都争先恐后想接这一单，高并发啊兄弟们。

在进店以后，前台会将顾客信息录入系统，执行 set xx的服务技师 = 待定的初始值表示目前无人接待保存到数据库和缓存中，之后再安排技师按摩服务。

如下图所示：

1. 98 号技师先下手为强，向系统发送 set 谢霸歌的服务技师 = 98 的指令写入数据库，这时候系统的网络出现波动，卡顿了，数据还没来得及写到缓存；

2. 接下来，520 号技师也向系统发送 set 谢霸哥的服务技师 = 520写到数据库中，并且也把这个数据写到缓存中了；

3. 这时候之前的 98 号技师的写缓存请求开始执行，顺利将数据 set 谢霸歌的服务技师 = 98 写到缓存中。

最后发现，数据库的值 = set 谢霸哥的服务技师 = 520，而缓存的值= set 谢霸歌的服务技师 = 98。

520 号技师在缓存中的最新数据被 98 号技师的旧数据覆盖了。

所以，在高并发的场景中，多线程同时写数据再写缓存，就会出现缓存是旧值，数据库是最新值的不一致情况。

该方案直接 pass。

如果第一步就失败，直接返回 50x 异常，并不会出现数据不一致。

3.3 先删缓存，再更新数据库

按照「码哥」前面说的套路，假设第一个操作成功，第二个操作失败推断下会发生什么？高并发场景下又会发生什么？

第二步写数据库失败

假设现在有两个请求：写请求 A，读请求 B。

写请求 A 第一步先删除缓存成功，写数据到数据库失败，就会导致该次写数据丢失，数据库保存的是旧值。

接着另一个读请 B 求进来，发现缓存不存在，从数据库读取旧数据并写到缓存中。

高并发下的问题

1. 还是 98 号技师先下手为强，系统接收请求把缓存数据删除，当系统准备将 set 肖菜鸡的服务技师 = 98写到数据库的时候发生卡顿，来不及写入；

2. 这时候，大堂经理向系统执行读请求，查下肖菜鸡有没有技师接待，方便安排技师服务，系统发现缓存中没数据，于是乎就从数据库读取到旧数据 set 肖菜鸡的服务技师 = 待定，并写到缓存中；

3. 这时候，原先卡顿的 98 号技师写数据 set 肖菜鸡的服务技师 = 98到数据库的操作完成。

这样子会出现缓存的是旧数据，在缓存过期之前无法读取到最数据。肖菜鸡本就被 98 号技师接单了，但是大堂经理却以为没人接待。

该方案 pass，因为第一步成功，第二步失败，会造成数据库是旧数据，缓存中没数据继续从数据库读取旧值写入缓存，造成数据不一致，还会多一次 cahche。

不论是异常情况还是高并发场景，会导致数据不一致。miss。

 3.4 先更新数据库，再删缓存

经过前面的三个方案，全都被 pass 了，分析下最后的方案到底行不行。

按照「套路」，分别判断异常和高并发会造成什么问题。

该策略可以知道，在写数据库阶段失败的话就直返返回客户端异常，不需要执行缓存操作了。

所以第一步失败不会出现数据不一致的情况。

删缓存失败

重点在于第一步写最新数据到数据库成功，删除缓存失败怎么办？

可以把这两个操作放在一个事务中，当缓存删除失败，那就把写数据库回滚。

高并发场景下不合适，容易出现大事务，造成死锁问题。

如果不回滚，那就出现数据库是新数据，缓存还是旧数据，数据不一致了，咋办？

所以，我们要想办法让缓存删除成功，不然只能等到有效期失效那可不行。

使用重试机制。

比如重试三次，三次都失败则记录日志到数据库，使用分布式调度组件 xxl-job 等实现后续的处理。

在高并发的场景下，重试最好使用异步方式，比如发送消息到 mq 中间件，实现异步解耦。

亦或是利用 Canal 框架订阅 MySQL binlog 日志，监听对应的更新请求，执行删除对应缓存操作。

高并发场景

再来分析下高并发读写会有什么问题。

 

1. 98 号技师先下手为强，接下肖菜鸡的这笔生意，数据库执行 set 肖菜鸡的服务技师 = 98；还是网络卡顿了下，没来得及执行删除缓存操作；

2. 主管 Candy 向系统执行读请求，查下肖菜鸡有没有技师接待，发现缓存中有数据 肖菜鸡的服务技师 = 待定，直接返回信息给客户端，主管以为没人接待；

3. 原先 98 号技师接单，由于卡顿没删除缓存的操作现在执行删除成功;

4. 读请求可能出现少量读取旧数据的情况，但是很快旧数据就会被删除，之后的请求都能获取最新数据，问题不大。

还有一种比较极端的情况，缓存自动失效的时候又遇到了高并发读写的情况。假设这会有两个请求，一个线程 A 做查询操作，一个线程 B 做更新操作，那么会有如下情形产生：

1. 缓存的过期时间到期，缓存失效；

2. 线程 A 读请求读取缓存，没命中，则查询数据库得到一个旧的值（因为 B 会写新值，相对而言就是旧的值了），准备把数据写到缓存时发送网络问题卡顿了；

3. 线程 B 执行写操作，将新值写数据库；

4. 线程 B 执行删除缓存；

5. 线程 A 继续，从卡顿中醒来，把查询到的旧值写到入缓存。

这还是出现了不一致的情况啊。

不要慌，发生这个情况的概率微乎其微，发生上述情况的必要条件是：

• 步骤 3 写数据库操作要比步骤 2 读操作耗时短速度快，才可能使得步骤 4 先于步骤 5；

• 缓存刚好到达过期时限。

通常 MySQL 单机的 QPS 大概 5K 左右，而 TPS 大概 1K 左右，（ps：Tomcat 的 QPS 4K 左右，TPS = 1K 左右）。

数据库读操作是远快于写操作的（正是因为如此，才做读写分离），所以步骤（3）要比步骤（2）更快这个情景很难出现，同时还要配合缓存刚好失效。

所以，在用旁路缓存策略的时候，对于写操作推荐使用：先更新数据库，再删除缓存。

 4. 一致性解决方案有哪些？

最后，针对 Cache-Aside (旁路缓存) 策略，写操作使用先更新数据库，再删除缓存的情况下，我们来分析下数据一致性解决方案都有哪些？

4.1 缓存延时双删

如果采用先删除缓存，再更新数据库如何避免出现脏数据？

采用延时双删策略：

1. 先删除缓存；

2. 写数据库；

3. 休眠 500 毫秒，再删除缓存。

这样子最多只会出现 500 毫秒的脏数据读取时间。关键是这个休眠时间怎么确定呢？

延迟时间的目的就是确保读请求结束，写请求可以删除读请求造成的缓存脏数据。

所以我们需要自行评估项目的读数据业务逻辑的耗时，在读耗时的基础上加几百毫秒作为延迟时间即可。

4.2 删除缓存重试机制

缓存删除失败怎么办？比如延迟双删的第二次删除失败，那岂不是无法删除脏数据。

使用重试机制，保证删除缓存成功。

比如重试三次，三次都失败则记录日志到数据库并发送警告让人工介入。

在高并发的场景下，重试最好使用异步方式，比如发送消息到 mq 中间件，实现异步解耦。

第 5 步如果删除失败且未达到重试最大次数则将消息重新入队，直到删除成功，否则就记录到数据库，人工介入。

该方案有个缺点，就是对业务代码中造成侵入，于是就有了下一个方案。启动一个专门订阅 数据库 binlog 的服务读取需要删除的数据进行缓存删除操作。

 4.3 读取 binlog 异步删除

 

1. 更新数据库；

2. 数据库会把操作信息记录在 binlog 日志中；

3. 使用 canal 订阅 binlog 日志获取目标数据和 key；

4. 缓存删除系统获取 canal 的数据，解析目标 key，尝试删除缓存。

5. 如果删除失败则将消息发送到消息队列；

6. 缓存删除系统重新从消息队列获取数据，再次执行删除操作。

总结

缓存策略的最佳实践是 Cache Aside 模式。分别分为读缓存最佳实践和写缓存最佳实践。

读缓存最佳实践

先读缓存，命中则返回；

• 未命中则查询数据库，再写到缓存中。

写缓存最佳实践

• 先写数据库，再操作缓存；

• 直接删除缓存，而不是修改。

当缓存的更新成本很高需要访问多张表联合计算时，建议直接删除缓存，而不是更新。另外，删除缓存操作简单，副作用只是增加了一次 chache miss，建议大家使用该策略。

在以上最佳实践下，为了尽可能保证缓存与数据库的一致性，我们可以采用延迟双删。

防止删除失败，我们采用异步重试机制保证能正确删除。异步机制我们可以发送删除消息到 MQ 消息中间件，或者利用 Canal 订阅 MySQL binlog 日志监听写请求删除对应缓存。

那么，如果我非要保证绝对一致性怎么办？

先给出结论：

没有办法做到绝对的一致性，这是由 CAP 理论决定的。缓存系统适用的场景就是非强一致性的场景，所以它属于 CAP 中的 AP。

所以，我们得委曲求全，可以去做到 BASE 理论中说的最终一致性。

其实一旦在方案中使用了缓存，那往往也就意味着我们放弃了数据的强一致性，但这也意味着我们的系统在性能上能够得到一些提升。

所谓 tradeoff 正是如此。

---

本文由giantpoplar发表于CSDN，转载请保留本声明。

---

“Cache Coherence” V.S. “Memory Consistency” V.S. “Data Consistency”

缓存一致性

cache coherence 的coherence这个词猜测是体系结构圈为了和memory consistency做区分，用了coherence这个词，但我理解缓存一致性和分布式多副本数据的一致性基本接近，只不过cache coherence是一种同步可靠通信、有全局时钟条件下的强一致(linearizability)。cache一致性协议有MSI，MESI等，虽然处理器的整个内存系统很复杂，但就cache一致性协议来说，比分布式环境下的数据一致要简明一些

多核处理器每个核会有私有cache，也就是内存里的一份数据在多个核上可能有了副本，这多个副本，每个核都可能会对一个内存地址有读写操作，每个核是直接读写自己私有的副本，这就要求各个副本上的读写操作顺序要一致，这和分布式环境下的数据一致性很接近。

具体的MSI，MESI协议暂不展开写。

内存一致性

内存一致性说的是共享内存多核处理器访存序的问题，进程对某一个内存地址(和分布式的同一数据多副本的一致性有所区别)的访问序的在多核下暴露出的问题 全部内存读写顺序的正确性问题，单核乱序执行重新排列无关的指令在多核系统中可能出现问题。也就是程序中 Load Store 的(ISA)顺序(冯诺依曼架构下看可以看做内存操作请求的顺序)和Load Store实际执行完成的顺序可能相同、可能不同(这取决于微体系结构的实现)，在多核情况下，程序的正确性可能出问题。有各种一致性模型来表达各种程度的相同不同，相应的有软、硬件机制来确保多核处理器上程序的正确运行。

这里只具体写顺序一致性(sequential consistency)模型，更弱的一致性模型在学习过相关资料论文后再做补充。顺序一致性的概念来源于Lamport 1977年的一篇论文How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Program
这里写一下论文中给出的阐述
看一个互斥协议，问题是多核处理器下多进程并发/并行会使得两个进程都进入临界区么？

几点说明写在前面：

• 1，2，3，4，5，6只是标号，数字本身带有的序和问题没联系
• 程序里的读写操作都是一条指令的粒度，不是高级语言的一句语句
• P1, P2指处理器

-	P1	-	P2
	a=0		b=0
	…		…
1	a=1	4	b=1
2	IF(b==0) THEN	5	IF(a==0) THEN
	(临界区)		(临界区)
3	a=0	6	b=0
	ELSE		ELSE
	{…}		{…}

考虑这个例子，如下事件依次发生

• 1 P1 发出a=1的请求，请求的是内存模块1，内存模块1此时正忙
• 2 P1 发出取b的请求，请求的是内存模块2，内存模块2此时可用，取b的指令执行
• 4 P2 发出b=1的请求，请求的是内存模块2，这个请求会在取b执行完成后执行
• 5 P2 发送取a得请求，请求的是内存模块1，内存模块1此时正忙

在这个例子里，这4条指令对同一内存请求顺序是1 ->5 ; 2->4
这4条指令执行完成的顺序是什么呢 2->4；
如果是 2->4；5 -> 1 这两个处理器会同时进入临界区
如果是 2->4；1 -> 5 则不会
-> 符号不直接对应happen-before

顺序一致性有两个条件：

• 每个处理器按程序序发射内存请求(1->2;4->5)
• 所有处理器到单个存储器模块的请求依照FIFO序服务。请求的发射过程包含进入FIFO队列。

我理解就是说，不管这多个处理器对同一内存的请求顺序如何交叠，都可以，但是内存必须按照请求到达的顺序执行（这里应该隐含着对同一地址先请求（指令发射）的先到达（指令执行）的假设），这样保证上面的互斥协议正确。这样的要求称为顺序一致的要求，是很严格的，会对硬件性能造成影响，其实可以放宽，不必严格按请求顺序执行，但是必须有软件机制来提供正确的互斥协议的实现，上面的护持互斥协议在弱于顺序一致的内存模型下是不正确的。

也就是说1，2，4，5的请求可以有C(4,2)=6种交叠方式，每一种都符合顺序一致只要每种情况的执行也是按照这个顺序

现在来看这句很拗口的话

the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program

似乎这个定义里要求每个核上不同内存地址的请求也要安程序序执行，但是在微体系结构层次，提交时要保持，但是执行时程序序是可以打破的，同一处理器不同地址请求序(乱序发射)和程序序(冯诺依曼ISA序)是否一致，请求序和执行序是否一致，这里似乎没有明说。分布式环境中的一致性是关于同一数据的多个副本上要达成全局一致性，某种角度来讲，如果把内存的请求发射和到达，类比分布式中对一个副本的写/读和向各个副本传播写/读操作，这两者非常类似 //但是感觉还是没有理解二者的本质

单核处理器下多进程并发会使得两个进程都进入临界区么？此时表里的P1,P2代指进程。不会有这个问题，内存请求是从同一个核过来，到达顺序和服务顺序一样(单核天然是顺序一致的)，不会有多核中多个请求到达，在执行请求时会涉及调度导致服务顺序和到达顺序不一致的情况。

如果你考虑一个多核处理器的内存体系，就会发现这个问题很复杂，cache以及一致性，buffer，pipeline和内存一致性的保证，和分布式的一致性相比，虽然分布式下异步不可靠网络带来了很大挑战，但是现在我觉得处理器的内存系统可以说比分布式环境下的一致性问题更加复杂

x86的内存一致模型是顺序一致的TSO，所以在实现一个正确的互斥锁的时候也没有考虑太多，比如没用memory barrier这种东西就对了

数据一致性

分布式系统为了性能、容错的需要，数据进行多副本冗余是一项很基本的技术。数据一致性说的是一份数据有多个副本，在多个副本上的读写操作的顺序要达成一致，这个一致也有很多不同的强弱要求，产生了众多的强弱一致性模型，这些模型的术语和内存一致性的术语有很大的重叠，可能是历史上并行体系结构和分布式系统两个领域是一伙人在搞？

由强到弱的数据一致性模型构成了 数据一致性谱

线性一致性和顺序一致性

这两种都是称为强一致性

• 线性一致性和顺序一致性都是强一致性
• 都给客户端提供单副本的假象
• Linearizability关乎时间，sequential consistency 关乎程序顺序

分布式下强一致是个困难问题，著名的paxos算法挺复杂的，Raft是2014年出的一个可以看作是改良版的算法。

线性一致性 Linearizability

• 表现出单副本的行为
• 读操作返回最近(most recent)的写，和client无关
• 所有后序读返回相同值，直到下一次写，和client无关

最近和所有后序： 由时间确定
e.g.

顺序一致性

• 表现出单副本的行为
• 读操作返回最近(most recent)的写，和client无关
• 所有后序读返回相同值，直到下一次写，和client无关

最近和所有后序：
同一个client的操作由时间决定(程序序)；
跨client的操作：不由时间决定，我们可以安排某种序，只要保持程序序。

从系统外的观察者来看：顺序一致性需要提供操作的全局序，1)工作起来像一个副本，2）来自同一个client的操作顺序被保持

e.g.

• 不违背顺序一致

-	-	-	-	-	-
P1:	W(x)a
P2:		W(x)b
P3:			R(x)b		R(x)a
P4:				R(x)b	R(x)a

这个例子里面，横轴代表时间，时间上虽然W(x)a在前，W(x)b在后，但是其序不一定也如此，所以这个例子并不违背分布式环境下的顺序一致，也再次说明分布式的顺序一致是比内存的顺序一致更弱的一致

• 违背顺序一致

-	-	-	-	-	-
P1:	W(x)a
P2:		W(x)b
P3:			R(x)b		R(x)a
P4:				R(x)a	R(x)b

• 不违背顺序一致，违背线性一致

-	-	-	-
P1:	W(x)a	W(x)b
P2:			R(x)a
time	——->	——->	——->

内存的顺序一致是顺序一致么？

内存的顺序一致性和分布式哪一种强一致性是一样的呢？是顺序一致性么？因为分布式环境下没有全局时间，所以分布式数据顺序一致性退化成较弱的一种一致性，而Linearizability和内存的顺序一致性更接近。

因果一致性
放宽顺序一致性的要求，有因果关联的操作保持顺序，并发的(相互没有因果关联的)写操作可能在不同机器上顺序不同
因果关系可以由vector-clock捕捉
e.g.

• 违背顺序一致,不违背因果一致

-	-	-	-	-	-	-
P1:	W(x)a			W(x)c
P2:		R(x)a	W(x)b
P3:		R(x)a			R(x)c	R(x)b
P4:		R(x)a			R(x)b	R(x)c

• 违背因果一致

-	-	-	-	-	-
P1:	W(x)a
P2:		R(x)a	W(x)b
P3:				R(x)b	R(x)a
P4:				R(x)a	R(x)b

• 不违背因果一致

-	-	-	-	-	-
P1:	W(x)a
P2:			W(x)b
P3:				R(x)b	R(x)a
P4:				R(x)a	R(x)b

最终一致性
某些副本的数据已经修改，而另一些副本的数据还没来得及修改。当修改可靠地传播到所有副本，并给予足够的时间，所有副本的数据都将变成新值，取得一致。

happen-before

理解一致性要理解一个并发系统中的“序”的问题，什么叫先，什么叫后。在分布式系统中，这个问题困难是因为没有完美的全局同步时钟，多核系统中是因为多核的微体系结构上的原因。

Lamport在1978年的论文中给出了happen-before的定义，这篇论文非常经典，提出了很多分布式系统中十分重要的概念，此处暂不展开，只谈happen-before。据说这篇文章受相对论启发，了解happen-before有助于理解时间、顺序。

happen-before 关系

基本假设

• 假设进程的事件(event)形成一个序列(sequence)，单个进程定义为 一组事件的全序(total ordering)
• 假设进程之间消息(message)的发送(send)和接受(receive)是事件

happen-before $\rightarrow$ 是满足以下条件的最小关系(relation)

• 如果a，b是同一个进程的事件，a在b前面 ,那么$a\rightarrow b$
• 如果a是发送消息进程的发送事件，b是接收该消息进程的接受事件，那么$a\rightarrow b$
• 如果$a\rightarrow b, b\rightarrow c$，那么$a\rightarrow c$

定义$a\nrightarrow a$
另外，如果两个不同的事件a,b,有 $a\nrightarrow b, b\nrightarrow a$,就称a,b是并发的(concurrent)

这样从数学上看，happen-before就是一个定义在所有事件上偏序关系，反自反，反对称，传递性都有了，偏序关系中存在不可比的情况，所以有些事件并无先后是并发的，如果在加上限制条件 break tie,那么在这个偏序关系上就可以定义一个全序关系。

进程和事件的定义非常general，事件可以是一个子程序的执行、也可以是一条机器指令的执行。

消息的发送和接受在分布式系统中很显然。在体系结构方面也有类似之处，考虑单核处理器、冯诺依曼架构中指令顺序执行，其实这些指令并不需要严格一条接着一条指令，所以会有乱序执行，在乱序执行里，如果把同一内存地址的写读看做消息发送接收，其实乱序执行的写后读依赖就和happen-before序十分类似。

引用

[1].Gharachorloo, Kourosh, et al. Memory consistency and event ordering in scalable shared-memory multiprocessors. Vol. 18. No. 2SI. ACM, 1990.
[2].Lamport, Leslie. “Time, clocks, and the ordering of events in a distributed system.” Communications of the ACM 21.7 (1978): 558-565.
[3]Lamport, Leslie. “How to make a multiprocessor computer that correctly executes multiprocess progranm.” IEEE transactions on computers 9 (1979): 690-691.
[4].Tanenbaum, Andrew S., and Maarten Van Steen. Distributed systems: principles and paradigms. Prentice-Hall, 2007.
[5].https://homes.cs.washington.edu/~bornholt/post/memory-models.html
[6].https://cse.buffalo.edu/~stevko/courses/cse486/spring15/lectures/23-consistency2.pdf