LRU缓存淘汰算法

一、遵循的策略

LRU是一种数据淘汰算法。LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。

我们一般使用双向链表+map实现该算法

1. 新数据插入到链表头部；
2. 每当缓存命中（即缓存数据被访问），则将数据移到链表头部；
3. 当链表满的时候，将链表尾部的数据丢弃。

二、实现方式：双向链表+map

Golang代码实现

import "container/list"
// LRU结构体
type LRUCache struct {
    capacity int
    cache    map[int]*list.Element
    list     *list.List
}
// key-value 结构体
type Pair struct {
    key   int
    value int
}
// 创建一个LRU对象
func NewLRUCache(capacity int) *LRUCache {
    return &LRUCache{
        capacity: capacity,
        list:     list.New(),
        cache:    make(map[int]*list.Element),
    }
}
// 根据key获取value,没获取到返回-1
// 通过map获取元素，获取到后把元素移动到头部
func (this *LRUCache) Get(key int) int {
    if item, ok := this.cache[key]; ok {
        this.list.MoveToFront(item)
        return item.Value.(Pair).value
    }
    return -1
}
// 放置一个key-value对
// 需要注意容量放满时的情况
func (this *LRUCache) Put(key int, value int) {
    if elem, ok := this.cache[key]; ok {
        this.list.MoveToFront(elem)
        elem.Value = Pair{key, value}
    } else {
        if this.list.Len() >= this.capacity {
            delete(this.cache,this.list.Back().Value.(Pair).key)
            this.list.Remove(this.list.Back())
        }
        this.list.PushFront(Pair{key, value})
        this.cache[key] = this.list.Front()
    }
}

进行测试：

func TestLRU(t *testing.T) {
    lruCache := NewLRUCache(3)

    lruCache.Put(1, 11)
    lruCache.Put(2, 22)
    lruCache.Put(3, 33)
    lruCache.Put(4, 44)

    aa := lruCache.Get(3)
    fmt.Println("aa:", aa)

    bb := lruCache.Get(4)
    fmt.Println("bb", bb)

    cc := lruCache.Get(1)
    fmt.Println("cc", cc)
}

输出结果：

=== RUN   TestLRU
aa: 33
bb 44
cc -1
--- PASS: TestLRU (0.00s)
PASS

Process finished with exit code 0

完整源码地址：github

三、相关应用

0、手机应用使用情况

1、Leetcode刷题

146. LRU缓存机制

2、Redis缓存替换策略

当 Redis 内存超出物理内存限制时，内存的数据会开始和磁盘产生频繁的交换 (swap)。 交换会让 Redis 的性能急剧下降，对于访问量比较频繁的 Redis 来说，这样龟速的存取效率基本上等于不可用。
在生产环境中我们是不允许 Redis 出现交换行为的，为了限制最大使用内存，Redis 提 供了配置参数 maxmemory 来限制最大可用内存。

当实际内存超出 maxmemory 时，Redis 提供了几种可选策略 (maxmemory-policy) 来让 用户自己决定该如何腾出新的空间以继续提供读写服务。

• noeviction：永不过期，返回错误。这是默认的淘汰策略。
• volatile-lru ：只对设置了过期时间的key进行LRU
• volatile-ttl ：删除即将过期的
• volatile-random 随机删除即将过期key
• allkeys-lru 对所有的key执行LRU算法（没有设置过期的key也会被淘汰）
• allkeys-random 随机删除key

  3、开源：golang-lru

  可以参考该框架的simplelru中的相关代码进行理解，代码量不多，基本上和我们写的Golang代码实现差不多。

参考资料

• 缓存淘汰算法—LRU算法