OceanBase 存储引擎 C++ 一面：缓存替换与落盘

《面试题目》

1. 实习经历（约 20 分钟）
2. ARC 自适应缓存对比 LRU、LRU 冷热隔离、LRU-K，优点在哪？
3. ARC 的自适应是怎么实现的？
4. OS 内核的 CopyOnWrite 怎么实现的？
5. gdb 怎么排查多线程死锁？
6. B+ 树对比 B 树、LSM 树？
7. MVCC 与隔离级别？
8. Redis 的持久化怎么做？
9. WAL、Redo Log 串行落盘怎么优化？写磁盘的瓶颈怎么优化？
10. 缺页中断是什么流程？
11. 线上 CPU 突然飙高怎么排查？OOM 怎么排查？
12. spinlock 对比 mutex？
13. 向量化模型对比火山模型？
14. C++ 的原子变量能不能保护整个缓存？你实现的缓存的 latch 路径是怎样的？replacer 在热点路径怎么优化？
15. 手撕：k 路归并排序。多个有序流，每条记录为 {key, seq, deleted, value}，每路内部 key 升序；同 key 保留最大 seq，墓碑（deleted=true）不输出。
16. 原帖补充：面试两天后收到挂信。

《参考解析》

ARC 与 LRU 系算法：LRU 只看「最近是否被访问」，无法抵御一次性扫描把热数据全冲掉，于是有了 LRU-K（看最近第 K 次访问的间隔）和冷热隔离（新数据先进冷区，被二次访问才晋升到热区）。ARC 的思路是把「访问频次」和「访问新旧」分成 T1（只访问过一次）和 T2（访问过两次以上）两个队列，再各留一份幽灵链表 B1/B2 记录刚被淘汰的 key；命中幽灵链表说明淘汰判断错了，就动态调整 T1/T2 的容量分配——这就是它的「自适应」。相比 LRU-K 它不需要额外参数 k，内存开销也只是幽灵链表存 key/parent 号，比 LRU-K 的多段历史更省。

CopyOnWrite：fork 之后父子进程共享同一份物理页，页表项都标成只读；任何一方写入触发写保护异常，内核在缺页处理里复制一份新页给写方，更新页表并恢复可写，原来的页仍留给另一方。xv6 里的实现要点是引用计数：每个物理页记录被几个页表引用，只有计数降到 1 时才真正释放；另外要处理 uget/uvmcopy 时对引用计数的加锁，否则多进程并发 fork 会漏记。

gdb 排查多线程死锁：先 gdb -p <pid> attach，thread apply all bt 拿到所有线程栈，看有没有线程停在 pthread_mutex_lock / futex_wait 上；找到持锁线程（通常停在业务代码里而没释放锁），再看它等的是哪把锁，构成环路即死锁。info threads、thread <n> 切栈、p <mutex> 看锁状态配合使用；如果是偶发，用 core dump 或 pstack 周期性采样。排查完的根治手段是统一加锁顺序、用 std::scoped_lock 一次锁多把、或者把锁粒度拆细。

B+ 树 / LSM 树与 MVCC：B+ 树把数据全放叶子节点并用链表串起来，内部节点只存 key，因此树矮、范围扫描友好，读放大低但随机写要原地改页；LSM 树把写先落内存表再顺序刷盘、后台做归并压缩，写吞吐高、写放大明显，读路径要跨多层查（布隆过滤器加速）。Redis 持久化分 RDB（定时快照，恢复快、可能丢最后一段数据）和 AOF（追加写命令，appendfsync 可选 always/everysec/no，everysec 是最常用的折中），AOF 重写压缩体积，重启时优先用 AOF 恢复。

WAL 串行落盘瓶颈：日志必须比数据页先落盘（WAL 规则），所以日志组提交是关键优化——把多个事务的提交合并成一次 fsync（group commit），减少 fsync 次数；磁盘瓶颈还可以用「预分配日志文件 + 顺序追加」避免元数据更新，用 O_DIRECT 绕过页缓存重复拷贝，或者把日志放到独立的低延迟设备（NVMe）上。进一步可以做日志与数据分离、并行刷盘、批量提交延迟与吞吐的权衡（牺牲一点延迟换吞吐）。

原子变量能否保护整个缓存 / latch 路径 / replacer 热点：不能。原子变量只保证单个变量的读写原子，它给不了「多个字段一起读改」的一致性——例如哈希桶查找、页码映射、replacer 链表三者之间有不变式，必须用锁或 latch 保护。常见做法是 latch crabbing：拿住父节点 latch 找到子节点后释放父 latch，只在必要时升级为写 latch；页面级 latch 用读写锁区分。replacer 在热点路径上的优化方向是减少全局竞争：分片（每分片一个 LRU 链表，哈希后各管各的）、用无锁队列或 CLOCK 近似算法代替严格 LRU、把 replacer 的元数据放进页表项里避免单独加锁。向量化对比火山模型则是另一条主线：火山模型一次一行的虚函数调用开销大、CPU 流水线利用差；向量化按批（比如 1024 行）在列式数据上做计算，配合 SIMD 和编译期展开，代价是内存占用和实现复杂度更高。手撕题的解法是标准多路归并：小根堆按 key 排序压入各路当前记录，弹出时同 key 比较 seq 保留最大者，deleted 为真则丢弃，然后推进对应流。