楔子
通过在后端服务和 MySQL 之间引入一层 Redis，可以极大地提升服务的响应速度。具体做法就是将数据放入 Redis 中，后续请求到来时，直接访问缓存，而不是数据库。
那么问题来了，我们应该往缓存里放多少数据，如果 MySQL 存了 1T 的数据，难道这 1T 的数据都要放到缓存中吗？显然不是的，原因有两个：
- 1）内存价格昂贵：1T 内存需要 3.5万元，而 1T硬盘只需要 1千元；
- 2）性价比不高：数据是有局部性的，1T 数据不可能时刻被访问，根据二八原则，百分之八十的请求只会访问百分之二十的数据（根据实际情况，这个百分比可能更大、也可能更小）；
所以缓存的大小肯定要有上限，随着时间的推移，内存总有被写满的时候。那么问题来了，Redis 把内存用完了怎么办？
内存用完了怎么办？
内存用完指的是 Redis 使用的运行内存超过了 Redis 设置的最大内存，该值可以通过参数 maxmemory 进行设置。
> config get maxmemory 1) "maxmemory" 2) "0"
返回的结果为 0，表示没有内存大小限制，直到耗尽机器中所有的内存为止，这是 Redis 服务端在 64 位操作系统下的默认值（32 位操作系统默认可使用最大内存为 3GB）。
如果你不想给 Redis 整个节点的内存，那么可以通过 maxmemory 进行设置，比如设置为 4GB。这样 Redis 可使用的最大内存就是 4GB，具体设置多少视情况而定，一般是总数据量的百分之15~30。
如果 Redis 所用内存达到了 maxmemory，接下来要怎么办呢？没错，显然要淘汰一部分 key，把空间腾出来，此时就会触发 Redis 的内存淘汰策略：
最大内存的检测源码位于 server.c 中，核心代码如下：
int processCommand(client *c) { // 最大内存检测 if (server.maxmemory && !server.lua_timedout) { int out_of_memory = freeMemoryIfNeededAndSafe() == C_ERR; if (server.current_client == NULL) return C_ERR; if (out_of_memory && (c->cmd->flags & CMD_DENYOOM || (c->flags & CLIENT_MULTI && c->cmd->proc != execCommand))) { flagTransaction(c); addReply(c, shared.oomerr); return C_OK; } } // 忽略其他代码 }
如果发现内存不够了，那么就要淘汰一部分数据，而淘汰策略有 8 种，可以使用 config get maxmemory-policy 命令来查看，如下所示：
> config get maxmemory-policy 1) "maxmemory-policy" 2) "noeviction"
结果显示 Redis 服务端默认采用的是 noeviction 策略，此策略表示当使用的内存超过最大限制时，不淘汰任何数据，但新增操作会报错。此策略为 Redis 默认的内存淘汰策略，此值可通过修改 redis.conf 文件进行修改。
关于淘汰策略，在前面介绍 Redis 配置文件的时候说过，总共有以下 8 种：
Redis 的内存最大值和内存淘汰策略都可以通过配置文件，或者命令行工具进行修改。
内存淘汰策略决定了内存淘汰算法，从以上八种内存淘汰策略可以看出，虽然它们的具体实现细节不同，但主要的淘汰算法有两种：LRU 算法和 LFU 算法，我们分别介绍一下。
LRU 算法实现
LRU 全称是 Least Recently Used，翻译为最近最少使用，是一种常用的页面置换算法，选择最近最少使用的页面予以淘汰。它的实现需要基于链表结构，链表中的元素按照操作顺序从前往后排列，最新操作的键会被移动到表头，当需要内存淘汰时，只需要删除链表尾部的元素即可。
当 LRU 链表的数据被访问时，它要移动到链表的头部，因为被访问了。然后在写入新数据 15 时，发现链表已经没有空间了，那么这时候 LRU 算法要做两件事：
- 1）15 是新数据，要写入 LRU 链表的头部；
- 2）为了维护 LRU 链表的长度，将尾部的数据 5 删除；
所以 LRU 算法的思想非常朴素，谁被访问了谁就跑到链表的头部，而刚刚写入的数据很有可能再次访问，于是也会把它写到链表的头部。随着时间的推移，链表尾部的数据就是最近最少访问的数据，在缓存满了的时候就优先删除它。
当前这个 LRU 算法是最基本、也是最简单的，而 MySQL 的 Buffer Pool 里面也有 LRU 链表，但它的实现要复杂一些。因为 MySQL 将 LRU 链表划分成两个区域，分别是热数据区域和冷数据区域。我们说新写入的数据一定是要被访问的，所以会放到 LRU 链表的头部，但如果该数据只有在写入的时候才会访问、之后就再也不访问了，该怎么办？
所以 MySQL 在加载数据的时候，会先放到 LRU 链表的冷数据区域中，如果 1s 后又被访问了，再移动 LRU 链表（热数据区域）的头部。然后在淘汰数据的时候，只需要从冷数据区域的尾部开始淘汰即可。
因为 MySQL 存在着预读机制，所以考虑的情况稍微多一些。总之这种冷热数据隔离的思想，也值得我们在工作中借鉴，尽可能将冷数据和热数据隔离开，避免冷数据影响热数据访问。
有兴趣的话，可以自己手动实现一个简单版的 LRU 链表，或者能将热数据和冷数据隔离开的高级版的 LRU 链表。
但对于 Redis 而言，它使用的其实是近似 LRU 算法。因为 LRU 算法在实现时需要使用链表管理所有的缓存数据，这会带来额外的空间开销；而且当数据被大量访问时，它们要频繁地在链表上移动，这会影响 Redis 的性能。所以在 Redis 中，LRU 算法被进行了简化，以减轻数据淘汰对性能的影响。
具体做法如下，首先 Redis 会记录每个数据最近一次访问的时间戳，而 Redis 所有的数据都是一个 redisObject，这个时间戳由内部的 lru 字段负责保存。
#define LRU_BITS 24 typedef struct redisObject { unsigned type:4; unsigned encoding:4; unsigned lru:LRU_BITS; int refcount; void *ptr; } robj;
我们前面在介绍 RedisObject 的时候，少说了两个字段，分别是 lru 和 refcount。refcount 保存的是引用计数，而 lru 则保存最近一次访问的时间戳。
然后 Redis 在淘汰数据时，第一次会随机选出 N 个数据，把它们作为一个候选集合。接着会比较这 N 个数据的 lru 字段，把字段值最小的数据从缓存中淘汰出去（每次淘汰一个）。
N 由配置参数 maxmemory-samples 决定，默认是 5 个
当需要再次淘汰时，Redis 会继续挑选数据进入第一次淘汰时创建的候选集合，如果候选集合的个数达到了 maxmemory-samples，那么继续将 lru 最小数据淘汰掉。这样一来，Redis 就不用为所有的数据维护一个大链表，也不用每次访问数据时都移动链表项，从而提升缓存的性能。
- 如果你的数据有明显的冷热区分，那么优先使用 allkeys-lru，这样可以充分利用 LRU 算法的优势，最近最常访问的数据留在缓存中，提升程序的访问性能；
- 但如果业务数据的访问频率差异不大，没有明显的冷热区分，那么建议选择 allkeys-random，随机选择淘汰的数据即可。
- 如果你的业务中有置顶需求，比如置顶一个回复、置顶一篇文章等等，那么可以使用 volatile-lru 策略，同时不给这些置顶数据设置过期时间。这样一来需要置顶的数据就永远不会被删除，而其它数据则会在过期时根据 LRU 规则进行筛选；
以上就是 LRU 算法，但它存在一个问题。首先它表示最近最少使用，假设有一个很久都没有使用的数据，突然被访问了一次，那么它就要被移动到链表的头部。但很明显，它是访问次数最少的数据，只不过最近突然被访问了一次，所以不会被淘汰。
所以 LRU 算法没有考虑到访问频率的影响，不管数据被访问的频率如何，哪怕它很久都没被访问了。但只要它被访问，就会被移动到链表的头部。所以这对那些访问频率高的数据是不公平的，为此 Redis 在 4.0 的时候引入了 LFU 算法。
LFU 算法
LFU 全称是 Least Frequently Used，翻译为最不常用的，该算法是根据总访问次数来淘汰数据的，它的核心思想是"如果数据过去被访问多次，那么将来被访问的频率也更高"。LFU 解决了偶尔被访问一次之后，数据就不会被淘汰的问题，相比于 LRU 算法也更合理一些。
redisObject 内部有一个 lru 字段（24 个位），但也可以用于 LFU 算法，其中前 16 位存储最近一次的访问时间，后 8 位用来存储访问次数，值越小代表访问频率越低，越容易被淘汰。
所以 LRU 和 LFU 都是一种页面置换算法：
- LRU 看的是数据最后一次访问到发生替换时的时间长短，时间越长，越优先被替换（或者说淘汰）；
- LFU 看的是数据在一段时间内的访问频率（次数），访问频率越低，越优先被淘汰；
至于 Redis 到底采用的是近 LRU 算法还是 LFU 算法，完全取决于内存淘汰策略的类型配置。
如何处理已过期的数据？
介绍完 Redis 内存用完之后的内存淘汰策略，我们再来看看 Redis 在键值过期之后的数据处理。这两者是不同的，前者是在内存满了的时候，对数据进行清理，算是异常情况；而后者是对键值过期之后的数据处理，算是正常情况下的数据清理。
我们知道 Redis 维护了一个全局的哈希表，用来存储所有的键值对；但对于那些设置了过期时间的数据，Redis 会存在另一个哈希表中。
源码中的 expires 就是 Redis 为设置了过期时间的键值对所维护的字典，设置了过期时间的键值对，会存到该字典中。我们使用设置过期时间的命令来举个例子，命令如下：
> set name hanser ex 30 OK
过期时间除了上面那种方式之外，还可以使用 expire 命令：
# 先设置，此时默认永不过期 > set age 28 OK # 添加一个过期时间 > expire age 20 (integer) 1
当我们获取键值对时，Redis 会先判断这个键是否存在于过期字典（expires）中，如果没有的话，表示没有设置过期时间（永不过期），于是会从全局字典（dict）直接返回数据。
如果键值在过期字典中，那么会判断当前时间是否小于过期时间，如果是，则说明没有过期，会正常返回；反之则表示数据已过期，于是会删除该键值对并返回 nil。执行流程如下：
这是键值数据的获取流程，同时也是过期键值的判断和删除流程，而删除也是有策略的。
删除策略
Redis 在删除一个 key 的时候有三种策略：定时删除、惰性删除、定期删除。
1）定时删除
在设置键值对的过期时间时，创建一个定时事件，当过期时间到达时，由事件处理器自动执行删除操作。
- 优点：保证内存可以被尽快地释放；
- 缺点：在 Redis 高负载的情况下、或者有大量过期键需要同时处理时，会造成 Redis 服务端卡顿，影响主业务执行；
2）惰性删除
从上面 Redis 访问键值对的流程图也能看出，Redis 不主动删除已经过期的键，每次从数据库获取键值对的时候会判断是否过期，如果过期才删除，并返回 nil。
- 优点：因为每次访问时，才会判断键是否过期，所以此策略只会使用很少的系统资源；
- 缺点：系统占用空间删除不及时，导致空间利用率降低，造成了一定的空间浪费；
Redis 中惰性删除的源码位于 src/db.c 文件的 expireIfNeeded 方法中，源码如下：
int expireIfNeeded(redisDb *db, robj *key) { // 判断键是否过期 if (!keyIsExpired(db,key)) return 0; if (server.masterhost != NULL) return 1; /* 删除过期键 */ // 增加过期键个数 server.stat_expiredkeys++; // 传播键过期的消息 propagateExpire(db,key,server.lazyfree_lazy_expire); notifyKeyspaceEvent(NOTIFY_EXPIRED, "expired",key,db->id); // server.lazyfree_lazy_expire // 为 1 表示异步删除（懒空间释放），反之同步删除 return server.lazyfree_lazy_expire ? dbAsyncDelete(db,key) : dbSyncDelete(db,key); } // 判断键是否过期 int keyIsExpired(redisDb *db, robj *key) { mstime_t when = getExpire(db,key); if (when < 0) return 0; if (server.loading) return 0; mstime_t now = server.lua_caller ? server.lua_time_start : mstime(); return now > when; } // 获取键的过期时间 long long getExpire(redisDb *db, robj *key) { dictEntry *de; /* No expire? return ASAP */ if (dictSize(db->expires) == 0 || (de = dictFind(db->expires,key->ptr)) == NULL) return -1; serverAssertWithInfo(NULL,key, dictFind(db->dict,key->ptr) != NULL); return dictGetSignedIntegerVal(de); }
所有对数据库的读写命令在执行之前，都会调用 expireIfNeeded 方法判断键值是否过期，过期则会从数据库中删除，反之则不做任何处理。
以上就是惰性删除。
3）定期删除
每隔一段时间检查一次数据库的过期哈希表（expires），随机删除一些过期键。Redis 默认每秒进行 10 次过期扫描，此配置可通过 redis.conf 中的 hz 参数进行配置，默认值是 hz 10。但需要注意的是：Redis 每次扫描并不是遍历过期字典中的所有键，而是采用随机抽取判断并删除过期键的方式。
定期删除流程如下：
- 1）从过期字典中随机取出 20 个 key；
- 2）删除这 20 个 key 里面过期的 key；
- 3）如果过期 key 的比例超过 25% ，重复步骤 1，否则结束；
同时为了保证过期扫描不会出现循环过度，导致线程卡死现象，算法还增加了扫描时间的上限，默认不会超过 25ms。定期删除执行流程，如下图所示：
- 优点：通过限制删除操作的时长和频率，来减少删除操作对 Redis 主业务的影响，同时因删除一部分过期的数据也能减少过期键值对造成的无效空间占用；
- 缺点：系统占用空间删除不及时，导致空间利用率降低，造成了一定的空间浪费；
Redis 中定期删除的核心源码在 src/expire.c 文件下的 activeExpireCycle 方法中。该方法在规定的时间内，分多次遍历各个数据库，从过期字典中随机检查一部分键的过期时间，删除其中的过期键。
如果只使用惰性删除会导致删除数据不及时，造成一定的空间浪费，又因为 Redis 本身是单线程执行的，如果因为删除操作而影响主业务的执行就得不偿失了。为此 Redis 需要制定多个过期删除策略：惰性删除加定期删除，来保证 Redis 能够及时并高效地删除 Redis 中的过期键。
小结
本次我们就介绍了，当内存满了 Redis 会采用的几种淘汰策略，总共是 8 种，需要根据实际情况灵活配置。
还有就是在删除过期 key 时，所使用的几种删除策略。定时删除比较消耗系统性能，惰性删除不能及时地清理过期数据从而导致了一定的空间浪费，为了兼顾存储空间和性能，Redis 采用了惰性删除加定期删除的组合删除策略。
本文参考自：
- 极客时间蒋德钧：《Redis 核心技术与实战》
