Least Frequently Used(LFU):

最不经常使用。淘汰一定时期内被访问次数最少的数据。
我会计算为每个缓存对象计算他们被使用的频率。我会把最不常用的缓存对象踢走。

Least Recently Used(LRU):

最近最少使用。根据数据的历史访问记录来进行淘汰数据。常用于页面置换算法,是为虚拟页式存储管理服务的。
我把最近最少使用的缓存对象给踢走。
浏览器就是使用了我(LRU)作为缓存算法。新的对象会被放在缓存的顶部,当缓存达到了容量极限,我会把底部的对象踢走,而技巧就是:我会把最新被访问的缓存对象,放到缓存池的顶部。
更优算法: LRU2 和 2Q,他们就是为了完善 LRU 而存在的。

Least Recently Used2(LRU2):

最近最少使用Twice。
我会把被两次访问过的对象放入缓存池,当缓存池满了之后,我会把有两次最少使用的缓存对象踢走。因为需要跟踪对象2次,访问负载就会随着缓存池的增加而增加。如果把我用在大容量的缓存池中,就会有问题。另外,我还需要跟踪那么不在缓存的对象,因为他们还没有被第二次读取。我比LRU好,而且是 adoptive to access 模式 。

Two Queues(2Q):

双队列。
我把被访问的数据放到 LRU 的缓存中,如果这个对象再一次被访问,我就把他转移到第二个、更大的 LRU 缓存。
我踢走缓存对象是为了保持第一个缓存池是第二个缓存池的1/3。当缓存的访问负载是固定的时候,把 LRU 换成 LRU2,就比增加缓存的容量更好。这种机制使得我比 LRU2 更好,我也是 LRU 家族中的一员,而且是 adoptive to access 模式 。

Continue reading