LRU在redis中的应用

1.LRU

在操作系统中,考虑到内存有限,需要将已经使用过的空间置换出来,LRU就是一个页面置换算法,淘汰掉不经常使用的页面。

下面事LRU的置换过程,使用的是FIFO。

2.基于 HashMap 和 双向链表实现 LRU

下面展示了,预设大小是 3 的,LRU存储的在存储和访问过程中的变化。为了简化图复杂度,图中没有展示 HashMap部分的变化,仅仅演示了上图 LRU 双向链表的变化。我们对这个LRU缓存的操作序列如下:

save(“key1”, 7)

save(“key2”, 0)

save(“key3”, 1)

save(“key4”, 2)

get(“key2”)

save(“key5”, 3)

get(“key2”)

save(“key6”, 4)

相应的 LRU 双向链表部分变化如下:

核心操作的步骤:

  1. save(key, value),首先在 HashMap 找到 Key 对应的节点,如果节点存在,更新节点的值,并把这个节点移动队头。如果不存在,需要构造新的节点,并且尝试把节点塞到队头,如果LRU空间不足,则通过 tail 淘汰掉队尾的节点,同时在 HashMap 中移除 Key。
  2. get(key),通过 HashMap 找到 LRU 链表节点,因为根据LRU 原理,这个节点是最新访问的,所以要把节点插入到队头,然后返回缓存的值。

3.Redis的LRU实现

如果按照HashMap和双向链表实现,需要额外的存储存放 next 和 prev 指针,牺牲比较大的存储空间,显然是不划算的。所以Redis采用了一个近似的做法,就是随机取出若干个key,然后按照访问时间排序后,淘汰掉最不经常使用的,

参考文献:https://zhuanlan.zhihu.com/p/34133067

全部评论

相关推荐

我见java多妩媚:大外包
点赞 评论 收藏
分享
小火柴燃烧吧:接啊,接了之后反手在咸鱼找个大学生搞一下,量大从优
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务