LRU算法的优化

常见的LRU算法的实现方式是：一条双链表+HashMap。旧文LRU算法的实现（Python版）和Go实现LRU算法、LRU算法的实现（Java版）讨论和实现过LRU算法。采用的思路都是一条双链表以时间戳大小排序组织排序数据，HashMap快速定位根据键指定的数据。

忽略实现的具体编程语言，这样的实现思路在特性场景下是有问题的。今天就来讨论如何优化LRU算法。谈优化一定要知道问题所在，有些问题是全局的，有些问题是在特殊场景下出现。

LRU算法的问题

首先我们来指出这种实现的问题：

（1）在某些情况下，应用进程一次过加载大量的数据到内存中，这些数据会进入LRU缓存，但问题是，加载完一次使用完一次后进程就不在使用了这些数据。由于缓存有限，这些数据会污染原来缓存中有效的数据。思考下面的场景

考虑下一个具体的场景：MySQL进行范围查找，一次过把大量的数据加载到内存中，并只使用了一次。假设它使用的是上述的LRU算法。那么，这次插在的数据会污染原来的缓存数据。

（2）基于散列表的实现，操作系统或进程需要在内存中维护一张散列表。在具体场景下，例如考虑并发、资源消耗会遇到很多问题。具体体现如下。

在并发场景下（这是常见的场景），缓存需要加锁保护，一保证数据的一致性，但散列表的加锁不简单，如果使用全局的锁来保护散列表，在高并发下会引起严重的性能问题。
由于散列表的实现使用数组，而数组会一次性占用内存的一片连续空间。这样它把页的引用都存储下来。但对于应用来说，它每次只需要部分数据即可，对比整个页面搜索空间来说，太大了。
使用散列表消耗更多的内存空间，且要求内存是连续的。
如果页搜索失败，要通过I/O访问磁盘，而此前搜索散列桶上的链表就白费时间。

解决上述的问题（1）可以采用双链策略。LRU算法维护两条双链表（也可以是一条双链表，但做分隔，例如MySQL的midpoint，实现上采用前者更方便）方便起见，我们把这两条链表分别命名为新链表和老链表。但页加载到内存，先保存到老链表上，等它在内存中停留一段时间在移动到新链表上，或者在再次使用时才移动到新链表上。如果要淘汰页面，先淘汰老链表上的页。为了保持这两条链表的平衡，定期把新链表上较旧的数据移动到老链表上。MySQL的InnoDB就采用类似的方法。

补充下MySQL对LRU算法的优化：链表上维护一条链表，链表中有一个midpoint结点，该结点前的链表称为新链表，结点后的链表称为旧链表。midpoint位置在整条链表的5/8上。当新数据插入是，只会放到旧链表的头部，待一段时间后才会已到新链表上。可以理解为，新链表上的数据为热数据，旧链表上的数据为临时数据（可能只使用一次）另外，还可以通过一定的策略保存新链表的大小，也就是说当新链表过长时，可以把链表尾部结点已到midpoint后，从而维护midpoint位置的稳定。上述的实现思路是一种分级思想，这里采用了二次分级。类似地可以推广到n次分级，但从实现上就更难了。

解决问题（2）就需要寻找一种能替代散列表的数据结构而又不引起散列表带来的问题。radix树就能解决这个问题。Linux内核的页高速缓存就采用这种方法。另外，在Redis3.0后的版本中也加入了radix数据结构。接下来我们详细讨论这颗树和它的亲戚~

radix tree

和radix树类似的还有trie树和patricia树、suffix树。先谈谈它们的关系。trie树是一种字典查找树，和常见的树不同。

radix tree的中文是基数树，和一般的树不同，它的叶子结点不保存key信息，边才保存key信息。可以这样理解，我们如果使用radix实现字典查找数据结构，那么它一定是键-值对的存储结构。在查找时，我们依据的是边的信息来判断当前位置的结点是否匹配我们要找的key，一旦是，那么这个当前结点就是key对应的保存了value的结点。原谅我说得有点绕口。这样的好处就是经量复用key子串相似的部分。trie、patricia在结构上也如上述的radix tree。

不同的是，radix的边（左右分支）只表示0或1比特位，也就是一个结点最多只有左右两个分支。而trie树是radix这种结构的推广，不局限于左右两个分支，从应用上可以是26个分支（刚刚满足每个分支代表一个字母，类似的需求可以设计更多的分支）。但trie的一个缺点是可能有很多的孤儿结点存在（也就是分支还有一个的结点），为了优化，我们把连续的孤儿结点合并在一起，这就是patricia tree。

这三种树的结构类似，出于应用推广和优化而发生改变，但它们都起到复用key信息的作用，降低数据的冗余度，节省内存。

那么，这种树是怎么解决问题（2）呢？

（待续~）