背景

使用过Redis做缓存的小伙伴肯定知道Redis里面有很多种缓存淘汰策略，其中有一种就是LRU。LRU其实就是最近最少使用(Least Recently Used，LRU)，一般它的实现是使用一个双向链表：

比如一开始链表如下，则元素3是最近被访问过的，元素1是最久没有被访问过的。

如果我们这时候访问元素1，则把元素1重新放到链表头部，表示它是最近被访问过的。

空间不足淘汰时选择链表尾部的元素进行淘汰，因为尾部的元素是最久没有被使用的。

LRU其实是一种非常有效的缓存淘汰策略，但是大家都知道Redis的内存空间是很宝贵的，而维护LRU的双向链表需要使用比较多的额外空间，至少需要一个前向指针、一个后向指针和一个指向数据的指针。

为此Redis的作者使用了一种基于随机采样的近似LRU（NearlyLRU），它在Redis里面是不需要花费额外空间的。

随机采样

随机淘汰其实是一种非常看运气的策略，它最好能达到理想的命中率，但是也可能达到最坏的命中率。当然它也不是完全没有用的，如果每个元素的权重是一样的，那么它确实是可以考虑。

当然更加一般的情况我们想要的是频繁被访问的元素不会被淘汰，而LRU刚好就有这种思想，其实LRU也可以实现为一个根据元素被访问时间戳排序的列表，每次淘汰列表的尾部的元素，也就是时间戳最小的元素。而这种最值场景一般需要维护一个堆结构，但是堆结构对于修改来说比较耗时。

而NearlyLRU就是利用了这个时间戳的思想，也就是每个元素带有最后一次被访问的时间戳（Redis里面本来就有记录，因此不需要额外的空间），但是它没有去维护一个堆，因此它只能随机进行采样。淘汰算法流程如下：

1. 从所有元素里面随机采样5个元素
2. 淘汰5个里面最后一次被访问的时间戳最小的元素

可以发现第2步其实就有LRU的思想，只是LRU是选取全部元素里面最后一次被访问的时间戳最小的元素，而NearlyLRU则是采样一小批。

因此NearlyLRU其实命中率是不如LRU的，但是它的好处也是明显的，不需要额外的数据结构。

如果想提高命中率，可以增大采样数量，这样会更加接近LRU，当然时间成本也会相应的上升。

实现

一个Golang的简单实现。

数据结构

可以看到数据结构非常简单，基本上只有一个map类型的entries，entries的值是lastAccessEntry，也就是Key和Value加上一个最后一次访问的时间戳，其实这个时间戳可以使用更加轻量的类型，比如int32。

type Cache[K comparable, V any] struct {
entries  map[K]*lastAccessEntry[K, V]
capacity int                 // 容量
samples  int                 // 淘汰时采样数量
onEvict  cache.OnEvict[K, V] // 淘汰时的回调函数
}

type lastAccessEntry[K comparable, V any] struct {
entry      *cache.Entry[K, V]
lastAccess time.Time // 最后一次使用时间
}

添加元素

添加元素分为三个小部分，第一个是如果元素存在直接设置新值和时间戳；第二个是如果缓存满了则淘汰一个元素；最后是添加新元素。

// 添加或更新元素
// 返回被淘汰的元素
func (c *Cache[K, V]) Put(key K, value V) *cache.Entry[K, V] {
// 如果 key 已经存在，直接设置新值
if entry, ok := c.entries[key]; ok {
entry.entry.Value = value
entry.lastAccess = time.Now()
return nil
}

// 如果已经到达最大尺寸，先剔除一个元素
var evicted *cache.Entry[K, V]
if c.Full() {
evicted = c.Evict()
}

// 添加元素
c.entries[key] = &lastAccessEntry[K, V]{
entry: &cache.Entry[K, V]{
Key:   key,
Value: value,
},
lastAccess: time.Now(),
}
return evicted
}

淘汰元素

因为Golang的map遍历的时候本来就是随机的（Golang故意加了随机种子，避免依赖于map的顺序），因此我们采样的时候直接使用遍历采集需要的样本，然后挑选里面时间戳最小的进行淘汰。

// 淘汰元素
func (c *Cache[K, V]) Evict() *cache.Entry[K, V] {
// 采样
var evictEntry *lastAccessEntry[K, V]
i := 0
for _, entry := range c.entries {
// 挑选里面时间戳最小的
if evictEntry == nil || entry.lastAccess.Before(evictEntry.lastAccess) {
evictEntry = entry
}
i++
if i >= c.samples {
break
}
}
if evictEntry == nil {
return nil
}
        // 淘汰
delete(c.entries, evictEntry.entry.Key)
// 回调
if c.onEvict != nil {
c.onEvict(evictEntry.entry)
}
return evictEntry.entry
}

设置采样数量

这个策略有一个参数需要设置，也就是采样数量。

// 设置采样个数
func (c *Cache[K, V]) SetSamples(samples int) {
        // 采样数量不能太小，否则和随机没区别
if samples < MinSamples {
samples = MinSamples
}
        // 也不能太大，否则和LRU没区别
if c.Cap() < samples {
panic("too large samples")
}
c.samples = samples
}

测试

测试是在一个有20.6w条日志记录的数据集里面进行，分别测试缓存大小为数据集合大小的0.1%、0.3%、0.5%、0.7%、1%、2%、3%、5%和10%的情况下的命中率。

LRU

Random

NearlyLRU

这里多添加了一个采样数量参数，分别是5、10和50个。

测试结果

可以看到NearlyLRU的命中率是不如LRU的，但是比Random好很多，在采样数量5就能达到67%的命中率。而且随着采样数量增加，在采样数量50的时候已经接近LRU。

总结

这是一个非常有意思的结构，它也是带有随机性的，但是它通过引入时间戳+采样，在避免了空间的消耗的同时，还能保证不错的命中率，而且实现非常简单。适合那些需要简单的淘汰策略，不能有太多的额外空间消耗的场景。