《拒绝最终一致性的脏读陷阱： 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 都做不到的