宜人贷浅析去除冗余和繁杂的内存淘汰算法——LRU

LRU的全称为Least Recently Used，它是一种内存淘汰算法，表示当内存不够时，将内存中最久没使用的数据清理掉。LRU算法常用于缓存的淘汰策略。

宜人贷认为，LRU算法基于以下这种假设：长期不被使用的数据，在未来被用到的几率也不大。所以，当数据所占内存达到一定阈值时，要移除掉最近最少使用的数据，去除冗余和繁杂。

一般情况下，LRU的实现思路容易理解。用户可以从数组长度限制，满足有序性，按时间排序，快速获取时间相关性，key-value性质数据等关键点来达到目的。

在宜人贷看来，LRU算法的实现使用了一个hash表和一个双向链表，hash表中存储了key值对应的具体node节点，node节点之间组成了一个双向链表，这样能提高查询效率，也能提高操作效率。

在这里，宜人贷提醒大家，如果一个不是经常使用的数据，偶尔或者周期性的被使用，那么该数据会被加到LRU链表头部，而这种不经常使用的数据，放在链表头部，占用了空间;一直等到LRU淘汰完，才能被剔除链表；当这种数据一次性过多时，那么链表数据都是这种无用的数据，将会导致缓存命中率低下，从而影响系统性能。

从应用方面看，LRU是为虚拟页式存储管理服务的。近年来，关于操作系统的内存管理和如何节省利用容量不大的内存为最多的进程提供资源，是计算机研究的重要方向。而内存的虚拟存储管理，是目前比较通用和成功的方式。

据宜人贷了解，在内存有限的情况下，扩展一部分外存作为虚拟内存，真正的内存只是存储当前运行时所用得到信息。如此一来，可以极大地扩充内存的功能，提高计算机的并发 度。

深挖虚拟页式存储管理，则是将进程所需空间划分为多个页面，内存中只存放当前所需页面，其余页面放入外存的管理方式。宜人贷希望将来，能看到LRU为虚拟页式存储管理作出更深层次的服务。