关于LRU（Latest Recently Used）算法

date

Jun 29, 2021

slug

status

Published

解决什么问题

想象我们有一个缓存系统，里面以key-value的形式存储了很多缓存数据，但存储空间总是有限的，如果我们不断的接受请求，那么总有存满的一天。当存储空间存满了之后，我们就要通过某种方式去释放空间，不然我们的缓存系统就无法接受新的请求了。

那么作为一个缓存系统，我们其实希望清理的是不再用到的数据，对于有很多请求的数据（热点），我们要留在系统中，这才是缓存系统该做的事情。那么如何判断不再用到呢？其实我们没有办法判断，因为客户端用哪些数据不是缓存系统能决定的，我们只能尽可能达到这个目标。

容易想到的有几种方案

FIFO，First In First Out，先来先服务，如果存储空间满了，就把最早存储的数据清理掉，对于大多数场景来说，这个策略可能不太合理，因为哪些是热点数据，用缓存的时间来判断不太靠谱

LIFO，Last In First Out，甚至比FIFO更加不合理。

LRU，Latest Recently Used，顾名思义，如果存储空间满了，我们要清理的是最久没被使用到的数据，这基于一个假设，就是越长时间没被用到的数据，之后被用到的概率也不会很大。显然这个策略是符合直觉的，比如微博的热搜，如果过去2天都没有人看了，时间过的越久，被人想起来再看看的概率就越低。

LFU，Least Frequently Used，本质上跟LRU是基于同一个假设，只不过角度不是时间，而是频率。清理的是被访问频率最低的数据。

其他还有很多算法，想要解决的都是类似的缓存淘汰问题。

下面我们来看主角——LRU算法

LRU算法应该如何实现

显然，如果我们需要清理最久没被使用的数据，首先我们要知道哪些是最久没被使用的数据。

一个朴素的想法是，记录数据被访问的时间，在需要清理的时候，按访问时间排序，然后清理时间最小的数据。这个算法是可行的，但是需要额外O(N)的存储空间，以及维护有序所需要的时间，另外还要考虑到当一个值后续被访问时，我们还要去更新它的被访问时间。总之这是一个逻辑上可行（堆、数组等等），但是实际成本非常大的算法。

其实我们需要的快速知道最小的数据是哪个，同时需要能快速把某数据放到最大的位置上（因为只要被访问了，访问时间就是当前时间），通常会用哈希表 + 双向链表来实现

这里引用知乎文章的图片（改了其中的错误）来说明，其中s表示set（即新的缓存值），g表示get（即对某缓存值的访问），哈希表的部分图中没表示出来，后面再进行说明。

下图是一个容量为3的LRU数据结构，是由双向链表构成，我们维护一个head结点，一个tail结点，其中head.next表示最近被访问的数据，而tail.pre表示最久没被访问的数据。LRU算法需要淘汰的就是tail.pre的数据。

重点从第5步开始可以看到，当新的请求进来后，发现容器满了，就要把新的元素放在head.next，并把tail.pre删除（并同步更新对应的哈希表），代码可以参考这里。这种实现可以用O(1)的时间复杂度以及O(N)的空间复杂度来实现LRU算法，其中N是容器的最大容量。

现实场景中的应用

在现实场景中，由于LRU算法就是用于缓存的淘汰，对效率和资源的要求非常高，实际上都往往没有使用上面的精准实现，比如Redis，使用的就是近似的LRU算法。

如文档里提到的，Redis是直接在池子里随机捞一批key，然后淘汰其中最久没被访问的数据，重复这个过程，直到释放了足够的空间。虽然不是完全精准，但是非常高效。

Redis LRU algorithm is not an exact implementation. This means that Redis is not able to pick the best candidate for eviction, that is, the access that was accessed the most in the past. Instead it will try to run an approximation of the LRU algorithm, by sampling a small number of keys, and evicting the one that is the best (with the oldest access time) among the sampled keys.

这也提醒我们，理论是理论，工业界更注重实践，一个产品的最终设计往往是多方面权衡妥协的结果.