Sunday面试指南

OT 和 CRDT 有什么区别?多人协同编辑时怎样合并并发修改?

下面是一段模拟面试对话。

🧑‍💻 面试官:两个人同时编辑一段文字,怎样让最后看到的内容一致?

🙋‍♂️ 我:通过 WebSocket,把修改广播给其他人。

🧑‍💻 面试官:原文是 ab,两个人都在 a 后面插入字符。一个插 X,一个插 Y,各自已经先显示了自己的输入。再照着原位置应用对方的操作,会发生什么?

🙋‍♂️ 我:两边的 X、Y 顺序可能不一样。

🧑‍💻 面试官:所以消息送到了还不够。你准备怎样处理这些基于旧内容产生的位置?

协同编辑要解决的不只是消息传输。并发修改发生后,所有副本还需要按照同一套规则,解释这些修改并得到一致内容。

面试速答(60 秒版)

OT 和 CRDT 都能用于协同编辑,但处理并发的方式不同。

OT 会根据已经发生的并发修改,对操作做转换。比如前面多插入了一个字符,后面的插入位置就可能需要向后调整。它需要正确的转换规则,以及与这些规则配套的版本和同步协议。

CRDT 则把合并规则设计进数据结构。以序列型 CRDT 为例,字符通常有稳定标识,并发插入也有一致的排序规则,因此副本可以在同步后得到相同结果。具体实现不一定都采用同一种标识或合并算法。

选型时,我会先看编辑器支持、离线需求、历史数据体积、权限和撤销语义,再选成熟实现。WebSocket 只负责传输;算法收敛也不代表结果一定符合人的意图,更不代表自动具备权限控制和完整的协作产品能力。

OT 与 CRDT,怎样处理并发编辑?

知识点详解:从同时插入两个字符说起

原位置为什么不能直接照用?

咱们假设两个人最初都看到 ab,下标从零开始。

  • A 在位置 1 插入 X,本地变成 aXb。
  • B 在位置 1 插入 Y,本地变成 aYb。

如果收到远端修改后,仍然原封不动地在位置 1 插入,A 会得到 aYXb,B 会得到 aXYb。操作都没有丢,结果却不同。

问题出在“位置 1”对应的是修改前的版本。发生本地编辑以后,当前位置已经不是原来的那个上下文了。

下面的例子只讨论纯文本插入,帮助理解机制,不是一套可以直接用于生产的协同算法。

OT 会转换操作,让它适应已经改变的内容

假设这套协议为同位置并发插入约定 X 在 Y 前面。

A 已经插入 X,收到 B 原来“在 1 插入 Y”的操作时,要把它转换成在位置 2 插入 Y,于是得到 aXYb。

B 已经插入 Y,收到 A 的操作时,按同样的优先规则,在位置 1 插入 X,也得到 aXYb。

这里不仅要调整偏移,还要让双方在同位置冲突时采用一致的规则。加入删除、连续编辑、富文本格式后,转换会复杂得多,不能只写一个“位置加一”就宣布完成 OT。

ShareDB 的类型机制把操作转换交给具体 OT 类型;传输、存储和协调框架并不自动替你实现所有文档类型的转换。它的总体架构采用服务端协调客户端编辑,但不要把这种架构扩大成“所有 OT 在理论上都必须有中心服务器”。

同位置插入,为什么要转换?

CRDT 不依赖不断猜测当前数组下标

序列型 CRDT 可以为插入元素保留稳定标识,并记录它与已有元素的相对关系。两个用户在同一个间隙插入时,算法用确定的规则安排先后,而不是让各客户端仅凭到达顺序决定结果。

可以把稳定标识理解成“这是哪一个元素”,把下标理解成“它目前排在第几位”。前面插入内容时,下标会变,元素身份不应跟着变。

这只是理解入口。CRDT 还包含集合、计数器等不同类型,不能用序列的实现方式概括全部 CRDT。Yjs 内部机制说明可用于进一步了解实际协作类型怎样组织内容。

对于 Yjs,文档更新 API规定更新可以重复应用、改变应用顺序;所有副本收到完整更新后可以同步到一致状态。这里指库产生的有效更新,不是说任意业务 JSON 改动都能随意交换顺序。

元素身份稳定,显示下标会变

算法一致,不等于用户觉得合并得合理

例如 A 想删除整句话,B 同时在里面补一个词。即使所有人最后都得到同一份文字,B 新补的词该保留还是删除,仍然涉及具体算法语义和产品预期。

因此,评估时至少要分开看三个问题。

问题要验证什么
副本能否收敛乱序、重复投递和断线重连后是否一致
编辑是否符合预期并发插删、格式调整和光标移动是否合理
产品规则是否成立无权限用户能否改动,撤销是否只撤回自己的操作

Yjs 的 UndoManager支持按事务来源等条件管理撤销。它提醒我们,协同场景的“撤销”不能简单等同于把整个文档替换成上一次快照,否则可能覆盖其他人的修改。

收敛只是协同编辑的一部分

工程选型,还得看哪些成本?

已有编辑器成熟支持哪一套方案,通常比抽象争论谁更先进更有用。还要检查离线期间能否继续编辑,重连同步多少数据,历史怎样保存,以及格式、批注和撤销是否匹配需求。

CRDT 的标识、删除记录等元数据会有成本;具体能否回收取决于算法和同步假设。Yjs 也明确说明,只合并二进制更新并不等于完成删除内容的垃圾回收。不能用“最终只剩几个字”推断历史数据一定很小。

OT 同样需要处理版本、待确认操作、历史截断与重连。算法名称不能替代对真实文档和长时间编辑轨迹的测试。

面试官继续追问

CRDT 是不是就不需要服务器了?

算法可以支持不同网络拓扑,但产品往往仍需要服务端负责身份、文档权限、持久化和连接管理。把服务器去掉,不会让这些需求自然消失。

客户端生成的修改,可以直接广播吗?

不能只看数据格式有效就放行。必须把修改关联到有权限的用户和文档。还要限制更新体积、频率,处理被撤销权限后的离线更新;这些是应用设计问题,不由收敛规则自动解决。

你会怎样做验收?

先构造同位置插入、插入与删除交错、重复更新和离线重连,再让不同客户端按不同顺序接收相同修改。比较最终文档之外,也检查光标、撤销、权限和同步体积。本文没有把这些建议包装成已运行的协作系统测试。

面试速记卡

  • WebSocket 解决传输,不负责解释并发编辑。
  • OT 根据并发修改转换操作,需要配套同步协议。
  • CRDT 将确定的合并规则放入数据类型,不等于没有顺序规则。
  • 收敛不代表保留所有用户意图,也不代替权限和撤销设计。
  • 结合编辑器生态、离线需求、历史体积和真实冲突轨迹选型。

公司面试真题

真题根据求职者公开面经整理,题意经过概括,非逐字原话或公司官方题库;本文为 Sunday 的独立解析。

浏览公司面试真题 →
简历汪永久免费在线制作简历,模板直接套用、导出无水印,永久免费、下载免费,不需要付费解锁任何功能。去写简历