Coding 面试：实现按时间查询的版本化键值存储

题干与适用场景

实现一个内存结构：set(key, value, timestamp) 写入版本，get(key, timestamp) 返回该 key 在给定时间点已经生效的最新值；没有满足条件的版本时返回空值。先澄清时间戳是否严格递增、同一时间戳是否允许覆盖、读写是否并发，以及是否需要删除或持久化。本题核心是把“每个 key 的历史”组织成可验证的不变量，而不是把所有记录排序后逐次扫描。

面试官考察点

强回答会先给出 O(log m) 查询目标，其中 m 是目标 key 的版本数，再说明如何在追加写入和乱序写入之间取舍。面试官会检查候选人是否处理空 key、时间戳在两端、重复时间戳、值为 null、未知 key，以及是否把“最新版本”误写成“最大时间戳之后的版本”。若声称线程安全，还要说明锁的粒度和快照语义。

回答前需要澄清的问题

1. 时间戳是否按 key 单调递增？ 若是，可追加并用一次反向扫描或二分；若否，要保持有序或拒绝乱序写入。
2. 相同时间戳如何定义？ 采用 last-write-wins 时要保存写入序号作为稳定 tie-breaker；若禁止覆盖，应返回错误。
3. 值能否为 null？ 能的话，未命中不能也用 null 表示，应返回带 found 的结果。
4. 是否需要并发？ 单线程题可先完成数据结构；并发版要定义 set 与 get 的可见性，再选择读写锁或不可变快照。
5. 历史是否无限增长？ 若有保留窗口或最大版本数，过期策略会改变删除和查询不变量。

30 秒回答框架

“我按 key 保存按时间排序的版本数组。查询用 upper_bound(timestamp) 找到第一个大于目标时间的位置，返回它前一个版本，因此查询是 O(log m)。如果写入时间戳不保证递增，我会用二分插入并明确插入成本；如果规模要求高写入吞吐，则改为先追加到日志，再在批处理或查询层建立索引。相同时间戳用递增序号决定覆盖顺序，未命中返回显式状态。最后用空 key、边界时间、乱序和重复时间戳测试不变量。”

分步骤深入解答

先定义记录 (timestamp, sequence, value)，并令每个 key 的数组按 (timestamp, sequence) 非递减排列。对 get(k, t)，寻找第一个 timestamp > t 的位置 i；若 i = 0 则没有生效版本，否则返回 records[i - 1]。这就是上界二分，避免把“等于 t”漏掉。

若写入按 key 递增，直接 append，set 均摊 O(1)，get 为 O(log m)。若允许乱序时间戳，二分定位后插入会移动数组元素，单次最坏 O(m)；可以改用平衡树，或接受写入摊销成本换取紧凑内存。不要只对全局数组排序，因为不同 key 的查询边界彼此独立。

重复时间戳必须有确定规则。last-write-wins 可给每次调用一个递增 sequence，并按 (timestamp, sequence) 排序；查询上界仍只比较 timestamp，落在同一 timestamp 的最后一条记录自然胜出。若 timestamp 可能超过安全整数，使用语言提供的整数类型或字符串比较器，不能静默转成浮点数。

并发时，最小实现可按 key 加锁：写入修改单个数组，读取在复制引用或持锁期间执行二分。若要求读不阻塞，可在写入时复制该 key 的不可变数组并原子替换；代价是写放大。持久化版本则需要日志、校验和和恢复指针，那已经超出纯内存题，应先确认面试官是否要扩展。

高质量示范回答

“我先假设同一 key 的时间戳可以乱序，重复时间戳采用后写覆盖，并且单线程。每个 key 对应一个按 (timestamp, sequence) 排序的数组。get 做上界二分：找第一个时间戳大于查询时间的位置，返回前一项；这样恰好包含等于查询时间的版本，复杂度是 O(log m)。若面试官保证时间戳递增，我会把 set 降到均摊 O(1)；若写入量远高于查询，我会考虑追加日志后异步建立索引。测试会覆盖未知 key、早于首版本、等于首尾时间、晚于末版本、乱序写入、重复时间戳和 null 值。”

常见错误

• 错误表现 → 用线性扫描找最后版本；失败原因 → 查询退化为 O(m)，规模增长后不可控；修正方法 → 保持排序不变量并使用上界二分。
• 错误表现 → 用 timestamp < t；失败原因 → 丢失恰好在 t 写入的版本；修正方法 → 查找第一个 timestamp > t。
• 错误表现 → 假设所有写入递增；失败原因 → 乱序数据会破坏数组顺序；修正方法 → 明确约束，或执行有序插入/改用树结构。
• 错误表现 → 用 null 同时表示未命中和值；失败原因 → 调用方无法区分两种状态；修正方法 → 返回 { found, value } 或显式 Optional。
• 错误表现 → 忽略重复时间戳；失败原因 → 结果依赖实现细节；修正方法 → 引入 sequence 或拒绝冲突。

追问及应对

如果写入时间戳保证递增，如何优化？

每个 key 直接追加，写入均摊 O(1)；查询仍可二分，或者在查询时间通常接近最新值时从尾部短扫。要说明尾扫只在访问分布支持时采用，不能把最坏复杂度写成 O(1)。

如果要限制每个 key 只保留最近 30 天？

按事件时间或服务时间明确口径，周期性删除低于保留下界的前缀；删除后仍保持排序。查询早于下界返回“历史不可用”，不能伪装成未命中。

如果多个线程同时读写怎么办？

先定义线性化点。简单方案是每个 key 的读写锁；追求无锁读时，写入构造新数组后原子替换引用，读者看到旧快照或新快照，但不会看到半成品。

如果要持久化并支持崩溃恢复？

追加写前先记录带序号的日志，定期生成索引快照；恢复时重放快照之后的日志并验证序号。题目若只要求内存，不应未经确认加入完整数据库设计。