Redis系列1：深刻理解高效能Redis的本質
Redis系列2：資料持久化提高可用性
Redis系列3：高可用之主從架構
Redis系列4：高可用之Sentinel(哨兵模式）
Redis系列5：深入分析Cluster 叢集模式
追求效能極致：Redis6.0的多執行緒模型
追求效能極致：使用者端快取帶來的革命
Redis系列8：Bitmap實現億萬級資料計算
Redis系列9：Geo 型別賦能億級地圖位置計算
Redis系列10：HyperLogLog實現海量資料基數統計
Redis系列11：記憶體淘汰策略
Redis系列12：Redis 的事務機制
Redis系列13：分散式鎖實現
Redis系列14：使用List實現訊息佇列
Redis系列15：使用Stream實現訊息佇列
Redis系列16：聊聊布隆過濾器（原理篇）
Redis系列17：聊聊布隆過濾器（實踐篇）
Redis系列18：過期資料的刪除策略

1 介紹

上一期我們介紹了 Redis系列18：過期資料的刪除策略 ，但是無論是惰性刪除還是定期刪除，都可能存在刪除不盡的情況，無法刪除完全，比如每次刪除完過期的 key 還是超過 25%，且這些 key 再也不會被使用者端存取。
這樣的話，定期刪除和墮性刪除可能都徹底的清理掉。如果這種情況長時間持續下去，可能會導致記憶體耗盡，所以Redis必須有一個完善的記憶體淘汰機制來保障。這就是我們這一篇的重點，Redis記憶體自動淘汰機制。

2 Redis記憶體淘汰策略

在 redis 中總共由8種淘汰策略，預設的淘汰策略是 noeviction。

2.1 設定過期時間的淘汰策略

volatile-ttl、volatile-random、volatile-lru、volatile-lfu 這4種策略淘汰的資料範圍為設定了過期時間的資料。

2.2 所有 key 的淘汰策略

allkeys-lru、allkeys-random、allkeys-lfu 這3種淘汰策略無論是否設定了過期時間，記憶體不足時都會進行淘汰。
也就是說無論它的過期時間到沒到，都有可能被刪除。

3 LRU淘汰策略執行過程

這邊以LRU演演算法為例子講解，它的全稱是 Least Rencently Used，即將最近最久未使用的演演算法進行資料淘汰。
我們這邊以圖例來講解，整個過程如下：

• 首先設定一個淘汰池（一個連結串列），假設預設大小是16，裡面的資料採用末尾淘汰制。如圖中
  • MRU：表示連結串列的表頭，代表著最近最常被存取的資料；
  • LRU：表示連結串列的表尾，代表最近最不常使用的資料。
• 如果淘汰池中的資料被存取，則會被移動到 MRU 端，其他位置的資料則相應往後移動一位
• 每次指令操作的時候，自旋會判斷當前記憶體是否滿足指令所需要的記憶體
• 如果當前記憶體不能滿足，會從淘汰池中的尾部拿取一個最適合淘汰的資料
  • 取樣模式（設定 maxmemory-samples屬性）從Redis中獲取隨機的取樣資料，避免一次性讀取All Key效能慢
  • 在取樣的資料中，根據淘汰演演算法 找到最適合淘汰的資料
• 將需要淘汰的資料從Redis刪除，並且從淘汰池移除

這邊注意，LRU 更新和新增資料都發生在連結串列首，刪除資料都發生在連結串列尾。
水果 Orange 跟 Pitaya 被存取，被移動到MRU端，新增的Mango也被插入到MRU端。而最末端的Olive則被刪除。

4 演演算法實現

以下是使用Go語言實現Redis LRU淘汰過程的範例程式碼，程式碼註釋很清楚：

package main  
  
import (  
    "container/list"  
    "fmt"  
    "time"  
)  
  
type Redis struct {  
    data map[string]*list.Element // 儲存快取項的鍵和值，以及它們在LRU連結串列中的位置  
    lru *list.List // LRU連結串列  
}  
  
type cacheItem struct {  
    key   string  
    value string  
    // 記錄該快取項最後一次被存取的時間  
    lastAccess time.Time  
}  
  
func NewRedis() *Redis {  
    return &Redis{  
        data: make(map[string]*list.Element),  
        lru: list.New(),  
    }  
}  
  
func (r *Redis) Get(key string) (string, bool) {  
    // 從LRU連結串列中查詢快取項  
    if elem, ok := r.data[key]; ok {  
        // 將該快取項移動到連結串列頭部，表示最近被存取過  
        r.lru.MoveToFront(elem)  
        // 更新快取項的最後存取時間  
        item := elem.Value.(*cacheItem)  
        item.lastAccess = time.Now()  
        return item.value, true  
    }  
    return "", false  
}  
  
func (r *Redis) Set(key string, value string) {  
    // 從LRU連結串列中查詢快取項  
    if elem, ok := r.data[key]; ok {  
        // 如果快取項存在，更新其值和最後存取時間，並將其移動到連結串列頭部  
        item := elem.Value.(*cacheItem)  
        item.value = value  
        item.lastAccess = time.Now()  
        r.lru.MoveToFront(elem)  
        return  
    }  
    // 如果快取項不存在，建立新的快取項並將其新增到LRU連結串列頭部  
    item := &cacheItem{  
        key:    key,  
        value:  value,  
        lastAccess: time.Now(),  
    }  
    elem := r.lru.PushFront(item)  
    r.data[key] = elem  
    // 如果快取空間已滿，執行LRU淘汰操作  
    for r.lru.Len() > maxItems {  
        // 從連結串列尾部查詢最久未被存取的快取項  
        elem := r.lru.Back()  
        item := elem.Value.(*cacheItem)  
        // 如果該快取項的過期時間已到達，則從連結串列中刪除該快取項  
        if item.lastAccess.Add(expireTime).Before(time.Now()) {  
            r.lru.Remove(elem)  
            delete(r.data, item.key)  
        } else {  
            // 否則，只從連結串列中刪除該快取項  
            r.lru.Remove(elem)  
        }  
    }  
}

在這個範例中，我們使用了一個map來儲存快取項的鍵和值，以及它們在LRU連結串列中的位置。我們使用了一個LRU連結串列來儲存快取項，並按照存取時間將它們排序。在Get方法中，我們從LRU連結串列中查詢快取項，並將其移動到連結串列頭部，表示最近被存取過。在Set方法中，如果快取項已存在，我們更新其值和最後存取時間，並將其移動到連結串列頭部；如果快取項不存在，我們建立新的快取項並將其新增到LRU連結串列頭部。如果快取空間已滿，我們執行LRU淘汰操作，從連結串列尾部查詢最久未被存取的快取項，並從連結串列中刪除它。注意，我們還檢查了快取項的過期時間，如果該快取項已過期，則也會從連結串列中刪除它。

5 總結

第4小節基本來自baidu文心一言的組織，非常感謝。
這一篇我們介紹了Redis的幾種記憶體淘汰策略，並且詳細分析了LRU演演算法的實現原理。下一篇我們分析下 LFU 演演算法。