验证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值，不断堆积

伪代码如下：

oldDBDize = newDBSize = DBSize = 0
while true {
	set(DBSize, 1)  // 设置一个key-val
	DBSize += 1		// DBSize + 1  这里记录的是总数

	newDBSize = getDBSize() // 获取当前的DBSize
	if oldDBDize == newDBSize { // 判断set之后的DBSize 与 set之前的DBSize大小是否相同
		break	// 相同跳出
	}
	oldDBDize = newDBSize // 记录DBSize结果
}

print 'LRU 淘汰生效'