验证Redis中的LRU算法

我们都知道Redis是一款内存型的KV数据库(为了便于理解,暂时先忽略掉Redis数据持久化的AOF和RDB)。
但是当内存即将被塞满的时候,如何决定哪些数据被淘汰是一种非常重要的决策。

一、LRU算法的简单理解

Redis里使用的一种淘汰算法LRU是一种链表型的淘汰策略。
一个值被加入到Redis中,就会进入到这个单链表里。

注:下文即将讲的LRU淘汰算法不是实际使用的LRU,图片演示仅供理解用途。
假设这个Redis的空间可以存放5个值。
第一步操作插入一个10,链表内容如下图


第二部操作插入一个11,链表内容如下图


第三步操作获取10,链表内容如下图


第四步操作插入一个50,链表内容如下图


第五步操作获取10,链表内容如下图


第六步操作插入20,链表内容如下图


第七步操作插入30,链表内容如下图


第八步操作获取10,链表内容如下图


第九步操作获取6,链表内容如下图

到第九步的时候你会发现,原本排在第链表第五位的11退出了链表,被淘汰了。

 

二、 LRU验证

从算法可以发现,我们不断地添加元素,当元素的体积达到内存的极限的时候,LRU算法就能被感受到了。
这里采用的验证方式是,相同val值,不断堆积

伪代码如下: