Meta 数据库Checkpoint：恢复剩余TTL与前缀查询

题目重点：实现两级键值、过期字段、检查点和恢复，区分字段前缀与值前缀，避免恢复后立即失效。

题意与假设

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

训练key→field→字符串value，时间单调不减；字段有效区间[setTime,setTime+ttl)，无TTL为永不过期。delete仅对当前活字段成功。
backup保存当时活字段及剩余TTL；restore(t,target)选择不晚于target的最近备份，并把TTL重新基于t计时。备份返回非空record数。不同问法分别要求字段前缀或value前缀，示例接口by显式指定，不能混成同一种。

解题路线

当前表只存(value,expireAt)，get/scan/delete统一用t<expireAt判断活性。无TTL用None，零TTL不在本训练合同内。不要把没有TTL当作已经过期。
scan返回(field,value)按field排序；by=field检查field.startswith，by=value检查value.startswith。空值字符串与缺字段不同，不能if not value就认为不存在。
backup遍历活字段，有限TTL保存remaining=expireAt-backupTime。永不过期仍为None。独立复制结构，之后更新不能修改已保存快照；空record不计返回值。
restore查最近backupTime≤target，再完整替换当前表；有限TTL转换expireAt=restoreTime+remaining。该操作恢复的是整个逻辑状态，不是只把旧字段补回，更不是历史getAt。
无法找到备份时失败而不改数据；未来target拒绝。若要复用同一backup反复恢复，每次依据不变remaining重算，不能上次restore时直接改snapshot里的到期时间。

手动走一遍

t=10写a→x、TTL20，t=15备份保存剩余15。t=100恢复该备份后有效到115，t=114可读、t=115不可读。如果直接复用expireAt=30，刚恢复就过期。无TTL的b→空字符串在恢复后仍可读，也应允许成功delete。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

class CheckpointDB:
    """Training: monotone operation timestamps, expiration half-open [set,set+ttl).

    A checkpoint records remaining TTL; restoring rebases it to restore time.
    Prefix filter target is explicit: 'field' or 'value'. Latest backup<=target.
    """
    def __init__(self):
        self.data={}; self.checkpoints={}; self.last_time=float('-inf')

    def _time(self, t):
        if t < self.last_time: raise ValueError('time went backwards')
        self.last_time=t

    def set(self, t, key, field, value, ttl=None):
        self._time(t)
        if ttl is not None and ttl<=0: raise ValueError('positive TTL required')
        self.data.setdefault(key,{})[field]=(value,None if ttl is None else t+ttl)

    def get(self,t,key,field):
        self._time(t); item=self.data.get(key,{}).get(field)
        if item is None or item[1] is not None and t>=item[1]: return None
        return item[0]

    def delete(self,t,key,field):
        if self.get(t,key,field) is None: return False
        del self.data[key][field]; return True

    def scan(self,t,key,prefix='',by='field'):
        self._time(t)
        if by not in ('field','value'): raise ValueError('invalid prefix target')
        return sorted((f,v) for f,(v,exp) in self.data.get(key,{}).items()
                      if (exp is None or t<exp) and
                      (f if by=='field' else v).startswith(prefix))

    def backup(self,t):
        self._time(t)
        snapshot={}
        for key,fields in self.data.items():
            live={f:(v,None if exp is None else exp-t) for f,(v,exp) in fields.items()
                  if exp is None or t<exp}
            if live: snapshot[key]=live
        self.checkpoints[t]=snapshot
        return len(snapshot)  # Number of nonempty records, not fields.

    def restore(self,t,target):
        self._time(t)
        if target>t: raise ValueError('future target')
        candidates=[b for b in self.checkpoints if b<=target]
        if not candidates: return False
        saved=self.checkpoints[max(candidates)]
        self.data={k:{f:(v,None if remaining is None else t+remaining)
                     for f,(v,remaining) in fields.items()} for k,fields in saved.items()}
        return True

复杂度

get/set/delete均摊O(1)，scan O(Fk log Fk)，全量backup/restore O(L)，L为活字段数。B个快照空间O(BL)最坏，最近备份选择当前基线O(B)，有序索引可二分O(log B)。

易错点与追问

容易失分的边界

保存绝对到期时间与恢复剩余TTL的合同不同，不能混用。
字段名以prefix开头并不代表value也以prefix开头，必须按题目对象过滤。
restore不应回滚全局操作时钟，否则后续请求时间可能倒退。

继续深挖

备份需要持久文件时怎样校验部分写入？用完整manifest、checksum与原子发布，当前内存示例不提供崩溃持久性。
第四阶段若只说replication，要补问复制一致性、冲突与故障合同；不能直接视作checkpoint。