Meta 四十线程内存缓存：线性化操作与淘汰锁

题意与假设

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

• 训练支持get/put/delete与最大entry数，要求每个操作线性化；LRU精确全局还是分片近似必须明确，示例先以精确全局LRU基线。
• 值不允许调用方未经锁直接修改内部对象；选择不可变value或返回副本。40线程是并发数，不等于保证40倍吞吐。
• 容量若按字节而不是条数，需要计算key/value及索引开销；大对象替换必须扣旧加新且防容量暂时超标。

解题路线

1. 基线用hashmap+双向链表与同一mutex：get命中也移动到MRU，所以通常是写操作，不能只加shared read lock。put替换/插入后按同锁淘汰最旧节点，保证map与list一一对应。
2. 若lock竞争明显，按key分shard，每shard有锁、map与局部LRU并分配额度；吞吐提升但全局LRU变为近似，不能继续声称“最旧全局元素必淘汰”。
3. TTL在get时校验，过期删除与LRU调整同锁；cleaner遍历过期索引时用entryVersion确认，旧到期任务不删同key的新value。eviction callback在锁外执行，避免回调再进入cache死锁。
4. 缓存miss的昂贵loader用per-key singleflight，共享在途Future，但不持有全局锁等待I/O。取消/异常必须清理在途记录并让等待者收到一致结果，不能无限阻塞后续请求。

手动走一遍

容量2，putA/putB，getA使A变MRU，再putC应淘汰B。另一个线程在getA同时putA新版本，操作必须有确定线性化点；不能返回一半更新的值或把旧TTL任务删掉新A。

规模与取舍

hash+链表每操作预期O(1)，锁等待随热点和临界区增长；shard数S时单热key仍争同一锁。全局严格LRU需要协调，不可能把所有跨shard顺序免费并行化。

易错点与追问

容易失分的边界

• 只锁map、不锁链表会断链或留下僵尸节点。
• 锁内回调、loader或用户自定义hash可产生长尾或递归死锁；接口需限制并隔离调用。

继续深挖

• 如何测40线程的正确性？记录并发操作起止和结果，用小历史线性化检查及结构不变量验证，压测吞吐本身不证明正确。
• 进程间共享与进程重启后保留不是本内存cache合同，需要单独服务或持久化层。