题目重点：Phone Coding 题目追问 KV 的 begin、commit、rollback 均为常数时间，再追问多线程；本文用不可变 Treap 快照让事务边界 O(1)，明确读写另计。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练版 key/value 是字符串，key 不含 NUL；提供 get/put 与可嵌套的 begin/commit/rollback。None 表示不存在，若允许 None 值则需另设 sentinel。
- begin 记录当前根指针；commit 保留当前根并丢弃最近快照；rollback 恢复最近快照。无活动事务调用 commit/rollback 报错。
- 示例是单线程全局事务栈；多线程需另外选全局串行化，或每线程事务局部根加提交时的版本 CAS/冲突重试，不能直接共享这个栈。
解题路线
- 将 KV 表实现为路径复制的不可变平衡搜索树；root 指向当前版本，put 只复制查找路径并复用未变子树。
- begin 把 root 指针压入快照栈 O(1)；rollback 弹出并恢复 root O(1)；commit 仅弹快照而保持当前 root O(1)。嵌套事务自然支持内层 commit 合并到当前工作根，外层 rollback 仍可回到外层初始根。
- 示例选随机优先级 Treap，split/merge 使 put 期望 O(log n)，get 期望 O(log n)，已存在键重写时沿用原优先级。
- 测试 100,000 次随机 put/get/嵌套事务，与独立 Python dict 每次 begin 复制快照的语义模型对照；参考模型不用于复杂度声明。
- 多线程最简单先对整个事务生命周期加排他锁，保证正确但吞吐差；若用快照隔离，每事务记录 baseVersion，commit 用 CAS 验证根仍对应 baseVersion，否则冲突重试。
手动走一遍
put(a,1)；begin；put(a,2)；begin；put(b,3)；commit，此时 a=2、b=3；对外层 rollback，root 回到外层开始的版本，因此 a=1、b 不存在。内层 commit 不能破坏外层 rollback 能力。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Immutable treap: O(1) begin/commit/rollback, expected O(log n) get/put."""
from dataclasses import dataclass
from random import Random
@dataclass(frozen=True)
class Node:
key: str
value: str
priority: int
left: "Node | None" = None
right: "Node | None" = None
def get(node: Node | None, key: str) -> str | None:
while node is not None:
if key == node.key:
return node.value
node = node.left if key < node.key else node.right
return None
def split(node: Node | None, key: str) -> tuple[Node | None, Node | None]:
if node is None:
return None, None
if node.key < key:
left_of_right, right = split(node.right, key)
return Node(node.key, node.value, node.priority, node.left, left_of_right), right
left, right_of_left = split(node.left, key)
return left, Node(node.key, node.value, node.priority, right_of_left, node.right)
def merge(left: Node | None, right: Node | None) -> Node | None:
if left is None:
return right
if right is None:
return left
if left.priority > right.priority:
return Node(left.key, left.value, left.priority, left.left, merge(left.right, right))
return Node(right.key, right.value, right.priority, merge(left, right.left), right.right)
class TransactionalKV:
def __init__(self, seed: int = 0):
self.root: Node | None = None
self.snapshots: list[Node | None] = []
self.rng = Random(seed)
def begin(self) -> None:
self.snapshots.append(self.root)
def commit(self) -> None:
if not self.snapshots:
raise RuntimeError("no active transaction")
self.snapshots.pop()
def rollback(self) -> None:
if not self.snapshots:
raise RuntimeError("no active transaction")
self.root = self.snapshots.pop()
def get(self, key: str) -> str | None:
return get(self.root, key)
def put(self, key: str, value: str) -> None:
left, rest = split(self.root, key)
middle, right = split(rest, key + "\0")
priority = middle.priority if middle is not None else self.rng.getrandbits(64)
self.root = merge(merge(left, Node(key, value, priority)), right)
复杂度
begin/commit/rollback 只操作根指针栈顶，为严格 O(1) 时间；get/put 在随机 Treap 上期望 O(log n)，最坏 O(n)。每次 put 复制 O(log n) 期望节点，活跃快照共享未变子树；历史版本不可达后可由垃圾回收释放。并发 CAS 方案的重试次数另计。
易错点与追问
容易失分的边界
- 把 begin 时复制整个 dict 称 O(1)。
- commit 时把整个事务 diff 合并到父层，却声称严格 O(1)。
- 只测单层事务，漏掉内层 commit 后外层 rollback。
- 把单线程共享 snapshots 栈直接用于多线程，事务互相污染。
- 声称事务边界 O(1) 就代表 get/put 也 O(1)。
继续深挖
- 若要求 delete 与范围扫描，持久化树如何扩展？
- 多线程并发写同一个 key 时，CAS 冲突和隔离级别如何定义？
- 内存历史版本太多，如何限制长事务并做持久化 GC？
- 若固定 key 宇宙可用 persistent trie，单次操作复杂度怎样变化？
