概要

本文的想法来自于本人学习MySQL时的一个知识点:MySQL Innodb引擎中对缓冲区的处理。虽然没有仔细研究其源码实现，但其设计仍然启发了我。

本文针对LRU存在的问题，思考一种增强算法来避免或降低缓存污染，主要办法是对原始LRU空间划分出young与old两段区域 ，通过命中数（或block时间）来控制，并用一个0.37的百分比系数规定old的大小。
内容分以下几小节，实现代码为Java：

1.LRU基本概念
2.LRU存在问题与LRUG设计
3.LRUG详细说明
4.完整示例代码

 

1.LRU基本概念
LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据。常用于一些缓冲区置换，页面置换等处理。

一个典型的双向链表+HashMap的LRU如下：

 

 

2.LRU存在问题与LRUG设计

LRU的问题是无法回避突发性的热噪数据，造成缓存数据的污染。对此有些LRU的变种，如LRU-K、2Q、MQ等，通过维护两个或多个队列来控制缓存数据的更新淘汰。我把本文讨论的算法叫LRUG，仅是我写代码时随便想的一个名字。

LRUG使用HashMap和双向链表，没有其他的维护队列，而是在双向链表上划分young，old区域，young段在old段之前，有新数据时不会马上插入到young段，而是先放入old段，若该数据持续命中，次数超过一定数量（也可以是锁定一段时间）后再进行插入首部的动作。两段以37%为界，即满载后old段的大小最多占总容量的37%。（图1）

（图1）

 

3.LRUG详细说明

3.1首先给出双向链表的节点结构，其中hitNum是命中次数：

复制代码
    private static class Node<K,V>{         int hitNum;         K key;         V value;         Node<K,V> prev;         Node<K,V> next;          Node(K key,V value){             this.key=key;             this.value=value;             hitNum=0;         }     }
复制代码

 

3.2在加载阶段，数据以先后顺序加入链表，半满载时，young段已满，新数据以插入方式加入到old段，如图2所示。注意半满载时，也可能有madeYoung操作，把old区的数据提到young头。

（图2）

 

 

 

复制代码
    public void put(K key,V value){         Node<K,V> node=caches.get(key);          if(node==null){             if(caches.size()>=capcity){                 caches.remove(last.key);                 removeLast();             }             node=new Node(key,value);              if(caches.size()>=pointBorder){                 madeOld(node);             }else{                 madeYoung(node);             }         }else {             node.value=value;             if(++node.hitNum>BLOCK_HIT_NUM){                 madeYoung(node);             }         }         caches.put(key,node);     }
复制代码

 

 


3.3当数据命中时，如果位于young区，命中数+1后进行常规的madeYoung操作，把该项提到链表首部。如图3