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的增长速度：
