redis 过期策略及内存回收机制

我就是我 2022-02-25 12:40 196阅读 0赞

redis作为缓存的场景下，内存淘汰策略决定的redis的内存使用效率。考虑到这个很多大厂给出的“送分题”，但一般人很少能讲清楚，除非你对真的对过期策略、懒惰删除、LRU、LRU有一定的研究。

**目录**

1. 过期策略

1.1 过期的 key 集合

1.2 定时扫描策略

1.3 从库的过期策略

2. 懒惰删除

2.1 异步线程

2.2 flush

2.3 异步队列

2.4 AOF Sync很慢的问题

2.5 更多异步删除点

3. 过期淘汰配置

4. LRU 算法

4.1 近似 LRU 算法

5. LRU

5.1 LRU 模式

5.2 LFU 模式

--------------------

## 1. 过期策略 ##

Redis 所有的数据结构都可以设置过期时间，时间一到，就会自动删除。就像死神，时刻盯着所有设置了过期时间的 key，寿命一到就会立即收割。

站在死神的角度思考：会不会在同一时间太多的 key 过期（Redis 是单线程的，收割的时间也会占用线程的处理时间，如果收割的太过于繁忙），以至于忙不过来？会不会导致线上读写指令出现卡顿？

### **1.1 过期的 key 集合** ###

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

redis 采用两种策略：

1.  **定时删除**是集中处理，
2.  **惰性删除**是零散处理，

### **1.2 定时扫描策略** ###

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

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

同时，为了保证过期扫描不会出现循环过度，导致线程卡死现象，算法还增加了扫描时间的上限，默认不会超过 25ms。

如果Redis 实例中所有的 key （几十万个）在同一时间过期会怎样？

Redis 会持续扫描过期字典 (循环多次)，直到过期字典中过期的 key 变得稀疏，才会停止 (循环次数明显下降)。内存管理器需要频繁回收内存页，此时会产生一定的 CPU 消耗，必然导致线上读写请求出现明显的卡顿现象。

当客户端请求到来时（服务器如果正好进入过期扫描状态），客户端的请求将会等待至少 25ms 后才会进行处理，如果客户端将超时时间设置的比较短，比如 10ms，那么就会出现大量的链接因为超时而关闭，业务端就会出现很多异常。而且这时你还无法从 Redis 的 slowlog 中看到慢查询记录，因为慢查询指的是逻辑处理过程慢，不包含等待时间。

其实这个故障在社区中时常爆出 ，**业务开发人员一定要注意不宜全部在同一时间过期**，可以给目标过期时间的基础上再加一个随机范围（redis.expire\_at(key, random.randint(86400) + expire\_ts)），分散过期处理的压力。

### **1.3 从库的过期策略** ###

从库不会进行过期扫描，从库对过期的处理是被动的。主库在 key 到期时，会在 AOF 文件里增加一条 `del` 指令，同步到所有的从库，从库通过执行这条 `del` 指令来删除过期的 key。

因为指令同步是异步进行的，所以主库过期的 key 的 `del` 指令没有及时同步到从库的话，会出现主从数据的不一致，主库没有的数据在从库里还存在，分布式锁的算法漏洞就是因为这个同步延迟产生的。

## 2. 懒惰删除 ##

**懒惰删除(lazy free)，**在客户端访问key时再进行检查如果过期了就立即删除

为什么要懒惰删除？

Redis内部实际上并不是只有一个主线程，它还有几个异步线程专门用来处理一些耗时的操作。删除指令 `del` 会直接释放对象的内存，大部分情况下，这个指令非常快，没有明显延迟。

不过如果删除的 key 是一个非常大的对象，那么删除操作就会导致单线程卡顿，怎么破？

**Redis 4.0** 版本引入了 `unlink` 指令（为了解决这个卡顿问题），它能对删除操作进行懒处理，丢给后台线程来**异步回收**内存。

> > unlink key  
> OK

你肯定会担心这里的线程安全问题，会不会出现多个线程同时并发修改数据结构的情况存在？

这里我打个比方：可以将整个 Redis 内存里面所有有效的数据想象成一棵大树。当 `unlink` 指令发出时，它只是把大树中的一个树枝别断了，然后扔到旁边的火堆里焚烧 (异步线程池)。树枝离开大树的一瞬间，它就再也无法被主线程中的其它指令访问到了，因为主线程只会沿着这颗大树来访问。

### 2.1 异步线程 ###

异步线程在 Redis 内部有一个特别的名称，它就是`BIO`，全称是`Background IO`，意思是在背后默默干活的 IO 线程。不过内存回收本身并不是什么 IO 操作，只是 CPU 的计算消耗可能会比较大而已。

**异步线程演进之路**

实现懒惰删除时，它并不是一开始就想到了异步线程。最初的尝试是在主线程里，使用类似于字典渐进式搬迁那样来实现渐进式删除回收。懒惰删除是采用类似于 scan 操作的方法，通过遍历第一维数组来逐步删除回收第二维链表的内容，等到所有链表都回收完了，再一次性回收第一维数组。这样也可以达到删除大对象时不阻塞主线程的效果。

但是说起来容易做起来却很难。渐进式回收需要仔细控制回收频率，它不能回收的太猛，这会导致 CPU 资源占用过多，也不能回收的蜗牛慢，因为内存回收不及时可能导致内存持续增长。

Antirez 需要采用合适的自适应算法来控制回收频率。他首先想到的是检测内存增长的趋势是增长 (+1) 还是下降 (-1) 来渐进式调整回收频率系数，这样的自适应算法实现也很简单。但是测试后发现在服务繁忙的时候，QPS 会下降到正常情况下 65% 的水平，这点非常致命。

所以 Antirez 才使用了如今使用的方案——异步线程。异步线程这套方案就简单多了，释放内存不用为每种数据结构适配一套渐进式释放策略，也不用搞个自适应算法来仔细控制回收频率。

不过使用异步线程也是有代价的，主线程和异步线程之间在内存回收器 (jemalloc) 的使用上存在竞争。这点竞争消耗是可以忽略不计的，因为 Redis 的主线程在内存的分配与回收上花的时间相对整体运算时间而言是极少的。

异步线程方案相当复杂，具体可参阅引用资料。

### **2.2 flush** ###

Redis 提供了 `flushdb` 和 `flushall` 指令，用来清空数据库，这也是极其缓慢的操作。

**Redis 4.0** 同样给这两个指令也带来了**异步化**，在指令后面增加 `async` 参数就可以将整棵大树拔起，扔给后台线程慢慢焚烧。

> > flushall async  
> OK

### **2.3 异步队列** ###

Redis4.0，主线程将对象的引用从「大树」中摘除后，会将这个 key 的内存回收操作包装成一个任务，塞进异步任务队列，后台线程会从这个异步队列中取任务。任务队列被主线程和异步线程同时操作，所以必须是一个线程安全的队列。

![20190402231022700.png][]

不是所有的 `unlink` 操作都会延后处理，如果对应 key 所占用的内存很小，延后处理就没有必要了，这时候 Redis 会将对应的 key 内存立即回收，跟 `del` 指令一样。

### **2.4 AOF Sync很慢的问题** ###

Redis需要每秒一次（可配置）同步AOF日志到磁盘，确保消息尽量不丢失，需要调用sync函数，这个操作会比较耗时，会导致主线程的效率下降，所以Redis也将这个操作移到异步线程来完成。

执行AOF Sync操作的线程是一个独立的异步线程，和前面的懒惰删除线程不是一个线程，同样它也有一个属于自己的任务队列，队列里只用来存放AOF Sync任务。

### **2.5 更多异步删除点** ###

Redis 回收内存除了 `del` 指令和 `flush` 之外，还会存在于在 key 的过期、LRU 淘汰、rename 指令以及从库全量同步时接受完 rdb 文件后会立即进行的 flush 操作。

**Redis4.0** 为这些删除点也带来了异步删除机制，打开这些点需要额外的配置选项。

1.  `slave-lazy-flush` 从库接受完 rdb 文件后的 flush 操作
2.  `lazyfree-lazy-eviction` 内存达到 maxmemory 时进行淘汰
3.  `lazyfree-lazy-expire key` 过期删除
4.  `lazyfree-lazy-server-del` rename 指令删除 destKey

## 3. 过期淘汰配置 ##

当 Redis 已使用内存超出物理内存限制时，内存中的数据会开始和磁盘产生频繁的交换 (swap)，交换会让 Redis 的性能急剧下降，而此时Redis的存取效率简直是龟速（基本上等于不可用）。在生产环境中这是不允许的，为了限制最大使用内存，Redis 提供了配置参数 `maxmemory` 来限制内存超出期望大小。

那如果实际内存超出 `maxmemory` 时该怎么办？

Redis提供了几种可选策略 (maxmemory-policy) 来让用户自己决定该如何腾出新的空间以继续提供读写服务。

<table> 
 <tbody> 
  <tr> 
   <td><strong>noeviction</strong></td> 
   <td style="width:667px;">不会继续服务写请求 (DEL 请求可以继续服务)，读请求可以继续进行。这样可以保证不会丢失数据，但是会让线上的业务不能持续进行。<strong>这是默认的淘汰策略</strong>。</td> 
  </tr> 
  <tr> 
   <td><strong>volatile-lru</strong></td> 
   <td style="width:667px;">尝试淘汰设置了过期时间的 key，最少使用的 key 优先被淘汰。没有设置过期时间的 key 不会被淘汰，这样可以保证需要持久化的数据不会突然丢失。</td> 
  </tr> 
  <tr> 
   <td><strong>volatile-ttl</strong></td> 
   <td style="width:667px;">跟上面一样，除了淘汰的策略不是 LRU，而是 key 的剩余寿命 ttl 的值，ttl 越小越优先被淘汰。</td> 
  </tr> 
  <tr> 
   <td><strong>volatile-random</strong></td> 
   <td style="width:667px;">跟上面一样，不过淘汰的 key 是过期 key 集合中随机的 key</td> 
  </tr> 
  <tr> 
   <td><strong>allkeys-lru</strong></td> 
   <td style="width:667px;">区别于 volatile-lru，这个策略要淘汰的 key 对象是全体的 key 集合，而不只是过期的 key 集合。这意味着没有设置过期时间的 key 也会被淘汰。</td> 
  </tr> 
  <tr> 
   <td><strong>allkeys-random</strong></td> 
   <td style="width:667px;">跟上面一样，不过淘汰的策略是随机的 key</td> 
  </tr> 
 </tbody> 
</table>

> redis.conf中配置  
> maxmemory <bytes>                 \#最大内存（单位字节）  
> maxmemory-policy noeviction   \#默认

小结

*  volatile-xxx 策略只会针对带过期时间的 key 进行淘汰，
 *  allkeys-xxx 策略会对所有的 key 进行淘汰

那该如何抉择呢？

如果你只是拿 Redis 做**缓存**，那最好使用 allkeys-xxx，客户端写缓存时不必携带过期时间。

如果你还想同时具备**持久化功能**，那就使用 volatile-xxx 策略，好处就是，没有设置过期时间的 key 不会被 LRU 算法淘汰

## 4. LRU 算法 ##

实现 LRU（最近最少） 算法除了需要 key/value 字典外，还需要附加一个链表，链表中的元素按照一定的顺序进行排列。

当空间满的时候，会踢掉链表尾部的元素。当字典的某个元素被访问时，它在链表中的位置会被移动到表头。所以链表的元素排列顺序就是元素最近被访问的时间顺序。

### 4.1 近似 LRU 算法 ###

Redis 使用的是一种近似 LRU 算法，它跟 LRU 算法还不太一样。之所以不使用 LRU 算法，是因为需要消耗大量的额外的内存，需要对现有的数据结构进行较大的改造。近似 LRU 算法则很简单，在现有数据结构的基础上使用随机采样法来淘汰元素，能达到和 LRU 算法非常近似的效果。

Redis 为实现近似 LRU 算法，它给每个 key 增加了一个额外的小字段，这个字段的长度是 24 个 bit，也就是最后一次被访问的时间戳。

前面讲过key 过期方式分为集中处理和懒惰处理，LRU 淘汰不一样，**它的处理方式只有懒惰处理**。当 Redis 执行写操作时，发现内存超出 maxmemory，就会执行一次 LRU 淘汰算法。这个算法也很简单，就是随机采样（可以通过maxmemory-policy配置）出 5个 key，然后淘汰掉最旧的 key，如果淘汰后内存还是超出 maxmemory，那就继续随机采样淘汰，直到内存低于 maxmemory为止。

下面是随机 LRU 算法和严格 LRU 算法的效果对比图：绿色部分是新加入的 key，深灰色部分是老旧的 key，浅灰色部分是通过 LRU 算法淘汰掉的 key。可以看出采样数量越大，近似 LRU 算法的效果越接近严格 LRU 算法。同时 Redis3.0 在算法中增加了淘汰池，进一步提升了近似 LRU 算法的效果。

![20190402225811808.png][]

淘汰池是一个数组，它的大小是 maxmemory\_samples，在每一次淘汰循环中，新随机出来的 key 列表会和淘汰池中的 key 列表进行融合，淘汰掉最旧的一个 key 之后，保留剩余较旧的 key 列表放入淘汰池中留待下一个循环。

## 5. LRU ##

**Redis 4.0** 里引入了一个新的淘汰策略 —— LFU （Least Frequently Used）模式，作者认为它比 LRU 更加优秀。它表示按最近的访问频率进行淘汰，它比 LRU 更加精准地表示了一个 key 被访问的热度。

它淘汰策略配置参数`maxmemory-policy`增加了 2 个选项，分别是 volatile-lfu 和 allkeys-lfu，分别是对带过期时间的 key 进行 lfu 淘汰以及对所有的 key 执行 lfu 淘汰算法。

如果一个 key 长时间不被访问，只是刚刚偶然被用户访问了一下，那么在使用 LRU 算法下它是不容易被淘汰的，因为 LRU 算法认为当前这个 key 是很热的。而 LFU 是需要追踪最近一段时间的访问频率，如果某个 key 只是偶然被访问一次是不足以变得很热的，它需要在近期一段时间内被访问很多次才有机会被认为很热。

Redis 的所有对象结构头中都有一个 24bit 的字段，这个字段用来记录对象的「热度」。

// redis 的对象头
    typedef struct redisObject {
        unsigned type:4; // 对象类型如 zset/set/hash 等等
        unsigned encoding:4; // 对象编码如 ziplist/intset/skiplist 等等
        unsigned lru:24; // 对象的「热度」
        int refcount; // 引用计数
        void *ptr; // 对象的 body
    }robj;

### 5.1 LRU 模式 ###

lru 字段存储的是 Redis 时钟`server.lruclock`，Redis 时钟是一个 24bit 的整数，默认是 Unix 时间戳对 2^24 取模的结果，大约 97 天清零一次。当某个 key 被访问一次，它的对象头的 lru 字段值就会被更新为`server.lruclock`，该值一直是递增的，通过这个逻辑就可以精准计算出对象多长时间没有被访问——对象的空闲时间。如果超过`server.lruclock`折返了。

![20190404220637277.png][]

有了对象的空闲时间，就可以相互之间进行比较谁新谁旧，随机 LRU 算法靠的就是比较对象的空闲时间来决定谁该被淘汰了。

默认 Redis 时钟值每毫秒更新一次，在定时任务`serverCron`里主动设置，在`serverCron`里面其实有很多很多定时任务，比如大型 hash 表的渐进式迁移、过期 key 的主动淘汰、触发 bgsave、bgaofrewrite 等等。

为什么 Redis 要缓存系统时间戳？

在java中我们使用`System.currentTimeInMillis``()，而`Redis 不能这样，因为每一次获取系统时间戳都是一次系统调用，系统调用相对来说是比较费时间的，这样的消耗对redis而言是伤不起的，所以获取时间都直接从缓存中直接拿。

### 5.2 LFU 模式 ###

lru 字段 24 个 bit 用来存储两个值，分别是`ldt(last decrement time)`和`logc(logistic counter)`。

![20190404215617763.png][]

**logc**是 8 个 bit，用来存储访问频次（最大整数值为 255）。存储频次远远不够（太小），所以这 8 个 bit 存储的是频次的对数值，并且这个值还会随时间衰减。如果它的值比较小，就很容易被回收，为了确保新创建的对象不被回收，新对象的初始化默认是`LFU_INIT_VAL=5`。

**ldt** 是 16 个位，用来存储上一次 logc 的更新时间（精度不可能很高），它取的是分钟时间戳对 2^16 进行取模，大约每隔 45 天就会折返。同 LRU 模式一样，我们也可以使用这个逻辑计算出对象的空闲时间，只不过精度是分钟级别的。

server.unixtime 是当前 redis 记录的系统时间戳，和 server.lruclock 一样，它也是每毫秒更新一次。

![20190404220839136.png][]

// nowInMinutes
    // server.unixtime 为 redis 缓存的系统时间戳
    unsigned long LFUGetTimeInMinutes(void) {
        return (server.unixtime/60) & 65535;
    }
    // idle_in_minutes
    unsigned long LFUTimeElapsed(unsigned long ldt) {
        unsigned long now = LFUGetTimeInMinutes();
        if (now >= ldt) return now-ldt; // 正常比较
        return 65535-ldt+now; // 折返比较
    }

**ldt** 的值不是在对象被访问时更新的，它在 Redis 的淘汰逻辑进行时进行更新，淘汰逻辑只会在内存达到 maxmemory 的设置时才会触发，在每一个指令的执行之前都会触发。每次淘汰都是采用随机策略，随机挑选若干个 key，更新这个 key 的「热度」，淘汰掉「热度」最低的。因为 Redis 采用的是随机算法，如果 key 比较多的话，那么 ldt 更新的可能会比较慢。不过既然它是分钟级别的精度，也没有必要更新的过于频繁。

**ldt** 更新的同时也会一同衰减 **logc** 的值，衰减也有特定的算法。它将现有的 logc 值减去对象的空闲时间 (分钟数) 除以一个衰减系数，默认这个衰减系数`lfu_decay_time`是 1。如果这个值大于 1，那么就会衰减的比较慢。如果它等于零，那就表示不衰减，它是可以通过配置参数`lfu_decay_time`进行配置。

**logc** 的更新和 LRU 模式的 lru 字段一样，都会在 key 每次被访问的时候更新，只不过它的更新不是简单的`+1`，而是采用概率法进行递增，因为 logc 存储的是访问计数的对数值，不能直接`+1`。

总结，通过LFU 和LRU的介绍，我们知道redis的设计有多优秀，不浪费一丁点内存！![53608999][]

**引用资料**

*  [Redis 作为 LRU Cache 的实现][Redis _ LRU Cache]
 *  [Redis LRU 实现策略][Redis LRU]
 *  [Redis 懒惰处理的细节][Redis]

[20190402231022700.png]: /images/20220225/eb0d69d24e3e403ea51fc8b1cb6587d2.png
[20190402225811808.png]: /images/20220225/f8d8febd69ba489baf630c5665277d83.png
[20190404220637277.png]: /images/20220225/e229b6cc4a7540048278cb4b16766c74.png
[20190404215617763.png]: /images/20220225/0ce582cb49944e0da2faf1d1bcd5faee.png
[20190404220839136.png]: /images/20220225/a02433319019483aaf2505c86e9f49b3.png
[53608999]: /images/20220225/8bb7ee5c705f4e20af8f048352736139.png
[Redis _ LRU Cache]: https://link.juejin.im/?target=https%3A%2F%2Fyq.aliyun.com%2Farticles%2F63034
[Redis LRU]: https://link.juejin.im/?target=https%3A%2F%2Fblog.csdn.net%2Fmysqldba23%2Farticle%2Fdetails%2F68482894
[Redis]: https://link.juejin.im/?target=https%3A%2F%2Fyq.aliyun.com%2Farticles%2F205504