1. LRU 淘汰策略

https://github.com/dreamjz/golang-notes/tree/main/books/7-days-golang/GeeCache/day1-lru

\DAY1-LRU
│  go.mod
│  
└─lru
        lru.go
        lru_test.go

1. 缓存淘汰算法

缓存数据全部存储在内存之中，内存资源是有限的，需要在特定的场合下删除某些数据以释放资源。

1.1 FIFO(First In First Out)

FIFO（先入先出）策略，最先加入缓存的数据最先被删除。使用队列即可实现。

缺点：某些数据虽然较早加入缓存，但是使用频率比较高，若被删除则会导致缓存命中率降低。

1.2 LFU(Least Frequently Used)

最不经常使用（最少使用），淘汰缓存中访问频率最低的数据。

优点：缓存命中率高

缺点：

1. 需要额外内存，维护每个记录的访问次数
2. 访问模式发生变化，需要较长时间适应，收到历史数据影响较大

1.3 LRU(Least Recently Used)

最近最少使用，相对平衡的算法。若数据最近被访问，则未来被访问的概率就更高。

2. LRU 算法实现

2.1 数据结构

LRU 算法数据结构为哈希表和双向链表的组合。

implement lru algorithm with golang

• 哈希表存储键值对(key, value)，查找操作时间复杂度 O(1)
• 值(value)之间相连形成双向链表
  • 移动节点到队尾（首）时间复杂度为 O(1)
  • 新增节点到队尾（首）时间复杂度为 O(1)
  • 删除节点复杂度为 O(1)

// Cache is LRU cache. It is not safe for concurrent cases.
type Cache struct {
	maxBytes int64
	nBytes   int64
	dl       *list.List // doubly linked list
    cache    map[string]*list.Element
	// optional and executed when an entry is purged
	OnEvicted func(key string, value Value)
}

type entry struct {
	key   string
	value Value
}

type Value interface {
	Len() int
}

• Cache：
  1. maxBytes：允许使用的最大内存
  2. nBytes：当前已使用的内存
  3. dl：标准库的双向链表list.List
  4. cache：LRU 缓存
  5. OnEvicted：删除数据时的回调函数
• entry：双向链表节点的数据类型
• Value：接口，定义值的通用类型；
  • Len：返回值占用的内存大小

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

// Len return the number of cache entries
func (c *Cache) Len() int {
	return c.dl.Len()
}

New用于实例化Cache，Len获取节点数量。

2.2 查找

此处约定队尾节点为最近最少使用的节点。

查找操作流程：

1. 通过 key 寻找对应的节点
2. 将节点移动至队首

// Get find key's value
func (c *Cache) Get(key string) (Value, bool) {
	if ele, ok := c.cache[key]; ok {
		c.dl.MoveToFront(ele)
		kv := ele.Value.(*entry)
		return kv.val, true
	}

	return nil, false
}

2.3 删除

删除最近最少使用的节点，即队首节点。

// RemoveOldest remove the oldest item
func (c *Cache) RemoveOldest() {
	ele := c.dl.Back()
	if ele != nil {
		c.dl.Remove(ele)
		kv := ele.Value.(*entry)
		delete(c.cache, kv.key)
		c.nBytes -= int64(len(kv.key)) + int64(kv.val.Len())
		if c.OnEvicted != nil {
			c.OnEvicted(kv.key, kv.val)
		}
	}
}

• 获取队首节点并删除
• 从哈希表中删除对应的键值对
• 更新使用的内存大小
• 若存在回调函数，则调用

2.4 插入/更新

若键值对存在，则更新，否则插入。

// Add adds a value to the cache.
func (c *Cache) Add(key string, val Value) {
	if ele, ok := c.cache[key]; ok {
		c.dl.MoveToFront(ele)
		kv := ele.Value.(*entry)
		c.nBytes += int64(val.Len()) - int64(kv.val.Len())
		kv.val = val
	} else {
		ele := c.dl.PushFront(&entry{key, val})
		c.cache[key] = ele
		c.nBytes += int64(len(key)) + int64(val.Len())
	}

	for c.maxBytes != 0 && c.maxBytes < c.nBytes {
		c.RemoveOldest()
	}
}

• 查找 key：
  • 若不存在
    1. 将节点添加至队首
    2. 键值对添加至哈希表
    3. 更新使用的内存大小
  • 存在
    1. 将节点移动至队首
    2. 修改哈希表的 value
    3. 更新使用的内存大小
• 若使用的内存大小超过限制，则删除队尾节点（最近最少使用）; maxBytes为 0 表示无限制

3. 测试

3.1 测试新增和获取

type String string

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

func TestGet(t *testing.T) {
	lru := New(int64(0), nil)
	lru.Add("key1", String("1234"))

	if v, ok := lru.Get("key1"); !ok || string(v.(String)) != "1234" {
		t.Errorf("cache hit key1=1234 failed")
	}

	if _, ok := lru.Get("key2"); ok {
		t.Errorf("cache miss key2 failed")
	}
}

3.2 测试缓存淘汰

func TestRemoveoldest(t *testing.T) {
	k1, k2, k3 := "key1", "key2", "k3"
	v1, v2, v3 := "value1", "value2", "v3"
	cap := len(k1 + k2 + v1 + v2)
	lru := New(int64(cap), nil)
	lru.Add(k1, String(v1))
	lru.Add(k2, String(v2))
	lru.Add(k3, String(v3))

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

3.3 测试回调函数

func TestOnEvicted(t *testing.T) {
	keys := make([]string, 0)
	callback := func(key string, value Value) {
		keys = append(keys, key)
	}
	lru := New(int64(10), callback)
	lru.Add("key1", String("123456"))
	lru.Add("k2", String("k2"))
	lru.Add("k3", String("k3"))
	lru.Add("k4", String("k4"))

	expect := []string{"key1", "k2"}

	if !reflect.DeepEqual(expect, keys) {
		t.Fatalf("Call OnEvicted failed, expect keys equals to %s", expect)
	}
}

Reference

1. https://geektutu.com/post/geecache-day1.html