缓存淘汰策略

作者: ropon 分类: Go 发布时间: 2021-12-14 11:43

淘汰策略

  • 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)
    }
}

如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!