LFU
在有内存限制,需要淘汰冷数据的系统中,需要有算法来算出哪些数据算是冷数据。最常见的就是LRU,最近最少使用。但是LRU有一定的缺陷,如果有个冷数据忽然被访问,则会被提到列表最前,这样子可能会导致真正的热数据被清理掉。
假设有以下数据访问:横轴是时间线,纵轴是同一个时间点。
~~~~~A~~~~~A~~~~~A~~~~A~~~~~A~~~~~A~~|
~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~|
~~~~~~~~~~C~~~~~~~~~C~~~~~~~~~C~~~~~~|
~~~~~D~~~~~~~~~~D~~~~~~~~~D~~~~~~~~~D|
则数据D可能被误认为即将被访问。
不同的系统解决的方式不一样,像MySQL就维护了两个链表分别存储热数据和冷数据,相互之间转换也需要有一定的规则。
redis中是怎么做的呢?它实现了LFU的算法:维护一个计数器,key被访问计数器增大。计数器越大,可以约等于访问越频繁。
LFU的访问次数除了增大之外,还需要随着时间衰减,才能反映出“最近”原则,其counter改变的函数为:
- 访问次数counter减少函数
- lfu-decay-time以分钟为单位,调整counter的减少速度
- 衰减周期数=(current_time – last_visited_time) /lfu_decay_time
- 访问次数counter增加函数
- lfu-log-factor调整counter的增长速度,越大counter增长的越慢。
- 因子p=1.0/(counter*lfu_log_factor+1),如果p大于当前随机数,则counter++。
可以从下面图中看出factory和hit结合下counter的增长速度: