概要
本文的想法來自於本人學習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{ int hitNum; K key; V value; Node prev; Node 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 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
（圖3）
如果命中項位於old區，對命中數+1後與BLOCK_HIT_NUM設置的值做判斷，超過設定值說明該項數據可能不是突發數據，進行madeYoung操作提到鍊表首部，否則不做處理。
特別的，如果命中項正好是point，則point應該往後退一項，指向原point的下一項，此時young區膨脹了一項，而old區縮小了一項。極端情況下，ponit項持續被命中並進行madeYoung，point不斷後退直到尾巴，此時young區占有100%容量，而old區為0，設置point指向last，意味著新數據項加入時，淘汰掉young區的末尾，而新數據項放在末尾成為old區。如圖4
（圖4）
public void madeYoung(Node node){ if(first==node){ return; } if(node==point){ point=node.next; if(point==null) { point=last; } } if(node.next!=null){ node.next.prev=node.prev; } if(node.prev!=null){ node.prev.next=node.next; } if(node==last){ last=node.prev; } if(first==null||last==null){ first=last=node; point=null; return; } node.next=first; first.prev=node; first=node; } public void madeOld(Node node){ if(point.prev!=null){ point.prev.next=node; node.prev=point.prev; } if(point.next!=null){ node.next=point.next; point.next.prev=node; } point=node; }3.4需要一個清理的方法。也可以設置一些監測方法，如一段時間內的命中數（監測命中率）等，這與本篇主要內容無關就不寫在這了。
public void removeLast(){ if(last!=null){ if(last==point) { point=null; } last=last.prev; if(last==null) { first=null; }else{ last.next=null; } } }4.示例代碼
主要代碼如下，時間倉促，可能一些地方會考慮不周，讀者如發現，歡迎指出。
package com.company;import java.util.HashMap;public class LRUNum { private HashMap caches; private Node first; private Node last; private Node point; private int size; private int capcity; private static final int BLOCK_HIT_NUM=2; private static final float MID_POINT=0.37f; private int pointBorder; public LRUNum(int capcity){ this.size=0; this.capcity=capcity; this.caches=new HashMap(capcity); this.pointBorder=this.capcity-(int)(this.capcity*this.MID_POINT); } public void put(K key,V value){ Node 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); } public V get(K key){ Node node =caches.get(key); if(node==null){ return null; } if(++node.hitNum>BLOCK_HIT_NUM){ madeYoung(node); } return node.value; } public Object remove(K key){ Node node =caches.get(key); if(node!=null){ if(node.prev!=null){ node.prev.next=node.next; } if(node.next!=null){ node.next.prev=node.prev; } if(node==first){ first=node.next; } if(node==last){ last=node.prev; } } return caches.remove(key); } public void removeLast(){ if(last!=null){ if(last==point) { point=null; } last=last.prev; if(last==null) { first=null; }else{ last.next=null; } } } public void clear(){ first=null; last=null; point=null; caches.clear(); } public void madeYoung(Node node){ if(first==node){ return; } if(node==point){ point=node.next; if(point==null) { point=last; } } if(node.next!=null){ node.next.prev=node.prev; } if(node.prev!=null){ node.prev.next=node.next; } if(node==last){ last=node.prev; } if(first==null||last==null){ first=last=node; point=null; return; } node.next=first; first.prev=node; first=node; } public void madeOld(Node node){ if(point.prev!=null){ point.prev.next=node; node.prev=point.prev; } if(point.next!=null){ node.next=point.next; point.next.prev=node; } point=node; } private static class Node{ int hitNum; K key; V value; Node prev; Node next; Node(K key,V value){ this.key=key; this.value=value; hitNum=0; } }}