0004. LRU-K(Least Recently Used K) - 快取演算法 (Cache Algorithm) - 快取策略：第 K 次最近最少使用演算法

日期：2026年 02月 14日

標籤： Algorithm Cache Algorithm C# Asp.NET Core

摘要：演算法-快取策略

n：設定快取的上限筆數
時間複雜度(Time Complex)：O(1) ※ 取值 / 存值
空間複雜度： O(n)
範例檔案：Source Code
範例專案：Code Project
基本介紹：本篇分為 3 大部分。
第一部分：LRU-K 演算法 - 介紹
第二部分：LRU-K 演算法 - 實現
第三部分：LRU-K 演算法 - 圖解流程

第一部分：LRU-K 演算法 - 介紹

Step 1：簡介

以下截取於Wiki

LRU-K[16] evicts the page whose K-th most recent access is furthest in the past. 
For example, LRU-1 is simply LRU whereas LRU-2 evicts pages according to the time of their penultimate access. 
LRU-K improves greatly on LRU with regards to locality in time.

簡言之： LRU 的 K = 1 ，而「LRU-K」則是 K 次，K 次最近存取的資料，概念上達到 K 次為 熱數據 ，在達到 K 次使用前為 冷數據
※來源：Wiki

Step 2：解決 LRU 的問題

** LRU-K 解決 LRU ** 以下問題：

問題類型	具體場景	LRU 的表現	業務影響
1. 掃描污染	資料庫全表掃描 100 萬筆	100 萬筆冷數據進入快取，熱數據（用戶表、訂單表）全被擠出	正常業務查詢變慢，資料庫負載暴增
2. 循環訪問	在 N+1 個頁面陣列上循環（快取容量=N）	每次訪問都 Cache Miss，命中率 = 0%	效能極差，等同於沒有快取
3. 爬蟲污染	爬蟲掃描 10000 個舊頁面	首頁、熱門文章被擠出快取	真實用戶訪問變慢
4. 無法區分冷熱	一次性訪問 vs 頻繁訪問	「訪問 1 次」和「訪問 100 次」的頁面被同等對待	重要數據容易被淘汰

Step 3：優缺點

優點具有以下：

優點	說明	實際效益
1. 抵抗掃描污染	一次性訪問不會驅逐熱數據	系統穩定性提升
2. 適應性強	即時適應訪問模式變化	應對工作負載變化，設定冷熱數據比例
3. 命中率提升	整體命中率顯著提高	減少 I/O，提升效能
4. 簡單開銷小	O(1) 時間複雜度	效能不受影響 Get/Put 仍都是 O(1)

缺點：

缺點	影響	嚴重程度	緩解方案
1. 記憶體開銷	需要額外 50-100% 記憶體存儲索引	中	對大型快取系統影響可忽略
2. 實作複雜	需要管理兩層架構 + 多個資料結構	中	一次實作，長期受益
3. 參數調整	需要設定 K 值和冷熱比例	輕	K=2 和 25-75 比例適用多數場景
4. 仍可被攻擊	攻擊者訪問每個 Key 兩次可污染	中	增加時間窗口限制、使用 ARC
5. 小容量不適合	例如容量 < 10 時冷數據區太小	高	小容量建議使用 LRU
6. 嚴格實作複雜	按第 K 次時間排序需 O(N log N)	輕	使用 LinkedList 近似，O(1)

實務面上，從 LRU 轉成 LRU-K 成本的增加是不可避免的。

Step 3：應用場景說明

以下列舉生活常見的 MRU Cache 應用，以及補充何種狀況下不合適採用

應用場景	適合 LRU	適合 LRU-K	原因
快取容量 < 10	✅		LRU-K 冷數據區太小，失去意義
快取容量 ≥ 10		✅	有足夠空間發揮優勢
有週期性掃描		✅	抵抗掃描污染
有爬蟲訪問		✅	過濾一次性訪問
記憶體非常受限	✅		降低記憶體開銷
追求極致簡單	✅		降低實作複雜度
資料庫緩衝區		✅	原始設計場景，效果最佳
CDN 快取		✅	處理大量一次性訪問
檔案系統快取		✅	處理病毒掃描等操作

第二部分：LRU-K 演算法 - 實現

Step 1：完整代碼

完整代碼可以從下載
主要以下 5 個部分完成，整理複雜度 + 代碼框架如下：
※與 LRU 關鍵差異 : 增加冷數據、熱數據機制

項目	複雜度	說明
1. 建構式-配置	空間 O(n)	LRU-K 增加了冷熱數據，並依照比例切分，所以空間 O(n)
2. Get 獲取方法	時間 O(1)	LRU-K 同 LRU 仍用 LinkedListNode 取得節點 = O(1)，增加的冷熱判斷式不影響
3. 設定鍵值	時間 O(1)	同 LRU，查找、插入/更新、鏈表調整全部都是 O(1)
4. 提升節點優先級	時間 O(1)	邏輯處理，冷數據被再次訪問升級為熱數據，但善用 LinkedListNode 仍為 O(1)
5. 淘汰策略	時間 O(1)	邏輯處裡，優先淘汰 historyQueue (只訪問一次)，其次淘汰 cacheQueue 的 LRU，不影響時間原 LRU 時間複雜圖

public class LRU2Cache
{
    private readonly Dictionary<string, Node> _cache; // 主快取
    private readonly static int LRU_K_Times = 2;// 冷數據閥值   
    private readonly LRU _HotData;// 熱數據 - LRU
    private readonly FIFO _ColdData;// 冷數據 - FIFO
    private readonly int _capacity;

    /// <summary>
    /// 1. 建構式 - 配置
    /// </summary>
    /// <param name="capacity"></param>
    public LRU2Cache(int capacity)
    {
        _capacity = capacity;
        _cache = new Dictionary<string, Node>();

        // 1-1. 配置冷熱數據比例：25% 冷數據，75% 熱數據
        int coldCapacity = Math.Max(1, capacity / 4);
        int hotCapacity = capacity - coldCapacity;

        // 1-2. 初始化冷熱數據上限
        _HotData = new LRU { LRUCapacity = hotCapacity };
        _ColdData = new FIFO { HistoryCapacity = coldCapacity };
    }

    /// <summary>
    /// 2. Get 獲取方法
    /// </summary>
    public string Get(string key)
    {
    }    

    /// <summary>
    /// 3. 設定鍵值
    /// </summary>
    public void Put(string key, string value)
    {       
    }

    /// <summary>
    /// 4. 提升節點優先級
    /// </summary>
    private void PromoteNode(string key, Node node)
    {
    }

    /// <summary>
    /// 5. 淘汰策略：優先淘汰 historyQueue (只訪問一次)，其次淘汰 cacheQueue 的 LRU
    /// </summary>
    private void Evict()
    {    
    }
}

Step 2：資料結構 - 冷熱數據

LRU-K 的資料結構需要冷熱數據，有以下資料結構

1. FIFO 結構 (冷數據)	LRU-K 未滿 K 次時，數據都為冷數據
2. LRU 結構 (熱數據)	LRU-K 達到 K 次以上時，數據都會由冷數據轉為熱數據
3. 快取資料	同 LRU，查找、插入/更新、鏈表調整全部都是 O(1)


/// <summary>
/// 1. FIFO 結構 (冷數據)
/// </summary>
private class FIFO
{
    /// <summary>
    /// 快取空間筆數
    /// </summary>
    public int HistoryCapacity { get; set; }
    /// <summary>
    /// 歷史佇列節點
    /// </summary>
    public Dictionary<string, LinkedListNode<string>> HistoryNodes { get; set; } = new Dictionary<string, LinkedListNode<string>>();
    /// <summary>
    /// 只訪問過一次的佇列 (FIFO)
    /// </summary>
    public LinkedList<string> HistoryQueue { get; set; } = new LinkedList<string>();
}

/// <summary>
/// 2. LRU 結構 (熱數據)
/// </summary>
private class LRU
{
    /// <summary>
    /// 快取空間筆數
    /// </summary>
    public int LRUCapacity { get; set; }
    /// <summary>
    /// 快取佇列節點
    /// </summary>
    public Dictionary<string, LinkedListNode<string>> CacheNodes { get; set; } = new Dictionary<string, LinkedListNode<string>>();
    /// <summary>
    /// 訪問過兩次以上的佇列 (LRU)
    /// </summary>
    public LinkedList<string> CacheQueue = new LinkedList<string>();
}

/// <summary>
/// 3. 快取資料
/// </summary>
private class Node
{
    public string Key { get; set; }
    public string Value { get; set; }
    /// <summary>
    /// 存取次數
    /// </summary>
    public int AccessCount { get; set; }
    /// <summary>
    /// 檢視用 - LinkedList 已有順序
    /// </summary>
    public DateTime FirstAccessTime { get; set; }
    /// <summary>
    /// 檢視用 - LinkedList 已有順序
    /// </summary>
    public DateTime? SecondAccessTime { get; set; }  
}

Step 3：1. 建構式 - 配置

LRU-K 應用時，需要設定一定比例的冷熱數據，這裡採用冷:25% 熱:75%
通常冷數據需比熱數據小，當第一層防護

/// <summary>
/// 1. 建構式 - 配置
/// </summary>
public LRU2Cache(int capacity)
{
    _capacity = capacity;
    _cache = new Dictionary<string, Node>();

    // 1-1. 配置冷熱數據比例：25% 冷數據，75% 熱數據
    int coldCapacity = Math.Max(1, capacity / 4);
    int hotCapacity = capacity - coldCapacity;

    // 1-2. 初始化冷熱數據上限
    _HotData = new LRU { LRUCapacity = hotCapacity };
    _ColdData = new FIFO { HistoryCapacity = coldCapacity };
}

Step 4：2. Get 獲取方法

取值的處理，每當被檢索到時，將數據權重提升，以下 3 種狀況

1. 無法檢索

2. 冷數據 -> 熱數據

3. 保持熱數據，並採用 LRU 方法權重往前

/// <summary>
/// 2. Get 獲取方法
/// </summary>
public string Get(string key)
{
    if (!_cache.ContainsKey(key))
        return "Not Found!";

    // 2-1. 提升權重
    var node = _cache[key];
    PromoteNode(key, node);
    return node.Value;
}

Step 4：3. 設定鍵值

存值的處理，當存入時，有 3 種情況

是否已存在	是否達到設定上限	處理方式
存在		將冷數據提升為熱數據
不存在	是	進行淘汰策略
不存在	否	加入到冷數據中，若冷數據達上限則 FIFO 最先進入的冷數據移除

/// <summary>
/// 3. 設定鍵值
/// </summary>
public void Put(string key, string value)
{
    // 3-1. 無空間直接結束
    if (_capacity == 0)
        return;

    // 3-2. 快取檢查，若被加入冷熱數據 中，皆可查詢到
    if (_cache.ContainsKey(key))
    {
        var node = _cache[key];
        node.Value = value;     
        
        // 3-3. 在冷數據中，重複 Put 的 Key 也可以升級成熱數據 
        // ※ Put 需依照應用情境，來決定是否提升權重
        PromoteNode(key, node);
    }
    else
    {
        // 3-3. 保存的數據達上限時，需要移除
        if (_cache.Count >= _capacity)
        {
            Evict();
        }

        // 3-4. 新增節點到冷數據區
        var newNode = new Node
        {
            Key = key,
            Value = value,
            AccessCount = 1,
            FirstAccessTime = DateTime.Now,
            SecondAccessTime = null
        };
        _cache[key] = newNode;

        // 3-5. 檢查冷數據區是否需要淘汰，達到上限時，移除最早加入的
        if (_ColdData.HistoryQueue.Count >= _ColdData.HistoryCapacity)
        {
            var oldestKey = _ColdData.HistoryQueue.First.Value;
            _ColdData.HistoryQueue.RemoveFirst();
            _ColdData.HistoryNodes.Remove(oldestKey);
            _cache.Remove(oldestKey);
        }

        var listNode = _ColdData.HistoryQueue.AddLast(key);
        _ColdData.HistoryNodes[key] = listNode;
    }
}

Step 5：淘汰策略

保存的緩存空間達到上限時， 2 種狀況

1. 優先淘汰冷數據區資料

2. 淘汰熱數據區資料

3. 沒有可淘汰的狀況 - 這並不會發生，進入點會先檢查是否觸發


/// <summary>
/// 5. 淘汰策略：優先淘汰 historyQueue (只訪問一次)，其次淘汰 cacheQueue 的 LRU
/// </summary>
private void Evict()
{
    string keyToRemove;

    // 5-1. 優先淘汰冷數據區
    if (_ColdData.HistoryQueue.Count > 0)
    {
        keyToRemove = _ColdData.HistoryQueue.First.Value;
        _ColdData.HistoryQueue.RemoveFirst();
        _ColdData.HistoryNodes.Remove(keyToRemove);
    }
    // 5-2. 否則淘汰熱數據區的-最久未使用的 (LRU)
    else if (_HotData.CacheQueue.Count > 0)
    {
        keyToRemove = _HotData.CacheQueue.Last.Value;
        _HotData.CacheQueue.RemoveLast();
        _HotData.CacheNodes.Remove(keyToRemove);
    }
    else// 5-3. 沒有可淘汰的狀況
    {
        return; 
    }

    _cache.Remove(keyToRemove);
}