安全笔试中的撤销/恢复：从双栈到事务性回滚设计

1. 考察点还原：安全笔试中的撤销/恢复到底在考什么

看到“奇安信笔试 撤销/恢复”这个题目，很多人第一反应是：这不就是一个栈的经典应用吗？双栈法，一个栈存撤销历史，一个栈存恢复历史，LeetCode上类似题目一大堆。但如果你真按刷题思路去准备，大概率会在笔试现场踩坑。

我接触过不少安全行业的笔试题目，也帮几个准备校招的朋友做过模拟测试。奇安信这类安全厂商考撤销/恢复，表面上考的是数据结构，实际上考的是两件事：第一，你能不能把“撤销/恢复”从纯文本编辑场景抽象成通用能力；第二，你知不知道在安全业务里，撤销/恢复往往意味着什么——配置回滚、策略变更、审计溯源，甚至故障恢复。这已经不是简单的“用两个栈模拟”能cover住的了。

笔试中这类题的常见出现形式有两种。一种是纯算法题，要求你设计一个数据结构，支持插入、删除、撤销、恢复操作，时间复杂度有明确要求。另一种是系统设计题，给你一个安全产品的场景，比如防火墙规则配置平台、终端管控策略下发系统，要求你设计撤销/恢复模块，要考虑并发、存储、权限、审计。两种都考，但第二种更能拉开差距，因为绝大多数人只会做第一种。

所以这篇文章我打算按两条线来讲：一条线是纯算法实现，从双栈到命令模式再到事务性撤销，把代码写扎实；另一条线是把撤销/恢复能力往安全业务场景迁移，讲讲配置回滚和策略变更的快照设计。两条线都打通了，笔试面试基本就稳了。

提示：如果你是临时抱佛脚，优先把第2章和第3章吃透，代码能默写；如果你还有两三天时间，第4章和第5章的思路一定要看，安全厂商特别吃这一套。

2. 核心实现思路：从双栈到命令模式的演进路线

2.1 双栈法的核心思想与隐藏约束

双栈法是最基础的实现，思路一句话就能讲完：维护两个栈，undoStack存历史操作，redoStack存被撤销的操作。执行新操作时压入undoStack，清空redoStack；撤销时从undoStack弹出操作并逆执行，压入redoStack；恢复时从redoStack弹出操作并正执行，压入undoStack。

代码写出来很简单，但笔试真正想考的是边界条件的处理。一个很隐蔽的约束是：新操作会清空恢复栈。也就是说，你先撤销了A，然后执行了一个新操作B，那么刚才撤销的A就再也恢复不回来了。这个语义是行业标准——几乎所有主流编辑器的撤销/恢复都是这么设计的。为什么？因为恢复栈里保存的是“历史分叉”，新操作意味着你选择了新分支，旧分支就作废了，不然恢复行为会产生歧义。

另外一个约束是操作记录的粒度。如果你把每个字符的插入都当成一个操作，那么输入“hello”就需要压栈5次，撤销时也要逐字符撤销。用户体验很差。所以实际工程中要做“操作合并”——把连续的同类型操作合并成一个批次。比如在输入框里连续打字，合并成一次“文本变更”，撤销时一次回退整个单词或整个输入过程。

这个思路在笔试中也值得主动提一句，因为考官/阅卷人看到你能主动考虑操作粒度合并，就知道你是有工程意识的人，而不是单纯背题。

2.2 命令模式与备忘录模式的选型逻辑

双栈法虽然直观，但有个致命缺陷：它假设所有操作都是可逆的，而且逆操作是确定性的。文本编辑器里“插入字符”的逆操作是“删除字符”，这没问题。但安全业务里很多操作是不可逆的——比如你往密钥管理系统里写入了一个新的密钥，你没法“撤销”写这个动作，因为密钥已经生效了；你能做的只是把状态恢复到写入之前，而这需要显式保存历史状态快照。

所以在系统设计层面，命令模式和备忘录模式是更普适的方案。

命令模式的核心思想是：把每个操作封装成对象，对象内部定义两个方法——execute()和undo()。执行操作时调用execute()，撤销时调用undo()。这个模式的好处是操作的可逆逻辑由操作对象自己负责，调用方不关心具体怎么撤销。比如“创建用户”这个操作，undo()就是“删除用户”；“修改密码”这个操作，undo()就是“恢复旧密码”——当然，旧密码得提前备份。

备忘录模式更进一步：不保存操作本身，而是保存状态快照。每次操作前，把当前完整状态存到一个备忘录对象里，然后放进历史栈。撤销时直接弹出最近的备忘录，把系统状态恢复成快照里的样子。这个方案简单粗暴，适合状态不算太庞大的场景。

两种模式如何取舍？我的经验是三条判断标准：

• 操作数量级：命令模式每个操作只存一份指令和参数，省内存；备忘录模式每个快照要存完整状态，如果状态很大，内存会爆。
• 操作复杂程度：如果操作步骤多、逆操作逻辑复杂容易写错，备忘录模式更省心，因为“保存状态”永远是对的。
• 状态变更频度：高频小变更建议命令模式，低频大变更建议备忘录模式。

举个例子，一个配置中心管理着几千条策略，每条策略几十个字段。每次变更产生一个全量快照，那内存得爆炸。正确做法是存差异（diff），或者用命令模式记录“这次改了哪个字段、从什么值改成什么值”。

2.3 事务性撤销：更贴近工程实践的重磅设计

如果你的代码做到了命令模式，恭喜，你已经领先了60%的候选人。但安全厂商的笔试往往还会加一问：“如果一个批量操作涉及多个步骤，中间某一步失败了，你怎么保证数据一致性？”这就引出了事务性撤销。

事务性撤销的思路是：把一个批量操作视为一个事务，事务里的每个子操作都走命令模式记录到临时列表。事务执行过程中，如果某一步抛异常，就把临时列表里已经执行过的子操作逐个undo()，相当于整体回滚。事务全部成功之后，才把这个临时列表作为一个整体压入全局撤销栈。这样做的好处是：撤销栈里的一条记录对应一个完整事务，用户一次撤销，整个批量变更全部回退，不会出现撤了一半的中间态。

这个设计在数据库领域叫“事务回滚日志”，在安全业务里叫“变更回滚预案”，其实是同一个东西。我参与过的某安全产品的策略批量下发功能，就是用这个思路做的：一批策略推给终端，部分终端成功、部分失败，失败的触发回滚，已成功的也要执行“补偿操作”恢复到下发前状态。这个逻辑在笔试里如果你能主动提出来，绝对是个大加分项。

3. 完整实现：手写一个支持撤销/恢复的编辑器核心模块

3.1 类设计与数据结构定义

理论讲再多，不如直接写代码。我给出一份可直接运行的Python实现，模拟一个文本编辑器里撤销/恢复的核心模块。整个项目代号叫模拟项目X，是我自己做的一个练手小项目，代码量不大，但胜在把命令模式和操作合并的思想都用上了。

先定义操作类型的枚举和操作对象的基类：

from abc import ABC, abstractmethod from enum import Enum from collections import deque class OpType(Enum): INSERT = "insert" DELETE = "delete" REPLACE = "replace" class TextOperation(ABC): """操作基类：所有可撤销操作都继承这个类""" def __init__(self, pos, text=""): self.pos = pos # 操作位置（字符索引） self.text = text # 操作涉及的文本内容 @abstractmethod def execute(self, buffer): """执行操作""" pass @abstractmethod def undo(self, buffer): """逆操作：撤销""" pass def merge(self, other): """尝试与相邻操作合并，返回合并后的对象或None""" return None

这一段定义了核心抽象。注意merge方法，这是前面说的操作合并机制的入口，我用它来把连续输入合并成一条记录。实际问题中，不合并的话，一个300字的文本录入就会产生几百条撤销栈记录，既占内存又难用。

然后定义三个具体操作类，插入、删除、替换：

class InsertOp(TextOperation): def execute(self, buffer): buffer[self.pos:self.pos] = list(self.text) def undo(self, buffer): del buffer[self.pos:self.pos + len(self.text)] def merge(self, other): # 连续插入且位置衔接，合并成一次插入 if isinstance(other, InsertOp) and other.pos == self.pos + len(self.text): merged = InsertOp(self.pos, self.text + other.text) return merged return None class DeleteOp(TextOperation): def __init__(self, pos, text): super().__init__(pos, text) # text保存的是被删除的内容，撤销时把它插回去 def execute(self, buffer): del buffer[self.pos:self.pos + len(self.text)] def undo(self, buffer): buffer[self.pos:self.pos] = list(self.text) def merge(self, other): # 连续删除且位置衔接，合并成一次删除 if isinstance(other, DeleteOp) and other.pos == self.pos: merged = DeleteOp(self.pos, self.text + other.text) return merged return None class ReplaceOp(TextOperation): """替换操作：保存旧文本和新文本""" def __init__(self, pos, old_text, new_text): super().__init__(pos, new_text) self.old_text = old_text def execute(self, buffer): buffer[self.pos:self.pos + len(self.old_text)] = list(self.text) def undo(self, buffer): buffer[self.pos:self.pos + len(self.text)] = list(self.old_text)

替换操作我单独做了个类型，因为它的逆操作不是简单的增或删，而是“把新的换回旧的”，务必保留old_text。这在文本编辑器里对应选区替换场景，在配置管理里对应字段值修改场景——一个道理。

3.2 撤销/恢复管理器：执行、撤销、恢复的完整逻辑

有了操作对象，接下来就是管理器类。管理器维护两个栈：undo栈和redo栈。为了性能和控制内存上限，我没有用Python自带的list直接当栈，而是用deque，并设置最大长度：

class UndoRedoManager: def __init__(self, max_history=50): self.undo_stack = deque(maxlen=max_history) self.redo_stack = deque(maxlen=max_history) def apply(self, buffer, op: TextOperation): """执行新操作，压入undo栈，清空redo栈""" # 尝试与栈顶操作合并 if self.undo_stack: top = self.undo_stack[-1] merged = top.merge(op) if merged is not None: self.undo_stack[-1] = merged op.execute(buffer) # 合并后仍需执行op，但栈里只留合并后的记录 self.redo_stack.clear() return op.execute(buffer) self.undo_stack.append(op) self.redo_stack.clear() def undo(self, buffer): """撤销：弹出undo栈顶，执行逆操作，压入redo栈""" if not self.undo_stack: return False op = self.undo_stack.pop() op.undo(buffer) self.redo_stack.append(op) return True def redo(self, buffer): """恢复：弹出redo栈顶，执行操作，压回undo栈""" if not self.redo_stack: return False op = self.redo_stack.pop() op.execute(buffer) self.undo_stack.append(op) return True def history_size(self): return len(self.undo_stack), len(self.redo_stack)

这里有个细节值得注意——合并时我仍然先执行了op，再把栈顶替换为合并后的对象。这样保证缓冲区内容正确，栈顶记录则变成一个更大的合并操作。下次撤销时，一次会撤回所有合并过的内容。

不过这个合并逻辑有个bug隐患：如果top.merge(op)返回了合并对象，但是合并对象的text构造有误，后续撤销会出错。所以合并方法要写得非常小心，最好写单元测试覆盖。我在下面第5章会专门讲测试。

3.3 边界处理与内存控制：笔试现场容易被追问的点

笔试最常见的追问是“你的撤销栈会不会内存爆炸”。所以我在管理器的构造函数里加了max_history参数，用deque的maxlen特性，超出限制自动丢弃最旧记录。50这个值是我调出来的——文本编辑场景下50步足够用户反悔，再往前的操作早就没意义了。内存开销方面，一条INSERT操作记录大概存一个位置整数和一段文本，Python对象本身有点重量，但50条也就是几十KB级别，完全可控。

另一个边界是空栈撤销。管理器里的if not self.undo_stack: return False就处理了。实际项目中返回False后UI层要灰掉“撤销”按钮，属于联动逻辑，这里不展开。

还有一个笔试爱问的边界：光标位置在操作后的修正。文本插入后，原来在插入点之后的字符位置都要向后移动，删除相反。我在管理器的实现里没有显式处理光标，因为Buffer是字符数组，操作类自己负责基于pos做片段切割，光标的定位逻辑得由编辑器的光标管理模块完成。如果你在笔试时能主动说“我在这个抽象里只处理了数据层的撤销，光标位置需要另外维护一个offset映射”，会显得思维很完整。

4. 进阶场景：把撤销/恢复迁移到安全业务中

4.1 配置中心的变更回滚怎么设计

纯文本编辑器的撤销/恢复做完之后，我们再往前迈一步：如果撤销的对象是安全产品的策略配置呢？

假设你参与了一个终端安全管理系统的模拟项目X，系统里有一张策略表，每条策略包含策略ID、规则表达式、生效范围、优先级等字段。安全运维人员经常需要批量修改策略，比如“把所有终端的上传带宽限制从10Mbps改成5Mbps”。这个批量操作涉及的表记录可能有几千条。如果改完发现效果不符合预期，需要一条命令整体回滚。

你当然可以选择用备忘录模式，在每次批量修改前把涉及的所有策略全量快照保存下来。但如果策略数量大、字段多，内存消耗极高。更合理的做法是结合命令模式和差异存储：每条策略的修改封装成一个UpdatePolicyOp，记录policy_id、修改的字段名、旧值、新值。undo()方法就是把对应字段从新值改回旧值。

class UpdatePolicyOp: def __init__(self, policy_id, field_name, old_value, new_value): self.policy_id = policy_id self.field_name = field_name self.old_value = old_value self.new_value = new_value def execute(self, policy_store): policy_store.update_field(self.policy_id, self.field_name, self.new_value) def undo(self, policy_store): policy_store.update_field(self.policy_id, self.field_name, self.old_value)

配合事务性撤销，这个批量变更可以这么组织：

class BatchTransaction: def __init__(self): self.ops = [] def add_op(self, op): self.ops.append(op) def execute_all(self, policy_store): executed = [] try: for op in self.ops: op.execute(policy_store) executed.append(op) except Exception: # 出错则回滚所有已执行的操作 for op in reversed(executed): op.undo(policy_store) raise

这段代码放在笔试里作为“扩展设计”回答，能直接体现出你对数据一致性问题的敏感度。安全产品对一致性的要求比普通业务系统高得多——策略下发一半失败导致终端处于无管控状态，这是重大生产事故。

4.2 策略下发的快照与快速恢复机制

再进一步，如果批量操作过程中，远程终端已经有一部分收到了新策略，另一部分没收到，怎么回滚？这就不是单纯的数据层撤销能解决的了，需要引入“两阶段提交”或“补偿事务”的思路。

我在实际项目中的做法是：先给所有目标终端打一个“预下发标记”，终端收到标记后不立即生效，而是先缓存。全部终端确认收到标记后，再广播“正式生效”指令。如果中间有终端失联或者校验不通过，就广播“取消下发”，各终端丢弃缓存并维持旧策略。这个方案也常被称为“灰度发布+快速回滚”。

这里面的核心思想是：不要等服务变更出了问题才去撤销，而是在变更前就设计好回滚路径。配置管理里叫“变更窗口”，金融系统里叫“灰度开关”，安全领域里叫“熔断降级”，本质都是给变更兜底。撤销/恢复这个经典算法题，放到业务里就成了容错设计的一部分。

这个进阶点如果你在笔试的最后问答题部分主动写出来，跟你和面试官聊“两阶段提交”的效果差不多——因为大部分候选人只会写双栈模拟，而你已经在思考分布式环境下的回滚一致性了。

4.3 审计日志与撤销记录的联动

安全领域的操作还有一个特殊要求——审计。运营人员做了撤销操作，系统必须记录：谁在什么时间撤销了哪个操作，撤销前和撤销后的状态分别是什么。这个审计需求的实现，其实就是在命令模式的基础上加一个观察者或事件回调。

class AuditedUndoRedoManager(UndoRedoManager): def __init__(self, audit_logger, max_history=50): super().__init__(max_history) self.audit_logger = audit_logger def undo(self, buffer): if super().undo(buffer): self.audit_logger.log("UNDO", self.undo_stack, buffer)

这里没必要展开代码，核心考点是：你能不能在基础功能之上，把可扩展性点说出来。审计日志、权限控制、操作人身份、IP、时间戳，这些都是安全产品里绕不开的。笔试题目叫“撤销/恢复”，你答出审计联动，说明你懂安全。

5. 笔试与面试中的高频追问与答题策略

5.1 常见问题速查表

我把这些年看到的关于撤销/恢复的笔试面试题做了一个汇总，做成速查表：

这个表我建议你背下来，不仅笔试有用，面试深挖的时候也能快速组织语言。

5.2 答题节奏与代码风格建议

笔试现场时间有限，我建议的答题节奏是：先用5分钟明确题目要求，判断是纯算法还是系统设计题。纯算法题直接上双栈+操作合并，代码控制在40行左右。系统设计题不要急着写代码，先用流程图把操作流画出来，再标注每个环节的数据结构。

代码风格方面注意三点。

第一，函数命名要有语义。不要写a()、b()，写undo()、execute()、merge()。安全公司的人写代码都很严谨，命名风格出卖你的工程习惯。

第二，边界条件提前写。空栈判断、非法参数校验，这些在一开始就写好，不要等代码写完了才发现漏了。

第三，主动写注释解释关键设计。笔试阅卷不会一行行跑代码，更多是看思路。你在关键位置写一行注释：“新操作必须清空redo栈，避免历史分叉”，阅卷人一眼就知道你懂原理。

5.3 一个被忽视的加分项：内存占用分析

很多候选人代码写对了，但追问“你这个方案的内存复杂度是多少”时卡壳。双栈法最坏情况下，两个栈各存N个操作，每个操作对象O(1)大小（不考虑文本内容长度），总空间复杂度是O(N)。但如果操作对象内部挂了完整文本内容，比如插入操作存了整个句子，那空间复杂度还要乘以文本长度L，实际是O(N×L)。

我习惯在答题末尾主动补一句：“本实现中每个操作对象持有文本内容，最坏空间复杂度为O(N×L)，如果文本较长可以通过游标或指针共享来优化，但会增加实现复杂度。”这句话看似轻描淡写，实际体现了你在性能和复杂度之间的权衡意识。很多笔试官就吃这一套。

5.4 实测中的常见错误清单

我在调试模拟项目X的过程中，踩过几次坑，列出来帮大家避雷。

第一个坑是合并逻辑破坏了撤销的正确性。我最初把合并写成了在execute之后直接修改栈顶，但合并后的对象包含了两次操作的总文本，而缓冲区只执行了第二次操作的变更。结果就是撤销时把第一次操作的成果也一并撤掉了。后来我改成“先execute再替换栈顶”，并且专门写了测试用例验证三种合并场景。

第二个坑是缓冲区类型的混用。我一开始用字符串管理文本，执行插入操作时buffer[:pos] + text + buffer[pos:]，看起来很合理。但撤销操作需要按索引精确切片删除，字符串的不可变性导致每次都要重建，性能很差。后来改成字符数组list[str]，所有操作直接在原数组上做切片赋值，性能提升明显。笔试如果考到文本编辑器实现，建议直接用数组，面试官问起来也好聊。

第三个坑是合并条件的过度宽松。DELETE操作的合并条件是other.pos == self.pos，也就是连续删除时新操作总是从同一个位置开始删。这在逻辑上是正确的，因为每次删除后，原来的后一个字符会移动到当前位置。但如果中间夹了一次光标移动，合并就不该发生。解决办法是把光标位置作为合并判断条件之一——只有光标位置没有移动过的连续删除才合并。这个细节笔试里提到的概率不低，大家留意一下。

个人实操体会

做这个模拟项目X之前，我一直以为撤销/恢复就是个双栈题。等真正撸完代码、踩完上面的坑，才意识到中学课本里“数据结构是算法的基础”这句话有多实在——但光有栈是不够的，设计模式、事务思维、审计扩展，这些工程化的东西才是安全厂笔试真正想筛的能力。

如果你时间紧，我最后给一条最实在的建议：把第3章的代码自己动手敲两遍，第一遍不看答案，第二遍加合并逻辑和事务批量操作。能连续两遍跑通并讲清楚每个边界条件，去笔试遇到类似的撤销/恢复题，基本就稳了。这个题考察的从来就不是“会不会用栈”，而是“你用栈的时候，脑子里有没有装着真实业务”。