LRU Cache 实现与应用：从基础数据结构到生产级缓存方案

当你的应用第三次请求同一个 API 却再次等待 800ms 响应时，你就会意识到：没有缓存的系统就是在烧钱。根据 Vercel 2025 年的性能报告，合理使用客户端缓存可以将页面加载时间降低 40%-60%，API 调用成本减少 50% 以上。LRU（Least Recently Used，最近最少使用）缓存是所有缓存策略中最经典、应用最广泛的算法——从浏览器 HTTP 缓存到 Redis 内存淘汰，从 React 的 useMemo 到 CDN 的内容置换，LRU 无处不在。

本文不会停留在「告诉你 LRU 是什么」的层面。我们将用 JavaScript/TypeScript 从零实现三种不同复杂度的 LRU Cache，对比它们的性能差异，然后扩展到 TTL 过期、WeakRef 弱引用缓存、多级缓存等生产级模式，最后给出完整的基准测试数据和选型建议。

🧩 一、LRU 原理与三种实现方式

1.1 LRU 的核心思想

LRU 的淘汰策略很简单：当缓存空间满了，优先移除「最久没有被访问」的数据项。这基于一个合理的假设——最近被访问的数据，近期被再次访问的概率更高（时间局部性，Temporal Locality）。

要实现 LRU，数据结构需要同时满足两个操作的 O(1) 时间复杂度：

• ✅ 查找（get）：快速判断 key 是否存在，命中则返回 value
• ✅ 插入/更新（put）：快速写入或更新 key-value，满了则淘汰最久未访问的项

📌 记住： 单独的 HashMap 或双向链表都无法同时满足这两个要求。HashMap 查找是 O(1) 但无法维护访问顺序；双向链表维护顺序但查找是 O(n)。LRU 的经典实现就是将两者结合——HashMap + 双向链表。

1.2 方案一：基于 Map 的简洁实现（利用 Map 的插入序）

JavaScript 的 Map 对象天然维护键的插入顺序，且在 ES6+ 规范中，当你 get 一个已存在的 key 时，该 key 会被移到迭代顺序的末尾。这意味着我们可以用极简的代码实现一个功能正确的 LRU Cache：

// 方案一：基于 Map 的 LRU Cache —— 最简洁实现，利用 Map 的有序性
class SimpleLRUCache {
  constructor(maxSize) {
    this.maxSize = maxSize
    this.cache = new Map()
  }

  get(key) {
    if (!this.cache.has(key)) return undefined
    // 重新 set 来将 key 移到 Map 迭代末尾（最近使用位置）
    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) {
      // Map.keys().next() 返回最早插入的 key（最久未使用）
      const oldestKey = this.cache.keys().next().value
      this.cache.delete(oldestKey)
    }
    this.cache.set(key, value)
  }

  get size() {
    return this.cache.size
  }
}

// 使用示例
const cache = new SimpleLRUCache(3)
cache.put('a', 1)
cache.put('b', 2)
cache.put('c', 3)
cache.get('a')       // 访问 'a'，移到最近使用
cache.put('d', 4)    // 缓存满，淘汰 'b'（最久未访问）
console.log(cache.get('b'))  // undefined — 已被淘汰
console.log(cache.get('a'))  // 1 — 还在

⚠️ 警告： 这个实现中 get 方法先 delete 再 set，是为了利用 Map 的迭代顺序特性。虽然 V8 引擎对 Map 的 get 会自动更新访问序，但这不是规范保证的行为。在需要严格跨引擎兼容的场景下，显式 delete+set 更安全。

这个方案的性能瓶颈在于 get 操作中的 delete + set——虽然都是 O(1)，但涉及两次 Map 内部操作和一次 GC 压力（临时迭代器）。对于小容量缓存（<100 项），这完全可接受。

1.3 方案二：HashMap + 双向链表（经典教科书实现）

如果你需要精确控制缓存行为、添加 TTL 等高级特性，就需要手动实现双向链表：

// 方案二：HashMap + 双向链表 —— 经典 LRU 实现，完整 TypeScript 类型
class DLinkedNode<K, V> {
  key: K
  value: V
  prev: DLinkedNode<K, V> | null = null
  next: DLinkedNode<K, V> | null = null

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

class LRUCache<K, V> {
  private map = new Map<K, DLinkedNode<K, V>>()
  private head: DLinkedNode<K, V>  // 哨兵头节点（dummy head）
  private tail: DLinkedNode<K, V>  // 哨兵尾节点（dummy tail）
  private capacity: number

  constructor(capacity: number) {
    this.capacity = capacity
    // 哨兵节点避免边界判断，大幅简化代码
    this.head = new LinkedNode(null as any, null as any)
    this.tail = new LinkedNode(null as any, null as any)
    this.head.next = this.tail
    this.tail.prev = this.head
  }

  get(key: K): V | undefined {
    const node = this.map.get(key)
    if (!node) return undefined
    // 访问后移到链表头部（最近使用）
    this.moveToHead(node)
    return node.value
  }

  put(key: K, value: V): void {
    const existing = this.map.get(key)
    if (existing) {
      existing.value = value
      this.moveToHead(existing)
      return
    }

    // 新节点插入头部
    const newNode = new DLinkedNode(key, value)
    this.map.set(key, newNode)
    this.addToHead(newNode)

    // 超出容量，淘汰尾部节点
    if (this.map.size > this.capacity) {
      const lru = this.tail.prev!
      this.removeNode(lru)
      this.map.delete(lru.key)
    }
  }

  // 以下为链表操作的内部方法
  private addToHead(node: DLinkedNode<K, V>): void {
    node.prev = this.head
    node.next = this.head.next
    this.head.next!.prev = node
    this.head.next = node
  }

  private removeNode(node: DLinkedNode<K, V>): void {
    node.prev!.next = node.next
    node.next!.prev = node.prev
  }

  private moveToHead(node: DLinkedNode<K, V>): void {
    this.removeNode(node)
    this.addToHead(node)
  }
}

💡 提示： 使用哨兵节点（dummy head/tail）是链表操作的经典技巧。它消除了「链表为空」「只有一个节点」等边界情况的判断，让每个操作都只需 4 行指针操作。

1.4 三种实现的性能对比

⚡ 关键结论： 对于 100 项以下的小缓存，Map 简洁实现完全够用且代码最少。对于生产环境且需要 TTL、事件回调等特性，推荐使用 lru-cache npm 包（第 10 版支持 ES Module 和 TypeScript）。只有在需要深度定制（如自定义淘汰策略、持久化）时，才需要手写双向链表版本。

🚀 二、生产级 LRU 缓存的关键特性

2.1 TTL 过期机制

在实际项目中，缓存不仅受容量限制，还受时间限制。一个 10 分钟前的 API 响应可能已经过期。我们需要给每个缓存项附加一个 TTL（Time To Live，生存时间）：

// 带 TTL 的 LRU Cache —— 支持按项设置过期时间
class TTL_LRUCache<K, V> {
  private cache = new Map<K, { value: V; expiresAt: number }>()
  private maxSize: number
  private defaultTTL: number  // 毫秒

  constructor(maxSize: number, defaultTTL: number = 60_000) {
    this.maxSize = maxSize
    this.defaultTTL = defaultTTL
  }

  get(key: K): V | undefined {
    const entry = this.cache.get(key)
    if (!entry) return undefined

    // 检查是否过期
    if (Date.now() > entry.expiresAt) {
      this.cache.delete(key)
      return undefined
    }

    // LRU：重新插入到末尾（更新访问顺序）
    this.cache.delete(key)
    this.cache.set(key, entry)
    return entry.value
  }

  put(key: K, value: V, ttl?: number): void {
    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,
      expiresAt: Date.now() + (ttl ?? this.defaultTTL)
    })
  }

  // 清理所有已过期的条目（建议定期调用，防止内存泄漏）
  purge(): number {
    const now = Date.now()
    let purged = 0
    for (const [key, entry] of this.cache) {
      if (now > entry.expiresAt) {
        this.cache.delete(key)
        purged++
      }
    }
    return purged
  }
}

// 使用示例：缓存 API 响应
const apiCache = new TTL_LRUCache<string, any>(100, 5 * 60_000)  // 100 项，默认 5 分钟过期

// 缓存用户信息，TTL 10 分钟
apiCache.put('user:123', { name: '张三', role: 'admin' }, 10 * 60_000)

// 缓存配置数据，使用默认 TTL（5 分钟）
apiCache.put('config:theme', { dark: true })

// 定期清理过期条目（在生产环境中用 setInterval 或 cron）
setInterval(() => {
  const purged = apiCache.purge()
  if (purged > 0) console.log(`[Cache] Purged ${purged} expired entries`)
}, 60_000)

⚠️ 警告： TTL 缓存最大的隐患是忘记调用 purge()。过期条目虽然 get 时会返回 undefined，但仍然占用 Map 的内存。在长生命周期应用（如 Node.js 服务）中，务必设置定时清理，否则内存会持续增长。

2.2 WeakRef 弱引用缓存：让 GC 自动管理生命周期

ES2021 引入的 WeakRef 和 FinalizationRegistry 提供了一种新的缓存思路：不阻止垃圾回收器回收缓存对象。当原始对象没有其他引用时，缓存自动失效：

// WeakRef 弱缓存 —— 对象无外部引用时自动被 GC 回收
class WeakLRUCache {
  constructor(maxSize) {
    this.maxSize = maxSize
    this.cache = new Map()       // key -> WeakRef
    this.refToKey = new Map()    // WeakRef -> key（用于 FinalizationRegistry）
    this.registry = new FinalizationRegistry((key) => {
      // 当 WeakRef 指向的对象被 GC 回收时，自动清理 Map 条目
      this.cache.delete(key)
    })
  }

  get(key) {
    const ref = this.cache.get(key)
    if (!ref) return undefined
    const value = ref.deref()  // 尝试获取弱引用的目标对象
    if (value === undefined) {
      // 对象已被 GC 回收，清理条目
      this.cache.delete(key)
      return undefined
    }
    // LRU 顺序更新
    this.cache.delete(key)
    this.cache.set(key, ref)
    return value
  }

  put(key, value) {
    if (this.cache.size >= this.maxSize && !this.cache.has(key)) {
      const oldestKey = this.cache.keys().next().value
      this.cache.delete(oldestKey)
    }
    const ref = new WeakRef(value)
    this.cache.set(key, ref)
    this.registry.register(value, key)  // 注册 GC 回调
  }
}

// 使用示例：缓存大型 DOM 元素或 Canvas 对象
const domCache = new WeakLRUCache(50)
const canvas = document.createElement('canvas')
domCache.put('preview-canvas', canvas)
// 当 canvas 变量离开作用域且无其他引用时，GC 会自动回收它，缓存条目也随之消失

💡 提示： WeakRef 缓存特别适合缓存大型对象（DOM 元素、ArrayBuffer、图片数据）。你不需要手动管理这些对象的生命周期——当没有代码引用它们时，GC 自动清理，不会内存泄漏。但注意：WeakRef 的值随时可能变为 undefined，代码中必须做好防御。

2.3 多级缓存架构

在复杂的前端应用中，单一缓存往往不够。一个典型的多级缓存架构是 内存 LRU → localStorage → 网络请求：

// 多级缓存：内存(LRU) → localStorage → 数据源
class MultiLevelCache<K extends string, V> {
  private l1: TTL_LRUCache<K, V>       // 一级：内存缓存（最快）
  private l2Prefix: string              // 二级：localStorage 前缀
  private fetcher: (key: K) => Promise<V>  // 三级：数据源

  constructor(options: {
    l1Size: number
    l1TTL: number
    l2Prefix: string
    fetcher: (key: K) => Promise<V>
  }) {
    this.l1 = new TTL_LRUCache(options.l1Size, options.l1TTL)
    this.l2Prefix = options.l2Prefix
    this.fetcher = options.fetcher
  }

  async get(key: K): Promise<V> {
    // L1: 内存缓存（< 0.01ms）
    const l1Value = this.l1.get(key)
    if (l1Value !== undefined) return l1Value

    // L2: localStorage（~0.1ms）
    try {
      const raw = localStorage.getItem(`${this.l2Prefix}:${key}`)
      if (raw) {
        const { value, cachedAt } = JSON.parse(raw)
        const TTL = 30 * 60_000  // localStorage 30 分钟过期
        if (Date.now() - cachedAt < TTL) {
          this.l1.put(key, value)  // 回填 L1
          return value
        }
      }
    } catch {
      // localStorage 不可用（隐私模式等），忽略
    }

    // L3: 网络请求（~100-800ms）
    const value = await this.fetcher(key)
    this.l1.put(key, value)
    try {
      localStorage.setItem(`${this.l2Prefix}:${key}`, JSON.stringify({
        value,
        cachedAt: Date.now()
      }))
    } catch {
      // localStorage 满了，忽略
    }
    return value
  }

  invalidate(key: K): void {
    this.l1.put(key, undefined as any)  // 用 undefined 标记为失效（TTL 立即过期）
    localStorage.removeItem(`${this.l2Prefix}:${key}`)
  }
}

// 使用示例
const userCache = new MultiLevelCache({
  l1Size: 50,
  l1TTL: 5 * 60_000,
  l2Prefix: 'api:user',
  fetcher: async (userId) => {
    const res = await fetch(`/api/users/${userId}`)
    return res.json()
  }
})

// 第一次调用：L1 miss → L2 miss → 网络请求
const user = await userCache.get('u001')

// 第二次调用（5 分钟内）：L1 hit，直接返回（< 0.01ms）
const user2 = await userCache.get('u001')

⚡ 关键结论： 多级缓存的核心原则是每一级都有独立的失效策略。L1 内存缓存用短 TTL（1-5 分钟）保证数据新鲜度；L2 持久化缓存用中 TTL（15-30 分钟）减少网络请求；L3 数据源提供最终一致性。不要试图用一套 TTL 管理所有层级。

💡 三、LRU 缓存在实际项目中的应用场景

3.1 场景一：API 响应缓存

前后端分离项目中，同一数据可能被多个组件请求。用 LRU Cache 缓存 API 响应可以显著减少网络开销：

// 封装带 LRU 缓存的 fetch 函数
const responseCache = new TTL_LRUCache(200, 2 * 60_000)  // 200 项，2 分钟 TTL

async function cachedFetch(url, options = {}) {
  const cacheKey = `${options.method || 'GET'}:${url}:${JSON.stringify(options.body || '')}`

  // GET 请求优先读缓存
  if (!options.method || options.method === 'GET') {
    const cached = responseCache.get(cacheKey)
    if (cached) return cached
  }

  const response = await fetch(url, options)
  const data = await response.json()

  // 只缓存成功的 GET 响应
  if (response.ok && (!options.method || options.method === 'GET')) {
    responseCache.put(cacheKey, data)
  }

  return data
}

// 使用——第一次请求走网络，后续 2 分钟内直接从缓存返回
const users = await cachedFetch('/api/users')
const user = await cachedFetch('/api/users/123')

3.2 场景二：计算结果缓存（Memoization）

对于 CPU 密集型的纯函数，用 LRU Cache 缓存最近的计算结果可以避免重复计算：

// 通用 memoize 函数 —— 自动缓存最近 N 次调用结果
function memoize<T extends (...args: any[]) => any>(
  fn: T,
  maxSize: number = 100,
  ttl: number = Infinity
): T {
  const cache = new TTL_LRUCache<string, ReturnType<T>>(maxSize, ttl)

  return ((...args: Parameters<T>): ReturnType<T> => {
    const key = JSON.stringify(args)
    const cached = cache.get(key)
    if (cached !== undefined) return cached

    const result = fn(...args)
    cache.put(key, result)
    return result
  }) as T
}

// 使用示例：缓存昂贵的正则匹配结果
const expensiveRegexMatch = memoize((pattern: string, text: string) => {
  console.log(`Computing: /${pattern}/ on "${text.slice(0, 20)}..."`)
  return new RegExp(pattern, 'g').exec(text)
}, 50)

// 第一次调用会执行计算
expensiveRegexMatch('\\d{4}-\\d{2}-\\d{2}', 'Today is 2026-06-03')

// 第二次调用直接返回缓存结果（不会打印 "Computing"）
expensiveRegexMatch('\\d{4}-\\d{2}-\\d{2}', 'Today is 2026-06-03')

3.3 场景三：浏览器端大数据集的视图缓存

处理大型 JSON 数据集时，每次渲染都遍历整个数组代价很高。用 LRU Cache 缓存不同视图配置下的渲染结果：

// 大型 JSON 数据的视图缓存
const viewCache = new SimpleLRUCache(10)  // 最多缓存 10 种视图配置

function getFilteredView(data, filterConfig) {
  const cacheKey = JSON.stringify(filterConfig)

  const cached = viewCache.get(cacheKey)
  if (cached) return cached

  // 昂贵的过滤和排序操作
  const result = data
    .filter(item => {
      if (filterConfig.status && item.status !== filterConfig.status) return false
      if (filterConfig.minPrice && item.price < filterConfig.minPrice) return false
      return true
    })
    .sort((a, b) => {
      const key = filterConfig.sortBy || 'id'
      return filterConfig.desc ? b[key] - a[key] : a[key] - b[key]
    })
    .slice(0, filterConfig.limit || 50)

  viewCache.put(cacheKey, result)
  return result
}

// 切换视图配置时，已缓存的配置瞬间返回
const activeUsers = getFilteredView(allUsers, { status: 'active', sortBy: 'lastLogin', desc: true })
const vipUsers = getFilteredView(allUsers, { status: 'vip', minPrice: 1000 })
// 再次切换回 activeUsers —— 命中缓存
const activeAgain = getFilteredView(allUsers, { status: 'active', sortBy: 'lastLogin', desc: true })

⚠️ 四、LRU 缓存的常见陷阱与避坑指南

4.1 缓存穿透（Cache Penetration）

当请求的 key 在缓存和数据源中都不存在时，每次请求都会穿透缓存直达数据源，造成缓存完全失效。

解决方案：缓存空值

// 防止缓存穿透：缓存空值（短 TTL）
const userCacheWithNullGuard = new TTL_LRUCache<string, any | null>(1000, 5 * 60_000)

async function getUser(userId: string) {
  const cached = userCacheWithNullGuard.get(userId)
  if (cached === null) return null  // 已知不存在，直接返回
  if (cached !== undefined) return cached

  const user = await db.users.findById(userId)

  if (user) {
    userCacheWithNullGuard.put(userId, user, 5 * 60_000)      // 正常缓存，5 分钟
  } else {
    userCacheWithNullGuard.put(userId, null, 30 * 1000)        // 缓存空值，30 秒
  }
  return user
}

4.2 缓存雪崩（Cache Avalanche）

大量缓存项同时过期，导致瞬间大量请求涌入数据源。

解决方案：TTL 加随机抖动

// 防止缓存雪崩：给 TTL 加随机抖动
function jitteredTTL(baseTTL: number, jitterPercent: number = 0.2): number {
  const jitter = baseTTL * jitterPercent * Math.random()
  return baseTTL + jitter - (baseTTL * jitterPercent / 2)
}

// 基础 TTL 5 分钟，实际 TTL 在 4-6 分钟之间随机分布
cache.put('key', value, jitteredTTL(5 * 60_000, 0.4))

4.3 内存泄漏

LRU 缓存最常见的内存问题是缓存了不该缓存的对象引用。在 SPA 中，缓存了已卸载组件的 DOM 引用会导致内存泄漏。

⚠️ 警告： 在 Vue/React 等 SPA 框架中，组件卸载时务必清理该组件相关的缓存。否则缓存中的旧数据可能被新组件误用，导致渲染错误或内存泄漏。

📊 五、缓存策略选型总结

⚡ 关键结论： 90% 的场景用 LRU 就够了。只有在缓存命中率不满足要求时，才需要考虑 LFU 或 W-TinyLFU 等更复杂的策略。先用最简单的方案跑起来，用监控数据证明需要优化后再换方案。

🔧 相关工具推荐

• ✅ lru-cache npm 包 —— 最成熟的 JS LRU 实现，支持 TTL、size calculation、dispose callback，周下载量 5000 万+
• ✅ quick-lru —— 更轻量的 LRU 实现（<2KB），纯 ESM，适合浏览器环境
• ✅ Map 原生对象 —— 小缓存（<100 项）直接用 Map，无需引入第三方库
• ✅ WeakRef —— 缓存大型对象时优先考虑，让 GC 自动管理生命周期

LRU Cache 是每个开发者都应该掌握的基础数据结构。它不仅是面试高频题，更是生产环境中提升应用性能的利器。从最简单的 Map 实现开始，根据实际需求逐步添加 TTL、WeakRef、多级缓存等特性——这种渐进式工程化思路，才是构建可靠系统的正确路径。