1.1 为什么需要缓存？

存储层次结构的现实：

CPU寄存器:   ~0.5ns    极小容量
L1 Cache:    ~1ns      KB级别
L2 Cache:    ~4ns      MB级别
L3 Cache:    ~10ns     数十MB
内存:        ~100ns    GB级别
SSD:         ~100μs    TB级别
HDD:         ~10ms     TB级别
网络存储:    ~100ms    PB级别

速度差距高达8个数量级！缓存是弥合这一鸿沟的关键。

1.2 缓存的基本原理

局部性原理（Locality）：

1. 时间局部性：刚访问的数据很可能再次被访问
2. 空间局部性：相邻的数据很可能一起被访问

// 时间局部性示例
const config = getConfig(); // 第一次慢
const config2 = getConfig(); // 应该从缓存读取

// 空间局部性示例
const user = getUser(123);
const posts = getUserPosts(123); // 可以预取
const friends = getUserFriends(123); // 可以预取

2.1 FIFO（先进先出）

最简单的策略：最早进入的数据最先被驱逐。

class FIFOCache<K, V> {
  private cache = new Map<K, V>();
  private queue: K[] = [];
  
  constructor(private capacity: number) {}
  
  get(key: K): V | undefined {
    return this.cache.get(key);
  }
  
  set(key: K, value: V): void {
    if (this.cache.has(key)) {
      // 已存在，更新值
      this.cache.set(key, value);
      return;
    }
    
    if (this.cache.size >= this.capacity) {
      // 满了，驱逐最早的
      const oldest = this.queue.shift()!;
      this.cache.delete(oldest);
    }
    
    this.cache.set(key, value);
    this.queue.push(key);
  }
}

// 使用示例
const cache = new FIFOCache<string, number>(3);
cache.set('a', 1);
cache.set('b', 2);
cache.set('c', 3);
cache.set('d', 4); // 驱逐 'a'

console.log(cache.get('a')); // undefined
console.log(cache.get('b')); // 2

问题：不考虑访问频率，可能驱逐热点数据。

2.2 LRU（最近最少使用）

驱逐最久未被访问的数据。

class LRUCache<K, V> {
  private cache = new Map<K, V>();
  
  constructor(private capacity: number) {}
  
  get(key: K): V | undefined {
    if (!this.cache.has(key)) {
      return undefined;
    }
    
    // 移动到最新位置（Map的插入顺序）
    const value = this.cache.get(key)!;
    this.cache.delete(key);
    this.cache.set(key, value);
    
    return value;
  }
  
  set(key: K, value: V): void {
    if (this.cache.has(key)) {
      // 已存在，删除旧的
      this.cache.delete(key);
    } else if (this.cache.size >= this.capacity) {
      // 满了，驱逐最久未使用的（Map的第一个）
      const oldest = this.cache.keys().next().value;
      this.cache.delete(oldest);
    }
    
    this.cache.set(key, value);
  }
}

// 使用
const lru = new LRUCache<string, number>(3);
lru.set('a', 1);
lru.set('b', 2);
lru.set('c', 3);
lru.get('a');      // 访问a，a变成最新
lru.set('d', 4);   // 驱逐b（最久未使用）

console.log(lru.get('b')); // undefined
console.log(lru.get('a')); // 1

优势：简单高效，适应大多数访问模式
问题：一次性扫描会污染缓存

2.3 LFU（最不经常使用）

驱逐访问频率最低的数据。

class LFUCache<K, V> {
  private cache = new Map<K, { value: V; freq: number; time: number }>();
  private minFreq = 0;
  private time = 0;
  
  constructor(private capacity: number) {}
  
  get(key: K): V | undefined {
    const item = this.cache.get(key);
    if (!item) return undefined;
    
    // 增加频率
    item.freq++;
    item.time = this.time++;
    
    return item.value;
  }
  
  set(key: K, value: V): void {
    if (this.capacity === 0) return;
    
    if (this.cache.has(key)) {
      const item = this.cache.get(key)!;
      item.value = value;
      item.freq++;
      item.time = this.time++;
      return;
    }
    
    if (this.cache.size >= this.capacity) {
      // 找到频率最低的项
      let minFreq = Infinity;
      let minKey: K | null = null;
      let minTime = Infinity;
      
      for (const [k, item] of this.cache.entries()) {
        if (item.freq < minFreq || (item.freq === minFreq && item.time < minTime)) {
          minFreq = item.freq;
          minKey = k;
          minTime = item.time;
        }
      }
      
      if (minKey !== null) {
        this.cache.delete(minKey);
      }
    }
    
    this.cache.set(key, { value, freq: 1, time: this.time++ });
  }
}

优势：保护热点数据
问题：

• 早期热点可能永久占据缓存
• 维护频率计数器的开销

2.4 LRU vs LFU：访问模式的哲学

// LRU适合的场景：时间局部性强
const accessPattern1 = ['A', 'B', 'C', 'A', 'B', 'C', 'A', 'B', 'C'];
// A、B、C都是热点，LRU表现好

// LFU适合的场景：频率差异大
const accessPattern2 = ['A', 'A', 'A', 'B', 'C', 'D', 'A', 'A', 'E'];
// A是绝对热点，LFU会保护它

// 两者都不理想的场景：周期性访问
const accessPattern3 = ['A', 'B', 'C', 'D', 'E', 'A', 'B', 'C', 'D', 'E'];
// 缓存大小<5时，命中率都很低

3.1 ARC（自适应替换缓存）

IBM发明的专利算法，结合LRU和LFU的优势。

核心思想：维护两个LRU列表

• T1：只访问过一次的数据（LRU）
• T2：访问过多次的数据（LRU）

class ARCCache<K, V> {
  private t1 = new Map<K, V>();     // 最近访问一次
  private t2 = new Map<K, V>();     // 最近访问多次
  private b1 = new Set<K>();         // T1的幽灵列表
  private b2 = new Set<K>();         // T2的幽灵列表
  private p = 0;                     // T1的目标大小
  
  constructor(private capacity: number) {}
  
  get(key: K): V | undefined {
    if (this.t1.has(key)) {
      // 从T1移到T2（从一次变多次）
      const value = this.t1.get(key)!;
      this.t1.delete(key);
      this.t2.set(key, value);
      return value;
    }
    
    if (this.t2.has(key)) {
      // 已在T2，移到最新位置
      const value = this.t2.get(key)!;
      this.t2.delete(key);
      this.t2.set(key, value);
      return value;
    }
    
    return undefined;
  }
  
  set(key: K, value: V): void {
    if (this.t1.has(key) || this.t2.has(key)) {
      // 已存在，更新
      if (this.t1.has(key)) {
        this.t1.delete(key);
        this.t2.set(key, value);
      } else {
        this.t2.delete(key);
        this.t2.set(key, value);
      }
      return;
    }
    
    // 新数据
    if (this.b1.has(key)) {
      // 在B1中，说明T1太小了，增加p
      this.p = Math.min(this.capacity, this.p + 1);
      this.replace(key, true);
      this.b1.delete(key);
      this.t2.set(key, value);
      return;
    }
    
    if (this.b2.has(key)) {
      // 在B2中，说明T1太大了，减小p
      this.p = Math.max(0, this.p - 1);
      this.replace(key, false);
      this.b2.delete(key);
      this.t2.set(key, value);
      return;
    }
    
    // 完全新的数据
    const totalSize = this.t1.size + this.t2.size;
    if (totalSize >= this.capacity) {
      this.replace(key, false);
    }
    
    this.t1.set(key, value);
  }
  
  private replace(key: K, inB1: boolean): void {
    if (this.t1.size > 0 && (this.t1.size > this.p || (inB1 && this.t1.size === this.p))) {
      // 从T1驱逐
      const oldest = this.t1.keys().next().value;
      this.t1.delete(oldest);
      this.b1.add(oldest);
    } else {
      // 从T2驱逐
      const oldest = this.t2.keys().next().value;
      this.t2.delete(oldest);
      this.b2.add(oldest);
    }
  }
}

优势：自动调整策略，适应访问模式变化
问题：实现复杂，专利限制

3.2 TinyLFU：Caffeine的核心

Caffeine（Java高性能缓存库）使用的算法。

核心思想：

1. 使用Count-Min Sketch近似统计频率（节省内存）
2. 使用Window LRU + Segmented LRU分层存储
3. 新数据必须比被驱逐数据更"热"才能进入

class CountMinSketch {
  private counters: Uint8Array[];
  private depth = 4;
  private width = 1024;
  
  constructor() {
    this.counters = Array.from({ length: this.depth }, 
      () => new Uint8Array(this.width)
    );
  }
  
  increment(key: string): void {
    for (let i = 0; i < this.depth; i++) {
      const hash = this.hash(key, i) % this.width;
      if (this.counters[i][hash] < 255) {
        this.counters[i][hash]++;
      }
    }
  }
  
  estimate(key: string): number {
    let min = 255;
    for (let i = 0; i < this.depth; i++) {
      const hash = this.hash(key, i) % this.width;
      min = Math.min(min, this.counters[i][hash]);
    }
    return min;
  }
  
  private hash(str: string, seed: number): number {
    let hash = seed;
    for (let i = 0; i < str.length; i++) {
      hash = ((hash << 5) - hash) + str.charCodeAt(i);
      hash = hash & hash; // Convert to 32-bit integer
    }
    return Math.abs(hash);
  }
}

class TinyLFUCache<K, V> {
  private windowCache = new Map<K, V>();      // 1% 容量
  private probationCache = new Map<K, V>();   // 79% 容量
  private protectedCache = new Map<K, V>();   // 20% 容量
  private sketch = new CountMinSketch();
  
  constructor(private capacity: number) {}
  
  get(key: K): V | undefined {
    // 记录访问
    this.sketch.increment(String(key));
    
    if (this.windowCache.has(key)) {
      return this.windowCache.get(key);
    }
    
    if (this.probationCache.has(key)) {
      // 从试用区提升到保护区
      const value = this.probationCache.get(key)!;
      this.probationCache.delete(key);
      
      if (this.protectedCache.size >= this.capacity * 0.2) {
        // 保护区满了，降级一个到试用区
        const demoted = this.protectedCache.keys().next().value;
        const demotedValue = this.protectedCache.get(demoted)!;
        this.protectedCache.delete(demoted);
        this.probationCache.set(demoted, demotedValue);
      }
      
      this.protectedCache.set(key, value);
      return value;
    }
    
    if (this.protectedCache.has(key)) {
      // 已在保护区，刷新位置
      const value = this.protectedCache.get(key)!;
      this.protectedCache.delete(key);
      this.protectedCache.set(key, value);
      return value;
    }
    
    return undefined;
  }
  
  set(key: K, value: V): void {
    this.sketch.increment(String(key));
    
    // 先放入窗口缓存
    if (this.windowCache.size >= this.capacity * 0.01) {
      // 窗口满了，移到试用区
      const oldest = this.windowCache.keys().next().value;
      const oldestValue = this.windowCache.get(oldest)!;
      this.windowCache.delete(oldest);
      
      // TinyLFU门禁：比较频率
      if (this.probationCache.size >= this.capacity * 0.79) {
        const victim = this.probationCache.keys().next().value;
        
        if (this.sketch.estimate(String(oldest)) > this.sketch.estimate(String(victim))) {
          // 新数据更热，驱逐受害者
          this.probationCache.delete(victim);
          this.probationCache.set(oldest, oldestValue);
        }
        // 否则，直接丢弃oldest
      } else {
        this.probationCache.set(oldest, oldestValue);
      }
    }
    
    this.windowCache.set(key, value);
  }
}

优势：

• 扫描抵抗性强（一次性访问不会污染）
• 内存效率高（Count-Min Sketch）
• 高命中率

3.3 W-TinyLFU：窗口化TinyLFU

Caffeine实际使用的改进版本。

改进点：

1. 窗口缓存（Window Cache）：捕获突发流量
2. 主缓存（Main Cache）：分为试用区和保护区
3. 频率衰减：定期重置计数器，适应长期模式变化

class WTinyLFU<K, V> {
  private windowSize: number;
  private mainSize: number;
  private protectedRatio = 0.8;
  
  private window = new Map<K, V>();
  private probation = new Map<K, V>();
  private protected = new Map<K, V>();
  
  private sketch = new CountMinSketch();
  private sampleSize = 0;
  private resetThreshold: number;
  
  constructor(capacity: number) {
    this.windowSize = Math.max(1, Math.floor(capacity * 0.01));
    this.mainSize = capacity - this.windowSize;
    this.resetThreshold = capacity * 10; // 每10*capacity次访问重置
  }
  
  get(key: K): V | undefined {
    this.recordAccess(key);
    
    // 按优先级查找：protected > probation > window
    if (this.protected.has(key)) {
      const value = this.protected.get(key)!;
      this.moveToMRU(this.protected, key, value);
      return value;
    }
    
    if (this.probation.has(key)) {
      const value = this.probation.get(key)!;
      this.promote(key, value);
      return value;
    }
    
    if (this.window.has(key)) {
      return this.window.get(key);
    }
    
    return undefined;
  }
  
  set(key: K, value: V): void {
    this.recordAccess(key);
    
    if (this.window.has(key) || this.probation.has(key) || this.protected.has(key)) {
      // 更新现有值
      this.window.delete(key);
      this.probation.delete(key);
      this.protected.delete(key);
    }
    
    // 插入窗口缓存
    if (this.window.size >= this.windowSize) {
      this.evictFromWindow();
    }
    
    this.window.set(key, value);
  }
  
  private recordAccess(key: K): void {
    this.sketch.increment(String(key));
    this.sampleSize++;
    
    if (this.sampleSize >= this.resetThreshold) {
      this.reset();
    }
  }
  
  private evictFromWindow(): void {
    // 从窗口移到主缓存
    const [key, value] = this.window.entries().next().value;
    this.window.delete(key);
    
    const protectedSize = Math.floor(this.mainSize * this.protectedRatio);
    
    if (this.probation.size + this.protected.size < this.mainSize) {
      this.probation.set(key, value);
    } else {
      // 主缓存满了，使用TinyLFU门禁
      const victim = this.probation.keys().next().value;
      const candidateFreq = this.sketch.estimate(String(key));
      const victimFreq = this.sketch.estimate(String(victim));
      
      if (candidateFreq > victimFreq) {
        this.probation.delete(victim);
        this.probation.set(key, value);
      }
    }
  }
  
  private promote(key: K, value: V): void {
    this.probation.delete(key);
    
    const protectedSize = Math.floor(this.mainSize * this.protectedRatio);
    
    if (this.protected.size >= protectedSize) {
      // 保护区满了，降级一个
      const [demotedKey, demotedValue] = this.protected.entries().next().value;
      this.protected.delete(demotedKey);
      this.probation.set(demotedKey, demotedValue);
    }
    
    this.protected.set(key, value);
  }
  
  private moveToMRU(map: Map<K, V>, key: K, value: V): void {
    map.delete(key);
    map.set(key, value);
  }
  
  private reset(): void {
    // 频率衰减：所有计数减半
    this.sketch = new CountMinSketch();
    this.sampleSize = 0;
  }
}

性能数据（相比LRU）：

• 命中率提升：10-20%
• CPU开销：增加 <5%
• 内存开销：增加 ~1%

4.1 Redis的缓存策略

Redis支持多种驱逐策略：

# redis.conf

# maxmemory <bytes>
maxmemory 2gb

# maxmemory-policy
# - noeviction: 内存满时拒绝写入
# - allkeys-lru: 对所有key使用LRU
# - volatile-lru: 只对设置了TTL的key使用LRU
# - allkeys-random: 随机驱逐
# - volatile-random: 随机驱逐有TTL的key
# - volatile-ttl: 驱逐最接近过期的key
# - allkeys-lfu: 对所有key使用LFU
# - volatile-lfu: 只对有TTL的key使用LFU

maxmemory-policy allkeys-lru

# LFU相关配置
lfu-log-factor 10      # 对数递减因子
lfu-decay-time 1       # 衰减时间（分钟）

Redis LFU实现：

// Redis源码简化版
typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:24;  // LRU时间或LFU数据
    int refcount;
    void *ptr;
} robj;

// LFU使用24位：
// 高16位：最后递减时间
// 低8位：对数计数器

uint8_t LFULogIncr(uint8_t counter) {
    if (counter == 255) return 255;
    double r = (double)rand() / RAND_MAX;
    double baseval = counter - LFU_INIT_VAL;
    if (baseval < 0) baseval = 0;
    double p = 1.0 / (baseval * server.lfu_log_factor + 1);
    if (r < p) counter++;
    return counter;
}

对数计数器：访问次数越多，增长越慢

• 5次访问 → 计数5
• 10次访问 → 计数6
• 100次访问 → 计数10

4.2 多层缓存架构

interface CacheLayer {
  get(key: string): Promise<any>;
  set(key: string, value: any, ttl?: number): Promise<void>;
}

class L1Cache implements CacheLayer {
  private cache = new WTinyLFU<string, any>(1000);
  
  async get(key: string): Promise<any> {
    return this.cache.get(key);
  }
  
  async set(key: string, value: any): Promise<void> {
    this.cache.set(key, value);
  }
}

class L2Cache implements CacheLayer {
  constructor(private redis: RedisClient) {}
  
  async get(key: string): Promise<any> {
    const value = await this.redis.get(key);
    return value ? JSON.parse(value) : undefined;
  }
  
  async set(key: string, value: any, ttl = 3600): Promise<void> {
    await this.redis.setex(key, ttl, JSON.stringify(value));
  }
}

class MultiLayerCache {
  private l1 = new L1Cache();
  private l2: L2Cache;
  
  constructor(redis: RedisClient) {
    this.l2 = new L2Cache(redis);
  }
  
  async get(key: string): Promise<any> {
    // L1查找
    let value = await this.l1.get(key);
    if (value !== undefined) {
      return value;
    }
    
    // L2查找
    value = await this.l2.get(key);
    if (value !== undefined) {
      // 回填L1
      await this.l1.set(key, value);
      return value;
    }
    
    return undefined;
  }
  
  async set(key: string, value: any, ttl?: number): Promise<void> {
    // 写入两层
    await Promise.all([
      this.l1.set(key, value),
      this.l2.set(key, value, ttl)
    ]);
  }
}

4.3 一致性哈希与缓存分片

class ConsistentHash {
  private ring = new Map<number, string>();
  private sortedKeys: number[] = [];
  private virtualNodes = 150; // 每个节点150个虚拟节点
  
  addNode(node: string): void {
    for (let i = 0; i < this.virtualNodes; i++) {
      const hash = this.hash(`${node}:${i}`);
      this.ring.set(hash, node);
    }
    this.sortedKeys = Array.from(this.ring.keys()).sort((a, b) => a - b);
  }
  
  removeNode(node: string): void {
    for (let i = 0; i < this.virtualNodes; i++) {
      const hash = this.hash(`${node}:${i}`);
      this.ring.delete(hash);
    }
    this.sortedKeys = Array.from(this.ring.keys()).sort((a, b) => a - b);
  }
  
  getNode(key: string): string | undefined {
    if (this.ring.size === 0) return undefined;
    
    const hash = this.hash(key);
    
    // 二分查找第一个 >= hash的节点
    let left = 0, right = this.sortedKeys.length - 1;
    
    while (left < right) {
      const mid = Math.floor((left + right) / 2);
      if (this.sortedKeys[mid] < hash) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }
    
    const nodeHash = this.sortedKeys[left];
    return this.ring.get(nodeHash);
  }
  
  private hash(str: string): number {
    // 简化的哈希函数
    let hash = 0;
    for (let i = 0; i < str.length; i++) {
      hash = ((hash << 5) - hash) + str.charCodeAt(i);
      hash = hash & hash;
    }
    return Math.abs(hash);
  }
}

class DistributedCache {
  private consistentHash = new ConsistentHash();
  private nodes = new Map<string, RedisClient>();
  
  addNode(name: string, client: RedisClient): void {
    this.nodes.set(name, client);
    this.consistentHash.addNode(name);
  }
  
  async get(key: string): Promise<any> {
    const node = this.consistentHash.getNode(key);
    if (!node) throw new Error('No nodes available');
    
    const client = this.nodes.get(node);
    return await client?.get(key);
  }
  
  async set(key: string, value: any): Promise<void> {
    const node = this.consistentHash.getNode(key);
    if (!node) throw new Error('No nodes available');
    
    const client = this.nodes.get(node);
    await client?.set(key, value);
  }
}

5.1 缓存雪崩（Cache Avalanche）

问题：大量缓存同时失效，请求直击数据库

// ❌ 所有缓存同时过期
cache.set('user:1', user1, 3600);
cache.set('user:2', user2, 3600);
cache.set('user:3', user3, 3600);
// 1小时后全部失效！

// ✅ 添加随机抖动
function setWithJitter(key: string, value: any, baseTTL: number): void {
  const jitter = Math.random() * baseTTL * 0.1; // ±10%
  const ttl = baseTTL + jitter;
  cache.set(key, value, ttl);
}

5.2 缓存穿透（Cache Penetration）

问题：查询不存在的数据，缓存和数据库都没有

// ✅ 布隆过滤器
class BloomFilter {
  private bits: Uint8Array;
  private size: number;
  private hashCount = 3;
  
  constructor(size: number) {
    this.size = size;
    this.bits = new Uint8Array(Math.ceil(size / 8));
  }
  
  add(item: string): void {
    for (let i = 0; i < this.hashCount; i++) {
      const index = this.hash(item, i) % this.size;
      const byteIndex = Math.floor(index / 8);
      const bitIndex = index % 8;
      this.bits[byteIndex] |= (1 << bitIndex);
    }
  }
  
  mightContain(item: string): boolean {
    for (let i = 0; i < this.hashCount; i++) {
      const index = this.hash(item, i) % this.size;
      const byteIndex = Math.floor(index / 8);
      const bitIndex = index % 8;
      if ((this.bits[byteIndex] & (1 << bitIndex)) === 0) {
        return false;
      }
    }
    return true; // 可能存在（有误报，无漏报）
  }
  
  private hash(str: string, seed: number): number {
    let hash = seed;
    for (let i = 0; i < str.length; i++) {
      hash = ((hash << 5) - hash) + str.charCodeAt(i);
    }
    return Math.abs(hash);
  }
}

// 使用
const bloom = new BloomFilter(10000);
// 启动时加载所有有效key
await loadAllKeysIntoBloom(bloom);

async function getData(key: string) {
  if (!bloom.mightContain(key)) {
    return null; // 肯定不存在，直接返回
  }
  
  // 可能存在，查缓存和数据库
  let data = await cache.get(key);
  if (!data) {
    data = await db.get(key);
    if (data) {
      await cache.set(key, data);
    }
  }
  return data;
}

5.3 缓存击穿（Cache Breakdown）

问题：热点key失效，大量并发请求直击数据库

// ✅ 互斥锁
class CacheWithMutex {
  private locks = new Map<string, Promise<any>>();
  
  async get(key: string): Promise<any> {
    let value = await cache.get(key);
    if (value !== undefined) {
      return value;
    }
    
    // 获取或创建锁
    let lock = this.locks.get(key);
    if (lock) {
      // 等待其他请求完成
      return await lock;
    }
    
    // 创建新锁
    lock = this.fetchAndCache(key);
    this.locks.set(key, lock);
    
    try {
      value = await lock;
      return value;
    } finally {
      this.locks.delete(key);
    }
  }
  
  private async fetchAndCache(key: string): Promise<any> {
    const value = await db.get(key);
    if (value) {
      await cache.set(key, value, 3600);
    }
    return value;
  }
}

6.1 预测性预取

class PredictivePrefetcher {
  private accessPatterns = new Map<string, string[]>();
  private windowSize = 10;
  
  recordAccess(key: string, nextKeys: string[]): void {
    if (!this.accessPatterns.has(key)) {
      this.accessPatterns.set(key, []);
    }
    
    const pattern = this.accessPatterns.get(key)!;
    pattern.push(...nextKeys);
    
    // 保持窗口大小
    if (pattern.length > this.windowSize) {
      pattern.splice(0, pattern.length - this.windowSize);
    }
  }
  
  predict(key: string): string[] {
    const pattern = this.accessPatterns.get(key);
    if (!pattern || pattern.length === 0) return [];
    
    // 统计频率
    const frequency = new Map<string, number>();
    pattern.forEach(k => {
      frequency.set(k, (frequency.get(k) || 0) + 1);
    });
    
    // 返回频率最高的3个
    return Array.from(frequency.entries())
      .sort((a, b) => b[1] - a[1])
      .slice(0, 3)
      .map(([k]) => k);
  }
  
  async prefetch(key: string): Promise<void> {
    const predictions = this.predict(key);
    
    // 异步预取
    predictions.forEach(async (predictedKey) => {
      const cached = await cache.get(predictedKey);
      if (!cached) {
        const value = await db.get(predictedKey);
        if (value) {
          await cache.set(predictedKey, value);
        }
      }
    });
  }
}

6.2 机器学习驱动的缓存

interface CacheAccessLog {
  key: string;
  timestamp: number;
  hitRate: number;
  size: number;
}

class MLCache {
  private model: any; // 简化的ML模型
  private logs: CacheAccessLog[] = [];
  
  async shouldCache(key: string, value: any): Promise<boolean> {
    const features = this.extractFeatures(key, value);
    const score = await this.model.predict(features);
    
    return score > 0.5; // 预测命中率阈值
  }
  
  private extractFeatures(key: string, value: any): number[] {
    return [
      this.getKeyPopularity(key),      // 历史访问频率
      this.getTimeOfDay(),             // 时间特征
      this.getValueSize(value),        // 数据大小
      this.getCurrentCacheLoad(),      // 当前缓存负载
      this.getSeasonality(key),        // 周期性
    ];
  }
  
  private getKeyPopularity(key: string): number {
    const recent = this.logs.filter(l => 
      l.key === key && Date.now() - l.timestamp < 3600000
    );
    return recent.length;
  }
  
  private getTimeOfDay(): number {
    const hour = new Date().getHours();
    return hour / 24; // 归一化到[0,1]
  }
  
  private getValueSize(value: any): number {
    const size = JSON.stringify(value).length;
    return Math.log(size) / 10; // 对数缩放
  }
  
  private getCurrentCacheLoad(): number {
    // 返回当前缓存使用率
    return 0.5; // 简化
  }
  
  private getSeasonality(key: string): number {
    // 检测周期性访问模式
    return 0; // 简化
  }
}

7.1 关键指标

class CacheMetrics {
  private hits = 0;
  private misses = 0;
  private evictions = 0;
  private totalLatency = 0;
  private requests = 0;
  
  recordHit(latency: number): void {
    this.hits++;
    this.requests++;
    this.totalLatency += latency;
  }
  
  recordMiss(latency: number): void {
    this.misses++;
    this.requests++;
    this.totalLatency += latency;
  }
  
  recordEviction(): void {
    this.evictions++;
  }
  
  getMetrics() {
    return {
      hitRate: this.hits / (this.hits + this.misses),
      missRate: this.misses / (this.hits + this.misses),
      avgLatency: this.totalLatency / this.requests,
      evictionRate: this.evictions / this.requests
    };
  }
  
  // 导出Prometheus格式
  toPrometheus(): string {
    return `
# HELP cache_hits_total Total number of cache hits
# TYPE cache_hits_total counter
cache_hits_total ${this.hits}

# HELP cache_misses_total Total number of cache misses
# TYPE cache_misses_total counter
cache_misses_total ${this.misses}

# HELP cache_hit_rate Current cache hit rate
# TYPE cache_hit_rate gauge
cache_hit_rate ${this.hits / (this.hits + this.misses)}
    `.trim();
  }
}

7.2 自适应TTL

class AdaptiveTTL {
  private baselineTTL = 3600;
  private hitRates = new Map<string, number>();
  
  calculateTTL(key: string): number {
    const hitRate = this.hitRates.get(key) || 0;
    
    if (hitRate > 0.8) {
      // 高命中率：延长TTL
      return this.baselineTTL * 2;
    } else if (hitRate < 0.2) {
      // 低命中率：缩短TTL
      return this.baselineTTL * 0.5;
    }
    
    return this.baselineTTL;
  }
  
  updateHitRate(key: string, hit: boolean): void {
    const current = this.hitRates.get(key) || 0.5;
    // 指数移动平均
    const alpha = 0.1;
    const newRate = alpha * (hit ? 1 : 0) + (1 - alpha) * current;
    this.hitRates.set(key, newRate);
  }
}

核心洞察

1. 没有银弹：不同访问模式需要不同策略
2. 空间换时间：但空间也是有成本的
3. 预测vs准确：近似算法往往更高效
4. 局部性原理：时间和空间局部性是缓存的基石
5. 监控驱动优化：数据比直觉更可靠

算法选择指南

设计原则

1. 测量先于优化：了解访问模式
2. 分层思考：L1/L2/L3各司其职
3. 故障隔离：缓存不可用不应拖垮系统
4. 合理TTL：过期策略比驱逐策略更重要
5. 监控告警：命中率、延迟、内存使用

最重要的认知：缓存不是简单的键值存储，而是一个需要持续调优的复杂系统。理解你的访问模式，选择合适的策略，持续监控和优化，才能发挥缓存的最大价值。