并发 lru 设计

最近线上遇到一个问题，在导入 25w 表之后执行 'select * from t limit 1' 这样的操作很慢。看了一下 profile 发现 CPU 都是被统计信息的缓存更新消耗掉了。

原因是我们在缓存更新的实现，使用了一个 copy-on-write 的更新机制。最初写代码的人可能没有考虑统计信息的数据量级。每一个小修改，比如更新其中一张表的，这个 copy-on-write 都要把 25w 的表的统计信息拷贝一遍，然后原子操作让 handle 指向更新后的那份内存，旧的那份就等着 Go 的 GC 机制去清理。copy-on-write 是为了并发安全，因为同时可能存在统计信息的使用和更新修改。用 copy-on-write 来保证并发安全本身倒没什么，只是这个场景不行。真正的使用场景一定要求：1. 更新的频率不高；2. copy 的数据量不大。

正好是通过这个 case，去看了一下 lru 缓存的一些设计点，尤其是并发这块的考量。最有价值的参考信息是 Ristretto 的这篇博客。

直接改成锁的方式行不行？如果是我们的场景，所有读、写操作一把大锁，可能不行。更新统计信息缓存需要时间，而更新期间将统计信息锁住，会导致读统计信息的连接卡顿。可能卡顿到几ms甚至上面ms可能是很平常的，会直接反映到用户的 SQL 查询请求那边，就会出现莫名其妙的 99 999 延迟响应高。而且能写得出这种代码的人，往往没有足够的可观察性意识，不会去记录 metrics，最后就会造成上线后排查困难，因为去排查那个人没有什么上下文信息。最后就是只知道慢，却又不知道慢在哪儿，就很崩溃。尤其是 99 999 这种慢的，它不是一直发生，只在是读写冲突时发生。

说到这儿，顺带讲一个 Go 很容易遇到的坑，带锁进入临界区以后的内存分配，触发了 GC 导致持有锁的 goroutine 带着锁上下文切换出去了，其它的 goroutine 都等待着这把锁，进而导致整体 goroutine 的延迟的升高。这类问题基本无法避免，带 runtime 的语言都有共同的，享受了便利就得容忍性能的不可控的点。可能有时候抖一下几ms 就过去了，还不好抓到现场，只知道自己用 Go 写出来的东西 999 延迟不稳。

lru 缓存本质上就是两块东西，一块是一个 hash 表这类缓存的 kv 结构，另一块是淘汰策略。如果简化成 nru 实现，淘汰策略这块就是用一个链表维护，每次访问把节点挪到队头，不被用到的自然被慢慢挤到队尾了，然后回收的时候就按队尾开始淘汰一批。

涉及到两个数据结构，就涉及到这两个数据结构的并发安全。

对于 hash 表，常规的减少锁冲突的方式，就是分 shard，比如说划分成 128 个 shard，每个 shard 上面用各自的锁，从而减少锁冲突。但是注意，划分 shard 解不了热点冲突问题。因为访问模式上，对所有 key 的访问分布并不是均匀的，可能有点热点 key。而热点 key 的访问还是会在同一个 shard 上面的锁冲突。

对于淘汰策略(policy)的维护，最重要的优化就是 batching。即，不需要每次访问都去更新 policy，而是 batch 一批之后去处理。 ristretto 里面，就是用 sync.Pool 维护一个 ring buffer，等 buffer 满的时候去更新一次。另外，读和写操作都是通过这个队列做了解耦的。 假设没有任何优化处理，一个 naive 的方式是每个客户侧并发都 获取读写锁 -> 操作 -> 释放读写锁。而通过队列解耦之后是，所有操作发到队列里面就返回了。后台线程异步却从队列里面取出操作并执行。

读写队列是很快的，因为没有持有锁之后去处理复杂逻辑。而后台异步线程数据是可以控制的，比如说 naive 方案中，用户并发用 1k 的 goroutine 访问，那么锁竞争在这么多 goroutine 里面的，而后台开 10 个 goroutine 处理的话，并发冲突就降到了这 10 个 goroutine 之间。