Meta 内存KV版本回滚：快照不可变与新分支

题目重点：实现保存版本与回滚当前状态，明确回滚后写入、旧版本保留和版本ID分配。

题意与假设

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

训练set/get/delete/checkpoint/rollback，value为不可变字符串；checkpoint返回单调递增ID，rollback只切换current，保留已保存后续版本。
不含TTL、CAS或磁盘持久化；若回滚定义为销毁后续历史，或每次write自动形成版本，则是需要另定的合同。

解题路线

先实现可检查的全量复制基线：current是可变dict，versions[id]是创建时的独立dict。checkpoint做拷贝，rollback也拷贝，杜绝当前写操作污染版本。
版本号来自独立nextVersion，不从当前状态长度或回滚目标计算。回滚v1后创建新版本仍是v3而非覆盖v2，两个分支都可以再次切换。
get缺键返回None、delete缺键False；空字符串合法。rollback未知ID失败不改变current，也不消耗新的版本号。
如果规模要求优化，持久化树采用路径复制：每次改键只重建根到该键路径，旧根引用不变。另一选择undo日志记录旧值/存在标记，但跨分支重放、版本回收和长距离rollback更复杂。
并发时checkpoint需要线性一致的根或锁住复制，rollback发布新根应原子；单线程dict拷贝示例不声称跨线程安全。可变对象value还需深拷贝或不可变表示，不能因为dict.copy就宣称任意嵌套数据安全。

手动走一遍

set(a,x)后保存v1；set(a,y)保存v2；rollback(v1)，set(b,z)保存v3。v2仍是{a:y}，v3是{a:x,b:z}。随后delete(a)不应改变v1或v3；回滚不存在v99也不能清空current。

Python 参考实现

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

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

class VersionedKV:
    """Full-copy baseline, immutable snapshots, branches get new monotone IDs.

    Rollback switches current state; it does not erase later saved snapshots.
    Values are immutable strings; missing get -> None, delete -> bool.
    """
    def __init__(self):
        self.current={}; self.versions={}; self.next_version=1

    def set(self,key,value):
        if not isinstance(value,str): raise TypeError('string value required')
        self.current[key]=value

    def get(self,key): return self.current.get(key)

    def delete(self,key):
        if key not in self.current: return False
        del self.current[key]; return True

    def checkpoint(self):
        version=self.next_version; self.next_version+=1
        self.versions[version]=dict(self.current); return version

    def rollback(self,version):
        if version not in self.versions: return False
        self.current=dict(self.versions[version]); return True

复杂度

全复制checkpoint和rollback O(K)，普通字典操作均摊O(1)，B版本最坏O(BK)空间。持久平衡树更新O(log K)、切根O(1)，但需计节点共享与引用回收成本，不能把所有操作都说O(1)。

易错点与追问

容易失分的边界

将versions[id]=current保存引用，后续set会改历史。
回滚后重用ID会让外部保存的版本句柄指向不同内容。
历史查询getAt不改变当前状态，rollback会；两题不能只改方法名。

继续深挖

版本删除与共享节点GC如何定？只回收没有current/版本根引用可达的节点。
大value的内存成本怎样算？持久树共享索引不等于深层value可安全共享。