我们都知道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 淘汰生效'