LRU缓存淘汰算法（Least Recently Used）即 最近最少使用算法，是一种页面置换算法，也就是淘汰不需要的页，是一种较优的算法。

Go实现LRU缓存淘汰算法

LRU缓存淘汰算法（Least Recently Used）即 最近最少使用算法，是一种页面置换算法，也就是淘汰不需要的页，是一种较优的算法。

顾名思义，就是 淘汰那些最近很少使用到的数据，本文通过Go语言来分析如何编写一个简单的LRU淘汰算法。

本文参考的groupcache是memcached作者Brad Fitzpatrick的另外一个kv缓存项目，是一个轻量级的分布式缓存库 groupcache，代码不是很多，可以研究

需要的基本数据结构有：

• 双向循环链表（Go的list.List）
• 哈希表 map，将链表中的键值映射到哈希表中，用于缓存检测

具体说明已写在注释里

cache.go代码

package cache

import (
	"fmt"
	"runtime"
)

// 接口
type Cache interface {
	Set(key string, value interface{})
	Get(key string) interface{}
	Del(key string)
	DelOldest()
	Len() int
	UsedBytes() int
}

type Value interface {
	Len() int
}

// 链表中存储的节点值
type entry struct {
	key   string
	value interface{}
}

// 计算value的实际占用大小
func CalcLen(value interface{}) int {
	var n int
	switch v := value.(type) {
	case Value:
		n = v.Len()
	case string:
		if runtime.GOARCH == "amd64" {
			n = 16 + len(v)
		} else {
			n = 8 + len(v)
		}
	case bool, uint8, int8:
		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
}

lru.go文件

package cache

import (
	"container/list"
)

// LRU 算法淘汰的是 最近最久没有访问过的对象，也就是首先删除最近的且最旧的数据
type lru struct {
	maxBytes  int	// 最大字节内存，一旦超出，则将会淘汰部分旧的对象，
	usedBytes int // 当前已经使用的字节内存
	onRemove  func(key string, value interface{})
	// 存储节点的链表，靠近表头的节点是旧的
	ll *list.List
	// 对链表节点进行映射，实现快速查找
	cache map[string]*list.Element
}

func New(maxBytes int, onRemove func(key string, value interface{})) Cache {
	return &lru{
		maxBytes: maxBytes,
		onRemove: onRemove,
		ll:       list.New(),
		cache:    make(map[string]*list.Element),
	}
}

func (f *lru) UsedBytes() int {
	return f.usedBytes
}

// Set 设置或修改缓存值
func (f *lru) Set(key string, value interface{}) {
	// 如果缓存命中，则直接修改值
	if e, ok := f.cache[key]; ok {
		// 表示对应的缓存修改过，处于最新的状态，因此需要放置到链表尾部防止被淘汰
		f.ll.MoveToBack(e)
		// 链表中存储的节点值
		en := e.Value.(*entry)
		f.usedBytes = f.usedBytes - CalcLen(en.value) + CalcLen(value)
		en.value = value
		return
	}

	en := &entry{key: key, value: value}
	// 在环形双向链表尾部创建节点，复杂度为 O(1)
	e := f.ll.PushBack(en)
	f.cache[key] = e
	f.usedBytes += CalcLen(value)

	// 如果缓存溢出，则自动删除老的缓存
  // 这里使用 for 来检测使用还会超出范围
  // 这是因为如果某次缓存一个非常大的对象，那么又可能会淘汰多个旧的对象
	for f.maxBytes > 0 && f.usedBytes > f.maxBytes {
		f.DelOldest()
	}
}

// Get 返回缓存值 entry.value
func (f *lru) Get(key string) interface{} {
	if e, ok := f.cache[key]; ok {
		// 这里很关键，对于LRU缓存淘汰算法而言，表示将最近访问过的缓存对象设置为最新状态，防止被淘汰
		f.ll.MoveToBack(e)
		return e.Value.(*entry).value
	}
	return nil
}

// Del 主动删除缓存
func (f *lru) Del(key string) {
	if e, ok := f.cache[key]; ok {
		f.removeElement(e)
	}
}

// DelOldest 被动删除旧的缓存
func (f *lru) DelOldest() {
	// 删除首个节点，也就是最老的缓存
	f.removeElement(f.ll.Front())
}

func (f *lru) Len() int {
	return f.ll.Len()
}

func (f *lru) removeElement(e *list.Element) {
	if e == nil {
		return
	}
	f.ll.Remove(e)
	en := e.Value.(*entry)
	f.usedBytes -= CalcLen(en.value)
    // 删除缓存映射中的键值
	delete(f.cache, en.key)

	if f.onRemove != nil {
		f.onRemove(en.key, en.value)
	}
}

LRU算法采用双向链表实现，链表头表示即将要被淘汰的对象，越靠近链表尾部的对象表示较新的缓存值，不能立马被删除。

需要注意的是，实现LRU算法的关键步骤是Get和Set方法。也就是每次访问Get时需要将被访问的缓存修改为最新状态，表示该缓存值还有用（既然我访问了，那么该命中的缓存下次可能还会用到），不能太快的被淘汰掉，同理，Set方法表示创建一个缓存值或者更新缓存值，因此该缓存值一定是最新的状态。

测试

package main

import (
	"log"

	"github.com/josexy/cache/cache"
)

func main() {
	lru := cache.New(25, func(key string, value interface{}) {
		log.Printf("del %s:%v", key, value)
	})

	lru.Set("k1", int64(100))
	lru.Set("k2", 1000)
  // 由于 k1 被访问，说明该缓存值还有用，不能立马被淘汰，因此将其移到链表尾部
	log.Println(lru.Get("k1"))
  // 当超出使用的字节时，淘汰部分缓存值
	lru.Set("k3", "hello world")
	log.Println(lru.UsedBytes())
	log.Println(lru.Len())
}

输出

2022/01/31 20:33:15 100
2022/01/31 20:33:15 del k2:1000
2022/01/31 20:33:15 27
2022/01/31 20:33:15 2