当近似LRU算法取值越大的时候就会越接近真实的LRU算法,因为取值越大获取的数据越完整,淘汰中的数据就更加接近最少使用的数据。这里其实涉及一个权衡问题,
如果需要在所有的数据中搜索最符合条件的数据,那么一定会增加系统的开销,Redis是单线程的,所以耗时的操作会谨慎一些。
为了在一定成本内实现相对的LRU,早期的Redis版本是基于采样的LRU,也就是放弃了从所有数据中搜索解改为采样空间搜索最优解。Redis3.0版本之后,Redis作者对于基于采样的LRU进行了一些优化:
Redis中维护一个大小为16的候选池,当第一次随机选取采用数据时,会把数据放入到候选池中,并且候选池中的数据会更具时间进行排序。
当第二次以后选取数据时,只有小于候选池内最小时间的才会被放进候选池。
当候选池的数据满了之后,那么时间最大的key就会被挤出候选池。当执行淘汰时,直接从候选池中选取最近访问时间小的key进行淘汰。
如图4-22所示,首先从目标字典中采集出maxmemory-samples个键,缓存在一个samples数组中,然后从samples数组中一个个取出来,和回收池中以后的键进行键的空闲时间,从而更新回收池。
在更新过程中,首先利用遍历找到的每个键的实际插入位置x,然后根据不同情况进行处理。
回收池满了,并且当前插入的key的空闲时间最小(也就是回收池中的所有key都比当前插入的key的空闲时间都要大),则不作任何操作。
回收池未满,并且插入的位置x没有键,则直接插入即可
回收池未满,且插入的位置x原本已经存在要淘汰的键,则把第x个以后的元素都往后挪一个位置,然后再执行插入操作。
回收池满了,将当前第x个以前的元素往前挪一个位置(实际就是淘汰了),然后执行插入操作。
图4-22这样做的目的是能够选出最真实的最少被访问的key,能够正确不常使用的key。因为在Redis3.0之前是随机选取样本,这样的方式很有可能不是真正意义上的最少访问的key。
LRU算法有一个弊端,加入一个key值访问频率很低,但是最近一次被访问到了,那LRU会认为它是热点数据,不会被淘汰。同样,
经常被访问的数据,最近一段时间没有被访问,这样会导致这些数据被淘汰掉,导致误判而淘汰掉热点数据,于是在Redis 4.0中,新加了一种LFU算法。
LFU算法LFU(Least Frequently Used),表示最近最少使用,它和key的使用次数有关,其思想是:根据key最近被访问的频率进行淘汰,比较少访问的key优先淘汰,反之则保留。
LRU的原理是使用计数器来对key进行排序,每次key被访问时,计数器会增大,当计数器越大,意味着当前key的访问越频繁,也就是意味着它是热点数据。 它很好的解决了LRU算法的缺陷:一个很久没有被访问的key,偶尔被访问一次,导致被误认为是热点数据的问题。
LFU的实现原理如图4-23所示,LFU维护了两个链表,横向组成的链表用来存储访问频率,每个访问频率的节点下存储另外一个具有相同访问频率的缓存数据。具体的工作原理是:
当添加元素时,找到相同访问频次的节点,然后添加到该节点的数据链表的头部。如果该数据链表满了,则移除链表尾部的节点
当获取元素或者修改元素是,都会增加对应key的访问频次,并把当前节点移动到下一个频次节点。
添加元素时,访问频率默认为1,随着访问次数的增加,频率不断递增。而当前被访问的元素也会随着频率增加进行移动。
图4-23 持久化机制的实现及原理Redis的强劲性能很大程度上是由于它所有的数据都存储在内存中,当然如果redis重启或者服务器故障导致redis重启,所有存储在内存中的数据就会丢失。但是在某些情况下,我们希望Redis在重启后能够保证数据不会丢失。
将redis作为nosql数据库使用。
将Redis作为高效缓存服务器,缓存被击穿后对后端数据库层面的瞬时压力是特别大的,所有缓存同时失效可能会导致雪崩。
这时我们希望Redis能将数据从内存中以某种形式同步到硬盘上,使得重启后可以根据硬盘中的记录来恢复数据。