Redis 缓存与淘汰策略

Redis

2021-06-07

阅读时长: 8 分钟

常见的缓存类型以及现实中常遇到的缓存问题，Redis 所采用的过期淘汰策略 LRU、LFU 等。

缓存的类型分为：本地缓存、分布式缓存和多级缓存。

本地缓存就是在进程的内存中进行缓存。

本地缓存是内存访问，没有远程交互开销，性能最好，但是受限于单机容量，一般缓存较小且无法扩展。

分布式缓存

分布式缓存一般都具有良好的水平扩展能力，对较大数据量的场景也能应付自如。

缺点就是需要进行远程请求，性能不如本地缓存。

实际业务中一般采用多级缓存，本地缓存只保存访问频率最高的部分热点数据，其他的热点数据放在分布式缓存中。

在目前的一线大厂中，这也是最常用的缓存方案，单考单一的缓存方案往往难以撑住很多高并发的场景。

缓存穿透 Cache Penetration，指数据库和缓存中都没有符合条件的数据，导致业务系统每次都绕过缓存服务器查询下游的数据库。

如果黑客发起针对该 key 的大量访问攻击，会导致数据库压力过大，最终击垮数据库。

解决方案：

首先需要在接口层做参数校验，拒绝逻辑上没有的数据，比如 id < 0；
查询数据库和缓存中没有的数据，在缓存中存储空值或默认值等（具体由产品决定）；
- 此缓存设置的过期时间要短，避免影响真实业务；
- 数据库更新时，需要及时更新对应缓存数据；
网关层对单个 IP 的访问量做出限制，避免异常用户的大量暴力访问；
布隆过滤器 Bloom Filter，此算法可以非常高效的判断数据数据一定不存在或可能存在，如果判定不存在，就可以直接不查数据库直接返回。

缓存击穿 Cache Breakdown，是指某一个大量请求不断访问的热点 key 突然过期时，大量请求直接访问数据库，让数据库压力瞬间增大的情况。

解决方案：

使用互斥锁，在发现某个缓存为空时，先加锁，从数据库加载数据完毕后解锁。其他线程获取锁失败时，则休眠一段时间后重试。这种方式保证同时只有一个请求去数据库读取数据更新缓存；
热点数据永不过期，只更新数据；

缓存雪崩 Cache Avalanche，是指大量缓存同时过期或缓存服务宕机，造成缓存逐级崩溃，最终压垮数据库的情况。

解决方案：

缓存集群部署，Redis 高可用，主从+哨兵，Redis cluster，尽量避免缓存服务的全盘崩溃；
随机过期时间，让缓存的过期时间在一定范围内随机浮动，将同一时间点的过期分散到一个时间段内，降低峰值；
热点数据永不过期，只更新数据；
数据限流，在各层缓存和数据库之间进行限流，保证系统整体可用；
系统熔断和降级，返回一些默认的值，或者友情提示，或者空白的值。

缓存一致性

缓存一致性指的是，在高并发情况下，请求使用数据旧值覆盖了缓存的新值情况。常见的有两种情况：

先更后更：

指的是先更新数据库，后更新缓存。此方法在以下情况会出现缓存不一致：

线程 A 更新数据库;
线程 B 更新数据库;
线程 B 更新缓存；
线程 A 使用旧值更新缓存。

先删后更：

指的是先删除缓存，后更新数据库。此方法在以下情况会出现缓存不一致：

请求 A 先删除缓存；
请求 B 查询发现缓存不存在；
请求 B 查询数据库，得旧值；
请求 B 将旧值写入缓存；
请求 A 将新值写入数据库；

此方法可以使用延时双删策略尽量保证数据一致性，也就是请求 A 将新值写入数据库后，延时一段时间，再次删除缓存。

解决方案：先更后删

目前业界主流的方式是使用先更后删策略更新缓存。此方案下依然可能会有缓存不一致的可能性：

缓存失效；
请求 A 查询数据库，得旧值；
请求 B 更新数据库；
请求 B 删除缓存；
请求 A 将查询到的旧值写入缓存；

在此情况下，依然会产生脏数据，但是前提是：步骤 3 比步骤 2 耗时更短，但通常来说更新数据耗时比查询数据长的，所以这一情况很难出现。

还有一个问题是请求 B 删除缓存失败怎么办，解决方案是使用一个保障删除成功的重试机制即可，比如消息队列。

Redis 淘汰策略

redis 会将每个设置了过期时间的 key 放入到一个独立的字典中，定期遍历这个字典来删除到期的 key。

Redis 默认会每秒进行十次过期扫描（100ms一次），过期扫描不会遍历过期字典中所有的 key，而是采用了一种简单的贪心策略。

从过期字典中随机取 20 个 key
删除这 20 个 key 中已经过期的 key
如果过期的 key 比率超过 1/4，重复步骤 1

此策略主要避免了当 Redis 数据量太大时，每次过期检测需要遍历所有设置了过期时间的 key，造成 cpu 负载过大的问题。

惰性策略就是在客户端访问这个 key 的时候，对 key 的过期时间进行检查，如果过期了就立即删除，不会返回任何东西。

定期删除可能会导致很多过期 key 到了时间并没有被删除掉。所以就有了惰性删除。

内存淘汰策略

由于定期删除和惰性删除策略，并不是所有的过期 key 都会被删除，所以需要内存淘汰策略进行补充。

Redis 4.0 以前有 6 种内存淘汰策略：

noeviction：当内存使用超过配置的时候会返回错误，不会驱逐任何键
allkeys-lru：加入键的时候，如果过限，首先通过 LRU 算法驱逐最久没有使用的键
volatile-lru：加入键的时候如果过限，首先从设置了过期时间的键集合中驱逐最久没有使用的键
allkeys-random：加入键的时候如果过限，从所有 key 随机删除
volatile-random：加入键的时候如果过限，从过期键的集合中随机驱逐
volatile-ttl：从配置了过期时间的键中驱逐马上就要过期的键

Redis 4.0 后新增了两种 lfu 策略：

volatile-lfu：从所有配置了过期时间的键中驱逐使用频率最少的键
allkeys-lfu：从所有键中驱逐使用频率最少的键

LRU 算法

LRU(Least Recently Used) 最近最少算法用于计算淘汰最久没有使用过的 key，但 Redis 没有使用标准 LRU 实现，而是使用了一种近似的 LRU 实现方式。

标准 LRU

标准的 LRU 算法使用一个双向链表来记录数据的最近被访问顺序。

新增 key 时，在链表结尾添加 node，如果超出 LRU 阈值，淘汰链表队头的 node
修改 key 时，先修改对应 node 的值，然后把 node 移动到链表队尾
访问 key 时，将 node 移动到链表队尾

Redis LRU 实现

Redis 在每一个 key 对象内部维护了一个以秒为单位的 24 位时间戳，通过对少量 key 进行采样（默认 5 个），对比时间戳，然后回收其中最久未被访问的 key。

需要注意的是此时间戳最大只能表示 194 天，不过这对于更新频繁的缓存数据来说是够用的。

Redis 中有三个配置和 LRU 有关：

maxmemory: Redis 存储数据时限制的内存大小，比如 100m。超过这个数值时触发数据淘汰。此配置为 0 时，不限制内存量。64 位的系统默认值为 0，32 位的系统默认内存限制为 3GB。
maxmemory_policy: 触发数据淘汰后的淘汰策略。
maxmemory_samples: 随机采样的精度，也就是随机取出 key 的数目。该数值配置越大, 越接近于真实的 LRU 算法，但是数值越大，相应消耗也变高，对性能有一定影响，样本值默认为 5。

Redis 3.0 LRU 优化：

优化后算法会维护一个候选池，大小为 16，池中的数据根据访问时间进行排序，第一次采样选取的 key 都会放入池中。

随后每次随机选取的 key 只有在访问时间小于池中最小的时间才会放入池中，直到候选池被放满。
池放满后，如果有新的 key 需要放入，则将池中最近被访问的移出池。
需要淘汰数据的时候，直接从池中选取最久没被访问的 key 淘汰掉。

为什么不使用标准 LRU

原生 LRU 算法需要双向链表来管理数据，需要更多的内存
原生 LRU 需要对所有 key 进行排序，性能损耗更高
如果请求符合长尾法则，那么真实 LRU 与 Redis LRU 之间表现基本无差异，实际效果基本相等
需要改造现有 Redis 数据结构

据 Redis 作者说，每个 Redis Object 可以挤出 24 bits 空间，但 24 bits 不够存储两个指针，但可以存储一个低位时间戳。

Redis LRU 算法性能

LFU 算法

使用 LRU 算法，有可能一个 key 很久没有被访问，只刚刚偶尔被访问了一次，那么它就被认为是热点数据，不会被淘汰，而有些 key 将来是很有可能被访问到但被淘汰了。

Redis 在 4.0 中新增了一种 LFU 淘汰策略，用于根据 key 的访问频率进行淘汰。

LFU 原理是为每个 key 维护一个计数器。每当 key 被访问时，计数器增大。计数器越大，可以约等于访问越频繁。每次采样时淘汰掉访问最不频繁的 key。

Redis LFU 实现

Redis 中有三个配置项可以调整 LFU 算法的行为：

lfu-log-factor: 默认为 10，访问频率增长速度，值越大，访问频率增长越慢。
lfu-decay-time: 默认为 1，访问频率降低速度，值越大，访问频率降低越慢。
LFU_INIT_VAL: 默认为 5，新增 key 的默认访问频率。

LFU 使用跟 LRU 同样的 24 bits 字段记录数据。

前 16 bits 用于记录以分钟为单位的时间，用于表示最近一次访问频率被降低的时间。
后 8 bits 记录访问频率 counter，最大为 255。

LFU 维护了一个与 LRU 相同的候选池，用于节省排序所有 key 访问频率所需要的时间。

增加访问频率

由于只使用 8 bits 记录访问频率，最大为 255，所以访问频率不能无限增大。Redis 的解决方式是，访问频率越高，则访问频率增加的可能性越低。

增加频率函数如下：

/* Logarithmically increment a counter. The greater is the current counter value
 * the less likely is that it gets really implemented. Saturate it at 255. */
uint8_t LFULogIncr(uint8_t counter) {
    if (counter == 255) return 255;
    double r = (double)rand()/RAND_MAX;
    double baseval = counter - LFU_INIT_VAL;
    if (baseval < 0) baseval = 0;
    double p = 1.0/(baseval*server.lfu_log_factor+1);
    if (r < p) counter++;
    return counter;
}

首先取一个 0-1 之间的随机数 r
由 counter 和 lfu_log_factor 决定一个 0-1 之间的值 p。counter 越大，p 值越小。
比较 r 与 p，如果 r < p，则 counter 增加 1。

可以看到当 counter 越大，则 p 值越小，则 r < p 的可能性越小，则 counter 增加的几率越小。

当 counter 为 255 时，则不再增加。

降低访问频率

如果只增加访问频率，则有可能一个 key 在某段时间被大量访问，之后不再被使用，这样的 key 将不会被淘汰，所以需要一种根据时间降低 key 访问频率的机制。

降低频率函数如下：

/* If the object decrement time is reached decrement the LFU counter but
 * do not update LFU fields of the object, we update the access time
 * and counter in an explicit way when the object is really accessed.
 * And we will times halve the counter according to the times of
 * elapsed time than server.lfu_decay_time.
 * Return the object frequency counter.
 *
 * This function is used in order to scan the dataset for the best object
 * to fit: as we check for the candidate, we incrementally decrement the
 * counter of the scanned objects if needed. */
unsigned long LFUDecrAndReturn(robj *o) {
    unsigned long ldt = o->lru >> 8;
    unsigned long counter = o->lru & 255;
    unsigned long num_periods = server.lfu_decay_time ? LFUTimeElapsed(ldt) / server.lfu_decay_time : 0;
    if (num_periods)
        counter = (num_periods > counter) ? 0 : counter - num_periods;
    return counter;
}

函数首先取得前 16 bits 的最近一次频率被降低时间。
计算最近一次频率被降低时间与当前时间的差值。
根据 lfu_decay_time 与差值的多少计算需要降低多少访问频率。

新增 key 默认访问频率

如果一个新增 key 的默认访问频率为 0，那么这个 key 很可能快速被删除掉，所以需要为新增 key 设定一个默认的访问频率值。

可以通过 LFU_INIT_VAL 设置，默认值为 5。

Redis 缓存与淘汰策略