《互联网产品的 AI 架构·推理性能与成本工程》5.2 缓存分层与容量

// file: src/perf/cache-tiers.ts
// tier: L2
// verify: node --test test/perf/cache-tiers.test.ts

import { AiError } from "../core/errors.ts";

export type EvictionPolicy = "lru" | "lfu" | "fifo";

/** cluster 是“同一意图”的标注，只有语义层用它判定命中。 */
export interface CacheAccess {
  key: string;
  cluster?: string;
}

export interface LayerStats {
  capacity: number;
  hits: number;
  evictions: number;
}

interface LayerState {
  capacity: number;
  policy: EvictionPolicy;
  semantic: boolean;
  keys: Map<string, true>;
  counts: Map<string, number>;
  hits: number;
  lookups: number;
  evictions: number;
}

function fail(message: string): never {
  throw new AiError("invalid-request", `cache-tiers: ${message}`);
}

function checkAccesses(accesses: readonly CacheAccess[]): void {
  if (accesses.length === 0) fail("访问序列不能为空");
  for (const access of accesses) {
    if (access.key.trim() === "") fail("key 不能为空");
  }
}

function createState(
  capacity: number,
  policy: EvictionPolicy,
  semantic: boolean,
): LayerState {
  if (!Number.isInteger(capacity) || capacity < 0) fail("capacity 必须是非负整数");
  return {
    capacity,
    policy,
    semantic,
    keys: new Map(),
    counts: new Map(),
    hits: 0,
    lookups: 0,
    evictions: 0,
  };
}

/** 一次查找：命中返回 true；未命中时写入本层，超容量按策略淘汰。 */
function lookup(state: LayerState, access: CacheAccess): boolean {
  state.lookups += 1;
  if (state.capacity === 0) return false;
  const key = state.semantic ? (access.cluster ?? access.key) : access.key;

  if (state.policy === "lfu") {
    const count = state.counts.get(key);
    if (count !== undefined) {
      state.counts.set(key, count + 1);
      state.hits += 1;
      return true;
    }
    state.counts.set(key, 1);
    if (state.counts.size > state.capacity) {
      let victim = "";
      let lowest = Number.POSITIVE_INFINITY;
      for (const [candidate, value] of state.counts) {
        if (value < lowest) {
          victim = candidate;
          lowest = value;
        }
      }
      state.counts.delete(victim);
      state.evictions += 1;
    }
    return false;
  }

  if (state.keys.has(key)) {
    if (state.policy === "lru") {
      state.keys.delete(key);
      state.keys.set(key, true);
    }
    state.hits += 1;
    return true;
  }
  state.keys.set(key, true);
  if (state.keys.size > state.capacity) {
    const oldest = state.keys.keys().next();
    if (!oldest.done) state.keys.delete(oldest.value);
    state.evictions += 1;
  }
  return false;
}

/** 单层容量实验：同一访问序列在不同容量与淘汰策略下的命中。 */
export function simulateLayer(
  accesses: readonly CacheAccess[],
  capacity: number,
  policy: EvictionPolicy,
): LayerStats {
  checkAccesses(accesses);
  if (policy !== "lru" && policy !== "lfu" && policy !== "fifo") {
    fail(`未知淘汰策略 ${String(policy)}`);
  }
  const state = createState(capacity, policy, false);
  for (const access of accesses) lookup(state, access);
  return { capacity, hits: state.hits, evictions: state.evictions };
}

/** 一层缓存的配置。semantic 为真时按 cluster 判定，且允许配置误命中率。 */
export interface TierConfig {
  name: string;
  capacity: number;
  policy: EvictionPolicy;
  lookupMicros: number;
  serveMicros: number;
  falseHitRate: number;
  falseHitCostMicros: number;
  semantic?: boolean;
}

export interface TierReport {
  name: string;
  capacity: number;
  hits: number;
  lookups: number;
  hitRate: number;
  lookupMicros: number;
  serveMicros: number;
  expectedFalseHits: number;
  falseHitMicros: number;
}

export interface LayeredReport {
  requests: number;
  baselineMicros: number;
  totalMicros: number;
  netBenefitMicros: number;
  netPerRequestMicros: number;
  costReduction: number;
  generated: number;
  expectedFalseHits: number;
  falseHitShare: number;
  lookupPerRequestMicros: number;
  tiers: TierReport[];
}

function checkTier(tier: TierConfig): void {
  if (tier.name.trim() === "") fail("tier.name 不能为空");
  if (!Number.isInteger(tier.capacity) || tier.capacity < 0) fail("capacity 必须是非负整数");
  if (!Number.isInteger(tier.lookupMicros) || tier.lookupMicros < 0) {
    fail(`${tier.name}: lookupMicros 必须是非负整数`);
  }
  if (!Number.isInteger(tier.serveMicros) || tier.serveMicros < 0) {
    fail(`${tier.name}: serveMicros 必须是非负整数`);
  }
  if (!(tier.falseHitRate >= 0 && tier.falseHitRate <= 1)) {
    fail(`${tier.name}: falseHitRate 必须落在 [0, 1]`);
  }
  if (!Number.isInteger(tier.falseHitCostMicros) || tier.falseHitCostMicros < 0) {
    fail(`${tier.name}: falseHitCostMicros 必须是非负整数`);
  }
}

/**
 * 分层模拟：请求按顺序穿过每一层，任何一层命中就停止；
 * 只有上一层未命中的请求才会进入下一层，避免用全量流量高估下层命中。
 */
export function simulateLayered(
  accesses: readonly CacheAccess[],
  tiers: readonly TierConfig[],
  generationMicros: number,
): LayeredReport {
  checkAccesses(accesses);
  if (!Number.isInteger(generationMicros) || generationMicros < 0) {
    fail("generationMicros 必须是非负整数");
  }
  for (const tier of tiers) checkTier(tier);

  const states = tiers.map((tier) =>
    createState(tier.capacity, tier.policy, tier.semantic === true),
  );
  let totalMicros = 0;
  let lookupChargedMicros = 0;
  let generated = 0;

  for (const access of accesses) {
    let served = false;
    for (let level = 0; level < tiers.length; level += 1) {
      const tier = tiers[level];
      totalMicros += tier.lookupMicros;
      lookupChargedMicros += tier.lookupMicros;
      if (!lookup(states[level], access)) continue;
      totalMicros += tier.serveMicros;
      if (tier.falseHitRate > 0) {
        totalMicros += Math.round(tier.falseHitRate * tier.falseHitCostMicros);
      }
      served = true;
      break;
    }
    if (!served) {
      totalMicros += generationMicros;
      generated += 1;
    }
  }

  const tiersReport: TierReport[] = tiers.map((tier, index) => {
    const state = states[index];
    const expectedFalseHits = state.hits * tier.falseHitRate;
    return {
      name: tier.name,
      capacity: tier.capacity,
      hits: state.hits,
      lookups: state.lookups,
      hitRate: state.hits / accesses.length,
      lookupMicros: state.lookups * tier.lookupMicros,
      serveMicros: state.hits * tier.serveMicros,
      expectedFalseHits,
      falseHitMicros: Math.round(expectedFalseHits * tier.falseHitCostMicros),
    };
  });

  const baselineMicros = accesses.length * generationMicros;
  const expectedFalseHits = tiersReport.reduce((sum, tier) => sum + tier.expectedFalseHits, 0);
  return {
    requests: accesses.length,
    baselineMicros,
    totalMicros,
    netBenefitMicros: baselineMicros - totalMicros,
    netPerRequestMicros: (baselineMicros - totalMicros) / accesses.length,
    costReduction: baselineMicros === 0 ? 0 : (baselineMicros - totalMicros) / baselineMicros,
    generated,
    expectedFalseHits,
    falseHitShare: expectedFalseHits / accesses.length,
    lookupPerRequestMicros: lookupChargedMicros / accesses.length,
    tiers: tiersReport,
  };
}

node --test test/perf/cache-tiers.test.ts

ℹ tests 6
ℹ pass 6
ℹ fail 0
ℹ duration_ms 145.918541