常用的淘汰算法
- Redis
- 时间：2022-11-03 20:37
- 2728人已阅读
🔔🔔好消息!好消息!🔔🔔
如果您需要注册ChatGPT，想要升级ChatGPT4。凯哥可以代注册ChatGPT账号，代升级ChatGPT4
有需要的朋友👉:微信号
总结：常用的淘汰算法有：FIFO、LRU、LFU
FIFO 算法（Fist in first out：先进先出）
FIFO 算法是一种比较容易实现的算法。它的思想：是基于队列的先进先出原则，最先进入的数据会被最先淘汰掉。这是最简单、最公平的一种思想。
（1）实现：维护一个FIFO队列，按照时间顺序将各数据（已分配页面）链接起来组成队列，并将置换指针指向队列的队首。再进行置换时，只需把置换指针所指的数据（页面）顺次换出，并把新加入的数据插到队尾即可。
（2）缺点：这种算法有个很严重的缺点，就是会导致缺页率增加。缺页率指的是判断一个页面置换算法优劣的指标。随着分配页面的增加，被置换的内存页面往往是被频繁访问的，因此FIFO算法会使一些页面频繁地被替换和重新申请内存，从而导致缺页率增加。由于缺页率会随着分配页面的增加而增加，使得redis的开销也逐渐增加，所以这种算法已经不再使用。
LRU算法（Least recently used：最近最少使用）
LRU算法是一种常见的缓存算法，它的思想是：最近最少使用的会被优先淘汰。如果一个数据在最近一段时间没有被访问到，那么可以认为在将来它被访问的可能性也很小。因此，当空间满时，最久没有访问的数据最先被淘汰掉。
（1）实现：最简单的实现方法是用数组+时间戳的方式，不过这样做效率较低。因此，我们可以用双向链表（LinkedList）+ 哈希表（HashMap）实现（链表用来表示位置，哈希表用来存储和查找），在Java里有对应的数据结构LinkedHashMap。
（2）缺点：它在需要淘汰时，只是随机选取有限的key进行对比，排除掉访问时间最久的元素，也就意味着它不能选择整个候选元素的最优解，只是局部最优。默认随机选取的key的数目为5，在配置文件redis.conf 中由maxmemory_samples属性的值决定，采样数量越大越接近于标准LRU算法，但也会带来性能的消耗。在Redis 3.0以后增加了LRU淘汰池，进一步提高了与标准LRU算法效果的相似度。淘汰池即维护的一个数组，数组大小等于抽样数量 maxmemory_samples，在每一次淘汰时，新随机抽取的key和淘汰池中的key进行合并，然后淘汰掉最旧的key，将剩余较旧的前面5个key放入淘汰池中待下一次循环使用。假如maxmemory_samples=5，随机抽取5个元素，淘汰池中还有5个元素，相当于变相的maxmemory_samples=10了，所以进一步提高了与LRU算法的相似度。
LFU算法（Least frequently used：最不常使用）
LFU算法的思想是：如果一个数据在最近一段时间很少被访问到，那么可以认为在将来它被访问的可能性也很小。因此，当空间满时，最小频率访问的数据最先被淘汰。
实现：如果只为每个key维护了一个计数器，每次key被访问的时候，计数器增大，计数器越大，则认为访问越频繁。这样还是远远不够的，还会存在两个问题：
（1）因为可能存在在开始一个小时内，某个key1有100万的访问量，但是在之后的一个小时内，这个key1的访问量为0了，而在这第二个小时内另外有个key2的访问量达到了20万，虽然这20万不如前面那个key1开始那个小时的100万访问量大，但是在第二个小时内这key2的访问量远大于key1的访问量，所以在第二个小时内key1依然会优先于key2被淘汰掉。
（2）当新加入的key，由于没有被访问过，所以初始的计数器为0，如果这时候触发淘汰机制的话，就会把最先添加到key最先淘汰掉。
所以在LFU算法中维护了这个24bit的字段，不过被分成了16 bits与8 bits两部分。第一部分：高16 bits用来记录计数器的上次缩减时间，时间戳，单位精确到分钟。第二部分：低8 bits用来记录计数器的当前数值，这个数值反映了访问频率，而不是次数。
在redis.conf配置文件中还有2个属性可以调整LFU算法的执行参数：lfu-log-factor、lfu-decay-time。其中lfu-log-factor用来调整计数器counter的增长速度，lfu-log-factor越大，counter增长的越慢。lfu-decay-time是一个以分钟为单位的数值，用来调整counter的缩减速度。
下一篇： 芋道后台 yudao 搭建调试环境