如何递归计算两个对象间可双向应用的diff差异补丁

公认通用规范 #

目前针对可序列化结构化对象（尤其是JSON兼容对象）的Diff/补丁领域，有明确的IETF公认标准，完全可以覆盖双向无损转换、版本回溯的需求：

• JSON Patch（RFC 6902）：这是目前生态最成熟、通用性最强的正式标准，原生定义6种原子操作：add、remove、replace、move、copy、test。标准本身定义的是单向补丁，但所有操作都天然可逆：add操作的逆是对应路径的remove，remove操作的逆是携带被删原始值的add，replace操作的逆是用旧值替换新值的replace，move操作的逆是反向路径移动。只需要在生成补丁时同步记录对应逆操作，不需要自定义全新格式，就能实现双向无损的补丁回放。目前几乎所有主流编程语言都有成熟的JSON Patch实现库，不需要从零编写核心Diff逻辑。
• JSON Merge Patch（RFC 7396）：这是另一个轻量IETF标准，但存在天生缺陷：无法精确描述数组修改、无法区分字段删除和赋值为null的场景，做不到复杂结构的无损转换，完全不适合数据库版本回溯的场景，不建议选用。
• 其余面向协同编辑的OT、CRDT类差分格式都属于场景特定方案，没有通用行业共识，生态适配差，不适合作为通用存储补丁格式。

面向数据库记录全生命周期回溯的实现建议 #

• 不要从零发明全新补丁格式：基于RFC 6902做最小扩展即可，在补丁结构中额外携带逆操作列表、前序版本校验值，就能满足双向回放需求，同时保留和现有生态工具的兼容性，后续要做Diff可视化、跨系统数据同步都不需要额外做格式转换。
• 生成补丁时注意无损比对：必须严格区分类型，避免动态类型语言中0、false、null、空字符串、空数组、空对象的误判；数组比对建议用最长公共子序列算法识别插入、删除、替换操作，不要直接转字符串做全量比对，避免生成冗余补丁、出现值偏差。
• 优化回放性能：存储补丁时直接预计算好正向、反向两套操作列表，不要在回放时实时计算逆操作；每个补丁携带对应版本的校验信息，应用补丁前用RFC 6902原生的test操作校验当前对象状态和补丁预期的基准状态一致，避免错序应用补丁导致脏数据。
• 不需要担心性能问题：成熟的JSON Patch实现对数组、嵌套对象的差分效率足够支撑常规业务场景，存储的补丁体积相比存储全量版本快照通常能缩小90%以上，回放速度远快于全量版本拷贝拼接。

内容的提问来源于stack exchange，提问作者user2344885