【面经】Anthropic Coding：调试 LRU 缓存的 Bug，再让它崩溃后能恢复（WAL + 快照）

分享一道我 Anthropic 电面遇到的题，分两部分：先给一个现有的缓存实现找 bug 并修好，再给它加上崩溃恢复。把我的做法贴出来供讨论。
题面。 给你一个内存里的 LRU 缓存（容量固定，满了淘汰最久未用的 key），在生产环境行为异常。第一部分：找出并修复所有 bug。第二部分：扩展它，让内容在进程崩溃重启后还能恢复。原始代码：

1. class LRUCache:
2.     def __init__(self, capacity):
3.         self.capacity = capacity
4.         self.data = {}      # key -> value
5.         self.order = []     # keys, 从最久未用（前）到最近用过（后）
7.     def get(self, key):
8.         if key in self.data:
9.             return self.data[key]
10.         return None
12.     def put(self, key, value):
13.         if len(self.data) > self.capacity:
14.             oldest = self.order.pop()
15.             del self.data[oldest]
16.         self.data[key] = value
17.         self.order.append(key)

复制代码

我先确认了几个问题：get 算不算一次「使用」（算，LRU 里读就是使用）；put 已存在的 key 应该刷新它的位置且不触发淘汰；capacity 为 0 时不存任何东西；持久化目标是进程崩溃（整机断电放在后续追问里）。
第一部分 —— 五个 bug，每个都给出复现序列

• get 不刷新 recency。
  1. put(a), put(b), get(a)

  复制代码
  之后
  1. order

  复制代码
  还是
  1. [a, b]

  复制代码
  ，刚读过的 key 还排在淘汰队列最前面。
• 淘汰判断差一。
  1. len(data) > capacity

  复制代码
  会让缓存装下 capacity + 1 条。容量为 1 时
  1. put(a), put(b)

  复制代码
  ，两个都还在。
• 淘汰弹错了端。
  1. order.pop()

  复制代码
  弹的是末尾，也就是最近用过的 key。容量 2，依次
  1. put(a), put(b), put(c), put(d)

  复制代码
  ：淘汰真正触发时，删掉的是最新的
  1. c

  复制代码
  ，最老的
  1. a

  复制代码
  反而活着。
• put 已存在的 key 会 append 重复条目。
  1. put(a,1), put(a,2)

  复制代码
  后
  1. order == [a, a]

  复制代码
  ，但
  1. data

  复制代码
  里只有一条。两边长度对不上，更新也不刷新位置，靠前的旧条目指向一个活着的 key——等淘汰方向修好之后，这个旧条目就是「刚更新的 key 被淘汰」甚至重复删除的来源。
• capacity 为 0 也能存。 对容量 0 的缓存
  1. put(a)

  复制代码
  ，再
  1. get(a)

  复制代码
  能读出来。

另外还有一个潜在的性能问题：就算逻辑修对，

1. list.pop(0)

复制代码

也是 O(n)，这个结构做不出 O(1)。
修复后的实现（get / put 都是 O(1)）：

1. from collections import OrderedDict
3. class LRUCache:
4.     def __init__(self, capacity):
5.         if capacity < 0:
6.             raise ValueError("capacity must be >= 0")
7.         self.capacity = capacity
8.         self.data = OrderedDict()          # 前 = 最久未用，后 = 最近用过
10.     def get(self, key):
11.         if key not in self.data:
12.             return None
13.         self.data.move_to_end(key)
14.         return self.data[key]
16.     def put(self, key, value):
17.         if self.capacity == 0:
18.             return
19.         if key in self.data:
20.             self.data.move_to_end(key)
21.         self.data[key] = value
22.         if len(self.data) > self.capacity:
23.             self.data.popitem(last=False)  # 淘汰最前面（最久未用）

复制代码

（不用 OrderedDict、手写 dict + 双向链表也能做到同样的 O(1)。）测试：每个 bug 一个针对性测试，用的就是上面那些复现序列，再加一个和朴素参考实现对跑的随机差分测试。
第二部分 —— WAL 预写日志 + 快照做崩溃恢复
先把保证说清楚： 只要

1. put()

复制代码

返回了，它的效果在进程崩溃重启后还在（前提是 OS 和磁盘兑现 fsync）。没返回的 put 可以丢。
写什么、什么时候写。 一个只追加的日志文件。每条记录的帧格式是

1. 长度 | payload | CRC32(payload)

复制代码

，payload 是

1. {"lsn": n, "op": "put", "k": key, "v": value}

复制代码

或

1. {"lsn": n, "op": "evict", "k": key}

复制代码

。

1. put

复制代码

的流程：先算出淘汰对象，把 put 记录（有淘汰就再加一条 evict 记录）追加进日志，flush + fsync，然后才改内存、才返回。先写日志，后改内存——崩溃之后，日志永远不会落后于已经确认过的写入。
为什么淘汰也要写日志。 读操作不落盘，如果只重放 put，recency 只能按 put 顺序重建，可能把运行期已经被淘汰的 key「复活」（或者反过来）。把每次淘汰显式记下来，恢复出的内容就是精确的：被淘汰的不会回来，活着的不会丢。一个诚实的保留：重启后的 recency 顺序里，put 是精确的，但上次快照之后的 get 没有进日志，所以重启后第一次淘汰选谁，可能和不中断运行时不一样。要连这个都精确，就得把读也写进日志——这个代价我没取。
恢复流程。 先加载快照（如果有），再从头扫日志，只应用 LSN 比快照新的记录。扫到第一条不完整或者 CRC 对不上的帧就停——那是崩溃在追加一半时留下的撕裂写，只可能出现在文件尾部，它前面的都完好——然后把日志截断到这个位置。
控制日志大小：快照。 日志超过阈值时，把全量状态（内容 + 顺序 + 已覆盖的最后 LSN）写到

1. snapshot.tmp

复制代码

，fsync 之后原子

1. rename

复制代码

覆盖

1. snapshot

复制代码

，再 fsync 目录，然后把日志清空重开。快照写一半崩溃，留下的要么是旧快照 + 完整日志，要么是新快照 + 一段按 LSN 跳过已覆盖记录的日志，两种情况重放都正确。
代价，实话实说。 每次 put 一次 fsync 就是这份保证的价格：本地 NVMe 是微秒级，慢盘或云盘是毫秒级，不批处理的话 put 吞吐大致被 1/fsync 延迟卡住（见下面的追问）。
被追问的几个后续：

• 批量同步： group commit——攒 ~1ms 或 ~100 个 put，一次 fsync 整批释放。崩溃只丢没返回的 put，保证不变，吞吐按批大小涨。
• 多线程： 一把锁同时护住「追加日志 + 改内存」，保证盘上顺序和内存顺序一致（上面的实现就是这么做的）；锁成为瓶颈时再按 key 分片、每片一份日志。
• TTL： 每条 put 记录里带过期时间戳；重放时丢弃已过期的；get 保持惰性过期，淘汰时把已过期的当不存在。
• 整机丢失： fsync 只能扛进程崩溃。要扛整机，就得把每条记录发到另一台机器（或持久化的远程存储），副本确认后才返回——fsync 的延迟变成一次网络往返，保证也变成「副本活着才算数」。

验证说明： 完整实现（修复版缓存 + 持久化缓存 + 测试）在发帖前实际跑过：五个 bug 都在原代码上复现；每个 bug 一个针对性测试；第一部分 20,000 次随机差分测试；第二部分崩溃恢复、撕裂尾截断、快照压缩、带多次模拟重启的 1,500 次差分测试——全部通过。
觉得有帮助的话欢迎收藏、加米，谢谢。

lestrois 发表于 2026-10-24 02:23
请问这个过程都是全程用 claude 吗？

面试的时候不行，不让用 AI。

W_S_W 发表于 2026-10-23 00:30
感谢楼主 已加米 想问下是必须用Python吗

不要求 Python，可以自己选语言，我用的 Python。

舒怡ABCF 发表于 2026-10-23 15:13
你这个LRU的第一问似乎和常见的LRU 题目不一样，那个是generate_key 的bug

我也不确定是会轮换题目，还是这个面试官的版本。我之前也看到过 generate_key 那个版本，发现不一样的时候也挺意外的。

谢谢分享 你是内推还是海投？

感谢楼主 已加米 想问下是必须用Python吗

楼主，你是哪个阶段遇到的这题？OA 还是screening/onsite 时候

难度果然不一样
面试总时长是？LZ多久完成的？

开心的猪 发表于 2026-10-22 17:26
谢谢分享 你是内推还是海投？

直接申请的，没有走内推。

sotonzepler 发表于 2026-10-23 08:34
楼主，你是哪个阶段遇到的这题？OA 还是screening/onsite 时候

电面 screening 这一轮。

duochuankuzi 发表于 2026-10-23 08:46
难度果然不一样
面试总时长是？LZ多久完成的？

一共 60 分钟。

冷目灼灼的扁豆 发表于 2026-10-23 11:02:19
一共 60 分钟。

60分钟两道题，这是上了难度的