LRU 缓存记录

1. Core Mechanism

LRU（Least Recently Used）是一种基于访问时序的缓存淘汰策略。核心规则：缓存容量达到上限时，淘汰最近最少被访问的条目。

策略假设：最近被访问过的数据有更高概率在近期被再次访问（temporal locality）。这个假设在翻译缓存、分页数据缓存、API 响应缓存等场景中成立，但不适用于均匀分布或随机访问模式。

淘汰决策的时间线模型：

访问序列: A → B → C → A → D  (maxSize=3)

A:     [A]           ← A 最新
B:     [A, B]        ← B 最新
C:     [A, B, C]     ← C 最新，缓存满
A:     [B, C, A]     ← A 被重新访问，移到队尾
D:     [C, A, D]     ← D 插入，B 最久未用，被淘汰

2. Implementation: Map-Based Construction

2.1 数据结构选择

ES6 Map 的迭代顺序由规范保证为插入顺序。这一特性让 Map 成为 LRU 的直接实现方式之一，插入顺序本身就可以对应访问时序，无需额外维护链表。

class LRUCache {
  constructor(maxSize) {
    this.maxSize = maxSize;
    this.cache = new Map();
  }

  get(key) {
    if (!this.cache.has(key)) return undefined;
    const value = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, value);
    return value;
  }

  put(key, value) {
    if (this.cache.has(key)) {
      this.cache.delete(key);
    } else if (this.cache.size >= this.maxSize) {
      const oldestKey = this.cache.keys().next().value;
      this.cache.delete(oldestKey);
    }
    this.cache.set(key, value);
  }
}

get 操作：delete + set 将已存在的 key 从当前位置移除并重新插入到队尾，更新其时序。

put 操作：若 key 已存在，先删除旧条目；若缓存已满，删除队头条目（最久未访问）；最后在队尾插入新条目。

哨兵值问题：get 返回 undefined 而非 -1，避免 -1 作为合法缓存值时产生歧义。若需区分"key 不存在"和"value 为 undefined"，使用 discriminated result：

type CacheResult<V> = { hit: true; value: V } | { hit: false };

2.2 Map vs Object

Object 的 key 遍历顺序在 ES2015 后虽有规范约束，但行为依赖属性类型（整数索引 key 按数值序排列，字符串 key 按插入序排列），在混合 key 类型场景下不可靠。Map 对所有 key 类型统一使用插入顺序，行为可预测。

2.3 时间复杂度

操作	稳态复杂度	退化条件
get (命中)	O(1)	rehash 时 O(N)
get (未命中)	O(1)	—
put (不淘汰)	O(1)	rehash 时 O(N)
put (淘汰)	O(1)	rehash 时 O(N)
keys().next()	O(1)	存在大量 hole 时退化

稳态下所有操作 O(1)。rehash 为 O(N)，触发条件见第 3 节。

3. Source Code Interpretation: V8 OrderedHashMap

3.1 Backing Store 结构

V8 的 Map 底层实现为 OrderedHashMap——一种确定性哈希表（deterministic hash table），将哈希桶与数据条目分离存储。

Backing store 是一块连续的 FixedArray：

┌──────────┬──────────────┬─────────────────────────────────┐
│  Header  │   Buckets    │           Entries               │
│  (3槽)   │ (2^n 个槽)   │  (capacity × 3 个槽)            │
└──────────┴──────────────┴─────────────────────────────────┘

Header slots:
  [0] numberOfElements        — 存活 entry 数量
  [1] numberOfDeletedElements — 已删除 entry（hole）数量
  [2] numberOfBuckets         — 哈希桶数量

Bucket slot:
  [i] chain_head_index        — 该桶的链头 entry 索引，-1 表示空桶

Entry slots (每组 3 个):
  [k] key                     — 键
  [k+1] value                 — 值
  [k+2] chain                 — 同桶下一个 entry 的索引，-1 表示链尾

关键设计特性：

• 查找路径（hash → bucket → chain 遍历）与遍历路径（entries 数组线性扫描）完全解耦。map.keys() 迭代走的是 entries 数组的线性扫描，跳过 hole，不经过哈希桶。
• 这一设计使得 Map 天然满足 LRU 对"按插入顺序遍历"的需求，无需像经典实现那样额外维护双向链表。

3.2 扩容与缩容规则

参数	值
初始 buckets	2
初始 capacity	4
负载因子	capacity = buckets × 2
扩容倍数	2×
扩容触发	live + deleted >= capacity
缩容触发	live < buckets / 2
64 位最大 capacity	2²⁷（≈1.34 亿 entries）

扩容序列：4 → 8 → 16 → 32 → 64 → 128 → 256 → 512 → ...

3.3 Delete 的真实行为

Map.prototype.delete(key) 不释放 entry 槽位。实现将 key 和 value 槽替换为 the_hole 哨兵，numberOfDeletedElements 递增，entry 槽位保留。Hole 仅在下一次 rehash（扩容或缩容）时被回收。

这对 LRU 的影响：

• 稳态：每次 get 触发一次 delete（产生一个 hole）+ 一次 set（在 entries 末尾追加）。只要 live + deleted < capacity，不触发 rehash，delete + set 均为 O(1)。
• hole 积累：若访问模式以 put 新 key 为主（频繁淘汰），每次 put 触发 delete + set，hole 快速积累直到 live + deleted >= capacity，触发 O(N) rehash。Rehash 时所有 hole 被一次性回收。
• 缩容条件苛刻：live < buckets / 2 意味着需要淘汰超过一半的 entry 才触发缩容。在实际 LRU 场景中（maxSize 通常接近 capacity），缩容几乎不会发生。

3.4 Capacity 500 的初始化开销

创建 new LRUCache(500) 时，Map 从 capacity=4 开始，经历 8 次 rehash 达到 capacity=512。每次 rehash 重新分配 backing store 并重哈希所有存活 entry。累计搬迁约 1020 次 entry 操作，每次 rehash 耗时 0.005-0.05ms，总初始化开销约 0.1ms。在构造函数中完成，不影响后续操作。

3.5 对象 Key 的哈希存储

Map 支持对象作为 key，V8 在对象 header 的固定偏移量处存储一个随机 32-bit hash（kObjectHashIndex），lazily generated on first use。该 hash 在对象生命周期内不变，即使对象属性被修改。

工程影响：

• 对象 key 使用引用相等性（SameValueZero）。结构相同但引用不同的两个对象被视为不同 key。
• Map 持有对象 key 的强引用，该对象及其引用链不会被 GC。在长生命周期缓存中使用对象 key 可能导致意外的内存驻留。

4. Architecture Model

4.1 系统定位

LRU 缓存在前端架构中定位为应用层与外部资源层之间的横切缓存层：

Application Layer ──→ Cache Layer ──→ External Resources
                         │
                    ┌────┴────┐
                    │ LRU     │  ← 淘汰策略可替换
                    │ TTL     │  ← 过期策略可叠加
                    │ Metrics │  ← 可观测性嵌入
                    └─────────┘

缓存层通过 get(key) → value | undefined 和 put(key, value) → void 两个纯函数式接口与上下层交互，不感知业务语义和资源类型。

4.2 与业务逻辑的解耦

耦合的写法（淘汰逻辑与 API 调用混合）：

async function fetchPage(n) {
  if (cache.has(n)) return cache.get(n);
  const data = await fetch(`/api/page/${n}`);
  if (cache.size >= 50) cache.delete(cache.keys().next().value);
  cache.set(n, data);
  return data;
}

解耦的写法（缓存层独立为高阶函数）：

function withCache(fetchFn, cache) {
  return async (key) => {
    const cached = cache.get(key);
    if (cached !== undefined) return cached;
    const result = await fetchFn(key);
    cache.put(key, result);
    return result;
  };
}

解耦后的缓存层可以独立测试、替换淘汰策略、注入监控，不影响业务调用方。

4.3 架构决策矩阵

决策	收益	代价	风险
引入 LRU 缓存层	减少外部 IO；降低 P99 延迟	内存占用；代码路径增加	命中率持续低于 30% 时净亏
Map 实现 vs 双向链表+HashMap	代码量减少 60%；规范保证顺序	依赖 V8 OrderedHashMap 实现细节	V8 内部重构可能改变性能特征（概率极低）
LRU + TTL 叠加	兼顾访问局部性和数据新鲜度	维护两套淘汰维度	策略交互 bug 排查困难
按业务分片 vs 全局共享	隔离故障域；避免互相污染	内存碎片化；总容量更大	分片热点导致部分缓存频繁淘汰
前端缓存 vs HTTP Cache-Control	细粒度控制；离线可用	手动管理失效；版本一致性需自行保证	与 HTTP 缓存不一致导致数据版本错乱

4.4 演化路径

缓存系统的演化由真实生产问题驱动，不是预先设计：

v1: 无缓存 → v2: 固定容量 LRU → v3: LRU + TTL
                                    ↓
                              v4: + 版本标记 / ETag
                                    ↓
                              v5: + IndexedDB 持久化
                                    ↓
                              v6: + 多 Tab 同步

v1→v3 覆盖绝大多数前端场景。v4+ 仅在数据一致性要求极高时（金融、实时协作）需要。

4.5 失效模式

缓存击穿（Cache Stampede）：同一 key 的并发请求在缓存 miss 后同时穿透到外部资源。缓解方案：in-flight promise map——同一 key 的第一个请求创建 promise 并缓存，后续请求复用该 promise。

const inflight = new Map();

async function cachedFetch(key) {
  const cached = cache.get(key);
  if (cached !== undefined) return cached;
  if (inflight.has(key)) return inflight.get(key);

  const promise = fetchData(key);
  inflight.set(key, promise);
  try {
    const result = await promise;
    cache.put(key, result);
    return result;
  } finally {
    inflight.delete(key);
  }
}

缓存雪崩：大量 key 在相近时间过期（TTL + LRU 场景），瞬间大量请求穿透。缓解：TTL 加随机抖动（jitter），使过期时间分散在 [TTL × 0.8, TTL × 1.2] 区间。

缓存污染（Sequential Scan Pollution）：一次性遍历产生的数据挤占缓存。例如用户顺序翻页 1→50，每页被插入后不再访问，但驱逐了真正的热数据。缓解：LRU-K（要求 K 次访问才进入缓存）或为不同访问模式使用独立缓存分片。

内存膨胀：缓存 value 引用复杂对象（闭包、DOM 节点），导致不可预期的内存占用。缓解：value 仅存储可序列化的纯数据，或对存储对象做深拷贝。

5. Runtime Behavior & Performance

5.1 帧预算分析

60fps 帧预算 16.6ms。稳态 LRU 操作耗时：

操作	典型耗时	帧预算占比
Map.has()	~0.0005ms	0.003%
get (delete + set)	~0.002ms	0.012%
keys().next() (淘汰)	~0.001ms	0.006%
rehash (capacity=512)	~0.05ms	0.3%
rehash (capacity=65536)	~3ms	18%

单个 LRU 操作对帧预算无实质影响。批量操作（如滚动加载连续 50 次 put）累计约 0.15ms，仍在安全范围内。唯一需关注的是大 capacity（>50000）场景下 rehash 可能占用 2-5ms——依然低于 50ms 的长任务阈值，但已可被性能监控捕获。

5.2 缓存命中收益模型

缓存的核心价值在减少外部 IO 延迟，而非减少 CPU 计算：

翻译缓存场景（网络 IO）：
  命中延迟：~0.002ms（Map 操作）
  未命中延迟：200-500ms（网络 + API 处理）
  收益比：~100,000x

计算缓存场景（CPU）：
  命中延迟：~0.002ms
  未命中延迟：~0.5ms（复杂格式化计算）
  收益比：~250x

对于计算缓存，LRU 的维护开销（delete + set）可能与直接重新计算的成本相当，需评估访问频率和计算成本的关系。

5.3 内存模型

Capacity=512 的 Map（对应 maxSize≈500）：

Header:     3 slots × 8 bytes = 24 bytes
Buckets:  256 slots × 8 bytes = 2,048 bytes
Entries:  512 × 3 slots × 8 bytes = 12,288 bytes
Total backing store: ~14.4 KB

Map 结构本身的物理内存占用可忽略。真正的内存压力来自 value 引用的对象。若每页 SKU 数据 50 条记录、每条 200 字节，500 页约 5MB —— 这才是 maxSize 需要约束的对象。

GC 关键点：被淘汰 entry 的 key/value 在 delete() 后立即失去 Map 的引用。若不存在外部引用，value 对象在下次 GC 时被回收。但 entry 的 hole 槽位仍在 backing store 中，直到 rehash 才回收空间——这是内部碎片，不是内存泄漏。

5.4 不适用 LRU 的场景

1. 数据量低于容量阈值：缓存 10 条数据，Map capacity=16。淘汰逻辑永远不触发，delete+set 的维护开销成为净损失。
2. 均匀分布访问模式：每个 key 访问概率相同。LRU 的 temporal locality 假设不成立，命中率趋近于随机淘汰。
3. 数据更新频率 > 访问频率：每次访问都是新 key，缓存永远 miss，put 仅在消耗内存和 CPU。

6. Production Constraints

6.1 可观测性

最小埋点集：

class LRUCache {
  constructor(maxSize) {
    this.maxSize = maxSize;
    this.cache = new Map();
    this.hits = 0;
    this.misses = 0;
    this.evictions = 0;
  }

  get(key) {
    if (!this.cache.has(key)) { this.misses++; return undefined; }
    this.hits++;
    const value = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, value);
    return value;
  }

  put(key, value) {
    if (this.cache.has(key)) {
      this.cache.delete(key);
    } else if (this.cache.size >= this.maxSize) {
      this.cache.delete(this.cache.keys().next().value);
      this.evictions++;
    }
    this.cache.set(key, value);
  }

  get hitRate() { /* hits / (hits + misses) */ }
}

三个指标足以判断缓存状态：

• hitRate < 0.3 + evictions 持续增长 → maxSize 过小或访问模式不适合 LRU
• hitRate > 0.7 + evictions 稳定 → 缓存有效工作
• hitRate 急剧下降 → 访问模式变化（可能是一次性批量请求污染了缓存）

6.2 缓存失效策略

淘汰（eviction）和失效（invalidation）是正交概念。LRU 只负责淘汰，不管数据是否过期。

失效策略分层：

1. TTL（Time-To-Live）：基于时间维度的失效。解决 80% 的时效性问题。
2. 版本标记：缓存 key 包含数据版本号（如 API 模型版本）。上游数据变更时，新 key 自动使旧缓存 miss。
3. 主动失效：上游推送失效事件，主动清除特定 key 或清空整个缓存。

6.3 问题排查顺序

当怀疑缓存导致数据异常时，按优先级排查：

1. 绕过缓存确认根因——直接请求数据源，观察问题是否消失。
2. 检查失效策略——TTL 设置、版本标记是否包含在 cache key 中。约 70% 的缓存数据问题源于失效策略不当。
3. 检查 cache key 设计——key 是否包含所有影响数据正确性的因子（API 版本、locale、feature flag）。
4. 检查淘汰频率——eviction count 是否异常增长，暗示容量不足或访问模式变化。
5. 最后审视淘汰算法——LRU vs LFU 在生产中很少成为根因，除非访问模式极为特殊。

7. Engineering Decision Summary

1. Map-based LRU 是前端场景的 pragmatically optimal 实现：代码量 25 行 vs 经典实现 60-80 行，性能等价。依赖 V8 OrderedHashMap 的插入顺序保证——该实现在 V8 中已稳定超过十年。

2. LRU 的核心价值是减少网络 IO，而非计算。若缓存的数据不涉及外部 IO，需评估缓存维护成本是否低于被缓存的计算成本。

3. maxSize 的选择依赖运行时数据：通过 hit rate 和 eviction rate 反推合理容量。没有先验公式。初始值可按以下经验设定：翻译缓存 200-1000，分页数据 20-100 页，API 响应 50-500 条。

4. 失效策略比淘汰策略更重要：生产中遇到的数据一致性问题，根因在失效不在淘汰。优先投入 TTL 和版本标记，淘汰算法的优化是最后一步。

5. 缓存抽象优于缓存实现：withCache 模式将缓存层与业务逻辑解耦，允许后续替换淘汰策略、叠加失效层、注入监控，不影响调用方。

6. 不是所有场景都需要缓存：数据量小、更新频繁、访问模式均匀分布的场景下，缓存是净开销。判断"不需要缓存"与判断"需要缓存"同等重要。