链表和哈希表拼起来,就是 LRU

难度 ★★★★☆ · 前置:数组到底快在哪 | 一句话结论:命中率由访问分布决定,哈希表加双向链表只负责把定位和排序压成 O(1),代价是每次命中写六个指针。

一个容量一千的缓存,一百万个请求打进去,命中率可以是 86%,也可以是 0。两组实现差不到三十行,请求序列换一种形状,数字就翻了面。我把四组数并排贴在一张表上,看了很久:同一台机器、同一版 Go、同一个容量,能决定结果的只有请求是怎么来的。写缓存最容易搞反的地方就在这儿,力气全花在挑结构、调哈希函数、算负载因子上,拍板的是上游那条流量曲线,而它不在你的代码里。机器是 i9-14900HX,go1.27.2 windows/amd64,GOMAXPROCS=32;一百万个请求,容量一千,读不到就回源,回源的结果写回缓存。

先写最像样的那个错法。

第一版是一条切片,0 号放最旧的,末尾放最新的。命中就抽出来塞到末尾,塞不下先砍 0 号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
type item struct {
key uint64
val int
}

type naive struct {
items []item // 0 号最旧,末尾最新
cap int
}

func (c *naive) get(k uint64) (int, bool) {
for i := range c.items {
if c.items[i].key == k {
it := c.items[i]
copy(c.items[i:], c.items[i+1:])
c.items[len(c.items)-1] = it
return it.val, true
}
}
return 0, false
}

func (c *naive) put(k uint64, v int) {
for i := range c.items {
if c.items[i].key == k {
c.items[i].val = v
return
}
}
if len(c.items) == c.cap {
copy(c.items, c.items[1:])
c.items[len(c.items)-1] = item{k, v}
return
}
c.items = append(c.items, item{k, v})
}

这段代码挑不出错。最久没被用过那条规则,它维护得很老实:Get 挪到末尾,Put 满了砍 0 号,重复的 key 就地更新,一个分支都不少。拿它跑 zipf 1.2 的一百万次请求,命中 861640 次,跟后面那版标准实现一模一样,连一次都差不出来。

问题全在代价上。

实现 耗时 每次 命中
哈希表 + 侵入式双向链表 18.748 ms 19 ns 861640
切片 + 线性找 239.1913 ms 239 ns 861640

命中一次,平均要扫半条切片:一千个元素线性找,五百次比较;找到之后还要 copy 一次,把后半段整体往前挪一格。一千个元素、每个 16 字节,一条切片 16 KB,每次命中都在碰这一整段内存。容量小的时候它完全能跑,一千、两千、五千,肉眼看不出来,一次操作也就几百纳秒,业务里那点 QPS 摊不平它;等到每秒几十万次,或者容量上万,这条切片才真的开始疼,而 pprof 只会把时间记在 get 那一行上,不会告诉你是因为你拿一条切片当了索引。这类写法我在别人的项目里见过好几次,第一版就能跑通、能过测试、能上线,所以它活得比很多正确但复杂的实现都久。

命中数一个不差。

哈希表知道 key 在哪,不知道谁该走

map[uint64]int 快,问题是它不存顺序。它能告诉你这个 key 在不在、值是多少,一秒查一千万次都行,但它不记录谁先来谁后到。要淘汰,你得回答最久没被访问的是哪个,map 里翻不出这个答案。能想到的补救是给每个 value 挂一个时间戳,淘汰时扫一遍找最小的:一次淘汰 O(n),比切片版还差,因为连顺序都要现算,每读一次又都得写一次时间戳,本来只读的操作被拖成了写。container/heap 也救不了,堆里按时间排序,可节点被访问之后要改位置,你得先知道它在堆里第几个,那又是一次查找。

时间戳补不出顺序。

双向链表反过来。维护顺序几乎不要钱:命中一个节点,从原位摘下来挂到头部,六次指针写,O(1),跟链表多长没关系。可你得先找到那个节点,链表没有下标,只能从头走,平均 n/2 步。

一个管定位,一个管顺序。

LRU 每次 Get 要同时回答这两件事,两个都得留,两个都得是 O(1)。拼法是让指针互相指:map 的值不放数据,放链表节点的地址。查找在 map 里做,拿到的是节点指针;顺序在链表里维护,拿到指针就能直接摘挂。定位的结果正好是排序结构里的位置,两个 O(1) 接在同一个动作上,中间没有一次额外的查找,也没有一次额外的分配。缺了哪一半都不成立,只有 map,顺序没了;只有链表,定位退化成线性扫。

一次命中写六个指针

实现只有三个动作:摘下来,挂到头部,满了摘尾巴。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
type entry struct {
key uint64
val int
prev, next *entry
}

type lru struct {
m map[uint64]*entry
head, tail *entry // 两个哨兵:head 之后最新,tail 之前最旧
capacity int
}

func newLRU(capacity int) *lru {
head, tail := &entry{}, &entry{}
head.next, tail.prev = tail, head
return &lru{
m: make(map[uint64]*entry, capacity),
head: head,
tail: tail,
capacity: capacity,
}
}

func (c *lru) unlink(e *entry) {
e.prev.next = e.next
e.next.prev = e.prev
}

func (c *lru) pushFront(e *entry) {
e.prev = c.head
e.next = c.head.next
e.next.prev = e
c.head.next = e
}

func (c *lru) get(k uint64) (int, bool) {
if e, ok := c.m[k]; ok {
c.unlink(e)
c.pushFront(e)
return e.val, true
}
return 0, false
}

func (c *lru) put(k uint64, v int) {
if e, ok := c.m[k]; ok {
e.val = v
c.unlink(e)
c.pushFront(e)
return
}
e := &entry{key: k, val: v}
c.m[k] = e
c.pushFront(e)
if len(c.m) > c.capacity {
oldest := c.tail.prev
c.unlink(oldest)
delete(c.m, oldest.key)
}
}

unlink 两次赋值,pushFront 四次,一次命中六次指针写。头尾各放一个哨兵 entry,摘挂的时候不用判断 nil,少四个分支,代价是两个永远不存数据的节点。

这叫侵入式链表:节点自己带 prev 和 next,map 的值是 *entry,一个 key 在内存里只有一份。Java 的 LinkedHashMap 走了另一条路,它在 HashMap 的 Node 上直接加了 before 和 after,等于在同一批节点上穿两条链,桶链一条、访问链一条,一次分配解决两件事,代价是每个 Node 都多两个指针,不管那个 key 用不用得上访问链。Go 的 container/list 是第三种,Element 是个独立类型,你得自己包一层,或者再存一个 map 从 key 找到 Element,多一次分配、多一次间接。三条路都行,差别就在每命中一次多跳几次指针、多占多少字节。

每次 Get 都在写,这一点最容易被忽略。unlink 改两个指针,pushFront 改四个,六次写落在两处内存上:被摘的节点一处,头部一处,两者不相邻就是两次缓存未命中。单线程下这是几个纳秒,可以忽略;多线程下它就是 LRU 难做并发的原因,命中率越高写越频繁,读操作要么拿写锁,要么上 CAS 重试,怎么绕都绕不开那六次写。1000 个 entry 散在堆上,每个 32 字节,key 8、val 8、两个指针 16,map 的桶还得另外算,一次命中至少碰两处不连续的内存。

命中率从 0 到 86

命中率只跟一件事有关:这次访问的 key,上一次被访问之后,中间插进来过多少个不同的 key。这个数叫重用距离,距离小于容量就命中,大于容量,那个 key 早被挤出去了。它跟用什么结构存没关系,跟哈希函数没关系,跟有没有用哨兵更没关系。

四种分布,同一份实现。

分布 key 空间 单实例 8 分片
uniform 均匀随机 10000 10.05%(100506) 10.06%(100623)
zipf 齐夫 1.2 10000 86.16%(861640) 86.16%(861582)
loop 循环扫 1001 0.00%(0) 87.33%(873251)
sequential 一遍过 1000000 0.00% 0.00%

uniform 最好算。key 空间一万,容量一千,理论上限就是一千除以一万,百分之十,实测 10.05%,几乎没有余量,说明这一千格用得极其干净。这条曲线是线性的,容量翻倍命中率翻倍,一千和两千的差别是十和二十。

zipf 1.2 完全另一副样子。头部一两百个 key 吃掉大半访问,容量过了一个点之后再翻倍,只多几个百分点。86.16% 在容量一千的时候就是这个值,加到两千也不会变多少,剩下的 13.84% 是长尾,靠加容量追不回来。

容量只在一种分布上是杠杆。

loop 和 sequential 是两种没有重用的极端。loop 扫 1001 个 key,容量 1000,永远差一个;sequential 一遍过,每个 key 只出现一次,命中率的上限就是零。这种输入下任何容量有限的缓存都是零,跟 LRU、LFU、FIFO 都没关系。

四种访问分布下,单实例与 8 分片的命中率对比:uniform 与 zipf 两组几乎等高,loop 一组从 0 跳到 87%,sequential 两组都贴在零线上

前两组的柱子几乎一样高,第三组差了八十七个点,第四组两根都贴着地。

定结果的是输入。

分片之后,慢了百分之十

分片是把 key 路由到 n 个独立 LRU 上,每片有自己的 map、自己的链表、自己的一把锁,容量一千平均分,8 片就是每片 125 格。

分片数 每片容量 命中率 耗时
1 1000 86.16% 20.317 ms
2 500 86.16% 19.9772 ms
8 125 86.16% 22.4366 ms
32 31 86.08% 23.6003 ms
128 7 85.25% 21.4295 ms

命中率几乎不动。1 片到 32 片,86.16 到 86.08,掉在小数点后两位。128 片掉到 85.25,每片只剩 7 格,全局的最久没用被拆成 128 个片内最久没用。耗时倒是涨了,20.317 ms 到 22.4366 ms,8 片比 1 片慢 10.4%。

2 片那次 19.9772 ms 是唯一比 1 片快的,差 0.34 ms,我倾向认为是噪声。

单线程下分片为什么慢,三笔账。第一笔是路由,每个请求先算一次下标,再取片指针,多一次间接寻址。第二笔是局部性,一个 1000 条的连续工作集被拆成 8 份 125 条,每份的 map 头、两个哨兵、桶数组各在各的堆块上,跳转目标从一处变成八处。第三笔是淘汰,全局最旧变成片内最旧,命中率掉的那零点几个点就是账单。三笔加起来,比省下的那点更短链表值钱,而单线程里根本没有锁可省。

有锁可抢,分片才值钱。

分片提升吞吐这句话有边界:有竞争时它才值钱,没竞争时它只是把一次访问拆成两次。表里 8 片的 22.4366 ms 和前面单实例的 18.748 ms 不是同一组实验。分片扫描那组为了让每片独立计数,埋点位置跟单实例那组不一样,基线本来就被抬高了一点。要横着比,看同一张表里的 1 片和 8 片。

循环扫 1001 个 key,一片都没中

loop 那一行最反直觉。

单实例 0.00%,一百万个请求一次都没中;切成 8 片,87.33%,差不多是从没有变成几乎全中。

原因在重用距离的形状。循环访问 1001 个 key、容量 1000,LRU 每次淘汰的正好是下一次要用的那个:最久没被访问的,就是循环里马上要轮到的那一个。顺序扫描和比容量大一点的循环都能触发,跟实现写得好不好没关系。

分片把这个循环打散了。一千格切八份,每份 125 格;1001 个 key 按哈希摊到八片上,大约是七片各 125 个、一片 126 个。前七片的工作集刚好等于容量,扫一圈每个 key 都还在,全中;第八片多一个,永远差一格,全不中。七乘 125 除以 1001,理想值 87.41%,实测 87.33%,差的 0.08 个百分点是冷启动那一两百次。原始那一整条流被切成八条互不相干的短流,每条都装得进自己那格,坏形状就没了。

同一条规则,符号反了。

坏分布得是循环;循环长度得刚好比容量大一点点,大十倍就没救;分片的切法得让每片的工作集刚好装进每片的容量。三条缺一条,分片就退回纯开销:zipf 下 86.16 对 86.16,没涨;uniform 下 10.05 对 10.06,也没涨。

分片数与命中率、耗时的对照:横轴是 1、2、8、32、128 片,命中率几乎是一条平线,耗时在 8 片之后抬起来,128 片因为每片只剩 7 格掉到 85.25%

五万次随机操作,两边每一步都一样

LRU 的 bug 不在算法上,都在边界上。我拿朴素版当对照,跑五万次随机操作,每一步都比对返回值和缓存内容,两边逐次一致。边界就那么几个:容量等于一,摘完 head 就轮到 tail,别把哨兵当成真节点;Put 一个已经存在的 key,要更新值并且挪到头部,只更新值不挪位置,顺序就错了,这个错在命中率高的分布下几乎看不出来,因为那个 key 大概率马上又会被用到;淘汰时先把 key 从 entry 里读出来再 delete,unlink 之后指针还在,delete 之后 map 里就没这个 key 了,两句写反就删错;len(m) 才是真实容量,别拿容量字段当计数器。

够随机,才撞得出边界。

自己写,还是直接用

单进程、容量一万以内、没有 TTL、读写比极高,四十行自己写。你要的只是一个按访问顺序排队的 map,引入一个库反而多一层依赖和一次版本升级的风险。

跨进程或者要 TTL,交给 Redis。它的 allkeys-lru 是近似 LRU:淘汰时采样几个 key,挑其中最旧的,不维护全序。精确 LRU 每次读都要写,近似 LRU 只花几次采样。

命中率差多少,上面那些数能回答一半:实现换了,命中数可以一个不差,精确性压根不是决定命中率的那一项。

要并发,先量锁竞争。pprof 的 mutex profile 里没有热点,就别分片;有热点,再按 key 分,并且接受 128 片时每片只剩 7 格的那个代价。

要按权重淘汰、要抗扫描,用现成的。Caffeine 和 ristretto 都把这件事做完了,W-TinyLFU 那套准入过滤器专门对付 loop 这种一次性的扫描流,它比 LRU 多花的是一次频率统计。

我现在的默认选择是:能自己写就自己写,四个函数加两个哨兵,可读、可调、出错好查;一旦要跨进程、要 TTL、要并发,立刻换成现成的。判据只有一条,换实现之后命中率会不会跟着变。这张表说不会。