本系列参考于极客兔兔-7天用Go从零实现分布式缓存GeeCache，将从零开始实现一个分布式缓存，称为 DawnCache。

在本节实现了 LRU 缓存删除策略，最终的代码目录结构如下：

lru/
	|--lru.go
	|--lru_test.go
go.mod

缓存淘汰策略

当有新数据加入缓存，缓存的容量已经超过了最大容量，就需要将之前加入的缓存数据替换出去。常见的缓存淘汰策略如下：

FIFO（First In First Out）先进先出：淘汰最先进入缓存的数据，这种策略局部性不好。
LFU（Least Frequently Used）最久未使用：LFU 需要为每一条缓存记录维护一个计数器，每一次命中会使得计数器+1，每次淘汰访问次数最少的即可。但是 LRU 有一个缺点，就是若某条缓存在过去被频繁访问，即使最近不再被访问也不会被立即淘汰。
LRU（Least Recently Used）最近最少未使用：LRU 认为，如果数据最近被访问过，那么将来被访问的概率也会更高。LRU 维护一个队列，如果某条记录被访问了，则移动到队头，那么队尾则是最近最少访问的数据，淘汰该条记录即可。

LRU 数据结构

LRU 的数据结构如下：

双向链表的顺序表示最近被访问的顺序，队头是最近被访问的数据，队尾是最久未被访问的数据。
字典记录了键值 key 与链表节点的映射关系，这样保证了查找和增删的时间复杂度不高。

LRU

lru/lru.go

实现 LRU

首先定义 LRU 缓存的结构体、链表节点值的结构体、value 的结构体：

// Cache LRU 缓存
type Cache struct {
	maxBytes  int64                         // 缓存的最大容量, 0 表示缓存容量不受限制
	nBytes    int64                         // 当前缓存已占用的空间
	ll        *list.List                    // 用于 LRU 的双向链表
	cache     map[string]*list.Element      // 用于保存 key 与双向链表节点地址之间的映射关系
	OnEvicted func(key string, value Value) // 移除数据时执行
}

// entry 保存在双向链表中的条目
type entry struct {
	key   string
	value Value
}

// Value 缓存中value的类型，只要能求出占用空间即可
type Value interface {
	Len() int
}

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

下面定义 Cache 的查找操作，当查找命中时将对应节点移动至双向链表的头部。

// Get 获取键值key对应的value
func (c *Cache) Get(key string) (value Value, ok bool) {
	if elem, ok := c.cache[key]; ok {
		// lru 命中
		value = elem.Value.(*entry).value
		// 将节点移动到链头
		c.ll.MoveToFront(elem)
		return value, ok
	}
	// 未命中
	return nil, false
}

Cache 的删除操作，即删除最近最久未使用的节点（双向链表的尾部节点）：

// DeleteOldest 删除最近最久未使用的节点 即链表尾部的节点
func (c *Cache) DeleteOldest() {
	elem := c.ll.Back() // 得到尾部节点
	if elem != nil {
		kv := elem.Value.(*entry)
		// 删除尾部节点
		c.ll.Remove(elem)
		// 从cache中删除
		delete(c.cache, kv.key)
		// 减少占用空间
		c.nBytes -= int64(len(kv.key)) + int64(kv.value.Len())
		if c.OnEvicted != nil {
			// 删除数据时执行
			c.OnEvicted(kv.key, kv.value)
		}
	}
}

Cache 的增加数据操作：

如果缓存里已有键值为key的数据，则更新value
没有键值为key的数据，新增一个节点，插入链表头部

// Add 在 lru 缓存中添加数据
func (c *Cache) Add(key string, value Value) {
	if elem, ok := c.cache[key]; ok {
		// 如果缓存里已有键值为key的数据，则更新value
		c.ll.MoveToFront(elem)
		kv := elem.Value.(*entry)
		c.nBytes += int64(value.Len()) - int64(kv.value.Len())
		kv.value = value

	} else {
		// 没有键值为key的数据，新增一个节点，插入链表头部
		elem := c.ll.PushFront(&entry{key: key, value: value})
		c.nBytes += int64(len(key)) + int64(value.Len())
		c.cache[key] = elem
	}
	// 超出最大空间，删除最久未使用节点
	for c.maxBytes != 0 && c.nBytes > c.maxBytes {
		c.DeleteOldest()
	}
}

测试

lru/lru_test.go

下面是对 LRU 缓存的测试：

package lru

import (
	"reflect"
	"testing"
)

type String string

// Len 实现 lru.Value 接口
func (s String) Len() int {
	return len(s)
}

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

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

	if _, ok := lru.Get(k1); ok {
		t.Fatalf("Deleteoldest key1 failed")
	}
}

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

Dawn's Blogs

从零实现分布式缓存 (1) LRU策略

缓存淘汰策略

LRU 数据结构

LRU

实现 LRU

测试