LinkedIn 单机 File KV：十亿 Key、MB 级 Value 与 Append Only 存储

题目重点：文件数量受限时把大值顺序写磁盘、索引分层，并处理 tombstone、崩溃恢复和 compact。

题意与假设

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

训练设计提供 put/get/delete key，value 存磁盘，key 索引可分层；File System 的创建/删除/append 是底层 API，不假设随机覆盖写。
若 10 亿 key 的索引条目每个几十字节，也需几十 GB，不能因为‘可用 map’就断言索引全驻单机内存。具体内存预算须当轮询问。

值按记录 `(key,version,length,checksum,value)` 追加到活跃 segment file，返回 file_id+offset+length；map 或 LSM 风格索引只保存位置与版本。大值不复制进内存缓存，读取按 offset 走块 IO 并校验 checksum。
文件数上限 100k：用大 segment 顺序写而非每 key 一文件。创建活跃文件、滚动封存；删除/更新只追加 tombstone/新版本，并在索引切到最新位置。
若索引无法驻内存，内存保存热 key cache、segment 元数据、Bloom/filter 与稀疏索引；冷 key 查磁盘有序索引/LSM run。写前日志或记录本身带校验与提交边界，崩溃后扫描尾部/manifest 重建。
后台 compact 读旧 segment，按索引版本只保留有效记录写新 segment；先原子发布新 manifest，再删除旧文件，防崩溃丢数据。并发写按 key 版本/CAS 顺序化，读取得到一致快照。
容量估算至少问 key 长度、value 分布和保留/覆盖频率：10 亿×1MB 是 PB 级，单机磁盘可能根本不足；在这个数量级应先确认工作集和是否必须真实存满。

put(k,v1) 追加到 segment 7 offset 100；put(k,v2) 再追加到 offset 2MB，索引指向新位置。delete(k) 写 tombstone，get(k) 返回不存在；compaction 只保留最新有效版本。

单次追加近似 O(value bytes) 顺序写；内存 hash 索引查期望 O(1) 加一次磁盘读取，但索引落盘时查找受层数/块 IO 影响。总磁盘约活数据+未 compact 旧版本，索引元数据 O(K) 条，K 最多 10 亿。