LFU算法族：window-LFU

2023-11-11

LFU算法族相关文章目录汇总：

LFU算法

LFU-Aging算法

window-LFU算法（本文）

1、LFU算法的不足

LFU（Least Frequently Used）是一种缓存淘汰算法。LFU算法是根据缓存的访问频率，去淘汰访问次数最低的缓存。这样就给LFU带来了两个问题：

不可避免的问题：对于每个缓存项，LFU都需要记录其访问次数，这导致了LFU需要一笔不小的额外内存开销；
可一定程度避免的问题：对于记录的访问次数，LFU要对其进行排序，用于淘汰访问次数最低的算法。而对大量数据的排序，则会带来一定的处理器开销。当然，这个开销可以通过在每次操作时调整排序顺序，来避免在内存淘汰时一次发生。

同时，由于LFU记录的是缓存生成以来访问频率，如果一条缓存曾经访问了很多次，但是如果服务的逻辑发生了改变，这条缓存已经很少甚至不再会被访问，这条缓存由于其历史访问次数很高，依然不会被淘汰。这就导致了缓存污染的问题：

缓存污染：系统将不常用的数据存入到缓存，造成常用数据的挤出，降低了缓存效率的现象。

总结来说，LFU算法有两个不可避免的问题：

对于每个缓存项，LFU都需要记录其访问次数，需要不小的额外内存开销；
近期不再访问的历史数据无法清理，导致缓存污染。

2、window-LFU算法描述

Window-LFU被用来一定程度上解决LFU上述两步不可避免的问题。

Window是用来描述算法保存的历史请求数量的窗口大小的。Window-LFU并不记录所有数据的访问历史，而只是记录过去一段时间内的访问历史。即当请求次数达到或超过window的大小后，每次有一条新的请求到来，都会清理掉最旧的一条请求，以保证算法记录的请求次数不超过window的大小。

2.1 缓存访问记录的维护

在实现时，Window-LFU一般会维护一个定长队列，或者用数组实现环形缓存区来存储访问历史。

例如：一个缓存场景，window = 9，现在有9条缓存访问记录，按时间顺序从先到后分别是：A,B,C,D,A,B,C,D,A，即缓存队列

此时又来了一条新的缓存请求B，这是Window-LFU算法就会把第一条缓存访问记录A删掉，并将B加到队尾：

2.2 缓存淘汰

Window-LFU的缓存淘汰方式和LFU是一致的。

Window-LFU首先会计算window条记录中各条缓存项的访问次数，然后根据访问次数排序，淘汰次数最少的缓存项。当然，计算缓存想访问次数的操作，也可以放到每次缓存访问记录更新的同时，这样就避免了每次缓存操作的耗时长的问题。

一般来说，Window-LFU会使用哈希结构来存储“缓存项 <---> 访问次数”的映射，因为哈希的时间复杂度低，为o(1)。

3、Window-LFU的优缺点

3.1 优点

由于Window-LFU不存储全部历史数据，所以其额外内存开销要明显低于LFU算法，同时由于数据量明显减少，Window-LFU排序的处理器成本也要低于LFU。

另外，由于早于前window次的缓存访问记录会被清理掉，所以Window-LFU也可以避免缓存污染的问题，因为过早时间访问的缓存已经被清理掉了。

在缓存命中率方面，Window-LFU一般会由于LFU，因为Window-LFU一定程度上解决了缓存污染的问题，缓存的有效性更高了。缓存污染问题越严重的场景，Window-LFU的命中率就比LFU高的越多。

另外，和LFU-Aging相比，Window-LFU对缓存污染问题的解决更彻底一些，所以在缓存使用场景产生改变时，命中率会优于LFU-Aging。

3.2 缺点

但是Window-LFU需要维护一个队列去记录历史的访问流，复杂度略高于LFU。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)