LFU算法族：window-LFU
LFU算法族相关文章目录汇总：
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。