go实现LRU缓存淘汰算法

注：以下的缓存淘汰算法实现，不考虑 并发 和 GC(垃圾回收) 问题

本文讨论的是 进程内缓存，是存放在内存中的，因此容量有限。当缓存容量达到某个阈值时，应该删除一条或多条数据。至于移出哪些数据？答案是移出那些 "无用" 的数据。而如何判断数据是否 "无用"，就设计到 缓存淘汰算法

常见的缓存淘汰算法有以下三种：

1. FIFO（first in first ）先进先出算法
   《go实现FIFO缓存淘汰算法》
2. LFU（least frequently used）最少使用算法
   《go实现LFU缓存淘汰算法》
3. LRU（least recently used）最近最少使用算法
   看本文

LRU缓存淘汰算法的实现

如上图示，实现 lru算法 的缓存架构图：

lru算法 是相对平衡的一种算法。
核心原则是：如果数据最近被访问过，那么将来被访问的概率会更高
如上图，用双链表来实现的话，如果某条数据被访问了，则把该条数据移动到链表尾部，
队尾是最少使用的元素，内存超出限制时，淘汰队尾元素即可

1. map 用来存储键值对。这是实现缓存最简单直接的数据结构，因为它的查找记录和增加记录时间复杂度都是 O(1)

2. list.List 是go标准库提供的双链表。
通过这个双链表存放具体的值，移动任意记录到队首的时间复杂度都是 O(1)，
在队首增加记录的时间复杂度是 O(1)，删除任意一条记录的时间复杂度是 O(1)

如下，fifo算法的代码实现

// 定义cache接口
type Cache interface {
    // 设置/添加一个缓存，如果key存在，则用新值覆盖旧值
    Set(key string, value interface{})
    // 通过key获取一个缓存值
    Get(key string) interface{}
    // 通过key删除一个缓存值
    Del(key string)
    // 删除 '最无用' 的一个缓存值
    DelOldest()
    // 获取缓存已存在的元素个数
    Len() int
    // 缓存中 元素 已经所占用内存的大小
    UseBytes() int
}

// 结构体，数组，切片，map,要求实现 Value 接口，该接口只有1个 Len 方法，返回占用内存的字节数
type Value interface {
    Len() int
}

// 定义key,value 结构
type entry struct {
    key   string
    value interface{}
}

// 计算出元素占用内存字节数
func (e *entry) Len() int {
    return CalcLen(e.value)
}

// 计算value占用内存大小
func CalcLen(value interface{}) int {
    var n int
    switch v := value.(type) {
    case Value: // 结构体，数组，切片，map,要求实现 Value 接口，该接口只有1个 Len 方法，返回占用的内存字节数，如果没有实现该接口，则panic
        n = v.Len()
    case string:
        if runtime.GOARCH == "amd64" {
            n = 16 + len(v)
        } else {
            n = 8 + len(v)
        }
    case bool, int8, uint8:
        n = 1
    case int16, uint16:
        n = 2
    case int32, uint32, float32:
        n = 4
    case int64, uint64, float64:
        n = 8
    case int, uint:
        if runtime.GOARCH == "amd64" {
            n = 8
        } else {
            n = 4
        }
    case complex64:
        n = 8
    case complex128:
        n = 16
    default:
        panic(fmt.Sprintf("%T is not implement cache.value", value))
    }

    return n
}

type lru struct {
    // 缓存最大容量，单位字节，这里值最大存放的 元素 的容量，key不算
    maxBytes int

    // 已使用的字节数，只包括value， key不算
    usedBytes int

    // 双链表
    ll *list.List
    // map的key是字符串，value是双链表中对应节点的指针
    cache map[string]*list.Element
}

// 创建一个新 Cache，如果 maxBytes 是0，则表示没有容量限制
func NewLruCache(maxBytes int) Cache {
    return &fifo{
        maxBytes: maxBytes,
        ll:       list.New(),
        cache:    make(map[string]*list.Element),
    }
}

// 通过 Set 方法往 Cache 头部增加一个元素，如果已经存在，则移到头部，并更新值
func (l *lru) Set(key string, value interface{}) {
    if element, ok := l.cache[key]; ok {
        // 移动到头部
        l.ll.MoveToFront(element)
        eVal := element.Value.(*entry)
        // 重新计算内存占用
        l.usedBytes = l.usedBytes - CalcLen(eVal.value) + CalcLen(value)
        // 更新value
        element.Value = value
    } else {
        element := &entry{
            key:   key,
            value: value,
        }

        e := l.ll.PushFront(element) // 头部插入一个元素并返回该元素
        l.cache[key] = e
        // 计算内存占用
        l.usedBytes += element.Len()
    }

    // 如果超出内存长度，则删除队首的节点. 0表示无内存限制
    for l.maxBytes > 0 && l.maxBytes < l.usedBytes {
        l.DelOldest()
    }
}

// 获取指定元素（有访问要将该元素移动到头部）
func (l *lru) Get(key string) interface{} {
    if e, ok := l.cache[key]; ok {
        // 移动到头部
        l.ll.MoveToFront(e)
        return e.Value.(*entry).value
    }

    return nil
}

// 删除指定元素
func (l *lru) Del(key string) {
    if e, ok := l.cache[key]; ok {
        l.removeElement(e)
    }
}

// 删除最 '无用' 元素，链表尾部为最无用元素
func (l *lru) DelOldest() {
    l.removeElement(l.ll.Back())
}

// 删除元素并更新内存占用大小
func (l *lru) removeElement(e *list.Element) {
    if e == nil {
        return
    }

    l.ll.Remove(e)
    en := e.Value.(*entry)
    l.usedBytes -= en.Len()
    delete(l.cache, en.key)
}

// 缓存池元素数量
func (l *lru) Len() int {
    return l.ll.Len()
}

// 缓存池已经占用的内存大小
func (l *lru) UseBytes() int {
    return l.usedBytes
}

测试：
func TestLruCache(t *testing.T) {
    cache := NewLruCache(512)

    key := "k1"
    cache.Set(key, 1)
    fmt.Printf("cache 元素个数：%d, 占用内存 %d 字节\n\n", cache.Len(), cache.UseBytes())

    val := cache.Get(key)
    fmt.Println(cmp.Equal(val, 1))
    cache.DelOldest()
    fmt.Printf("cache 元素个数：%d, 占用内存 %d 字节\n\n", cache.Len(), cache.UseBytes())
}
----------------------------------------------------------------------------------------------------------
结果：
=== RUN   TestLruCache
cache 元素个数：1, 占用内存 8 字节

true
cache 元素个数：0, 占用内存 0 字节

--- PASS: TestLruCache (0.00s)
PASS