缓存淘汰策略

概念定义

容量有限，缓存必须决定遗忘谁。策略编码的是对未来访问的假设：新近性假设支撑 LRU，频率假设支撑 LFU，自适应策略融合两者。

工作机制

LRU 维护新近序链表；近似 LRU 采样 N 个键淘汰最旧者，避开精确链表的争用。LFU 用带衰减的计数器让流行度会过期。分段 LRU 把缓存分为试用段与保护段：命中两次才进保护段，扫描被吸收。

使用场景

后台扫描任务碾压共享缓存、循环访问模式大于缓存容量、流行度会漂移的负载。应按键类别对比策略改动前后的命中率。

常见误区

淘汰策略只影响命中率不影响正确性——正确性属于 TTL 与失效这两个独立轴。“LRU 万能默认”会被扫描与超大工作集打脸。Redis 的 allkeys-lru 与 volatile-lru 静默改变语义：淘汰一切还是只淘汰带过期的。过键应先于淘汰压力被清除，否则容量在服务死重。小容量下策略差异是噪声，要在真实尺寸下比较。

代码示例

import { createClient } from 'redis';

const redis = createClient({ url: process.env.REDIS_URL ?? 'redis://127.0.0.1:6379' });
redis.on('error', (err) => console.error('redis:', err.message));
await redis.connect();

const TTL_SECONDS = 300;

async function cached(key, loader) {
  const hit = await redis.get(key);
  if (hit !== null) {
    await redis.incr('cache:stats:hits');
    return JSON.parse(hit);
  }
  const fresh = await loader();
  await redis.set(key, JSON.stringify(fresh), { EX: TTL_SECONDS, NX: true });
  await redis.incr('cache:stats:misses');
  return fresh;
}

async function invalidate(prefix) {
  const pattern = prefix + ':*';
  for await (const key of redis.scanIterator({ MATCH: pattern, COUNT: 200 })) {
    await redis.del(key);
  }
}

const product = await cached('product:42', () => fetchProduct(42));
await invalidate('product');
await redis.quit();

class CacheNode<K, V> {
  public previous: CacheNode<K, V> | null = null;
  public next: CacheNode<K, V> | null = null;

  public constructor(
    public readonly key: K,
    public value: V,
    public frequency: number,
  ) {}
}

class FrequencyList<K, V> {
  private head: CacheNode<K, V> | null = null;
  private tail: CacheNode<K, V> | null = null;
  public size = 0;

  public addFront(node: CacheNode<K, V>): void {
    node.previous = null;
    node.next = this.head;
    if (this.head !== null) this.head.previous = node;
    this.head = node;
    if (this.tail === null) this.tail = node;
    this.size += 1;
  }

  public remove(node: CacheNode<K, V>): void {
    if (node.previous !== null) node.previous.next = node.next;
    else this.head = node.next;
    if (node.next !== null) node.next.previous = node.previous;
    else this.tail = node.previous;
    node.previous = null;
    node.next = null;
    this.size -= 1;
  }

  public removeLast(): CacheNode<K, V> | null {
    if (this.tail === null) return null;
    const node = this.tail;
    this.remove(node);
    return node;
  }
}

export class LfuCache<K, V> {
  private readonly entries = new Map<K, CacheNode<K, V>>();
  private readonly frequencies = new Map<number, FrequencyList<K, V>>();
  private lowestFrequency = 0;

  public constructor(private readonly capacity: number) {
    if (!Number.isInteger(capacity) || capacity < 1) {
      throw new RangeError("capacity must be a positive integer");
    }
  }

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

  public get(key: K): V | undefined {
    const node = this.entries.get(key);
    if (node === undefined) return undefined;
    this.touch(node);
    return node.value;
  }

  public peek(key: K): V | undefined {
    return this.entries.get(key)?.value;
  }

  public put(key: K, value: V): this {
    const existing = this.entries.get(key);
    if (existing !== undefined) {
      existing.value = value;
      this.touch(existing);
      return this;
    }

    if (this.entries.size >= this.capacity) this.evict();
    const node = new CacheNode(key, value, 1);
    this.entries.set(key, node);
    this.listFor(1).addFront(node);
    this.lowestFrequency = 1;
    return this;
  }

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

  private touch(node: CacheNode<K, V>): void {
    const oldFrequency = node.frequency;
    const oldList = this.frequencies.get(oldFrequency);
    if (oldList === undefined) {
      throw new Error("cache invariant violated");
    }
    oldList.remove(node);
    if (oldList.size === 0) {
      this.frequencies.delete(oldFrequency);
      if (this.lowestFrequency === oldFrequency) {
        this.lowestFrequency = oldFrequency + 1;
      }
    }
    node.frequency = oldFrequency + 1;
    this.listFor(node.frequency).addFront(node);
  }

  private evict(): void {
    const list = this.frequencies.get(this.lowestFrequency);
    if (list === undefined) return;
    const node = list.removeLast();
    if (node === null) return;
    this.entries.delete(node.key);
    if (list.size === 0) this.frequencies.delete(this.lowestFrequency);
  }

  private removeNode(node: CacheNode<K, V>): void {
    const list = this.frequencies.get(node.frequency);
    if (list === undefined) {
      throw new Error("cache invariant violated");
    }
    list.remove(node);
    this.entries.delete(node.key);
    if (list.size === 0) this.frequencies.delete(node.frequency);
  }

  private listFor(frequency: number): FrequencyList<K, V> {
    let list = this.frequencies.get(frequency);
    if (list === undefined) {
      list = new FrequencyList<K, V>();
      this.frequencies.set(frequency, list);
    }
    return list;
  }
}

const cache = new LfuCache<string, number>(2);
cache.put("a", 1).put("b", 2);
console.log(cache.get("a"));
cache.put("c", 3);
console.log(cache.get("b"), cache.peek("a"), cache.get("c"));
cache.put("d", 4);
console.log(cache.get("a"), cache.get("c"), cache.get("d"));
console.log(cache.size);