作者：张仕华
LRU 是什么
LRU(least recently used) 是一种缓存置换算法。即在缓存有限的情况下，如果有新的数据需要加载进缓存，则需要将最不可能被继续访问的缓存剔除掉。因为缓存是否可能被访问到没法做预测，所以基于如下假设实现该算法:
如果一个 key 经常被访问，那么该 key 的 idle time 应该是最小的。
(但这个假设也是基于概率，并不是充要条件, 很明显,idle time 最小的, 甚至都不一定会被再次访问到)
这也就是 LRU 的实现思路。首先实现一个双向链表, 每次有一个 key 被访问之后，就把被访问的 key 放到链表的头部。当缓存不够时, 直接从尾部逐个摘除。
在这种假设下的实现方法很明显会有一个问题，例如 mysql 中执行如下一条语句:
select * from table_a;
如果 table_a 中有大量数据并且读取之后不会继续使用, 则 LRU 头部会被大量的 table_a 中的数据占据。这样会造成热点数据被逐出缓存从而导致大量的磁盘 io
mysql innodb 的 buffer pool 使用了一种改进的 lru 算法，大意是将 lru 链表分成两部分，一部分为 newlist, 一部分为 oldlist,newlist 是头部热点数据，oldlist 是非热点数据,oldlist 默认占整个 list 长度的 3 /8. 当初次加载一个 page 的时候，会首先放入 oldlist 的头部，再次访问时才会移动到 newlist. 具体参考如下文章:
https://dev.mysql.com/doc/ref…
而 Redis 整体上是一个大的 dict，如果实现一个双向链表需要在每个 key 上首先增加两个指针，需要 16 个字节，并且额外需要一个 list 结构体去存储该双向链表的头尾节点信息。Redis 作者认为这样实现不仅内存占用太大，而且可能导致性能降低。他认为既然 LRU 本来就是基于假设做出的算法，为什么不能模拟实现一个 LRU 呢。
Redis 中的实现
首先 Redis 并没有使用双向链表实现一个 lru 算法。具体实现方法接下来逐步介绍
首先看一下 robj 结构体 (Redis 整体上是一个大的 dict,key 是一个 string, 而 value 都会保存为一个 robj)
typedef struct redisObject {
…
unsigned lru:LRU_BITS; //LRU_BITS 为 24bit
…
} robj;
我们看到每个 robj 中都有一个 24bit 长度的 lru 字段，lru 字段里边保存的是一个时间戳。看下边的代码
robj *lookupKey(redisDb *db, robj *key, int flags) {
…
if (server.maxmemory_policy & MAXMEMORY_FLAG_LFU) {// 如果配置的是 lfu 方式，则更新 lfu
updateLFU(val);
} else {
val->lru = LRU_CLOCK();// 否则按 lru 方式更新
}
…
}
在 Redis 的 dict 中每次按 key 获取一个值的时候，都会调用 lookupKey 函数, 如果配置使用了 lru 模式, 该函数会更新 value 中的 lru 字段为当前秒级别的时间戳 (lfu 方式后文再描述)。
那么，虽然记录了每个 value 的时间戳，但是淘汰时总不能挨个遍历 dict 中的所有槽，逐个比较 lru 大小吧。
Redis 初始的实现算法很简单，随机从 dict 中取出五个 key, 淘汰一个 lru 字段值最小的。(随机选取的 key 是个可配置的参数 maxmemory-samples, 默认值为 5).
在 3.0 的时候，又改进了一版算法，首先第一次随机选取的 key 都会放入一个 pool 中 (pool 的大小为 16),pool 中的 key 是按 lru 大小顺序排列的。接下来每次随机选取的 keylru 值必须小于 pool 中最小的 lru 才会继续放入，直到将 pool 放满。放满之后，每次如果有新的 key 需要放入，需要将 pool 中 lru 最大的一个 key 取出。
淘汰的时候，直接从 pool 中选取一个 lru 最小的值然后将其淘汰。
我们知道 Redis 执行命令时首先会调用 processCommand 函数，在 processCommand 中会进行 key 的淘汰，代码如下:
int processCommmand(){
…
if (server.maxmemory && !server.lua_timedout) {
int out_of_memory = freeMemoryIfNeeded() == C_ERR;// 如果开启了 maxmemory 的限制, 则会调用 freeMemoryIfNeeded() 函数，该函数中进行缓存的淘汰
…
}
}
可以看到，lru 本身是基于概率的猜测，这个算法也是基于概率的猜测，也就是作者说的模拟 lru. 那么效果如何呢？作者做了个实验，如下图所示
首先加入 n 个 key 并顺序访问这 n 个 key, 之后加入 n / 2 个 key（假设 redis 中只能保存 n 个 key, 于是会有 n / 2 个 key 被逐出）. 上图中浅灰色为被逐出的 key, 淡蓝色是新增加的 key, 灰色的为最近被访问的 key(即不会被 lru 逐出的 key)
左上图为理想中的 lru 算法, 新增加的 key 和最近被访问的 key 都不应该被逐出。
可以看到,Redis2.8 当每次随机采样 5 个 key 时，新增加的 key 和最近访问的 key 都有一定概率被逐出
Redis3.0 增加了 pool 后效果好一些 (右下角的图)。当 Redis3.0 增加了 pool 并且将采样 key 增加到 10 个后，基本等同于理想中的 lru(虽然还是有一点差距)
如果继续增加采样的 key 或者 pool 的大小，作者发现很能进一步优化 lru 算法, 于是作者开始转换思路。
上文介绍了实现 lru 的一种思路, 即如果一个 key 经常被访问，那么该 key 的 idle time 应该是最小的。
那么能不能换一种思路呢。如果能够记录一个 key 被访问的次数, 那么经常被访问的 key 最有可能再次被访问到。这也就是 lfu(least frequently used), 访问次数最少的最应该被逐出。
lfu 的代码如下:
void updateLFU(robj *val) {
unsigned long counter = LFUDecrAndReturn(val);// 首先计算是否需要将 counter 衰减
counter = LFULogIncr(counter);// 根据上述返回的 counter 计算新的 counter
val->lru = (LFUGetTimeInMinutes()<<8) | counter; //robj 中的 lru 字段只有 24bits,lfu 复用该字段。高 16 位存储一个分钟数级别的时间戳，低 8 位存储访问计数
}
unsigned long LFUDecrAndReturn(robj *o) {
unsigned long ldt = o->lru >> 8;// 原来保存的时间戳
unsigned long counter = o->lru & 255; // 原来保存的 counter
unsigned long num_periods = server.lfu_decay_time ? LFUTimeElapsed(ldt) / server.lfu_decay_time : 0;
//server.lfu_decay_time 默认为 1, 每经过一分钟 counter 衰减 1
if (num_periods)
counter = (num_periods > counter) ? 0 : counter – num_periods;// 如果需要衰减, 则计算衰减后的值
return counter;
}
uint8_t LFULogIncr(uint8_t counter) {
if (counter == 255) return 255;//counter 最大只能存储到 255, 到达后不再增加
double r = (double)rand()/RAND_MAX;// 算一个随机的小数值
double baseval = counter – LFU_INIT_VAL;// 新加入的 key 初始 counter 设置为 LFU_INIT_VAL, 为 5. 不设置为 0 的原因是防止直接被逐出
if (baseval < 0) baseval = 0;
double p = 1.0/(baseval*server.lfu_log_factor+1);//server.lfu_log_facotr 默认为 10
if (r < p) counter++;// 可以看到,counter 越大, 则 p 越小，随机值 r 小于 p 的概率就越小。换言之,counter 增加起来会越来越缓慢
return counter;
}
unsigned long LFUGetTimeInMinutes(void) {
return (server.unixtime/60) & 65535;// 获取分钟级别的时间戳
}
LRU 本质上是一个概率计数器，称为 morris counter. 随着访问次数的增加,counter 的增加会越来越缓慢。如下是访问次数与 counter 值之间的关系
factor 即 server.lfu_log_facotr 配置值，默认为 10. 可以看到, 一个 key 访问一千万次以后 counter 值才会到达 255.factor 值越小, counter 越灵敏
lfu 随着分钟数对 counter 做衰减是基于一个原理: 过去被大量访问的 key 不一定现在仍然会被访问。相当于除了计数，给时间也增加了一定的权重。
淘汰时就很简单了，仍然是一个 pool, 随机选取 10 个 key,counter 最小的被淘汰
算法验证
redis-cli 提供了一个参数, 可以验证 lru 算法的效率。主要是通过验证 hits/miss 的比率，来判断淘汰算法是否有效。命中比率高说明确实淘汰了不会被经常访问的 key. 具体做法如下:
配置 redis lru 算法为 allkeys-lru
test ~/redis-5.0.0$./src/redis-cli -p 6380
127.0.0.1:6380> config set maxmemory 50m // 设置 redis 最大使用 50M 内存
OK
127.0.0.1:6380> config get maxmemory-policy
1) “maxmemory-policy”
2) “noeviction”
127.0.0.1:6380> config set maxmemory-policy allkeys-lru// 设置 lru 算法为 allkeys-lru
OK
执行 redis-cli –lru-test 验证命中率
./src/redis-cli -p 6380 –lru-test 1000000// 模拟 100 万个 key
通过 info 查看使用的内存和被逐出的 keys
…
# Memory
used_memory:50001216
…
evicted_keys:115092
…
查看 lru-test 的输出
131250 Gets/sec | Hits: 124113 (94.56%) | Misses: 7137 (5.44%)
132250 Gets/sec | Hits: 125091 (94.59%) | Misses: 7159 (5.41%)
131250 Gets/sec | Hits: 124027 (94.50%) | Misses: 7223 (5.50%)
133000 Gets/sec | Hits: 125855 (94.63%) | Misses: 7145 (5.37%)
136250 Gets/sec | Hits: 128882 (94.59%) | Misses: 7368 (5.41%)
139750 Gets/sec | Hits: 132231 (94.62%) | Misses: 7519 (5.38%)
136000 Gets/sec | Hits: 128702 (94.63%) | Misses: 7298 (5.37%)
134500 Gets/sec | Hits: 127374 (94.70%) | Misses: 7126 (5.30%)
134750 Gets/sec | Hits: 127427 (94.57%) | Misses: 7323 (5.43%)
134250 Gets/sec | Hits: 127004 (94.60%) | Misses: 7246 (5.40%)
138500 Gets/sec | Hits: 131019 (94.60%) | Misses: 7481 (5.40%)
130000 Gets/sec | Hits: 122918 (94.55%) | Misses: 7082 (5.45%)
126500 Gets/sec | Hits: 119646 (94.58%) | Misses: 6854 (5.42%)
132750 Gets/sec | Hits: 125672 (94.67%) | Misses: 7078 (5.33%)
136000 Gets/sec | Hits: 128563 (94.53%) | Misses: 7437 (5.47%)
132500 Gets/sec | Hits: 125450 (94.68%) | Misses: 7050 (5.32%)
132250 Gets/sec | Hits: 125234 (94.69%) | Misses: 7016 (5.31%)
133000 Gets/sec | Hits: 125761 (94.56%) | Misses: 7239 (5.44%)
134750 Gets/sec | Hits: 127431 (94.57%) | Misses: 7319 (5.43%)
130750 Gets/sec | Hits: 123707 (94.61%) | Misses: 7043 (5.39%)
133500 Gets/sec | Hits: 126195 (94.53%) | Misses: 7305 (5.47%)
大概有 5%-5.5% 之间的 miss 概率。我们将 lru 策略切换为 allkeys-lfu，再次实验
结果如下:
131250 Gets/sec | Hits: 124480 (94.84%) | Misses: 6770 (5.16%)
134750 Gets/sec | Hits: 127926 (94.94%) | Misses: 6824 (5.06%)
130000 Gets/sec | Hits: 123458 (94.97%) | Misses: 6542 (5.03%)
127750 Gets/sec | Hits: 121231 (94.90%) | Misses: 6519 (5.10%)
130500 Gets/sec | Hits: 123958 (94.99%) | Misses: 6542 (5.01%)
130500 Gets/sec | Hits: 123935 (94.97%) | Misses: 6565 (5.03%)
131250 Gets/sec | Hits: 124622 (94.95%) | Misses: 6628 (5.05%)
131250 Gets/sec | Hits: 124618 (94.95%) | Misses: 6632 (5.05%)
128000 Gets/sec | Hits: 121315 (94.78%) | Misses: 6685 (5.22%)
129000 Gets/sec | Hits: 122585 (95.03%) | Misses: 6415 (4.97%)
132000 Gets/sec | Hits: 125277 (94.91%) | Misses: 6723 (5.09%)
134000 Gets/sec | Hits: 127329 (95.02%) | Misses: 6671 (4.98%)
131750 Gets/sec | Hits: 125258 (95.07%) | Misses: 6492 (4.93%)
136000 Gets/sec | Hits: 129207 (95.01%) | Misses: 6793 (4.99%)
135500 Gets/sec | Hits: 128659 (94.95%) | Misses: 6841 (5.05%)
133750 Gets/sec | Hits: 126995 (94.95%) | Misses: 6755 (5.05%)
131250 Gets/sec | Hits: 124680 (94.99%) | Misses: 6570 (5.01%)
129750 Gets/sec | Hits: 123408 (95.11%) | Misses: 6342 (4.89%)
130500 Gets/sec | Hits: 124043 (95.05%) | Misses: 6457 (4.95%)
%5 左右的 miss 率，在这个测试下,lfu 比 lru 的预测准确率略微高一些。
在实际生产环境中, 不同的 redis 访问模式需要配置不同的 lru 策略，然后可以通过 lru test 工具验证效果。
参考链接
1.http://antirez.com/news/109
2.https://redis.io/topics/lru-c…