go cache 实现综述 « 一派胡言

本文是 The State of Caching in Go 的读书笔记，希望通过本文，理清缓存设计的一些思路，同时考擦已有的 go 缓存实现的方案，“鉴于往事，有资于治道也”。

缓存的几点要求

并发；
可以限制内存使用；
随着 goroutine 或 core 的数目增长，scale well；
非随机 key 的情况下， scale well；
缓存命中率高；

几种 trival 的方案

Go map with sync.Mutex

直接用 Go 的 map 来做缓存，这种方法当然简单实在，加上 sync.Mutex 可以避免并发的问题。但首先它不会限制内存的使用，其次，goroutine 一旦多了，所有 goroutine 都在等锁释放，性能下降了。（但是我看不出它跟 key 的分布有什么关系，感觉缓存命中率也不是考虑的范围。原文说它不符合要求2-5，这令我觉得很诧异。

Go map using lock striping

关于什么是 lock striping, 可以看这个回答。通过 lock striping，多线程（多 goroutine) 场景下，不会整个缓存锁住（只会锁住一部分），解决了要求3，但是依然没有限制朱内存使用。

LRU cache

然后 Dgraph 的开发人员使用了 groupcache 中的 lru 缓存。整个 lru 实现非常经典：一条限制了长度的链表记录了对应的 key 的新旧情况，然后一个 map 记录了对应的 key-value 对。通过限制链表长度来限制内存使用存在不足——谁知道你往缓存里面存些什么东西。当然它们还对这个 lru 做了二次开发——加了锁。

然后他们就被悲哀地发现，这种双链表的 lru 实现每次读都要写一次链表（更新记录的新旧情况）实在太坑了，它带来了大量的 contention，所以这种方案不符合要求3-4

Striped LRU cache

这种方案他们都懒得试了，只是做了性能测试，并认为它不会满足要求4。

流行的缓存实现

bigcache

bigcache 对先对 key hash 分配到不同的 shard 中，shard 的数量可配置（默认1024）。每个 shard 有一个 ring buffer 实际存储数据，有一个 map 记录 key 对应的 index，如果同一个 key 被 set 多次，那么前面的 entry 会被置为 invalid。 shard 会在容量不够切且没有到达上限的时候扩容。缓存有生存周期，每个生存周期都会把过期的缓存清除。