深入解析Redis的LRU与LFU算法实现 _Redis

文章插图
一、前言redis是一款基于内存的高性能NoSQL数据库，数据都缓存在内存里，这使得Redis可以每秒轻松地处理数万的读写请求。
相对于磁盘的容量，内存的空间一般都是有限的，为了避免Redis耗尽宿主机的内存空间， Redis内部实现了一套复杂的缓存淘汰策略来管控内存使用量。
Redis 4.0版本开始就提供了8种内存淘汰策略，其中4种都是基于LRU或LFU算法实现的，本文就这两种算法的Redis实现进行了详细的介绍，并阐述其优劣特性。
二、Redis的LRU实现在介绍Redis LRU算法实现之前，我们先简单介绍一下原生的LRU算法。
2.1 LRU算法原理LRU（The Least Recently Used）是最经典的一款缓存淘汰算法，其原理是：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很低，当数据所占据的空间达到一定阈值时，这个最少被访问的数据将被淘汰掉。
如今， LRU算法广泛应用在诸多系统内，例如linux内核页表交换， MySQL Buffer Pool缓存页替换，以及Redis数据淘汰策略。
以下是一个LRU算法示意图：

文章插图

向一个缓存空间依次插入三个数据A/B/C ，填满了缓存空间；
读取数据A一次，按照访问时间排序，数据A被移动到缓存头部；
插入数据D的时候，由于缓存空间已满，触发了LRU的淘汰策略，数据B被移出，缓存空间只保留了D/A/C 。

一般而言， LRU算法的数据结构不会如示意图那样，仅使用简单的队列或链表去缓存数据，而是会采用Hash表 + 双向链表的结构，利用Hash表确保数据查找的时间复杂度是O(1) ，双向链表又可以使数据插入/删除等操作也是O(1) 。

文章插图

如果你很熟悉Redis的数据类型，你会发现这个LRU的数据结构与ZSET类型OBJ_ENCODING
_SKIPLIST编码结构相似，只是LRU数据排序方式更简单一些。
2.2 Redis LRU算法实现按照官方文档的介绍， Redis所实现的是一种近似的LRU算法，每次随机选取一批数据进行LRU淘汰，而不是针对所有的数据，通过牺牲部分准确率来提高LRU算法的执行效率。
Redis内部只使用Hash表缓存了数据，并没有创建一个专门针对LRU算法的双向链表，之所以这样处理也是因为以下几个原因：

筛选规则， Redis是随机抽取一批数据去按照淘汰策略排序，不再需要对所有数据排序；
性能问题，每次数据访问都可能涉及数据移位，性能会有少许损失；
内存问题， Redis对内存的使用一向很“抠门” ，数据结构都很精简，尽量不使用复杂的数据结构管理数据；
策略配置，如果线上Redis实例动态修改淘汰策略会触发全部数据的结构性改变，这个Redis系统无法承受的。

redisObject是Redis核心的底层数据结构，成员变量lru字段用于记录了此key最近一次被访问的LRU时钟(server.lruclock) ，每次Key被访问或修改都会引起lru字段的更新。

#define LRU_BITS 24typedef struct redisObject {unsigned type:4;unsigned encoding:4;unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or* LFU data (least significant 8 bits frequency* and most significant 16 bits access time). */int refcount;void *ptr;} robj;

默认的LRU时钟单位是秒，可以修改LRU_CLOCK_RESOLUTION宏来改变单位， LRU时钟更新的频率也和server.hz参数有关。

unsigned int LRU_CLOCK(void) {unsigned int lruclock;if (1000/server.hz <= LRU_CLOCK_RESOLUTION) {atomicGet(server.lruclock,lruclock);} else {lruclock = getLRUClock();}return lruclock;}

由于lru字段仅占用了24bit的空间，按秒为单位也只能存储194天，所以可能会出现一个意想不到的结果，即间隔194天访问Key后标记的时间戳一样， Redis LRU淘汰策略局部失效。