Databricks 单机 Cache：WAL 持久化、分片锁与 LRU 驱逐

题目重点：从内存 map 出发，梳理写入线性化与恢复、锁竞争和容量驱逐，避免把缓存与权威数据库混淆。

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

训练版 API 为 get(key)、put(key,value)、delete(key)，单机多线程、容量上限以 bytes 计；题目未给实际接口、容量和 TTL。
若 cache 是唯一权威状态，成功 put 需有可靠 WAL 持久点；若只是一份可重建的缓存，WAL 可省且故障时回源。两者不能同时混说。

先定语义：纯缓存可先查 map，miss 从后端取并版本化填充；写回/写穿策略需与后端一致。若本地 cache 承担权威写，WAL record 包括序号、操作、key/value、校验，先追加并 durable commit，再发布到 map；重启从快照+WAL 顺序回放。
简单基线一把 mutex 保护 map+LRU 链表，get 若要更新 recency 也是写操作；put/delete 同锁保持索引与链表不变量。缩小临界区的前提是外部 IO/序列化在锁外做，但提交 WAL 与 map 发布的顺序仍须可线性化，不能随便拆锁造成读到未提交数据。
按稳定 hash 分 S 个 shard，每 shard 有 map、LRU 链和锁，减少不同 key 的争用；总容量可以按 shard 固定配额，代价是一个 shard 满而其他 shard 空时未充分利用。全局精确 LRU 需跨 shard 协调，会重新引入热点锁；可采用每 shard 近似 LRU。
WAL 写入与 shard 锁的顺序必须统一：例如分配提交序号、写日志、提交后更新 map，读未提交状态的范围要写清。多个 shard 的复合操作按 shard id 固定锁顺序，或设计成不支持跨 shard 原子事务。
容量驱逐选择候选时要检查对象是否 dirty/in-flight；若是权威层，驱逐仅释放内存，持久记录与可回读索引仍需保留。重启回放的内存上限、日志压缩与快照截断需要版本水位和原子切换。

key K 的 put(v2) 在 WAL 写到一半时宕机：恢复扫描校验失败的尾 record 并截断，map 仍为 v1；若 fsync 成功后进程在 map 更新前宕机，重启回放 v2。若只是可重建缓存，进程崩溃直接丢缓存并从源库重新填充即可。

map 查找/更新期望 O(1)，LRU 链维护 O(1)；S 个 shard 增锁/元数据 O(S)。WAL 追加每次 O(record length) 加 IO flush，恢复按日志总字节线性扫描；近似吞吐与竞争/磁盘延迟有关，题目未明确 QPS。