golang-lru 源码分析

最近要改一个之前同学遗留下来的问题，这个问题描述如下：我们的业务进程会定时去扫另一个业务的数据库，将得到的数据信息缓存在内存中，业务进程从缓存中读取数据信息并进行业务处理。由于对数据的实时性要求并不是很高，之前的同学为了实现简单，每 60s 全量扫描一次数据表，将缓存与数据库进行同步。问题是全量查询的 SQL 语句并没有 where 子句，DBA 同学认为这条语句是慢查询语句，需要我们业务方整改。

由于我们业务需要使用到的数据在数据库中只会增加、删除，数据本身并不会被修改，而且如果某条数据在数据库中删除了，我们业务也不会有与这条数据相关的输入。整个业务流程可以如下表示：

分析清楚整个业务流程后，打算使用 lru-cache 来解决该问题，整体解决思路如下：

• 业务需要处理某条数据时，如果 cache 中没有相关数据条目，则通过 db 查询获取数据信息，并保存在 cache 中
• 为了防止 cache 无限制增大，这里使用 lru-cache，当缓存条目达到限制后，lru-cache 淘汰那些很久没有命中的缓存条目

这样就解决了全量扫描 DB 的问题，同时缓存也不会无限制增大。这里打算使用开源的、基于 golang 的 golang-lru，这篇文章主要分析其代码实现原理。但是在深入代码之前，还是需要掌握 lru cache 的基本原理。

缓存淘汰算法

缓存不可能无限制的增长，因此当缓存条目达到规定数量时，需要某种算法来决定将哪些缓存条目进行淘汰：

LRU

LRU（Least Recently Used）：最近最少使用算法。从时间角度对缓存条目进行淘汰，即最长时间没有被使用的缓存条目会被淘汰。该算法有一个问题：如果某些历史数据突然被大量访问，但仅仅访问一次，就可能会把那些需要频繁访问的缓存条目给淘汰掉，造成之后大量频繁访问的缓存条目出现 cache-miss。

LFU

LFU（Least Frequenty Used）：最不常用算法。从访问频率角度对缓存条目进行淘汰，即访问频率最少的缓存条目会被淘汰。该算法也存在问题：如果之前频繁访问过一些缓存条目，但是现在并不会访问这些条目，这些条目也会一直占据缓冲区，很难被淘汰。

LRU-K

相比于 LRU， LRU-K 算法多维护一个队列，用来记录所有缓存数据被访问的历史，只有当数据访问的次数达到 K 时，才将数据放入真正的缓存队列。整个缓存运作过程如下：

• 数据第一次被访问，直接进入访问历史队列
• 访问历史队列也是按照 LRU 的规则进行淘汰
• 如果历史队列中的数据访问达到 K 次后，将数据从历史队列中删除，移入到缓存队列中
• 缓存数据队列仍然按照 LRU 的规则进行淘汰

LRU-K 一定程度上解决了 LRU 的缺点。实际应用中，通常采用 LRU-2。

2Q

2Q 即 two-queues 算法，类似于 LRU-2，也是使用两个缓存队列，只不过一个是 FIFO 队列，一个是 LRU 队列。缓存的运作过程如下：

• 数据第一次访问，插入到 FIFO 队列
• 如果 FIFO 队列中的数据再次被访问，将移入到 LRU 队列
• FIFO 按照先进先出的方式进行数据淘汰
• LRU 队列按照 LRU 规则进行数据淘汰

ARC

ARC（Adaptive Replacement Cache）：自适应缓存替换算法。它同时结合了 LRU 和 LFU，当访问的数据趋向于最近访问的条目时，会更多地命中 LRU cache；当访问的数据趋向于最频繁的条目时，会更多地命中 LFU cache。ARC 会动态调整 LRU 和 LFU 的比例，从而提高缓存命中率。

golang-lru 源码分析

golang-lru 一共提供了 3 种 LRU cache 类型：

• Cache 是最简单的 LRU cache，它的实现基于 groupcache
• TwoQueueCache 使用 2Q 缓存淘汰算法，从访问时间和访问频率两个维度来跟踪缓存条目
• ARCCache 使用 ARC 缓存淘汰算法，它也是从访问时间和访问频率两个维度来跟踪缓存条目，同时它也会跟踪缓存条目的淘汰情况，从而动态调整 LRU 队列和 FRU 队列的 size 比例

三种 Cache 提供的 API 接口如下（详细文档可以参考 https://pkg.go.dev/github.com/hashicorp/golang-lru）：

Cache：

API 接口	作用
New	创建 Cache 实例
NewWithEvict	创建 Cache 实例，同时可以提供 cache 条目淘汰时的回调函数
Add	添加缓存条目
ContainsOrAdd	判断缓存条目是否存在，如果不存在则直接添加
Get	根据 key 获取缓存值
GetOldest	返回最老的缓存条目
keys	返回所有的 key 列表
Len	获取 cache 缓存数目
Peek	根据 key 获取缓存值，但并不更新该 key 的缓存状态
PeekOrAdd	根据 key 获取缓存值，如果不存在则直接添加
Purge	清空缓存
Remove	移除某一个缓存条目
RemoveOldest	移除最老的缓存条目
Resize	调整缓冲区大小

TwoQueueCache

API 接口	作用
New2Q	创建 2QCache 实例
New2QParams	创建 2QCache 实例，同时允许设置 2QCache 的参数
Add	添加缓存条目
Contains	判断缓存条目是否存在
Get	根据 key 获取缓存值，但并不更新该 key 的缓存状态
keys	返回所有的 key 列表
Len	获取 cache 缓存数目
Peek	根据 key 获取缓存值
Purge	清空缓存
Remove	移除某一个缓存条目

ARCCache

API 接口	作用
ARCCache	创建 ARCCache 实例
Add	添加缓存条目
Contains	判断缓存条目是否存在
Get	根据 key 获取缓存值
keys	返回所有的 key 列表
Len	获取 cache 缓存数目
Peek	根据 key 获取缓存值，但是并不更新该 key 的缓存状态
Purge	清空缓存
Remove	移除某一个缓存条目

golang-lru 代码主要包含如下文件：

API 接口	作用
simplelru/lru.go	lru cache 的实现，是三种 Cache 的实现基础
lru.go	Cache 的实现，对 simplelru/lru.go 的包装，提供并发安全
2q.go	2QCache 的实现
arc.go	ARCCache 的实现

LRU 实现

三种 cache 类型底层都依赖 LRU，因此首先来看 LRU 结构体的定义：

type LRU struct {
    size      int
    evictList *list.List
    items     map[interface{}]*list.Element
    onEvict   EvictCallback
}

• size：LRU cache 的大小
• evictList：缓存条目链表，通过该链表来实现 LRU 算法
• items：缓存条目 map，缓存条目的查找通过该 map 实现。map 的 key 是缓存条目的 key，而 value 则是 evictList 链表元素的指针。链表元素中包含缓存条目的 key 和 value
• onEvict：缓存条目淘汰时的回调函数

LRU.Get 方法实现了从 LRU 中根据 key 查找缓存项：

// Get looks up a key's value from the cache.
func (c *LRU) Get(key interface{}) (value interface{}, ok bool) {
    // 从 map 中根据 key 查找
    if ent, ok := c.items[key]; ok {
        // 如果找到该缓存，需要将其移动到链表头
        c.evictList.MoveToFront(ent)
        if ent.Value.(*entry) == nil {
            return nil, false
        }
        // 返回链表元素中保存的缓存 key 对应的 value
        return ent.Value.(*entry).value, true
    }
    return
}

接下来再看往 LRU 中添加元素的 Add 方法实现：

func (c *LRU) Add(key, value interface{}) (evicted bool) {
    // Check for existing item
    if ent, ok := c.items[key]; ok {
        c.evictList.MoveToFront(ent)
        ent.Value.(*entry).value = value
        return false
    }

    // Add new item
    ent := &entry{key, value}
    entry := c.evictList.PushFront(ent)
    c.items[key] = entry

    evict := c.evictList.Len() > c.size
    // Verify size not exceeded
    if evict {
        c.removeOldest()
    }
    return evict
}

• 首先判断 cache 中是否已经有该元素了，如果存在，则更新该缓存条目，同时将该缓存条目移动到链表头
• 否则新增缓存条目：将该缓存条目添加到调表头，同时在 map 中添加对应的索引
• 检查当前缓存条目的个数是否超过 size 限制，如果超过，则调用 removeOldest 移除该缓存元素

最后再分析下 removeOldest 的实现

// removeOldest removes the oldest item from the cache.
func (c *LRU) removeOldest() {
    // 从缓存队列的尾部获取缓存元素
    ent := c.evictList.Back()
    if ent != nil {
        c.removeElement(ent)
    }
}

// removeElement is used to remove a given list element from the cache
func (c *LRU) removeElement(e *list.Element) {
    // 从缓存队列中移除该元素
    c.evictList.Remove(e)
    kv := e.Value.(*entry)
    // 从 map 中删除索引
    delete(c.items, kv.key)
    if c.onEvict != nil {
        // 调用用户指定的缓存淘汰回调函数
        c.onEvict(kv.key, kv.value)
    }
}

Cache 实现

Cache 结构体定义如下：

type Cache struct {
    lru                      *simplelru.LRU
    evictedKeys, evictedVals []interface{}
    onEvictedCB              func(k, v interface{})
    lock                     sync.RWMutex
}

• lru：Cache 本身其实是对 LRU cache 的封装
• evictedKeys, evictedVals：用于临时保存当前被淘汰的缓存条目，这样就可以不用在临界区内回调 onEvictedCB
• onEvictedCB：缓存条目淘汰时的回调函数
• lock：Cache 提供线程安全能力

由于 Cache 其实就是对 LRU cache 的封装，所以 Cahce 的接口实现，底层基本上都是调用 simplelru.LRU 的相应接口。唯一需要注意的一点是：Cache 对淘汰缓存条目的回调处理。如果用户创建 Cache 时指定了 onEvicted 回调函数，那么 Cache 会将该函数保存到 onEvictedCB。Cache 运行过程中，如果出现了缓存淘汰，会将这些淘汰的缓存条目临时保存到 evictedKeys/evictedVals slice 中，之后再针对每一个淘汰的缓存条目调用回调函数。

接下来以 Cache 的 Add 接口为例，分析其实现逻辑，其他接口的实现都是类似的。

func (c *Cache) Add(key, value interface{}) (evicted bool) {
    var k, v interface{}

    // 操作 lru cache 时需要加锁，保证线程安全
    c.lock.Lock()
    // 调用 lru.Add 添加 key/value
    evicted = c.lru.Add(key, value)
    // 如果因为 Add 操作而造成其他缓存条目被淘汰，同时用户指定了回调函数
    if c.onEvictedCB != nil && evicted {
        // 被淘汰的缓存条目保存在 Cache 的 evictedKeys/evictedVals 中
        k, v = c.evictedKeys[0], c.evictedVals[0]
        c.evictedKeys, c.evictedVals = c.evictedKeys[:0], c.evictedVals[:0]
    }
    c.lock.Unlock()
    // 在非临界区调用用户的回调函数
    if c.onEvictedCB != nil && evicted {
        c.onEvictedCB(k, v)
    }
    return
}

那为什么被淘汰的缓存条目会保存在 Cache 的 evictedKeys/evictedVals 中呢？因为创建 Cache 时，如果用户提供了回调函数，那么 simple.LRU 的回调被被设置成 Cache 自己的 onEvicted 函数，其逻辑就是将被淘汰的缓存条目保存到自己的 buffer 中：

func NewWithEvict(size int, onEvicted func(key, value interface{})) (c *Cache, err error) {
    // create a cache with default settings
    c = &Cache{
        onEvictedCB: onEvicted,
    }
    // 如果用户提供了回调函数
    if onEvicted != nil {
        c.initEvictBuffers()
        // 将回调设置为 Cache 自己的 onEvicted 函数
        onEvicted = c.onEvicted
    }
    c.lru, err = simplelru.NewLRU(size, onEvicted)
    return
}

// Cache 自己的 onEvicted 就是将被淘汰的 key/value 保存到 Cache 的 evictedKeys/evictedVals
func (c *Cache) onEvicted(k, v interface{}) {
    c.evictedKeys = append(c.evictedKeys, k)
    c.evictedVals = append(c.evictedVals, v)
}

2QCache

golang-lrucache 实现的 2QCache 和上文介绍的 2Q 缓存淘汰算法不太一样，可以认为 golang-lrucache 实现的 2QCache 是 lru-2 和 ARC 的结合体。

type TwoQueueCache struct {
    size       int
    recentSize int

    recent      simplelru.LRUCache
    frequent    simplelru.LRUCache
    recentEvict simplelru.LRUCache
    lock        sync.RWMutex
}

• size 是整个 cache 的大小、recentSize 是 recent LRU 的大小
• recent LRU 队列用来记录最近访问的缓存条目、frequent LRU 队列用来记录最频繁访问的缓存条目
• recentEvcit 队列用来跟踪从 recent LRU 中淘汰的缓存条目
• lock 保证线程安全

在创建 TwoQueueCache 时，可以通过参数指定 recent 和 recentEvict 队列占用 cache size 的比例，从而设置 recent 和 recentEvict 的大小。如果没有指定比例参数，TwoQueueCache 会使用默认的比例参数，分别是 0.25 和 0.5。

接下来分析 TwoQueueCache 从缓存中获取 key 对应的缓存条目的代码：

func (c *TwoQueueCache) Get(key interface{}) (value interface{}, ok bool) {
    c.lock.Lock()
    defer c.lock.Unlock()

    // Check if this is a frequent value
    if val, ok := c.frequent.Get(key); ok {
        return val, ok
    }

    // If the value is contained in recent, then we
    // promote it to frequent
    if val, ok := c.recent.Peek(key); ok {
        c.recent.Remove(key)
        c.frequent.Add(key, val)
        return val, ok
    }

    // No hit
    return nil, false
}

• 首先尝试从 frequent LRU 中查找 key
• 如果 key 不存在，则尝试从 recent 中查找 key，如果找到，则将该缓存条目从 recent 中移除，添加到 frequent（这说明该缓存条目已经访问两次了，可以添加到 frequent 中）

再来看往 TwoQueueCache 中添加缓存条目的逻辑：

// Add adds a value to the cache.
func (c *TwoQueueCache) Add(key, value interface{}) {
    c.lock.Lock()
    defer c.lock.Unlock()

    // Check if the value is frequently used already,
    // and just update the value
    if c.frequent.Contains(key) {
        c.frequent.Add(key, value)
        return
    }

    // Check if the value is recently used, and promote
    // the value into the frequent list
    if c.recent.Contains(key) {
        c.recent.Remove(key)
        c.frequent.Add(key, value)
        return
    }

    // If the value was recently evicted, add it to the
    // frequently used list
    if c.recentEvict.Contains(key) {
        c.ensureSpace(true)
        c.recentEvict.Remove(key)
        c.frequent.Add(key, value)
        return
    }

    // Add to the recently seen list
    c.ensureSpace(false)
    c.recent.Add(key, value)
}

• 首选判断 frequent 中是否已经包含了该 key，如果包含，则用最新的值更新该 key 对应的缓存条目
• 如果 frequent 中不存在该缓存，再判断 recent 中是否包含该 key。如果包含，则认为该 key 被再次访问，将其从 recent 中移除，添加到 frequent 中
• 最后再检查 recentEvict 中是否包含该 key，如果存在，则代表该 key 是不久前被淘汰的，则将其添加到 frequent LRU 中。在添加之前通过 ensureSpace 确保 cache 中存在空间
• 否则将其添加到 recent LRU 中，同样添加之前需要通过 ensureSpace 确保存在空间

之后再看 ensureSpace 的实现：

// ensureSpace is used to ensure we have space in the cache
func (c *TwoQueueCache) ensureSpace(recentEvict bool) {
    // If we have space, nothing to do
    recentLen := c.recent.Len()
    freqLen := c.frequent.Len()
    if recentLen+freqLen < c.size {
        return
    }

    // If the recent buffer is larger than
    // the target, evict from there
    if recentLen > 0 && (recentLen > c.recentSize || (recentLen == c.recentSize && !recentEvict)) {
        k, _, _ := c.recent.RemoveOldest()
        c.recentEvict.Add(k, nil)
        return
    }

    // Remove from the frequent list otherwise
    c.frequent.RemoveOldest()
}

• 当没有达到 cache size 时，recent 和 frequent 都可以任意增长，不受各自的 size 限制
• 如果 cache 达到 size 限制时，首先判断 recent 是否达到 recentSize 的限制，如果达到了，则从 recent LRU 中移除元素
• 否则则从 frequent LRU 中移除元素

2QCache 的其他接口就不再分析了，比较简单。

ARCCache

接下来再分析 ARCCache 的实现，首先来看 ARCCache 结构体的定义：

type ARCCache struct {
    size int // Size is the total capacity of the cache
    p    int // P is the dynamic preference towards T1 or T2

    t1 simplelru.LRUCache // T1 is the LRU for recently accessed items
    b1 simplelru.LRUCache // B1 is the LRU for evictions from t1

    t2 simplelru.LRUCache // T2 is the LRU for frequently accessed items
    b2 simplelru.LRUCache // B2 is the LRU for evictions from t2

    lock sync.RWMutex
}

• size 是整个 ARCCache 的大小
• p 是 LRU 和 FRU 队列的分隔点，p 的位置可以动态调整
• t1 实现了 LRU 缓存队列，b1 用来记录从 t1 中淘汰的缓存条目
• t2 实现了 FRU 缓存队列，b2 用来记录从 t2 中淘汰的缓存条目

接下来分析从 ARCCache 中获取缓存元素的实现逻辑：

func (c *ARCCache) Get(key interface{}) (value interface{}, ok bool) {
    c.lock.Lock()
    defer c.lock.Unlock()

    // If the value is contained in T1 (recent), then
    // promote it to T2 (frequent)
    if val, ok := c.t1.Peek(key); ok {
        c.t1.Remove(key)
        c.t2.Add(key, val)
        return val, ok
    }

    // Check if the value is contained in T2 (frequent)
    if val, ok := c.t2.Get(key); ok {
        return val, ok
    }

    // No hit
    return nil, false
}

• 首先判断 LRU 缓存队列中（t1）是否包含该元素，如果存在，则将其从 t1 中移除，添加到 FRU 缓存队列（t2）
• 如果 t1 中不存在，判断 FRU 缓存队列（t2）中是否包含该元素

最后再看看 ARCCache 添加元素的逻辑，其整体流程如下：

这个流程中，在往队列中添加新元素时，都需要确保相应的队列有足够的位置能够增加缓存条目。这是通过 replace 函数实现的，它会根据 p 的位置以及 t1/t2 当前的大小，自动从 t1/t2 中移除 oldest：

// replace is used to adaptively evict from either T1 or T2
// based on the current learned value of P
func (c *ARCCache) replace(b2ContainsKey bool) {
    t1Len := c.t1.Len()
    // 如果当前 t1 队列的长度已经达到限制，从 t1 中移除缓存条目
    if t1Len > 0 && (t1Len > c.p || (t1Len == c.p && b2ContainsKey)) {
        k, _, ok := c.t1.RemoveOldest()
        if ok {
            c.b1.Add(k, nil)
        }
    } else {
        // 从 t2 中移除缓存条目
        k, _, ok := c.t2.RemoveOldest()
        if ok {
            c.b2.Add(k, nil)
        }
    }
}

总结

关于 golang-lru 的源码分析就基本完成了，代码写的十分清晰。通过学习这个模块，可以进一步熟悉 go 语言，同时对 LRU 算法也有一个比较全面的了解。

Reference

• LRU算法及其变种算法原理分析
• 图解 LRU LFU ARC FIFO 缓存淘汰算法
• 缓存淘汰算法分析