設計 LRU/LFU Cache — 雜湊表與雙向鏈結串列的 O(1) 快取實作 | 資料結構與演算法

/**
 * LRU Cache — HashMap + Doubly Linked List
 * get / put 均為 O(1)
 */

class LRUNode<K, V> {
  key: K;
  value: V;
  prev: LRUNode<K, V> | null = null;
  next: LRUNode<K, V> | null = null;
  expiresAt: number | null = null; // TTL 支援

  constructor(key: K, value: V, ttlMs?: number) {
    this.key = key;
    this.value = value;
    if (ttlMs !== undefined) {
      this.expiresAt = Date.now() + ttlMs;
    }
  }

  isExpired(): boolean {
    return this.expiresAt !== null && Date.now() > this.expiresAt;
  }
}

class LRUCache<K = string, V = unknown> {
  private capacity: number;
  private map: Map<K, LRUNode<K, V>> = new Map();

  // 哨兵節點（Sentinel Nodes）避免邊界判斷
  private head: LRUNode<K, V>; // dummy head（最久未用端）
  private tail: LRUNode<K, V>; // dummy tail（最近使用端）

  // 統計資訊
  private hits: number = 0;
  private misses: number = 0;

  constructor(capacity: number) {
    if (capacity <= 0) throw new Error("Capacity must be positive");
    this.capacity = capacity;

    // 初始化哨兵節點，head ⟺ tail
    this.head = new LRUNode<K, V>(null as K, null as V);
    this.tail = new LRUNode<K, V>(null as K, null as V);
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  /**
   * 將節點從 DLL 中摘除（不從 Map 刪除）
   * 只需修改前後節點的指標 → O(1)
   */
  private removeNode(node: LRUNode<K, V>): void {
    node.prev!.next = node.next;
    node.next!.prev = node.prev;
  }

  /**
   * 將節點插入到 tail 前方（最近使用位置）
   */
  private insertToTail(node: LRUNode<K, V>): void {
    node.prev = this.tail.prev;
    node.next = this.tail;
    this.tail.prev!.next = node;
    this.tail.prev = node;
  }

  /**
   * 移動節點到最近使用位置 = 摘除 + 插入尾部
   */
  private moveToTail(node: LRUNode<K, V>): void {
    this.removeNode(node);
    this.insertToTail(node);
  }

  /**
   * 淘汰最久未使用的節點（head 的下一個）
   */
  private evictLRU(): void {
    const lruNode = this.head.next!;
    if (lruNode === this.tail) return; // 空快取

    this.removeNode(lruNode);
    this.map.delete(lruNode.key);
  }

  get(key: K): V | -1 {
    const node = this.map.get(key);

    if (!node) {
      this.misses++;
      return -1;
    }

    // TTL 過期處理
    if (node.isExpired()) {
      this.removeNode(node);
      this.map.delete(key);
      this.misses++;
      return -1;
    }

    this.hits++;
    this.moveToTail(node); // 標記為最近使用
    return node.value;
  }

  put(key: K, value: V, ttlMs?: number): void {
    if (this.map.has(key)) {
      // 已存在：更新 value，移到尾部
      const node = this.map.get(key)!;
      node.value = value;
      if (ttlMs !== undefined) {
        node.expiresAt = Date.now() + ttlMs;
      }
      this.moveToTail(node);
    } else {
      // 新增：若滿則先淘汰
      if (this.map.size >= this.capacity) {
        this.evictLRU();
      }
      const newNode = new LRUNode(key, value, ttlMs);
      this.map.set(key, newNode);
      this.insertToTail(newNode);
    }
  }

  delete(key: K): boolean {
    const node = this.map.get(key);
    if (!node) return false;
    this.removeNode(node);
    this.map.delete(key);
    return true;
  }

  get size(): number {
    return this.map.size;
  }

  getHitRate(): number {
    const total = this.hits + this.misses;
    return total === 0 ? 0 : this.hits / total;
  }

  getStats() {
    return {
      hits: this.hits,
      misses: this.misses,
      hitRate: `${(this.getHitRate() * 100).toFixed(2)}%`,
      size: this.map.size,
      capacity: this.capacity,
    };
  }

  /**
   * 回傳當前快取內容（從最久未用到最近使用）
   */
  toArray(): Array<{ key: K; value: V }> {
    const result: Array<{ key: K; value: V }> = [];
    let curr = this.head.next;
    while (curr !== this.tail) {
      result.push({ key: curr!.key, value: curr!.value });
      curr = curr!.next;
    }
    return result;
  }
}

// === 測試 ===
const lru = new LRUCache<number, number>(3);
lru.put(1, 10);
lru.put(2, 20);
lru.put(3, 30);
console.log("初始狀態:", lru.toArray());
// 輸出：[{key:1, value:10}, {key:2, value:20}, {key:3, value:30}]

lru.get(1); // 訪問 key=1，移到尾部
console.log("get(1) 後:", lru.toArray());
// 輸出：[{key:2, value:20}, {key:3, value:30}, {key:1, value:10}]

lru.put(4, 40); // 容量已滿，淘汰最久未用的 key=2
console.log("put(4) 後:", lru.toArray());
// 輸出：[{key:3, value:30}, {key:1, value:10}, {key:4, value:40}]

console.log("get(2):", lru.get(2)); // 輸出：-1（已被淘汰）
console.log("get(3):", lru.get(3)); // 輸出：30
console.log("統計:", lru.getStats());
// 輸出：{ hits: 3, misses: 1, hitRate: '75.00%', size: 3, capacity: 3 }

/**
 * LFU Cache — keyMap + freqMap + minFreq
 * get / put 均為 O(1)
 *
 * 資料結構：
 *   keyMap:  key → Node（快速存取節點）
 *   freqMap: freq → DoublyLinkedList（每個頻率一個鏈結串列）
 *   minFreq: 當前最低頻率（用於快速找淘汰對象）
 */

class LFUNode<K, V> {
  key: K;
  value: V;
  freq: number = 1;
  prev: LFUNode<K, V> | null = null;
  next: LFUNode<K, V> | null = null;

  constructor(key: K, value: V) {
    this.key = key;
    this.value = value;
  }
}

class FreqList<K, V> {
  head: LFUNode<K, V>; // dummy head（最久未用端）
  tail: LFUNode<K, V>; // dummy tail（最近使用端）
  size: number = 0;

  constructor() {
    this.head = new LFUNode<K, V>(null as K, null as V);
    this.tail = new LFUNode<K, V>(null as K, null as V);
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  /** 插入到尾部（最近使用位置） */
  insertToTail(node: LFUNode<K, V>): void {
    node.prev = this.tail.prev;
    node.next = this.tail;
    this.tail.prev!.next = node;
    this.tail.prev = node;
    this.size++;
  }

  /** 移除指定節點 */
  removeNode(node: LFUNode<K, V>): void {
    node.prev!.next = node.next;
    node.next!.prev = node.prev;
    this.size--;
  }

  /** 移除並回傳頭部節點（最低頻率中最久未用的） */
  removeLRU(): LFUNode<K, V> | null {
    if (this.size === 0) return null;
    const lru = this.head.next!;
    this.removeNode(lru);
    return lru;
  }

  isEmpty(): boolean {
    return this.size === 0;
  }
}

class LFUCache<K = string, V = unknown> {
  private capacity: number;
  private currentSize: number = 0;
  private minFreq: number = 0;

  private keyMap: Map<K, LFUNode<K, V>> = new Map();
  private freqMap: Map<number, FreqList<K, V>> = new Map();

  constructor(capacity: number) {
    this.capacity = capacity;
  }

  private getOrCreateFreqList(freq: number): FreqList<K, V> {
    if (!this.freqMap.has(freq)) {
      this.freqMap.set(freq, new FreqList<K, V>());
    }
    return this.freqMap.get(freq)!;
  }

  /**
   * 將節點頻率 +1，並移到對應頻率桶的尾部
   * 這是 LFU 最核心的操作
   */
  private incrementFreq(node: LFUNode<K, V>): void {
    const oldFreq = node.freq;
    const oldList = this.freqMap.get(oldFreq)!;
    oldList.removeNode(node);

    // 若舊頻率桶空了且是最低頻率，更新 minFreq
    if (oldList.isEmpty() && oldFreq === this.minFreq) {
      this.minFreq++;
    }

    node.freq++;
    const newList = this.getOrCreateFreqList(node.freq);
    newList.insertToTail(node);
  }

  get(key: K): V | -1 {
    const node = this.keyMap.get(key);
    if (!node) return -1;

    this.incrementFreq(node); // 增加頻率
    return node.value;
  }

  put(key: K, value: V): void {
    if (this.capacity <= 0) return;

    if (this.keyMap.has(key)) {
      // 已存在：更新 value，增加頻率
      const node = this.keyMap.get(key)!;
      node.value = value;
      this.incrementFreq(node);
    } else {
      // 新增
      if (this.currentSize >= this.capacity) {
        // 淘汰：最低頻率中最久未用的節點
        const minFreqList = this.freqMap.get(this.minFreq)!;
        const evicted = minFreqList.removeLRU();
        if (evicted) {
          this.keyMap.delete(evicted.key);
          this.currentSize--;
        }
      }

      const newNode = new LFUNode(key, value);
      this.keyMap.set(key, newNode);

      // 新節點頻率為 1，minFreq 一定重置為 1
      this.minFreq = 1;
      const freqList = this.getOrCreateFreqList(1);
      freqList.insertToTail(newNode);
      this.currentSize++;
    }
  }

  get size(): number {
    return this.currentSize;
  }
}

// === 測試 ===
const lfu = new LFUCache<number, number>(2);
lfu.put(1, 10);
lfu.put(2, 20);
console.log("get(1):", lfu.get(1));  // 輸出：10（key=1 freq 變為 2）
lfu.put(3, 30);                      // 容量已滿，淘汰 freq 最低的 key=2（freq=1）
console.log("get(2):", lfu.get(2));  // 輸出：-1（已被淘汰）
console.log("get(3):", lfu.get(3));  // 輸出：30（key=3 freq 變為 2）
lfu.put(4, 40);                      // key=1 freq=2, key=3 freq=2 → 淘汰較久未用的 key=1
console.log("get(1):", lfu.get(1));  // 輸出：-1（已被淘汰）
console.log("get(3):", lfu.get(3));  // 輸出：30
console.log("get(4):", lfu.get(4));  // 輸出：40

/**
 * LRU Cache — C++ 實作
 * 使用 std::list 作為 DLL + std::unordered_map 儲存 key → iterator
 * 關鍵：splice() 在 O(1) 內移動節點而不使 iterator 失效
 */

#include <unordered_map>
#include <list>
#include <optional>
#include <iostream>
#include <mutex>
#include <shared_mutex>
#include <atomic>
#include <vector>
#include <string>

using namespace std;

template<typename K, typename V>
class LRUCache {
private:
    int capacity_;

    // list 儲存 {key, value}，front = 最近使用，back = 最久未用
    list<pair<K, V>> dll_;

    // key → list iterator，有了 iterator 就能 O(1) 操作節點
    unordered_map<K, typename list<pair<K, V>>::iterator> map_;

    mutable shared_mutex mutex_; // 讀寫鎖（允許並行讀取）

    // 統計
    mutable atomic<int64_t> hits_{0};
    mutable atomic<int64_t> misses_{0};

public:
    explicit LRUCache(int capacity) : capacity_(capacity) {
        if (capacity <= 0) {
            throw invalid_argument("Capacity must be positive");
        }
    }

    /** O(1) 查詢 */
    optional<V> get(const K& key) {
        unique_lock<shared_mutex> lock(mutex_);

        auto it = map_.find(key);
        if (it == map_.end()) {
            misses_.fetch_add(1);
            return nullopt;
        }

        hits_.fetch_add(1);

        // splice：O(1) 將節點移到 front（最近使用位置）
        // 關鍵：splice 不會使 iterator 失效
        dll_.splice(dll_.begin(), dll_, it->second);

        return it->second->second;
    }

    /** O(1) 插入或更新 */
    void put(const K& key, const V& value) {
        unique_lock<shared_mutex> lock(mutex_);

        auto it = map_.find(key);
        if (it != map_.end()) {
            // 已存在：更新 value，移到 front
            it->second->second = value;
            dll_.splice(dll_.begin(), dll_, it->second);
        } else {
            // 新增
            if (static_cast<int>(map_.size()) >= capacity_) {
                // 淘汰 back（最久未用）
                const K& evict_key = dll_.back().first;
                map_.erase(evict_key);
                dll_.pop_back();
            }
            dll_.emplace_front(key, value);
            map_[key] = dll_.begin();
        }
    }

    bool remove(const K& key) {
        unique_lock<shared_mutex> lock(mutex_);
        auto it = map_.find(key);
        if (it == map_.end()) return false;
        dll_.erase(it->second);
        map_.erase(it);
        return true;
    }

    int size() const {
        shared_lock<shared_mutex> lock(mutex_);
        return static_cast<int>(map_.size());
    }

    double hit_rate() const {
        int64_t h = hits_.load();
        int64_t m = misses_.load();
        int64_t total = h + m;
        return total == 0 ? 0.0 : static_cast<double>(h) / total;
    }

    vector<pair<K, V>> to_vector() const {
        shared_lock<shared_mutex> lock(mutex_);
        return vector<pair<K, V>>(dll_.begin(), dll_.end());
    }
};

/**
 * LFU Cache — C++ 實作
 * key_map: key → list iterator
 * freq_map: freq → list<Node>
 * min_freq: 追蹤最低頻率
 */

template<typename K, typename V>
class LFUCache {
private:
    struct Node {
        K key;
        V value;
        int freq;
        Node(K k, V v, int f = 1) : key(k), value(v), freq(f) {}
    };

    int capacity_;
    int min_freq_ = 0;

    // key → list iterator（在 freq_map[freq] 的 list 中）
    unordered_map<K, typename list<Node>::iterator> key_map_;

    // freq → DLL（front = 最近使用，back = 最久未用）
    unordered_map<int, list<Node>> freq_map_;

    mutex mutex_;

    void increment_freq(typename list<Node>::iterator& it) {
        int old_freq = it->freq;
        auto& old_list = freq_map_[old_freq];

        // 暫存 node 資料，從舊頻率桶移除
        Node node = *it;
        node.freq++;
        old_list.erase(it);

        // 若舊頻率桶空了且為 min_freq，更新
        if (old_list.empty() && old_freq == min_freq_) {
            min_freq_++;
        }

        // 插入新頻率桶的 front（最近使用）
        freq_map_[node.freq].emplace_front(node);
        key_map_[node.key] = freq_map_[node.freq].begin();
    }

public:
    explicit LFUCache(int capacity) : capacity_(capacity) {}

    optional<V> get(const K& key) {
        lock_guard<mutex> lock(mutex_);

        auto it = key_map_.find(key);
        if (it == key_map_.end()) return nullopt;

        auto list_it = it->second;
        V value = list_it->value;
        increment_freq(list_it);

        return value;
    }

    void put(const K& key, const V& value) {
        if (capacity_ <= 0) return;

        lock_guard<mutex> lock(mutex_);

        auto it = key_map_.find(key);
        if (it != key_map_.end()) {
            // 更新 value，增加頻率
            it->second->value = value;
            increment_freq(it->second);
        } else {
            // 新增：若滿則淘汰
            if (static_cast<int>(key_map_.size()) >= capacity_) {
                auto& min_list = freq_map_[min_freq_];
                const K& evict_key = min_list.back().key;
                key_map_.erase(evict_key);
                min_list.pop_back();
            }

            freq_map_[1].emplace_front(key, value, 1);
            key_map_[key] = freq_map_[1].begin();
            min_freq_ = 1;
        }
    }

    int size() const {
        return static_cast<int>(key_map_.size());
    }
};

// === 測試 ===
int main() {
    cout << "=== LRU Cache (C++) ===" << endl;

    LRUCache<int, int> lru(3);
    lru.put(1, 10);
    lru.put(2, 20);
    lru.put(3, 30);

    auto state = lru.to_vector();
    cout << "狀態 (最近→最久): ";
    for (auto& [k, v] : state) cout << k << ":" << v << " ";
    cout << endl; // 輸出：3:30 2:20 1:10

    lru.get(1); // 移到 front
    lru.put(4, 40); // 淘汰最久未用（key=2）

    state = lru.to_vector();
    cout << "get(1)+put(4) 後: ";
    for (auto& [k, v] : state) cout << k << ":" << v << " ";
    cout << endl; // 輸出：4:40 1:10 3:30

    auto v2 = lru.get(2);
    cout << "get(2): " << (v2.has_value() ? to_string(*v2) : "-1") << endl;
    // 輸出：-1（已被淘汰）

    cout << "命中率: " << lru.hit_rate() * 100 << "%" << endl;

    cout << "\n=== LFU Cache (C++) ===" << endl;

    LFUCache<int, int> lfu(2);
    lfu.put(1, 10);
    lfu.put(2, 20);

    auto r1 = lfu.get(1);
    cout << "get(1): " << (r1.has_value() ? to_string(*r1) : "-1") << endl;
    // 輸出：10

    lfu.put(3, 30); // 淘汰 freq 最低的 key=2
    auto r2 = lfu.get(2);
    cout << "get(2): " << (r2.has_value() ? to_string(*r2) : "-1") << endl;
    // 輸出：-1

    auto r3 = lfu.get(3);
    cout << "get(3): " << (r3.has_value() ? to_string(*r3) : "-1") << endl;
    // 輸出：30

    return 0;
}

// 解法：Bloom Filter + 快取空值
async function getCachedData(key: string): Promise<Data | null> {
  // 1. Bloom Filter 快速過濾不存在的 key
  if (!bloomFilter.mightExist(key)) {
    return null; // 確定不存在，不查 DB
  }

  // 2. 查快取
  const cached = await redis.get(key);
  if (cached !== null) {
    return cached === "null" ? null : JSON.parse(cached);
  }

  // 3. 查 DB
  const data = await db.query(key);

  // 4. 寫回快取（包含空值，防止重複穿透）
  if (data === null) {
    await redis.setex(key, 30, "null"); // 快取空值 30 秒
  } else {
    await redis.setex(key, 300, JSON.stringify(data));
    bloomFilter.add(key);
  }

  return data;
}

// 解法：互斥鎖（Mutex Lock）
async function getWithLock(key: string): Promise<Data | null> {
  const cached = await redis.get(key);
  if (cached !== null) return JSON.parse(cached);

  // 嘗試獲取鎖（SETNX + 5 秒過期）
  const lockKey = `lock:${key}`;
  const locked = await redis.set(lockKey, "1", { NX: true, EX: 5 });

  if (!locked) {
    // 未獲鎖：等待 100ms 後重試讀快取
    await new Promise((r) => setTimeout(r, 100));
    return getWithLock(key);
  }

  try {
    // 雙重檢查（double-check）
    const doubleCheck = await redis.get(key);
    if (doubleCheck !== null) return JSON.parse(doubleCheck);

    // 查 DB 並寫回快取
    const data = await db.query(key);
    await redis.setex(key, 300, JSON.stringify(data));
    return data;
  } finally {
    await redis.del(lockKey); // 釋放鎖
  }
}

// 解法：TTL 加隨機偏移，避免同時過期
function setWithJitter(
  key: string,
  value: string,
  baseTTL: number // 秒
): void {
  const jitter = Math.floor(Math.random() * 60); // 0~60 秒隨機偏移
  redis.setex(key, baseTTL + jitter, value);
}

# redis.conf 推薦配置
maxmemory 4gb
maxmemory-policy allkeys-lru
maxmemory-samples 10  # LRU/LFU 採樣數（越高越精確，預設 5）

/**
 * 生產就緒的多層快取服務
 * L1: 本地 LRU 快取（in-process）
 * L2: Redis 分散式快取
 * 防護：互斥鎖防擊穿 + TTL 隨機偏移防雪崩
 */
class CacheService<V> {
  private localCache: LRUCache<string, V>;
  private redis: any;
  private defaultTTL: number;

  constructor(options: {
    localCapacity: number;
    redisClient: any;
    defaultTTLSeconds: number;
  }) {
    this.localCache = new LRUCache<string, V>(options.localCapacity);
    this.redis = options.redisClient;
    this.defaultTTL = options.defaultTTLSeconds;
  }

  async get(
    key: string,
    loader: () => Promise<V | null>,
    ttl: number = this.defaultTTL
  ): Promise<V | null> {
    // L1: 本地快取
    const local = this.localCache.get(key);
    if (local !== -1) return local as V;

    // L2: Redis 快取
    const redisVal = await this.redis.get(key);
    if (redisVal !== null) {
      const parsed = JSON.parse(redisVal) as V;
      this.localCache.put(key, parsed, 60_000); // 本地 TTL 60 秒
      return parsed;
    }

    // 互斥鎖防擊穿
    const lockKey = `lock:${key}`;
    const lockAcquired = await this.redis.set(
      lockKey, "1", { NX: true, EX: 5 }
    );

    if (!lockAcquired) {
      await new Promise((resolve) => setTimeout(resolve, 100));
      return this.get(key, loader, ttl);
    }

    try {
      // Double-check
      const doubleCheck = await this.redis.get(key);
      if (doubleCheck !== null) {
        return JSON.parse(doubleCheck) as V;
      }

      // 回源載入
      const data = await loader();

      if (data === null) {
        await this.redis.setex(key, 30, "null"); // 防穿透
        return null;
      }

      // 寫入 Redis（加隨機 TTL 防雪崩）
      const jitter = Math.floor(Math.random() * 60);
      await this.redis.setex(key, ttl + jitter, JSON.stringify(data));

      // 回填本地快取
      this.localCache.put(key, data, 60_000);

      return data;
    } finally {
      await this.redis.del(lockKey);
    }
  }

  async invalidate(key: string): Promise<void> {
    this.localCache.delete(key);
    await this.redis.del(key);
  }
}