目录

一、缓存应用二、淘汰机制三、LRU 算法四、LFU 算法

一、缓存应用

一个系统中不同层面数据访问速度不一样，以计算机为例，CPU、内存和磁盘这三层的访问速度从几十 ns 到 100ns，再到几 ms，性能的差异很大，如果每次 CPU 处理数据时都要到磁盘读取数据，系统运行速度会大大降低。

所以，计算机系统中，默认有两种缓存：

（1）CPU 里面的末级缓存，即 LLC，用来缓存内存中的数据，避免每次从内存中存取数据。（2）内存中的高速页缓存，即 page cache，用来缓存磁盘中的数据，避免每次从磁盘中存取数据。

在一个层次化的系统中，缓存一定是一个快速子系统，数据存在缓存中时，能避免每次从慢速子系统中存取数据。对应到互联网应用来说，Redis 就是快速子系统，而数据库就是慢速子系统了。

Redis 是一个独立的系统软件，如果应用程序想使用 Redis 缓存，就需要增加相应的代码。所以，我们也把 Redis 称为旁路缓存，也就是说，读取缓存、读取数据库和更新缓存的操作都需要在应用程序中来完成。

Redis 缓存按照是否接受写请求，分为只读缓存和读写缓存两种类型，只读缓存能加速读请求，而读写缓存可以同时加速读写请求。读写缓存又分为同步直写和异步写回，可以根据业务需求在保证性能和保证数据可靠性之间进行选择。

二、淘汰机制

缓存的容量终究是有限的，需要按一定规则淘汰出去，为新来的数据腾出空间，提高缓存命中率，提升应用的访问性能。缓存容量的规划通常是需要结合应用数据实际访问特征和成本开销来综合考虑的，建议把缓存容量设置为总数据量的 15% 到 30%，兼顾访问性能和内存空间开销。设置容量命令（如4gb）：CONFIG SET maxmemory 4gb

8种淘汰策略：noeviction、volatile-random、volatile-ttl、volatile-lru、volatile-lfu、allkeys-lru、allkeys-random、allkeys-lfu

大体分为两类，noeviction（不淘汰数据），缓存被写满了，再有写请求时 Redis 不再提供服务，直接返回错误。另外7种是一类，按照一定范围对缓存数据进行淘汰，对设置过期时间的数据进行淘汰，和对所有数据进行淘汰。分类如图：

具体策略如下：

（1）volatile-ttl： 根据过期时间的先后进行删除，越早过期的越先被删除。（2）volatile-rando： 在设置了过期时间的键值对中，进行随机删除。（3）volatile-lru： 使用 LRU 算法筛选设置了过期时间的键值对。（4）volatile-lfu： 使用 LFU 算法选择设置了过期时间的键值对。（5）allkeys-random：从所有键值对中随机选择并删除数据。（6）allkeys-lru： 使用 LRU 算法在所有数据中进行筛选。（7）allkeys-lfu： 使用 LFU 算法在所有数据中进行筛选。

三、LRU 算法

LRU 算法全称 Least Recently Used，按照最近最少使用的原则来筛选数据，最不常用的数据会被筛选出来，而最近频繁使用的数据会留在缓存中。

LRU 会把所有的数据组织成一个链表，链表的头和尾分别表示 MRU 端和 LRU 端，分别代表最近最常使用的数据和最近最不常用的数据。

举个栗子：数据 20 和 3 被访问后，它们在链表中的位置移动到了 MRU 端，LRU 算法选择删除数据时，都是从 LRU 端开始，所以当新数据15被写入时，LRU 端的数据5被删除。

LRU 算法在实际实现时，需要用链表管理所有的缓存数据，这会带来额外的空间开销。而且，当有数据被访问时，需要在链表上把该数据移动到 MRU 端，如果有大量数据被访问，就会带来很多链表移动操作，会很耗时，进而会降低 Redis 缓存性能。

所以，在 Redis 中，LRU 算法被做了简化，以减轻数据淘汰对缓存性能的影响，具体实现原理是 Redis 默认会记录每个数据的最近一次访问的时间戳（由键值对数据结构 RedisObject 中的 lru 字段记录），在需要选择淘汰的数据时，Redis首先会随机选择N个数据将它们作为一个候选集合，然后比较他们的lru字段，将lru字段最小的数据淘汰掉。

N 可以通过命令设置：

CONFIG SET maxmemory-samples 100

当再次淘汰时，Redis会再挑选一些lru字段比候选集合中最小lru字段还要小的键值对，将它们放入候选集，如果候选集的数据的个数达到了 maxmemory-sample 配置的个数，Redis就开始将lru字段值最小的数据淘汰

四、LFU 算法

与 LRU 策略相比，LFU 策略中会从两个维度来筛选并淘汰数据：一是，数据访问的时效性（访问时间离当前时间的远近）；二是，数据的被访问次数。就是在 LRU 策略基础上，为每个数据增加了一个计数器，来统计访问次数。淘汰数据时，首先会根据数据的访问次数进行筛选，把访问次数最低的数据淘汰出缓存。如果两个数据的访问次数相同，再比较这两个数据的访问时效性，把距离上一次访问时间更久的数据淘汰出缓存。

具体实现是把原来 24bit 大小的 lru 字段，又进一步拆分成了两部分：ldt 值（lru 字段的前 16bit，表示数据的访问时间戳）、counter 值（lru 字段的后 8bit，表示数据的访问次数）。但是 counter 只有 8bit，记录的最大值是 255，显然不能因对数据成千上万次的访问。实际 LFU 策略实现时，数据访问并不是简单的 counter 值加 1 的计数规则，而是采用了一个更优化的计数规则。

每当数据被访问一次时，首先，用计数器当前的值乘以配置项 lfu_log_factor 再加

1，再取其倒数，得到一个 p 值；然后，把这个 p 值和一个取值范围在（0，1）间的随机数 r 值比大小，只有 p 值大于 r

值时，计数器才加 1，通过设置不同的 lfu_log_factor 配置项，来控制计数器值增加的速度。以下是计算方式部分代码

（baseval当前值）和 lfu_log_factor 设置不同值的变化情况：

double r = (double)rand()/RAND_MAX;

...

double p = 1.0/(baseval*server.lfu_log_factor+1);

if (r < p) counter++;

正是因为使用了非线性递增的计数器方法，即使缓存数据的访问次数成千上万，LFU 策略也可以有效地区分不同的访问次数，从而进行合理的数据筛选。从刚才的表中，我们可以看到，当 lfu_log_factor 取值为 10 时，百、千、十万级别的访问次数对应的 counter 值已经有明显的区分了，所以，我们在应用 LFU 策略时，一般可以将 lfu_log_factor 取值为 10。

有些数据在短时间内被大量访问后就不会再被访问了，按访问次数筛选时，这些数据会被留存在缓存中，但不会提升缓存命中率。为此，Redis 在实现 LFU 策略时，还设计了一个 counter 值的衰减机制。通过配置衰减因子 lfu_decay_time 来控制访问次数的衰减。

具体操作是计算当前时间和数据最近一次访问时间的差值，换算成分钟单位，再除以 lfu_decay_time 值，就是数据 counter 要衰减的值。lfu_decay_time 值越大，相应的衰减值会变小，衰减效果也会减弱。所以，如果业务应用中有短时高频访问的数据的话，建议把 lfu_decay_time 值设置为 1，它们不再被访问后，会较快地衰减它们的访问次数，尽早把它们从缓存中淘汰出去，避免缓存污染。