《拒绝最终一致性的脏读陷阱： Umem-cache 强一致性实现原理》

[imchuncai]

原文：consistency.rst

缓存一致性是 Umem-cache 最关键的特性，缓存协议和集群的设计方案都是围绕着它展开的。 缓存一致性能减少软件开发中的复杂性，因为你不需要担心过时的数据，这是最终一致性做不到的。

选择缓存一致性是有代价的：我们牺牲了可用性。 也就是一旦 Umem-cache 挂掉，即使你的其他服务依旧完好，整个系统也无法工作。 但是不必担心，我们有基于 raft 共识算法的集群解决方案，它可以提供很高的容错能力。

缓存协议

我们的缓存协议提供了 GetOrSet 和 Delete 两个命令，是的， 我们把 Get 和 Set 合并了。

缓存一致性的实现是靠在数据库中的 Key 更新完成的瞬间，以下事件确保发生：

• 没有任何连接正在读取 Key
• 所有在此之前读到 Key 且未完成 Set 的连接都已被关闭
• Umem-cache 中不存在该 Key

下面我将详细说明：

缓存命中

缓存命中时，Umem-cache 直接返回数据。

但是如果 key 因为正在 set 而被锁住了，该 get 操作会给该锁设置上过期时间，并排队等待 value 。 另外，如果锁到期了，持有锁的连接会被关闭，并把锁转交给排队中的下一个连接。

::

客户端                  Umem-cache                  数据库
           get key
|------------------------->|
                           | 1. 等待锁释放
           返回 value        |
|<-------------------------|

缓存未命中

当缓存未命中时，我们会锁住 key ，然后尝试 set ，其他 get 请求会排队等待，这种机制是为了防止缓存击穿。

你可能发现了，Umem-cache 不响应 Set ，这让我们省掉了一次网络传输。 因为它大概率会成功，就算失败也不是什么大事。

::

客户端                  Umem-cache                  数据库
           get key
|------------------------->|
                           | 1. 锁住 key
           返回 miss         |
|<-------------------------|

                       get key
|--------------------------------------------------->|
                                                     | 2. 等待读锁
                       返回 value                      |
|<---------------------------------------------------|


|------------------------->| 3. set value
                             4. 释放 key 的锁

更新或删除

事务和锁能保证数据库在更新完成时，该 key 未被缓存，且不在缓存的路上。

将第 4 步放在事务的最后是最佳实践，因为如果该 key 已被缓存，那么在此之前，所有的 Get 都会命中， 而不是在队列中等待。

::

客户端                Umem-cache               数据库

|-------------------------------------------------->| 1. 开启事务
                                                    | 2. 获取 key 的写锁
|<--------------------------------------------------| 3. 更新或删除 key

      删除 key
|-------------------->|	4. 删除 key 或关闭持有 key 锁的连接
|<--------------------|


|-------------------------------------------------->| 5. 提交事务

集群

集群的负载均衡靠的是客户端散列，在集群模式下，每个 key 都携带了 8 字节的版本号前缀， 这个版本号与它要散列到的成员的版本号一致。 一旦 key 散列到的成员发生变化，对应成员的版本号会增长，这个版本号是由 Raft 共识协议来维护的， 并且我们保证了所有成员的版本号都不同。 所以一旦 key 散列到的成员发生变化，旧成员上的 key 就会因为版本号的变化自动失效， 这个机制就保证了同一时间不可能有两个成员上存在相同的有效的 key 。

集群也有一个版本号，这个版本号可以用来快速判断集群是否发生变化，这个版本号也是由 Raft 共识协议来维护的。 每次集群成员变更或者成员可用状态变更都会导致集群版本号增长。 所以集群版本号的增长也代表着集群中 Key 的散列分布发生了变化。

我们的集群协议提供了 Leader ，Authority 和 Cluster 三个命令， 每一个缓存命令都会向集群获取执行授权，这个授权通过 Authority 命令来执行，Authority 命令会返回当前集群的版本号。

下面是客户端实现流程：

::

                            -----
                            |开始|
                            -----
                              |
                              v
                  -------------------------
                  |随机选择服务器查询领导者信息|<----------
                  -------------------------          |
                              |                      |
                              v                      |
             ----------------------------------      |
             |向领导者查询集群信息，得到 version V1|      |
             ----------------------------------      |
                              |                      |
                 ---------------------------         |
                 |           并行           |         |
                 v                         v         |
 ----------------------------------      -----       |
 |向领导者请求认证权威，得到 version V2|      |缓存|       |
 ----------------------------------      -----       |
                 |                         |         |
                 ---------------------------         |
                              |                      |
                              v                      |
                             / \                     |
                            /   \                    |
                           /     \                   |
                          /V1==V2 \                  |
                          \       /--------否---------
                           \     /
                            \   /
                             \ /
                              |
                              是
                              |
                              v
                            -----
                            |结束|
                            -----

[cloudzhou]

一直讨论类似缓存一致性问题，直到我选择了更简单的方式
你的这个实现方式太重度了，以至于无法验证正确性

我的方式很简单：依赖 db/redis 的一致性
简单说：
无论是 insert/update/delete ，都认为是变更，version + 1
cdc 监听事件变更：
（ version, object ）变成一个事件

cache:
object_key_$id : {version: $version, objcet...}

redis 更新，update if version > current
简单高效，不阻塞更新过程，允许瞬间 cache 差异

---
你这套机制，除非高一致性才需要
但是，到了这一级别的高一致性，简单依赖 db 就好了，没必要这么复杂

[LDa]

@cloudzhou 确实 深有同感

[cloudzhou]

@LDa 他这里还有一个非常难解决的问题，就是 update 然后其实隐含多个 cache 更新
比如 update order set xxx where yyy ，导致多个 order 修改
这时候，触发的不是单个 order 更新，是批量更新
cdc + 版本号，解决这个问题

[imchuncai]

@cloudzhou 你说的多个 cache 更新的问题是在我流程里是不存在的，因为第一步就是 select for update 去拿写锁，所有要改的都已经查出来了。
至于你说的前面一套方案，你还要考虑很多问题，第一你的业务和 cdc 是需要对 key 的格式有约定的，这一点是需要同步的；第二数据库需要维护 version 字段，业务上 insert/update/delete 这些操作你都需要额外得去维护 version 字段，万一忘记更新就会变成永久的不一致，连最终一致性都达不到。
其实这些都不是问题，只要你能接受短暂的不一致，只要你够小心。我的观点是如果缓存能直接提供强一致性，你不需要考虑额外的东西，业务的实现会变得简单，也不需要部署额外的 cdc ，考虑 cdc 的可用性。

[imchuncai]

@cloudzhou 另外在部署集群的情况下多个 cache 更新，redis 连最终一致性都保证不了，因为 redis 不支持跨节点的 lua 脚本

[imchuncai]

@cloudzhou 不好意思，我说的 redis 不支持跨节点的 lua 脚本的问题是不存在的，因为你的方案是一条一条独立更新的

[imchuncai]

@cloudzhou 我的方案只有 Get 操作才会对缓存进行写入，而你的方案所有的操作都会对缓存进行写入，我的方案对热点数据更友好，冷数据的修改可能永远都不会触发写入缓存

[cloudzhou]

@imchuncai

1. 因为第一步就是 select for update 去拿写锁，所有要改的都已经查出来了。
你这一步，对业务的开发，已经影响很大了，不管是模式还是性能，开发肯定习惯 update/delete 一个 sql 搞定

2. cdc 是需要对 key 的格式有约定的
这就太简单了，${table_name}_${id}，约定大于配置即可

3. 第二数据库需要维护 version 字段
这个 version ，可以放在 db column ，也可以是独立的 redis ，或者 kv db ，核心还是 ${table_name}_${id}: ${version}。如果是 db column ，那么天然就有，update version = version+1 ，如果其他途径，无非就是变更 version+1
因为 cdc 是顺序的，所以 version + 1 然后设置一个最新的 table object 数据，没问题，只需要确定 version 递增，和关联表数据，没有乱序即可

cdc 是难得的，把所有变更都纳进来的一种方式，不管从哪里更新

cache 这玩意，就不要讲究高一致性了，raft 带来的损耗，还不如去掉缓存，把 mysql innodb cache 加大点

[imchuncai]

@cloudzhou 如果是中途引入 redis 呢？你这种方案应该怎么操作？应该会很比较复杂吧。

[imchuncai]

@cloudzhou 还有个一理论上存在比较极限的一个情况，比中途引入 redis 更极限，会破坏最终一致性：
1. 连接 1 cash miss ，get 数据库 version = 1, set redis 还没发射请求
2. 连接 2 更新数据库 version = 2, cdc set redis version = 2 成功
3. redis 因为缓存压力驱逐了该 key ，在中途迁移的情况是，大量 key 的写入，导致了该 key 的驱逐
4. 连接 1 停止卡顿，set version = 1

[cloudzhou]

@imchuncai

Get 操作才会对缓存进行写入
你这里我看不懂，Get 有 cache 就直接拿，不要等 set 结束了，cache 怕的是持久不刷新，不是这种场景

key 的驱逐这个情况，是不考虑的，这要考虑，就 Keyspace Notifications 订阅，然后 row 数据重放一下就行了，version 已经自带。

我这个方案，其实核心差异是：version 是否是 db 自带，各有优劣
version db 自带，所有问题都非常简单，任意重放 row 数据即可，除了 update/delete 需要注意

如果 db 不自带，这时候 version 来自外部，尤其要考虑到 cache miss ，就有些复杂度

但是如果使用你这个方案，那问题就非常简单了：
1. cache miss 触发一个 miss 事件
2. 在补充 cache 的时候，设置 lock key 周期，单位时间 lock time +1
3. 补充 cache ，检查 lock key 没有其他写操作，也就是 lock time 依然是 1 ，说明补充 cache 成功
4. 如果 lock time 不等于 1 ，说明有其他写操作，设置 next try 重试
5. 其他写操作，lock time +1

这个逻辑和你的 缓存未命中 是很想的
就是说，你的方案，在解决 db 没有 version 情况下，我是可以用的

---
cache 一定要做到，读没有代价，写稍微带来代价，尽量异步，允许缓存不一致窗口，但是不要永久缓存
cdc 这种后台订阅，事件驱动，刷新 cache 的方案，对读写都是没啥代价的

[imchuncai]

@cloudzhou 你可能没理解我 10 楼说的情况，我说的就是 db 有 version 列的情况下，没法达到最终一致。我画个图：
::

客户端 redis 数据库
1.客户端 A：get key
|------------------------->|
| 2.未命中
3.返回 miss |
|<-------------------------|

4.客户端 A：get key
|--------------------------------------------->| 5. version = 1
|<---------------------------------------------|

6. 客户端 B：update key
|---------------------------------------------->|
| 7. 更新成功，version = 2
|<----------------------------------------------|

8.CDC：set key
|------------------------->| 9.set value, version = 2
|<-------------------------|

10.redis 因为压力导致驱逐了 key

11.客户端 A: 因为 miss 触发 set key
|------------------------->| version = 1 （因为 version = 2 的条目被驱逐了）
|<-------------------------|

最终 key 的 version 在 redis 为 1

[cloudzhou]

@imchuncai 没错，我是理解你这个意思，和你的图一样的，核心无非是高版本被驱逐，低版本自然就占据

8.CDC：set key ，这时候是不是已经设置到 redis ，然后又被驱逐，然后 version = 1 设置进去，对吧

1. redis 驱逐本身不合理，意味着 cache 有丢失
2. 我们监听 redis Keyspace Notifications ，驱逐事件，根据 id 重新读取 version = 2 数据进行重放，覆盖更新 cache

[imchuncai]

@cloudzhou 监听 redis Keyspace Notifications 是改不了现状的，只是延长了步骤 10 的时间，只要二次驱逐发生在步骤 11 之前，就没有意义，因为步骤 11 的 version 是在第 5 步拿到的。引入 redis Keyspace Notifications 只是把极限的情况拉到更加极限罢了，此时业务又在不知不觉中变复杂了。另外 Umem-cache 是一个缓存，它有内存上限，如果把 Redis 当作数据库用而不是缓存，我们的讨论没有意义，因为此时 Umem-cache 和 Redis 就是截然不同的东西。而在把 Redis 当作数据库使用的情况下，再引入 DB 和 CDC 我感觉也没什么意义了。

[imchuncai]

@cloudzhou 如果 key 被驱逐了就重新 Set ，只会反复触发驱逐。

[cloudzhou]

@imchuncai 你有没有想过驱逐这种情况，接下去所有的 update 都可能是失败的

你的设计，无非只是用 raft 做一个全局 lock 而已，lock 成功，当时写失败（驱逐）
cache 一样长期都是失败的

缓存讨论驱逐，几乎没有意义的，时序完全无法保证

[cloudzhou]

@imchuncai 读写 cache 失败，导致的并发问题，vs cache 逻辑的设计，是两个问题

[imchuncai]

@cloudzhou 在我的步骤里读写 cache 没有失败，只是有延迟。缓存最重要的就是驱逐的设计，而数据库是没有驱逐的。

[cloudzhou]

@imchuncai 你这里根本没有涉及到真实的 cache 存储啊，除非你存储到内存缓存？你要是接上 redis 或者任何远程 cache ，这写 cache 不就是会出现吗？还是说你用 raft 作为 cache store ？

[cloudzhou]

我大概理解你，你这里就充当了 cache 的角色，通过 rpc 然后触发 cache 读取/更新，存储 cache 的就是你这服务，通过 raft lock 的机制，保证了读写的时序和并发安全。

然而，你这个机制略显尴尬：

1. to c 端，大流量大并发，几乎不可用，raft 用来保证集群仲裁而已，连 kv 都谨慎使用，没见过谁敢接 c 端请求的。讲究啥一致性，cache 周期一过能刷最新值就好了

2. to b 端，尤其是银行等强一致性，db 走起，硬件堆上，让 db 自己做好 cache 缓存就好了

你这套机制，适用场景，非常少。

[imchuncai]

@cloudzhou Umem-cahce 是 Redis 作为缓存的替代品,我设计它的初衷就是提供强一致性，这是 Memcached 和 Redis 都做不到的

[valord577]

如果是推广的话 技术思路值得学习; 经历过电商库存超售的事件 我还是会选择一楼的方案 `到了这一级别的高一致性，简单依赖 db 就好了` 只依赖 db 记录的库存数 宁可查询慢一点

[imchuncai]

@valord577 不明白你说的，缓存只是加速查询。更新本来就是只依赖 db ，也就是 select for update ， 是绝不可能从缓存查数据的。

[valord577]

@imchuncai 你要推广一个库或者一个组件 你得解决实际的业务问题。在什么业务 什么场景下 用你的技术方案解决了 并且对比竞品有什么更好点 这样才能推广地更加顺利。

看了下你和 @cloudzhou 的对话 (纯个人主观结论): cloudzhou 业务经验很丰富 他在用实际业务经验说明什么技术方案最合适 尤其是 20 楼的描述 很符合行业的解决方案; 而 op 你的描述给我的感觉是: 你只看重技术本身 而没有结合业务。

所以我说 你的代码 只值得学习技术思路 做不了业务解决方案

[cloudzhou]

@valord577 作为技术方案探讨，也很不错了，毕竟，ai 时代，已经不提技术了 :~

他这套方案，有应用场景，但不是 cache ，而是分布式 lock
lock 要做细腻，也有很多细节可思考：
1. 乐观/悲观，读/写锁，最高并发锁？令牌桶？（问号概念是我拍脑袋的）
2. 锁周期，不能导致资源长期不可用
3. 顺序，以及锁关联的 do once
等等

借助 raft 机制下，做一个全局的分布锁 lib ，用在敏感领域，大家用起来如同本地 lock

@imchuncai
昨天有几个问题没有回答：

Q: 而你的方案所有的操作都会对缓存进行写入，我的方案对热点数据更友好，冷数据的修改可能永远都不会触发写入缓存
A: 其实这是策略问题，我收到 update 事件，也可以根据是否在缓存里然后更新，缓存依然是按需的

Q: 驱逐的问题
A: 依然是策略问题
- 可以根据 ttl 尽量避免驱逐（现实中采取方案，因为 cache 驱逐是非常不好的行为，无法确定驱逐的数据是否重要）
- 在驱逐情况下，你提到的并发问题，可以根据监听 redis Keyspace Notifications 然后一个延迟周期，只更新 cache 已有的 key ，这样避免持久相互驱逐，同时更新并发竞态数据

[imchuncai]

@cloudzhou 酒逢知己千杯少 这是我写的 Umem-cache: https://github.com/imchuncai/umem-cache
第一个问题：你说的是对的，我昨天也是想过了，确实是策略问题，CDC 甚至可以直接选择 delete 操作，就跟我的方案一样了

第二个问题：我设计 Umem-cache 是直接不支持 ttl ，我认为这很烦人，很多时候我根本就不知道要设多久。我是统一采用了 S3-FIFO 算法，按热度自动淘汰，我的测试中是显示命中率比 Memcached 高出 10%，比 redis 的 lfu 策略高出更多，我的测试项目也是在 github 开源的。然后你提到的驱逐情况下，只更新 cache 已有的 key ，这其实相当于就是什么也不做，因为监听的就是驱逐事件，此时 key 已经不在 redis 了。在我所列的流程里，就是 key 不在 redis 会导致旧数据被缓存起来，导致没法实现最终一致，它有些极端但是理论上存在。

至于锁周期只在更新的时候存在，而能被放在缓存的数据应该是读得多极少要改动的，不然完全是不应该缓存起来的。

最后是集群问题，我也是有意在这避而不谈，因为 raft 也是很复杂，特别是它是为持久化集群设计的，我把它引入到缓存是要做一些适配，讨论起来我不知从何说起，评论区会变得混乱。因为我是深入了解过 raft ，在我的项目里也是有文档说明了我对 raft 存在的不足之处的一些见解，甚至我都没法翻译到中文来，专业术语太多了。我所有的设计都是为了一个最终的目标，就是简单性，我提供极少的配置，然后我也不想用户去引入其他的系统去为一致性和缓存击穿擦屁股，防缓存击穿在我这套方案里也是浑然天成的，不需要额外的语义。

[imchuncai]

@cloudzhou
第一个问题：我又想了下，不 set 会有更严重的并发问题，相当于此时没法用 version 去避免覆盖了
1. 客户端 get key ，miss ，查数据库 version=1
2. 数据库更新，version=2
3. CDC 触发更新，redis 不存在该 key,所以不更新
4. 第 1 步在查询完成后 set redis version = 1

第二个问题:监听驱逐事件会触发数据库的读取，会增加数据库压力。

[cloudzhou]

@imchuncai

Q 不 set 会有更严重的并发问题
A 你这个问题，和监听驱逐事件是一个类型，就是你说的竞争态：
“在短时间，高版本事件的不设置（不管是驱逐还是没有不处理 update 事件到 cache ），导致低版本进行覆盖”

所以这里我有一个简单处理方案：
*** 引入一个延迟周期，只更新 cache 已有的 key ，这样避免持久相互驱逐，同时更新并发竞态数据 ***
等于你的 3. CDC 触发更新，redis 不存在该 key,所以不更新，这一步，是有一个延迟周期的，确保 “理论上” 覆盖 1 ，4 这个 T 时间周期

一句话总结，按需写 cache 操作（驱逐、更新触发），延迟一个周期，以便覆盖可能历史低版本（读触发）

---

当然，这不是真正并发安全。
但是如果真要做到一致性，这个是好做的。逻辑如你实现方案
你看：
version=1 ，事件 1 ，4 ，是一个事务
version=2 ，事件 2 ，3 ，是一个事务

这两个事务都是同一个 data ，在这里面做分布式锁就可以了

---

更简单的工程实现：
触发事件然后缓存集中处理，也就是没有并发态：
1. 读触发 cache 更新，触发 event: (read, table, id)
2. 驱逐、写触发 cache 可能更新，触发 event: (write/volatile, table, id)
3. kafka 集中监控，按照 table 分区，同一个 table 事件顺序处理
4. 无论是 1 ，2 事件，从 db 拉去新数据，read 操作直接 cas 更新 cache ，write/volatile 一样，cas and only exists

mysql 在 select by id 这一块，速度高的超过你估计，这些事件都意味着对应 table, id 刚访问过，再次读取都只是从 db 的 cache 获取
无论是 ttl ，volatile 都可控

你看这个实际的工程事件：
1. 无论读写，对业务都没任何影响，分发事件可以搞个异步，goroutine channel with max length ，消费不了直接丢弃
2. cache 动态可控，消费点做逻辑，无论是 ttl 还是 update 事件是否进入 cache

[imchuncai]

@cloudzhou 你给的方案太多了，我有点绕不过来了，而且越来越复杂，引入的组件越来越多。

[zzhirong]

@imchuncai 强一致本身就很难实现，你给出的方法大体可行，代价就是丢失了性能，读写都需要锁，几乎等同于串行，如果涉及到集群，就更复杂了。

@cloudzhou #1 基于 Redis 给出的最终一致性（允许短暂的不一致）方案，即便在这个基础上再做一些修改，还是无法保证强一致性，优点就是性能更好。