Cache Algorithm

26 October, 2020

本文主要讲的是目前存在的几种缓存算法, 没错, 我又来~~误人子弟~~了.

内容会围绕近几年比较流行的LFU, LRU, 还有W-TinyLRU这么三种缓存算法来讲, 尽量使用最简练的文本.

LFU

近期最少使用算法，即LFU算法（Least Frequently Used algorithm）。 这种算法会淘汰近期最少访问的缓存, 仔细分析一下, 没错，这是一种非常合理的算法，因为到目前为止最少使用的页面， 很可能也是将来最少访问的页面。 该算法既充分利用了内存中缓存调度情况的历史信息，又正确反映了程序的局部性。

但是，这种算法的开销极其高, 为了记录每个缓存的使用情况, 你不得不为每一个缓存增加一个很大的计数器, 每次到达临界点, 我们还需要找到所有计数器中最少的缓存, 淘汰它.

核心思想：如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小.

通常我们会这么去实现:

外部结构为Array, 存储元素为KV. K: 该缓存访问次数. V: 缓存本身. 数组按照K排序. 每次缓存大小即将临界, 淘汰K最小的缓存.

顺便一提 Window-LFU 它是LFU算法的改良版. LFU中缓存的访问次数记录的时间范围为整个程序的生命周期, 在Window-LFU中只对特定范围的访问次数进行淘汰. (比如最近10次访问的缓存.)

LRU

最久没有使用算法，即LRU算法（Least Recently Used algorithm）。 这种算法把近期最久没有被访问过的页面作为被替换的页面。 它把LFU算法中要记录数量上的"多"与"少"简化成判断"有"与"无"，因此，实现起来比较容易。

核心思想：如果在一段时间内长时间不访问的页面将来也不会访问.

实现很简单:

假设我们的缓存容量大小为2, 最多缓存2个元素. 下面是缓存的访问顺序.

1 2 2 3

第一次: [1]

第二次: [2, 1]

第三次: [2, 1]

第四次: [3, 2]

最新访问的缓存会放在首位, 很久没有访问的缓存自然而然的就到了末尾, 然后被淘汰.

W-TinyLRU

知名缓存框架 caffeine 就是使用的这种算法 这种算法结合LRU和LFU算法，解决了突发流量问题带来的。

整个算法数据结构分成三个段,分别为  Eden,Probation,Protected 三个队列

• Eden队列: 在caffeine中规定只能为缓存容量的%1,如果size=100, 那这个队列的有效大小就等于1。这个队列中记录的是新到的数据， 防止突发流量由于之前没有访问频率，而导致被淘汰。 比如有一部新剧上线，在最开始其实是没有访问频率的， 防止上线之后被其他缓存淘汰出去，而加入这个区域。

• Probation队列:叫做缓刑队列，在这个队列就代表你的数据相对比较冷，马上就要被淘汰了。
  这个有效大小为size减去eden减去protected。

• Protected队列:在这个队列中，可以稍微放心一下了，你暂时不会被淘汰， 但是别急，如果Probation队列没有数据了或者Protected数据满了， 你也将会被面临淘汰的尴尬局面。当然想要变成这个队列， 需要把Probation访问一次之后，就会提升为Protected队列。 这个有效大小为(size减去eden) X 80% 如果size =100，就会是79。

区域规则:

1. 所有的新数据都会进入Eden。
2. Eden满了，淘汰进入Probation。
3. 如果在Probation中访问了其中某个数据，则这个数据升级为Protected。
4. 如果Protected满了又会继续降级为Probation。

Probation的淘汰算法也比较有意思, 取出队尾和队首的元素, 然后让这两皇城PK, 输了就淘汰了.

皇城PK规则:

1.如果队尾元素的频度大于队首，那么就直接淘汰队首，

2.当队尾频度小于等于队首，且频度小于5的时候，直接将其淘汰

3.当队尾频度小于等于队首，且频度大于5的时候，通过随机的方式进行淘汰任意一个。(看谁运气好咯)