LRU
Posted on
最近最少使用（ Least Recently Used ）也就是 LRU 算法是内存页面置换算法的一种，使用该算法可以在有限的资源内提高内存访问的速度，它利用了著名的局部性原理，更具体的说是时间局部性，也就是说如果一个信息项正在被访问，那么在近期它很可能还会被再次访问。
例如我们有3个物理块，访问序列为 7，0，1，2，0，3，0
- 访问7时，LRU缺失，此时LRU未满，放入7，此时淘汰顺序为7
- 访问0时，LRU缺失，此时LRU未满，放入0，此时淘汰顺序为7，0
- 访问1时，LRU缺失，此时LRU未满，放入1，此时淘汰顺序为7，0 ，1
- 访问2时，LRU缺失，此时LRU已满，驱逐7，放入2，此时淘汰顺序为0，1，2
- 访问0时，LRU命中，更新淘汰顺序，此时淘汰循序为1，2，0
- 访问3时，LRU缺失，此时LRU已满，驱逐1，放入3，此时淘汰顺序为2，0，3
- 访问0时，LRU命中，更新淘汰顺序，此时淘汰顺序为0，3，2
我们利用链表（ *list.List ）维护其淘汰顺序，利用 map 作为其存储引擎（作为物质基础）。
1
2
| <--------------------------------------------------------->
newest oldest
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| type Key interface
type entry struct {
key Key
value interface{}
}
type Cache struct {
MaxEntries int
OnEvicted func(key Key, value interface{})
ll *list.List
cache map[interface{}]*list.Element
}
func New(maxEntries int) *Cache {
return &Cache{
MaxEntries: maxEntries,
ll: list.New(),
cache: make(map[interface{}]*list.Element),
}
}
|
因为我们经常需要判断当前的 LRU 缓存是否存满，所以我们构造一个helper function 来获取当前缓存的容量。
1
2
3
4
5
6
| func (c *Cache) Len() int {
if c.cache == nil {
return 0
}
return c.ll.Len()
}
|
淘汰顺序在两种情况下会更新，一是新增元素时，如果元素在 LRU 缓存中不存在，则将它放在链表的头部（ PushFront ），如果存在，则直接将其移到链表的头部（ MoveToFront ）。二是在获取元素时，如果元素存在，则直接将其移到链表的头部（ MoveToFront ）。这样一来我们就能确保最新的东西在链表头，最老的东西在链表尾。
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
| func (c *Cache) Add(key Key, value interfacfe{}) {
if c.cache == nil {
c.cache = make(map[interface{}*list.Element])
c.ll = list.New()
}
if ee, ok := c.cache[key]; ok {
c.ll.MoveToFront(ee)
ee.Value.(*entry).value = value
return
}
ele := c.ll.PushFront(&entry{key, value})
c.cache[key] = ele
if c.MaxEntries != 0 && c.ll.Len() > c.MaxEntries {
c.RemoveOldest()
}
}
func (c *Cache) Get(key Key) (value interface{}, ok bool) {
if c.cache == nil {
return
}
if ele, hit := c.cache[key]; hit {
c.ll.MoveToFront(ele)
return ele.Value.(*entry).value, true
}
return
}
|
RemoveOldest 将最老的元素淘汰，也就是说将链表中最后一项移除，并将map 中对应的元素删除。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| func (c *Cache) RemoveOldest() {
if c.cache == nil {
return
}
ele := c.ll.Back()
if ele != nil {
c.removeElement(ele)
}
}
func (c *Cache) removeElement(e *list.Element) {
c.ll.Remove(e)
kv := e.Value.(*entry)
delete(c.cache, kv.key)
if c.OnEvicted != nil {
c.OnEvicted(kv.key, kv.value)
}
}
|
清除 LRU 缓存只需要将链表和 map 设为 nil 就可以了。
1
2
3
4
5
6
7
8
9
10
| func (c *Cache) Clear() {
if c.OnEvicted != nil {
for _, e := range c.cache {
kv := e.Value.(*entry)
c.OnEvicted(kv.key, kv.value)
}
}
c.ll = nil
c.cache = nil
}
|
