LRU背景介绍
LRU，全称Least Recently Used-最近最少使用，是一种内存淘汰算法，笔者最早接触到这个算法是在本科操作系统的课程上，讲到操作系统的虚拟内存页面置换的时候提到的。
这个经典内存淘汰算法也被很多其它地方使用，经常作为缓存的淘汰策略，缓存作为一种提升查询速度的手段，本身就是为了将持久化到硬盘上的数据中的热点部分加载到读取速度更快的内存中（局部性原理），而内存肯定是加载不了磁盘中的全部数据的，那就涉及到如果加载到缓存时发现内存满了怎么办？需要从缓存中淘汰掉谁？于是很自然的会想到淘汰内存中最冷门的记录*，于是LRU算法定义了标记跟踪到这个最冷门数据的方法。
手机后台也是一种LRU
操作系统中的LRU
虚拟内存
操作系统作为用户应用与硬件设备之间的代理人，有着屏蔽底层不同硬件逻辑的职责，例如内存条，
内存条
对于用户应用程序来说，不应该由它来操心运行在的这台机器到底查了几个内存条、啥型号的、有多大内存，也不需要关注会不会读到其它应用的内存信息、会不会写到人家内存上导致数据错乱。而是由操作系统封装了这一切，操作系统的封装方式就是虚拟内存。
操作系统的这种封装底层硬件、为上层用户应用提供API接口的思想也是计算机领域的核心思想，即分层思想，每一层只做当前这一层的封装功能，屏蔽掉底层的异构特性后为上一层提供抽象的统一的API接口，学会抽象是程序员的核心思维，无论是操作系统、TCP/IP网络架构、Java的Spring容器，都是这种思想的体现。
操作系统的虚拟内存通过页表为硬件和用户应用之间提供了固定内存大小和隔离不同进程内存空间的功能，本文重点讨论固定内存大小的实现。操作系统屏蔽了底层硬件内存的大小，例如对于32位操作系统来说，不论你用多少G的内存条，进程可用的内存空间都是4G（用户态+核心态），如果实际内存条根本没有这么大的时候，就只能在内存条中存放部分数据，其它的内存数据存储在磁盘中，这就涉及到谁留在内存，谁又该放在磁盘上的经典哲学问题。
虚拟内存
虚拟内存与LRU
操作系统往往采用的就是LRU算法判断那些经常被访问的热点数据，把它们留在内存中，而将最近最少使用的内存数据淘汰到磁盘上。龙龙的奇妙比喻：想象你是一个皇帝，操作系统是一个太监，太监总管根据你翻牌子的历史行为预判你今晚找哪位嫔妃侍寝，后宫佳丽三千，皇上选择的耐心有限，于是太监总管将最近最少翻牌子的嫔妃直接移出牌子池了。
翻牌子
其它页面置换（淘汰）算法
- 最佳置换算法（OPT），太监总管能预知未来，知道哪个嫔妃将来永远不会被宠幸，直接将她们淘汰，但这是不可能的，所以作为淘汰算法的评价标准
- 先进先出置换算法（FIFO），太监总管比较耿直，永远公平公正，严格按照嫔妃的先来后到放牌子
- 最少使用（LFU）置换算法，LRU关注每个嫔妃最后被临幸的时间，LFU关注每个嫔妃历史被宠幸的频率，例如华妃历史上天天被临幸，但是刚好最近一周不被临幸了，对于LRU来说可能会被淘汰，对于LFU来说可能会保留；甄嬛早期天天不被临幸，但是最近一周被皇帝看上了，如果太监总管使用LRU-甄嬛必定是放到第一位，如果使用LFU-甄嬛这个新宠可能还是上不了牌子池
emmm...所以显然LRU更得圣心啊。。。
redis与LRU
redis的过期时间淘汰方式
一般情况中redis作为缓存是通过Expire KEY_NAME TIME_IN_SECONDS命令给key设置一个固定的淘汰时间，key到期后redis通过惰性删除或定期删除将过期的key从内存中清理掉。
redis的惰性删除与定期删除：
redis的缓存过期处理策略有三种实现方案：
- 定时删除，每当给一个key设置expire的时候，都启动一个定时器，在key过期的时候立刻删除。优点是节省内存，到期立刻清理；缺点是浪费CPU时间做清理工作，创建了大量定时器，性能影响严重
- 惰性删除，每次get key的时候看看是否过期。优点和1刚好相反，节省CPU时间；缺点是可能有长期不读的key一直赖在内存，浪费内存（内存泄漏）
- 定期删除，1和2的方案折衷，自如阿姨定期打扫一次房间，1和2的优缺点都有
最终redis采用的是惰性删除和定期删除的结合。
redis的LRU
以上清理都是发生在redis内存充足的时候，对于已经过期的key进行清理。
redis作为一种数据缓存层而存在的时候，也会遇到上文中操作系统的场景，当越来越多数据被缓存时，如果内存不够用了怎么办，redis提供了六种淘汰方式
config set maxmemory-policy volatile-lru
maxmemory-policy 六种方式
- volatile-lru：只对设置了过期时间的key进行LRU（默认值）
- allkeys-lru ： 删除lru算法的key
- volatile-random：随机删除即将过期key
- allkeys-random：随机删除
- volatile-ttl ： 删除即将过期的
- noeviction ： 永不过期，返回错误
笔者使用模块中的LRU
笔者工作中使用的模块可以理解为封装了各个数据源的查询、筛选、分页、排序功能，对外暴露出简单的select xxx from view where ... 的语句，可以理解为对MySQL view视图概念的模仿，对外只提供只读的功能。因而该模块也对查询操作进行了内存缓存，而缓存的淘汰算法同样是采用了经典的LRU算法。
笔者使用模块中的LRU
LRU的实现——双向链表+哈希表
LRU cache作为一种cache，put/get操作的时间复杂度要求是O(1)，因此需要采用哈希表来存储KV的映射关系。
同时需要有一种数据结构，支持将最近最新访问过的节点排在最前面 && 将最近最少访问的节点移除出去，当然可以采用在Node[]数组中记录Node.lastestVisitTime时间戳，然后移除的时候排个序，这样的话每次排序都需要O(logn)的快排耗时，为保证内存淘汰的时间复杂度也为O(1)，需要采用双向链表，讲最新访问的节点放在表头，同时将表尾的节点踢出去
综上，LRU的实现需要将哈希表与双向链表的数据结构进行组合，通过冗余的一层数据结构来优化put/get的性能。
LRU cache的结构图如下
哈希表+双向链表
LRU cache的get操作流程动图演示
LRU cache的get操作流程动图演示
LRU cache的put操作流程动图演示
LRU cache的put操作流程动图演示
LRU cache的伪代码如下
class LRUCached:
哈希表 # key -> Node(key, value)
双向链表 # Node -> Node -> Node
capacity = 10 # 容量，超过大小按照LRU算法开始淘汰
def get(key):
if(key 不存在):
return -1
else:
将数据挪到双向链表的表头 # 调用一次put(key, value)
return 哈希表.get(key).value
def put(key, value):
Node node = new Node()
if(key 已存在):
双向链表.remove(哈希.get(key))
双向链表.addFirst(node)
else: # key不存在
哈希表.put(key, value)
双向链表.addFirst(node)
if(双向链表.size > capacity):
双向链表.removeLast()
哈希表.remove(双向链表的lastNode.key)
网友评论