題幹與適用場景
實作一個記憶體快取：每個鍵有值和過期時間，支援 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、時鐘和故障。