使用Go实现一个LRU缓存

什么是LRU缓存

我们以数据库访问为例解释缓存的工作原理。假设缓存的大小固定，初始状态为空。每发生一次数据读取操作。首先检查待读取的数据是否存在于缓存中，若是，则缓存命中，返回数据；若否，则缓存未命中，从数据库中读取数据，并将该数据添加到缓存中。向缓存添加数据时，如果缓存已满，则需要删除访问时间最早的那条记录，这种更新缓存的方法就叫做LRU。

实现

实现LRU缓存时，首先应该考虑的问题应该是读写性能，理想情况下，读写的时间复杂度应该都是O(1)。

读操作的时间复杂度保证为O(1)很好解决，我们使用内置类型map来实现，该类型是Go实现的哈希表数据结构，保证了根据数据键访问数据项可以达到O(1)的速度。

但是map无法保证更新缓存项的速度达到O(1)，因为需要确定哪一条记录的访问时间最早，这需要遍历所有的缓存项才能找到。

因此，我们需要一种既按照访问时间排序，又可以在常熟时间内随机访问的数据结构。

这可以通过map + list.List 来实现。list包下的List对象是一个双向链表实现，我们可以将缓存项按照访问时间顺序链接起来，这用做的好处是：缓存的get和set操作可以保证O(1)的时间复杂度，同时，也可以通过双向链表来保证LRU的删除和更新操作也具有O(1)的复杂度。

image.png
其中灰底框代表缓存键，蓝底框代表缓存项，可以看到，缓存项已经按照访问时间进行了排序。

实现代码如下：

package lru

import (
    "container/list"
)

// Cache 代表LRU缓存实现，暂时未考虑线程安全
type Cache struct {
    // MaxEntries 表示缓存容量的最大值，0表示是一个空缓存
    MaxEntries int

    ll    *list.List
    cache map[string]*list.Element
}

// entry 表示一个缓存键值对
type entry struct {
    key   string
    value interface{}
}

// New 函数新建一个LRU缓存对象
func New(max int) *Cache {
    return &Cache{
        MaxEntries: max,
        ll:         list.New(),
        cache:      make(map[string]*list.Element),
    }
}

// Set 函数添加一个缓存项到Cache对象中
func (c *Cache) Set(key string, value interface{}) {
    if c.cache == nil {
        c.cache = make(map[string]*list.Element)
        c.ll = list.New()
    }
    // 如果缓存已经存在于Cache中，那么将该缓存项移到双向链表的最前端
    if ee, ok := c.cache[key]; ok {
        c.ll.MoveToFront(ee)
        ee.Value.(*entry).value = value
        return
    }

    // 将新添加的缓存项放入双向链表的最前端
    ele := c.ll.PushFront(&entry{key, value})
    c.cache[key] = ele

    // 如果超出缓存容量，那么移除双向链表中的最后一项
    if c.MaxEntries != 0 && c.ll.Len() > c.MaxEntries {
        c.RemoveOldest()
    }
}

// Get 方法获取具有指定键的缓存项
func (c *Cache) Get(key string) (value interface{}, ok bool) {
    if c.cache == nil {
        return
    }
    if ele, hit := c.cache[key]; hit {
        c.ll.MoveToFront(ele)
        return ele.Value.(*entry).value, true
    }
    return
}

// Remove 方法移除具有指定键的缓存
func (c *Cache) Remove(key string) {
    if c.cache == nil {
        return
    }
    if ele, hit := c.cache[key]; hit {
        c.removeElement(ele)
    }
}

// RemoveOldest 移除双向链表中访问时间最远的那一项
func (c *Cache) RemoveOldest() {
    if c.cache == nil {
        return
    }
    ele := c.ll.Back()
    if ele != nil {
        c.removeElement(ele)
    }
}

func (c *Cache) removeElement(e *list.Element) {
    c.ll.Remove(e)
    kv := e.Value.(*entry)
    delete(c.cache, kv.key)
}

// Len 方法获取Cache中包含的缓存项个数
func (c *Cache) Len() int {
    if c.cache == nil {
        return 0
    }
    return c.ll.Len()
}

// Clear 清除整个Cache对象
func (c *Cache) Clear() {
    c.ll = nil
    c.cache = nil
}