前言
Redis內存淘汰指的是用戶存儲的一些鍵被可以被Redis主動地從實例中刪除，從而產生讀miss的情況，那麼Redis為什麼要有這種功能？這就是我們需要探究的設計初衷。Redis最常見的兩種應用場景為緩存和持久存儲，首先要明確的一個問題是內存淘汰策略更適合於那種場景？是持久存儲還是緩存？
內存的淘汰機制的初衷是為了更好地使用內存，用一定的緩存miss來換取內存的使用效率。
在研究Redislru之前，我們先看下操作系統內存頁面置換算法
1. 最佳置換算法(OPT)
最佳(Optimal, OPT)置換算法所選擇的被淘汰頁面將是以後永不使用的，或者是在最長時間內不再被訪問的頁面,這樣可以保證獲得最低的缺頁率。但由於人們目前無法預知進程在內存下的若千頁面中哪個是未來最長時間內不再被訪問的，因而該算法無法實現。
2. 先進先出(FIFO)頁面置換算法
優先淘汰最早進入內存的頁面，亦即在內存中駐留時間最久的頁面。該算法實現簡單，只需把調入內存的頁面根據先後次序鏈接成隊列，設置一個指針總指向最早的頁面。但該算法與進程實際運行時的規律不適應，因為在進程中，有的頁面經常被訪問。
3.最近最久未使用(LRU)置換算法
選擇最近最長時間未訪問過的頁面予以淘汰，它認為過去一段時間內未訪問過的頁面，在最近的將來可能也不會被訪問。該算法為每個頁面設置一個訪問字段，來記錄頁面自上次被訪問以來所經歷的時間，淘汰頁面時選擇現有頁面中值最大的予以淘汰。
再對上面的實例釆用LRU算法進行頁面置換，如圖3-29所示。進程第一次對頁面2訪問時，將最近最久未被訪問的頁面7置換出去。然後訪問頁面3時，將最近最久未使用的頁面1換出。
時鐘(CLOCK)置換算法
LRU算法的性能接近於OPT,但是實現起來比較困難，且開銷大；FIFO算法實現簡單，但性能差。所以操作系統的設計者嘗試了很多算法，試圖用比較小的開銷接近LRU的性能，這類算法都是CLOCK算法的變體。
簡單的CLOCK算法是給每一幀關聯一個附加位，稱為使用位。當某一頁首次裝入主存時，該幀的使用位設置為1;當該頁隨後再被訪問到時，它的使用位也被置為1。對於頁替換算法，用於替換的候選幀集合看做一個循環緩衝區，並且有一個指針與之相關聯。當某一頁被替換時，該指針被設置成指向緩衝區中的下一幀。當需要替換一頁時，操作系統掃描緩衝區，以查找使用位被置為0的一幀。每當遇到一個使用位為1的幀時，操作系統就將該位重新置為0；如果在這個過程開始時，緩衝區中所有幀的使用位均為0，則選擇遇到的第一個幀替換；如果所有幀的使用位均為1,則指針在緩衝區中完整地循環一週，把所有使用位都置為0，並且停留在最初的位置上，替換該幀中的頁。由於該算法循環地檢查各頁面的情況，故稱為CLOCK算法，又稱為最近未用(Not Recently Used, NRU)算法。
傳統的淘汰算法：
FIFO：First In First Out，先進先出。判斷被存儲的時間，離目前最遠的數據優先被淘汰。
LRU：Least Recently Used，最近最少使用。判斷最近被使用的時間，目前最遠的數據優先被淘汰。
LFU：Least Frequently Used，最不經常使用。在一段時間內，數據被使用次數最少的，優先被淘汰。
REDIS淘汰策略
Redis提供了下面幾種淘汰策略供用戶選擇，其中默認的策略為noeviction策略：
· noeviction：當內存使用達到閾值的時候，所有引起申請內存的命令會報錯。
· allkeys-lru：在主鍵空間中，優先移除最近未使用的key。
· volatile-lru：在設置了過期時間的鍵空間中，優先移除最近未使用的key。
· allkeys-random：在主鍵空間中，隨機移除某個key。
· volatile-random：在設置了過期時間的鍵空間中，隨機移除某個key。
· volatile-ttl：在設置了過期時間的鍵空間中，具有更早過期時間的key優先移除。
下面看看幾種淘汰策略策略的適用場景：
· allkeys-lru：如果我們的應用對緩存的訪問符合冪律分佈（也就是存在相對熱點數據），或者我們不太清楚我們應用的緩存訪問分佈狀況，我們可以選擇allkeys-lru策略。
· allkeys-random：如果我們的應用對於緩存key的訪問概率相等，則可以使用這個策略。
· volatile-ttl：這種策略使得我們可以向Redis提示哪些key更適合被eviction。
手寫最近最久未使用(LRU)置換算法
距離現在最早使用的會被我們替換掉。不夠形象的話我們看下面的例子。
插入1234231
位置11112342
位置2null223423
位置3nullnull34231
…
位置1始終是最早進來的元素，是淘汰位置。新進來的元素如果是新元素直接放在位置3，然後將位置1彈出。如果是已有元素則將其放在位置3並刪除之前位置上的已有元素，保持其他元素相對位置不變。
這裡的例子就是一個size=3的緩存淘汰實現。
利用LinkedHashMap實現的簡單LRU
對於Java.util.LinkedHashMap我們的認識僅僅只是停留在該map可以按照插入的順序保存，那是不夠的。 linkedHashMap還可以實現按照訪問順序保存元素。
先看看如何利用它實現LRU的吧
public class UseLinkedHashMapCacheextends LinkedHashMap {
private int cacheSize;
public UseLinkedHashMapCache(int cacheSize){
//構造函數一定要放在第一行
super(16,0.75f,true); //那個f如果不加 就是double類型，然後該構造沒有該類型的入參。 然後最為關鍵的就是那個入參 true
this.cacheSize = cacheSize;
}
@Override
protected boolean removeEldestEntry(Map.Entry
return size()>cacheSize; //臨界條件不能有等於，否則會讓緩存尺寸小1
}
}
關鍵點:
繼承了LinkedHashMap並使用
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
構造函數
重寫了
protected boolean removeEldestEntry(Map.Entryeldest) {
return false;
}
看看如何使用
public static void main(String[]args){
UseLinkedHashMapCache<integer> cache = new UseLinkedHashMapCache<integer>(4);
cache.put(1, "one");
cache.put(2, "two");
cache.put(3, "three");
cache.put(4, "four");
cache.put(2, "two");
cache.put(3, "three");
Iterator<map.entry>> it = cache.entrySet().iterator();
while(it.hasNext()){
Map.Entry<integer> entry = it.next();
Integer key = entry.getKey();
System.out.print("Key:\t"+key);
String Value = entry.getValue(); //這個無需打印...
System.out.println();
}
}
/<integer>/<map.entry>/<integer>/<integer>
結果是:
Key: 1
Key: 4
Key: 2
Key: 3
與我們表格中的結果一致。
手寫LRU（利用數組）
/**
* 用數組寫了一個
*
* 有個疑問， 比如當緩存大小為5 這時候1、2、3、4、4 請問最後一個4是應該插入還是不處理呢？
*
* 我個人覺得如果這裡理解為緩存的key ，那麼就應該是不插入 結果應該還是1、2、3、4、null
* */
public class HandMakeCache {
//添加次數 計數器
static int count =0;
//數組元素 計數器
static int size=0;
//最大長度
int maxSize;
//對象數組
int [] listArray; //為了簡略比較
//順序表的初始化方法
public HandMakeCache(int maxSize)
{
listArray = new int [maxSize];
this.maxSize = maxSize;
}
public int getSize(){
return size;
}
public void insert(int obj) throws Exception {
// 插入過程不應該指定下標，對於用戶來講這應該是透明的，只需要暴露插入的順序
boolean exist = false; // 每次insert校驗一下是否存在
int location = 0; // 對於已有元素，記錄其已存在的位置
for (int i = 0; i < maxSize; i++) {
if (obj == listArray[i]) {
exist = true;
location = i; // 記錄已存在的位置
}
} // 遍歷看是否已有，每次插入都要遍歷，感覺性能很差
if (size < this.maxSize) { // 當插入次數小於緩存大小的時候隨意插入
if (exist) {
if (location == 0) {
moveArrayElements(listArray,0,size-2);
} else if (location < size - 1) { // 已存在元素不在最新的位置
moveArrayElements(listArray,location,size-2);
}
listArray[size - 1] = obj; // 由於已存在
} else {
listArray[size] = obj;
size++; // 數組未滿時才計數
}
} else { // 此時緩存為滿，這時候要保留最末端元素先
if (!exist || obj == listArray[0]) { // 新元素添加進來，和最遠元素添加進來效果一樣
moveArrayElements(listArray,0,maxSize-2);
} else if (obj != listArray[maxSize - 1]) {
moveArrayElements(listArray,location,maxSize-2);
} // 如果添加的是上次添加的元素，則不管了。。
listArray[maxSize - 1] = obj;
}
count++; // 計數
}
public Object get(int index) throws Exception {
return listArray[index];
}
/**
* 平移數組的方法，start是要移動至的頭位置，end為最後被移動的位置。
* */
public void moveArrayElements(int [] arr, int start, int end){
for(int i=start;i<=end;i++){
arr[i] = arr[i+1];
}
}
public static void main(String[] args) {
int cacheSize = 5;
HandMakeCache list = new HandMakeCache(cacheSize);
try
{
list.insert(1);
list.insert(2);
list.insert(3);
list.insert(1);
list.insert(3);
list.insert(4);
list.insert(4);
list.insert(5);
// list.insert(3);
for(int i=0;i<cachesize> {
System.out.println(list.get(i));
}
System.out.println("成功插入"+count+"次元素.");
}
catch(Exception ex)
{
ex.printStackTrace();
}
}
}
/<cachesize>
非常重要的一點~ 寫LRU之前你一定要知道LRU的正確的含義。。
這裡分為幾種情況吧..
1. 當數組未滿的情況下，隨便插
2. 數組滿了之後，插入介於頭和尾的元素，需要記錄其之前存在的下標，然後將大於該下標的元素整體前移。
3. 數組滿了之後，插入最新的元素等於什麼操作也沒有。保持原樣
3. 數組滿了之後，插入一個不存在的元素 等同於 插入數組最開始的元素。
比如 1、2、3、4 之後插入5 和 1、2、3、4 之後插入1 結果分別為 2、3、4、5和 2、3、4、1。
缺點:
如果利用數組來存儲的話，當我們緩存的大小非常大的時候。比如10W，那麼假設我們需要淘汰最遠的元素，就需要將99999個元素整體往前移一位，這樣還僅僅只是替換一次。大量這樣的操作是非常低效的，所以我們還是考慮用鏈表來實現↓。
閱讀更多 青峰科技 的文章
