MySQL 實現本地 Key-Value 緩存：mmap 零拷貝、LRU 淘汰、持久化、400 行核心代碼

設計目標

• 嵌入式本地緩存，無獨立進程依賴 (對比 Redis/Memcached)。
• 極致效能：Value 1KB 時，單核 200 萬 ops/sec (讀寫混合)。
• 零 malloc/free：記憶體映射檔案 (mmap)，避免碎片、洩漏。
• 崩潰安全：映射至磁碟檔案，進程重啟資料保留；機器掉電可能損壞最後寫入頁。
• 近似 LRU：鏈表級 LRU (非全域)，平衡效能與淘汰準確度。
• 泛型支援：Key/Value 可為任意 C++ 類型 (struct/class)，非僅字串。
• 生產驗證：數十台線上機器運行半年零故障。

核心架構

+------------------+     +------------------+     +------------------+
|  Hash Table      |     |  Doubly Linked   |     |  Memory Mapped   |
|  (Array of       |     |  List per Bucket |     |  File (mmap)     |
|  Buckets)        |     |  (LRU order)     |     |                  |
+------------------+     +------------------+     +------------------+
        |                        |                        |
        v                        v                        v
   Bucket Array            Entry Nodes              Physical Storage
   (index = hash%len)      (Key, Value,             (TableHead +
    Head/Tail ptrs         Prev/Next,               Array + Entries)
                            HashCode)

關鍵資料結構 (C++ Template)

template
class HashTable {
    struct TableHead {
        uint32_t table_len;      // 桶數量
        uint32_t node_total;     // 最大節點數
        uint32_t free_base;      // 空閒區起始
        uint32_t recycle_head;   // 回收鏈表頭
        uint32_t used_count;     // 已用節點數
        char table_name[256];
        uint32_t padding[0];     // 彈性擴展區
    };

    struct Array {               // 桶 (雙向鏈表頭尾)
        uint32_t head, tail;
    };

    struct Entry {               // 節點
        V value;
        K key;
        uint32_t hash_code;
        uint32_t next, prev;
    };

    // 記憶體映射指針
    TableHead* head_;
    Array*     buckets_;
    Entry*     entries_;
    ThreadMutex mutex_;
    // ...
};

核心操作複雜度

LRU 淘汰邏輯 (桶級)

// LruAdd: 新增時若滿，淘汰桶尾 (最久未訪問)
bool LruAdd(K& key, V& value, K& recy_key, V& recy_val, bool& recycled) {
    if (Exist(key)) return false;
    if (Add(key, value)) return true;  // 還有空位

    uint32_t idx = key.HashCode() % head_->table_len;
    uint32_t tail_id = GetTailNodeId(idx);  // 取桶尾
    if (tail_id == INVALID) return false;

    Entry* tail = entries_ + tail_id;
    recy_key = tail->key;      // 返回被淘汰 KV 供應用層處理
    recy_val = tail->value;
    recycled = true;

    RecycleNode(idx, tail_id); // 從桶移除、掛入回收鏈
    return Add(key, value);    // 再次嘗試新增
}

持久化與崩潰恢復

• 建構子呼叫 MemFile::Realloc(name, size) → mmap (Linux) / CreateFileMapping (Windows)。
• 析構子呼叫 MemFile::Release(addr, size) → munmap / UnmapViewOfFile。
• 資料即磁碟檔案，進程結束自動由 OS 刷回磁碟 (取決於 msync/頁面置換)。
• 機器掉電可能丟失未刷新的髒頁 (通常最後幾毫秒寫入)。

使用範例

// Key/Value 為結構體
struct UserKey { uint64_t uid; uint32_t HashCode() const { return uid * 31; } bool Equals(const UserKey& o) const { return uid == o.uid; } };
struct UserVal { char name[32]; int level; time_t last_login; };

HashTable cache("user_cache", 10007, 1000000); // 10007 桶, 100萬節點

UserKey k{12345};
UserVal v{"Alice", 10, time(nullptr)};
cache.LruAdd(k, v, k, v, recycled);  // 寫入

UserVal out;
if (cache.LruGet(k, out)) { /* hit */ }

效能基準 (參考)

遷移至 Redis 的判斷標準

• 需要分散式/多機共享緩存 → Redis Cluster。
• 需要豐富資料結構 (Set/SortedSet/Stream) → Redis。
• 緩存體積 > 單機記憶體 50% → Redis (或本地緩存分層：L1 本地 + L2 Redis)。
• 單機、高效能、簡單 KV、可容忍機器故障丟失 → 本方案完美契合。