LRU算法浅析

留言

使用


LRU即Least Recently Used的缩写, 即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的资源予以淘汰

或者说是 一种内存管理方法，最早应用于Linux系统

如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小(局部性原理)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
package main

import (
	"fmt"
	lru "github.com/hashicorp/golang-lru"
)

func main() {

	l, _ := lru.New(128)

	for i := 0; i < 256; i++ {
		l.Add(i, fmt.Sprintf("这是第%d号元素的值", i))
	}

	v10, ok := l.Get(10)

	if ok {
		fmt.Println("第10号key对应的值为：", v10)
	} else {
		fmt.Println("缓存中没有10号key")
	}

	v128, ok := l.Get(128)

	if ok {
		fmt.Println("第128号key对应的值为：", v128)
	} else {
		fmt.Println("缓存中没有128号key")
	}

	if l.Len() != 128 {
		panic(fmt.Sprintf("bad len: %v", l.Len()))
	}

	// 此时会"挤出"一个key
	l.Add(300, fmt.Sprintf("这是第%d号元素的值", 300))

	// 但不会是第128号key，因为在上面刚刚被get； 第129号key就成了排在队列最前面的key
	v128, ok = l.Get(128)
	if ok {
		fmt.Println("第128号key对应的值为：", v128)
	} else {
		fmt.Println("缓存中没有128号key")
	}

	v129, ok := l.Get(129)
	if ok {
		fmt.Println("第129号key对应的值为：", v129)
	} else {
		fmt.Println("缓存中没有129号key")
	}

}

输出为：

1
2
3
4
缓存中没有10号key
第128号key对应的值为： 这是第128号元素的值
第128号key对应的值为： 这是第128号元素的值
缓存中没有129号key


原理


以下内容来自 漫画：什么是 LRU 算法？

哈希链表 （Java中的LinkedHashMap）


LRU算法四种实现方式介绍



代码实现


可参考 go实现LRU cache



知名项目中的使用


  • XORM

  • Redis底层也实现了类似LRU的回收算法

  • substrate以及N多个项目中，都广泛使用到LRU



Golang官方提供了一个groupcache库，其中包含LRU。使用可参考Golang groupcache LRU 缓存简介与用法