2021-12-14

缓存淘汰策略

淘汰策略

FIFO(First In First Out)

先进先出，也就是淘汰缓存中最老(最早添加)的记录，创建一个队列，新增记录添加到队尾，当内存不足时，淘汰队首；

但是很多场景下，部分记录虽然是最早添加的但也经常被访问，这类数据会被频繁添加缓存然后又被淘汰，导致命中率降低
LFU(Least Frequently Used)

最少使用，也就是淘汰缓存中访问频率最低的记录，LFU需要维护一个按访问次数排序的队列，每次访问次数加1，队列重新排序，

当内存不足时，淘汰访问次数最少的记录，维护每个记录的访问次数，对内存消耗较高，另外访问模式发生变化，LFU需要时间去适应，也就是说LFU算法受历史数据影响较大，比如某个记录历史访问很高，但在某个时间点后几乎不再被访问，因历史访问次数过高，迟迟不能被淘汰
LRU(Least Recently Used)

最近最少使用，创建一个队列，如果某个记录被访问了，则移动到队尾，那么队首则是最少访问的数据，当内存不足时，淘汰改记录即可

Go语言实现LRU

字典/双向链表(Map list.List)

type Cache struct {
    maxBytes  int64                         //最大容量
    uBytes    int64                         //已使用容量
    ll        *list.List                    //双向链表
    cache     map[string]*list.Element      //缓存数据
    OnRemoved func(key string, value Value) //当记录被淘汰时回调
}

type Value interface {
    Len() int
}

type entry struct {
    key   string
    value Value
}

func New(maxBytes int64, onRemoved func(string, Value)) *Cache {
    return &Cache{
        maxBytes:  maxBytes,
        ll:        list.New(),
        cache:     make(map[string]*list.Element),
        OnRemoved: onRemoved,
    }
}

对缓存增删改查

//增/改
func (c *Cache) Add(key string, value Value) {
    //如果健存在，更新健值并将起移到队尾，因双向链表队尾是相对的
    if ele, ok := c.cache[key]; ok {
        c.ll.MoveToBack(ele)
        kv := ele.Value.(*entry)
        c.uBytes += int64(value.Len()) - int64(kv.value.Len())
        kv.value = value
    } else {
        //不存在则新增并向队尾添加节点，并在字典中添加key和节点映射关系
        //更新已使用容量，如果设置最大容量，则移除最少访问的节点
        ele := c.ll.PushBack(&entry{key: key, value: value})
        c.cache[key] = ele
        c.uBytes += int64(len(key)) + int64(value.Len())
    }
    for c.maxBytes != 0 && c.uBytes > c.maxBytes {
        c.RemoveOldEle()
    }
}

//删
func (c *Cache) RemoveOldEle() {
    //取队首节点
    ele := c.ll.Front()
    if ele != nil {
        //从链表删除并从cache删除该节点的映射关系
        c.ll.Remove(ele)
        kv := ele.Value.(*entry)
        delete(c.cache, kv.key)
        //更新已使用容量
        c.uBytes -= int64(len(kv.key)) + int64(kv.value.Len())
        //回调函数
        if c.OnRemoved != nil {
            c.OnRemoved(kv.key, kv.value)
        }
    }
}

//查
func (c *Cache) Get(key string) (value Value, ok bool) {
    //从cache中找到双向链表的节点并将该节点移到队尾
    if ele, ok := c.cache[key]; ok {
        c.ll.MoveToBack(ele)
        kv := ele.Value.(*entry)
        return kv.value, ok
    }
    return
}

测试

package lru

import (
    "reflect"
    "testing"
)

type String string

func (s String) Len() int {
    return len(s)
}

func TestGet(t *testing.T) {
    c := New(0, nil)
    c.Add("key1", String("val1"))
    if v, ok := c.Get("key1"); !ok  string(v.(String)) != "val1" {
        t.Fatalf("cache hit key1=val1 failed")
    }
    if _, ok := c.Get("key2"); ok {
        t.Fatalf("cache miss key2 failed")
    }
}

func TestRemoveOldEle(t *testing.T) {
    k1, k2, k3 := "key1", "key2", "key3"
    v1, v2, v3 := "val1", "val2", "val3"
    maxBytes := len(k1 + k2 + v1 + v2)
    c := New(int64(maxBytes), nil)
    c.Add(k1, String(v1))
    c.Add(k2, String(v2))
    c.Add(k3, String(v3))

    if _, ok := c.Get("key1"); ok  c.Len() != 2 {
        t.Fatalf("removeoldele key1 failed")
    }
}

func TestOnRemoved(t *testing.T) {
    keys := make([]string, 0)
    callback := func(key string, value Value) {
        keys = append(keys, key)
    }
    c := New(int64(10), callback)
    c.Add("k1", String("v1"))
    c.Add("k2", String("v2"))
    c.Add("k3", String("v3"))
    c.Add("k4", String("k4"))

    expect := []string{"k1", "k2"}
    if !reflect.DeepEqual(expect, keys) {
        t.Fatalf("call onremoved failed, expect keys equals to %s, get %s", expect, keys)
    }
}