题目重点：用每层增量覆盖而非整库拷贝，实现 get/set/delete、begin/commit/rollback；子提交只合并父层。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 单线程内存实现；缺失 get 抛 KeyError，删除不存在返回 False，commit/rollback 无活动事务报错。这些错误协议题目未明确。
- 事务层保存键→值或删除哨兵，最外层 commit 才改全局；不提供隔离级别、持久化或跨线程并发。
解题路线
- 基础 committed 哈希表保存已提交状态，layers 栈保存每个活跃事务的写集；get 从栈顶到栈底查第一个命中，删除哨兵表示即使父层有值也应视为不存在，栈均未命中才读 committed。
- set 写当前最顶层，若无事务直接写 committed；delete 先检查可见性，活跃事务中写 tombstone，不提前删除父层/全局。
- begin 压空层。commit 弹顶层：如果还有父层，就把顶层全部变化覆盖父写集；否则应用到 committed。rollback 直接丢弃顶层，保留父视图。
- 嵌套例：父 set K=A、子 set K=B、子 commit 后父读 B；父 rollback 丢弃整个父写集，global 仍无 K。用独立快照模型对 600,000 次短序列状态检查核对。
手动走一遍
db.set('k','base'); begin(); set('k','parent'); begin(); delete('k'); get 报缺失；rollback() 恢复父视图 `parent`；begin(); set('k','child'); commit() 后父读 `child`；父 rollback 后全局又读 `base`。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
_DELETED = object()
class TransactionalKV:
"""In-memory nested overlays; child commit merges into parent, not global."""
def __init__(self) -> None:
self.committed: dict[str, str] = {}
self.layers: list[dict[str, str | object]] = []
def get(self, key: str) -> str:
for layer in reversed(self.layers):
if key in layer:
value = layer[key]
if value is _DELETED:
raise KeyError(key)
return value
return self.committed[key]
def set(self, key: str, value: str) -> None:
target = self.layers[-1] if self.layers else self.committed
target[key] = value
def delete(self, key: str) -> bool:
try:
self.get(key)
except KeyError:
return False
if self.layers:
self.layers[-1][key] = _DELETED
else:
del self.committed[key]
return True
def begin(self) -> None:
self.layers.append({})
def commit(self) -> None:
if not self.layers:
raise RuntimeError("no transaction")
changes = self.layers.pop()
if self.layers:
self.layers[-1].update(changes)
else:
for key, value in changes.items():
if value is _DELETED:
self.committed.pop(key, None)
else:
self.committed[key] = value
def rollback(self) -> None:
if not self.layers:
raise RuntimeError("no transaction")
self.layers.pop()
复杂度
set/delete/begin 期望 O(1)（delete 需 get，故按深度 d 最坏 O(d)）；get 最坏查 d 层为 O(d) 平均哈希访问；commit 最坏 O(本层变更键数)，rollback O(1) 丢引用（垃圾回收另计）；空间为 global 键数加所有活跃层写集。
易错点与追问
容易失分的边界
- 子事务 commit 直接改全局，父 rollback 无法撤销。
- 删除父层已有键时直接删父层，子 rollback 无法恢复。
- 空字符串或 None 当删除哨兵，与合法值混淆。
- 每次 begin 整库复制，不必要的 O(N) 成本。
- 把本题的事务解释成持久 ACID 数据库保证。
继续深挖
- 同一 key 在父/子层都删改，读视图如何确定？
- 若要跨线程并发，隔离与冲突检测怎样做？
- 如何实现 commit 后崩溃恢复？
- 大量嵌套层读取太慢，能否加缓存且保持 rollback 正确？
