题干与适用场景
实现一个内存缓存：每个键有值和过期时间，支持 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、时钟和故障。