缓存算法
Cache Algorithms
2021-06-15 19:38:31
Algorithm
354
  • FIFO: First In First Out (The first put's object will be deleted)
  • LIFO: Last In First Out (The last put's object will be deleted)
  • LFU: Least Frequently Used (The least number of hits will be deleted)
  • MFU: Most Frequently Used (The most number of hits will be deleted)
  • LRU: Least Recently Used (Not Recently Used, The longest visit will be deleted)
  • MRU: Most Recently Used (The latest visit will be deleted)
  • ARC: Adaptive Replacement Cache
  • LFU-EA(LFU with Exponential Aging)

**先进先去算法(FIFO) ** : 如果一个数据最先进入缓存中,则应该最早淘汰掉。也就是说,当缓存满的时候,应当把最先进入缓存的数据给淘汰掉。

**后进先去算法(LIFO) ** : 如果一个数据最先进入缓存中,则应该最后淘汰掉。也就是说,当缓存满的时候,应当把最后进入缓存的数据给淘汰掉, 即最后置换的只有最后一个缓存数据,这种算法作用不大。

最不经常使用算法(LFU):把最不常用的缓存对象踢走(访问次数最少的删除),如果一个数据在最近一段时间内使用次数很少,那么在将来一段时间内被使用的可能性也很小, 这个缓存算法使用一个计数器来记录条目被访问的频率。通过使用LFU缓存算法,最低访问数的条目首先被移除。这个方法并不经常使用,因为它无法对一个拥有最初高访问率之后长时间没有被访问的条目缓存负责。

最经常使用算法(MFU):把最经常用的缓存对象踢走(访问次数最多的删除),这种算法作用不大

最近最少使用算法(LRU):把很久没有访问的缓存对象踢走(访问时间最久的删除),这个缓存算法将最近使用的条目存放到靠近缓存顶部的位置。当一个新条目被访问时,LRU将它放置到缓存的顶部。当缓存达到极限时,较早之前访问的条目将从缓存底部开始被移除。这里会使用到昂贵的算法,而且它需要记录“年龄位”来精确显示条目是何时被访问的。此外,当一个LRU缓存算法删除某个条目后,“年龄位”将随其他条目发生改变。

最近最常使用算法(MRU):把最近有访问的缓存对象踢走(访问时间最新的删除), 这个缓存算法最先移除最近最常使用的条目。一个MRU算法擅长处理一个条目越久,越容易被访问的情况。

**自适应缓存替换算法(ARC) **:在IBM Almaden研究中心开发,这个缓存算法同时跟踪记录LFU和LRU,以及驱逐缓存条目,来获得可用缓存的最佳使用。

注意LFU和LRU算法的不同之处,LRU的淘汰规则是基于访问时间,而LFU是基于访问次数的。