redis的几个数据结构 —— LFU

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改变的函数为:

  1. 访问次数counter减少函数
    • lfu-decay-time以分钟为单位,调整counter的减少速度
    • 衰减周期数=(current_time – last_visited_time) /lfu_decay_time
  2. 访问次数counter增加函数
    • lfu-log-factor调整counter的增长速度,越大counter增长的越慢。
    • 因子p=1.0/(counter*lfu_log_factor+1),如果p大于当前随机数,则counter++。

可以从下面图中看出factory和hit结合下counter的增长速度:
redis-lfu

comments powered by Disqus