并发 lru 设计

2023-06-02

最近线上遇到一个问题,在导入 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 之间。

lruconcurrent

HNS.to is a highly insecure way of browsing Handshake domains and should only be used for demo or educational purposes. Click to see preferable resolutions methods