題幹與適用場景
實作一個内存快取：每個鍵有值和過期時間，支持 set、get、delete 或清理。get 不能返回已過期值；說明時間來源、過期边界、容量策略、並行安全和復杂度。
Amazon 的软件开發面试主题把数据结构、算法和编码列為核心准备方向，並强调應用知识解决問題。Redis 官方文档說明 TTL/EXPIRE 保存鍵的剩余生命周期，過期精度和命令语义必须明确。本题不同于 LRU/LFU：核心是時間语义和過期清理。
面試官考察點
- 是否先定义 TTL 单位、時間來源和過期边界。
- 是否把存储结构與過期索引分开考虑。
- get 是否先检查過期，再返回值。
- 是否讨论惰性清理、主动清理、容量和並行。
- 是否给出時間、空间復杂度及測試边界。
回答前需要釐清的問題
- TTL 单位是毫秒還是秒？TTL 為零時立即過期吗？
- 使用单调時钟還是墙上時钟？
- 過期条目是否必须立即從内存删除？
- 是否需要固定最大容量或 LRU 淘汰？
- 多執行緒下 set、get、cleanup 如何互斥？
- 是否支持更新鍵時重置 TTL？
- 是否需要持久化或跨进程共享？
- 時間復杂度目标是 get O(1) 還是 cleanup 也要有界？
30 秒回答框架
“我用哈希表保存鍵到值和绝对過期時間，get 先读取单调時钟並检查 expiresAt；過期就删除並返回 miss。set 可以覆盖值並重置 TTL。基础版本采用惰性清理，get 為均摊 O(1)，空间 O(n)；為避免冷鍵长期占用，再用最小堆或定時扫描主动清理。並行實作用互斥或分片锁，測試覆盖零 TTL、時間相等、更新 TTL 和 cleanup 竞态。”
分步驟深入解答
步骤一：定义数据结构
哈希表项包含 value 和 expiresAt；无 TTL 可用无限值。過期判断统一為 now >= expiresAt，避免不同路径使用不同边界。
步骤二：實作 get 和 set
get 先查鍵，不存在返回 miss；存在但已過期则删除後返回 miss。set 计算绝对過期時間，覆盖旧值，並决定是否把鍵加入主动清理索引。
步骤三：處理時間
优先使用单调時間测量间隔，避免系统時钟回拨延长 TTL。跨进程或持久化场景需要存储明确的時間基准，並說明精度。
步骤四：选择清理策略
惰性清理简单且 get 快，但冷鍵可能保留。主动清理可用最小堆按 expiresAt 弹出，或周期扫描；清理執行緒不能阻塞所有 get。
| 策略 | 优点 | 代价 |
|---|---|---|
| 惰性清理 | 實作简单、读路径快 | 冷鍵可能占内存 |
| 最小堆 | 按最早過期時間清理 | 更新鍵要處理旧堆项 |
| 周期扫描 | 易于限制每轮工作量 | 過期删除有延迟 |
步骤五：並行與更新
set、get、delete、cleanup 需要一致地检查和删除。可以用全局锁、读写锁或分片锁；若使用最小堆，哈希表和堆的更新必须保持原子关系。
步骤六：容量和淘汰
TTL 不是容量策略。达到最大容量時仍要选择 LRU、随机或拒绝写入；淘汰與過期删除都要更新统计，不能把淘汰误报成過期。
步骤七：復杂度與伪代码
下面伪代码只展示核心边界：
get(key):
item = table[key]
if item is absent: return MISS
if clock.now() >= item.expiresAt:
delete table[key]
return MISS
return item.value惰性版本 get/set 為均摊 O(1)，空间 O(n)；最小堆清理為 O(log n) 每次弹出。
步骤八：測試與故障边界
測試零 TTL、now 等于 expiresAt、更新 TTL、重復 cleanup、時钟跳变、並行 get/set、容量淘汰和异常值。使用可注入時钟，避免睡眠导致測試不稳定。
高品質示範回答
“我会定义 CacheItem(value, expiresAt)，用哈希表存储。set(key, value, ttl) 將 ttl 转成绝对過期時間；ttl 為零表示立即過期。get 先检查鍵，再用单调時钟判断 now >= expiresAt，過期就删除並返回 miss。
第一版采用惰性清理，读写均摊 O(1)，空间 O(n)。如果冷鍵较多，我加入按 expiresAt 排序的最小堆；每次 set 产生带版本号的堆项，cleanup 弹出到期项時驗证版本，避免旧堆项删除刚更新的值。並行下用分片锁保护对應哈希桶和堆操作。測試覆盖時間相等、更新 TTL、重復 cleanup、並行竞态和容量淘汰。”
常見錯誤
- 用当前時間加 TTL，却没有定义零 TTL 和相等边界。
- 使用墙上時钟，系统回拨後让快取异常延长。
- 只在後台清理，get 仍返回過期值。
- 用最小堆更新鍵，却没有處理旧堆项。
- 把 TTL 当成 LRU 容量策略。
- cleanup 持有全局锁太久，阻塞所有读写。
- 只测正常命中，不测時間相等和並行竞态。
- 没有說明復杂度與時間精度。
追問及應對
追问一：為什麼使用绝对過期時間？
统一判断逻辑，並让 cleanup 能按時間排序；更新 TTL 時直接替换 expiresAt。
追问二：系统時钟被调回怎么办？
测量本地间隔使用单调時钟；持久化或跨节点协议要明确時間基准和精度。
追问三：冷鍵很多但不能使用後台執行緒怎么办？
在写入或读取路径上做有界主动清理，例如每次操作最多弹出固定数量的到期项，並接受删除延迟。
追问四：如何保证堆與哈希表一致？
使用同一锁或事務式操作，並给堆项加版本号；弹出時只删除仍匹配的版本。
追问五：达到容量上限時怎么办？
先删除已過期条目，再按明确淘汰策略移除有效条目；统计原因並說明对命中率的影响。
追问六：多进程如何共享快取？
内存實作只适合单进程；跨进程需外部存储或分布式快取，並重新讨论原子 TTL、時钟和故障。