用go实现一个LRU缓存

LRU(Least Recently Used)，是一种常用的缓存机制和算法，在数据数量达到缓存容量时最久没有访问的会优先淘汰。

简介

其形式如下：

它有以下的需求：

• 数据插入后，其优先级最高，不会被淘汰。
• 数据查询后，由于最近被访问，优先级变最高，不会被淘汰。
• 空间不足时，淘汰最久没有被访问的数据，直到空间充足。

常用的应用有：

• 操作系统内存管理
• redis 数据的淘汰
• 手机 App 使用记录

实现设计

上面的特点可以哈希表和双链表这两种数据结构。哈希表的查询和删除的效率很高，都是\(O(1)\)；双链表的数据插入、移动和删除效率很高，时间复杂度只有\(O(1)\)。

其实际形式如下：

实现

先定义双链表：

// LRU 双链表节点
type lruNode struct {
	key   string
	value interface{}
	pre   *lruNode
	next  *lruNode
}

// LRU 双链表，数据从尾部追加
type lruDoubleLinkedList struct {
	head *lruNode // 虚拟节点，不存数据
	tail *lruNode // 虚拟节点，不存数据
	size int
}

// 添加节点，加到头部
func (list *lruDoubleLinkedList) add(node *lruNode) {
	node.pre = list.tail.pre
	node.next = list.tail
	list.tail.pre.next = node
	list.tail.pre = node
	// 非空，在尾部添加
	list.size++
}

// 删除节点
func (list *lruDoubleLinkedList) remove(node *lruNode) {
	node.pre.next = node.next
	node.next.pre = node.pre
	list.size--
}

// 移除第一个节点head.next
func (list *lruDoubleLinkedList) removeFirst() *lruNode {
	if list.head.next == nil {
		// 没有
		return nil
	}
	// 删除第一个
	result := list.head.next
	list.remove(result)
	return result
}

定义LRU缓存：

type LRUCache struct {
	dataMap  map[string]*lruNode // map数据部分
	dataList lruDoubleLinkedList // 双链表部分
	capacity int                 // 容量
}

// 将指定key置为最近访问的
func (cache *LRUCache) makeRecent(key string) {
	if node, ok := cache.dataMap[key]; ok {
		cache.dataList.remove(node)
		cache.dataList.add(node)
	}
}

func (cache *LRUCache) Init(capacity int) {
	cache.capacity = capacity
	// 创建两个虚拟节点
	head := &lruNode{
		key:   "",
		value: nil,
		pre:   nil,
		next:  nil,
	}
	tail := &lruNode{
		key:   "",
		value: nil,
		pre:   nil,
		next:  nil,
	}
	head.next = tail
	tail.pre = head
	// 初始化双链表
	cache.dataList = lruDoubleLinkedList{
		head: head,
		tail: tail,
		size: 0,
	}
	// 初始化map
	cache.dataMap = make(map[string]*lruNode)
}

// 添加数据
func (cache *LRUCache) Put(key string, value interface{}) {

	if node, ok := cache.dataMap[key]; ok {
		// key 已经存在，更新
		node.value = value
		// 移到tail，表示最近使用的
		cache.makeRecent(key)
	} else {
		// 不存在，添加
		node := &lruNode{
			key:   key,
			value: value,
			pre:   nil,
			next:  nil,
		}
		cache.dataMap[key] = node
		cache.dataList.add(node)
		if cache.dataList.size > cache.capacity {
			// 超出容量，删除最旧的
			delNode := cache.dataList.removeFirst()
			delete(cache.dataMap, delNode.key)
		}
	}

}

// 读取指定数据
func (cache *LRUCache) Get(key string) interface{} {
	if node, ok := cache.dataMap[key]; ok {
		// 标记为最近使用
		cache.makeRecent(key)
		return node.value
	}
	return nil
}

// 获取所有数据
func (cache *LRUCache) ToList() []interface{} {
	result := make([]interface{}, cache.Length())
	node := cache.dataList.head.next
	idx := 0
	for node != cache.dataList.tail {
		result[idx] = node.value
		node = node.next
		idx++
	}
	return result
}

// 获取数据容量
func (cache *LRUCache) Capacity() int {
	return cache.capacity
}

// 获取数据长度
func (cache *LRUCache) Length() int {
	return cache.dataList.size
}

测试：

func main() {
	var cache LRUCache
	cache.Init(5)
	cache.Put("a", "apple")
	cache.Put("b", "big")
	cache.Put("c", "car")
	fmt.Printf("lru cache content:%v,length:%v \n", cache.ToList(), cache.Length())
	cache.Put("c", "cab") // 覆盖上面的2
	cache.Put("d", "dog")
	cache.Put("e", "eye")
	fmt.Printf("lru cache content:%v,length:%v \n", cache.ToList(), cache.Length())
	fmt.Printf("get c from cache:%v \n", cache.Get("c"))
	fmt.Printf("lru cache content:%v,length:%v \n", cache.ToList(), cache.Length())
	cache.Put("f", "fog") // 淘汰上面的 a
	fmt.Printf("lru cache content:%v,length:%v \n", cache.ToList(), cache.Length())
	fmt.Printf("get a non-exist key:x from cache:%v \n", cache.Get("x"))
}

输出：

lru cache content:[apple big car],length:3
lru cache content:[apple big cab dog eye],length:5
get c from cache:cab
lru cache content:[apple big dog eye cab],length:5
lru cache content:[big dog eye cab fog],length:5
get a non-exist key:x from cache:<nil>

这样一个基本的LRU缓存就做好了。

缩容改进

实际使用中可能需要在缓存容量满的时候缩减数据量到一个程度，以减少存储空间的长时间占用。我们可以设定一个比率来表示缩减后的最佳 数据长度/数据容量 比值。

结构体改进如下：

type LRUCache struct {
	dataMap   map[string]*lruNode // map数据部分
	dataList  lruDoubleLinkedList // 双链表部分
	capacity  int                 // 容量
	spaceRate float64             // 最佳 数据长度/容量 比例
}

初始化方法改进下：

func (cache *LRUCache) Init(capacity int, spaceRate float64) {
	if spaceRate <= 0 || spaceRate > 1 {
		panic("spaceRate should be in (0,1] interval")
	}
	cache.capacity = capacity
	// 创建两个虚拟节点
	head := &lruNode{
		key:   "",
		value: 0,
		pre:   nil,
		next:  nil,
	}
	tail := &lruNode{
		key:   "",
		value: 0,
		pre:   nil,
		next:  nil,
	}
	head.next = tail
	tail.pre = head
	// 初始化双链表
	cache.dataList = lruDoubleLinkedList{
		head: head,
		tail: tail,
		size: 0,
	}
	// 初始化map
	cache.dataMap = make(map[string]*lruNode, capacity)
}

添加数据方法改进：

func (cache *LRUCache) Put(key string, value interface{}) {

	if node, ok := cache.dataMap[key]; ok {
		// key 已经存在，更新
		node.value = value
		// 移到tail，表示最近使用的
		cache.makeRecent(key)
	} else {
		// 不存在，添加
		node := &lruNode{
			key:   key,
			value: value,
			pre:   nil,
			next:  nil,
		}
		cache.dataMap[key] = node
		cache.dataList.add(node)
		if cache.dataList.size > cache.capacity {
			// 超出容量，删除最旧的
			properLength := int(float64(cache.capacity) * cache.spaceRate)
			for cache.Length() > properLength {
				delNode := cache.dataList.removeFirst()
				delete(cache.dataMap, delNode.key)
			}
		}
	}
}