Notion 如何使用 CRDTs 处理并发编辑

# Notion如何通过CRDT处理并发编辑 来源：https://www.notion.com/blog/how-notion-handles-concurrent-editing-with-crdts Notion编辑器常用于协作场景，成百上千的团队成员共同写作和工作。但直到2025年，Notion才真正实现实时协作。为帮助人们更无缝地协作，我们重新设计了底层的文本编辑系统和数据模型。这包括实现一套支持冲突自由的富文本编辑系统，并针对Notion基于块(https://www.notion.com/blog/data-model-behind-notion)的文档模型开发了处理特殊情况的技术。 首先，假设有Emma和Charlie两位用户正在编辑同一个文本块： Emma将文本更新为： 而Charlie将文本更新为： Emma和Charlie各自持有一个版本的块，彼此**并未感知**对方的编辑。他们进行的是“并发”编辑。 理想情况下，服务器应该将两个更新合并为： 然而服务器按照到达顺序逐个处理块记录的更新，后到的更新决定了最终结果：“快速构建”或“构建酷东西”。在这种“最后写入胜出”（LWW）系统中，某个人的编辑会**完全丢失**。随着协作者数量增多，个人修改被他人覆盖的可能性也会增加。 Notion页面在表面上仍显得协作流畅，因为页面通常由多个块组成，每个块存储为独立的数据库记录。人们可以同时编辑不同块而互不干扰，但编辑同一块时仍会产生冲突，导致用户丢失修改。此外，推出离线模式(https://www.notion.com/blog/how-we-made-notion-available-offline)会增加数据丢失风险——离线编辑页面的用户，可能在重新连接时发现所有修改已因他人对相同块的编辑而丢失。 那么我们如何解决这个问题？我们采用了**冲突自由复制数据类型**（CRDT）来支持跨块的富文本编辑，允许用户同时编辑、拆分和合并文本。 ## CRDT简介 CRDT是一种允许客户端保存同一数据的本地副本，并确定性地合并同步变更的数据结构。采用CRDT的主要原因是确保并发编辑能被合并而不丢失任何人的修改。即使修改未被完全丢失，每位协作者的意图也未必能完美保留。如果Emma希望文本**恰好**是“构建酷东西”，合并后的结果就无法实现该目标。但在长文档中，人们通常修改同一文本中相隔较远的部分，CRDT在这些情况下能很好地保留编辑意图。 我们使用的CRDT基于经典的序列型CRDT——**复制可增长数组**（RGA）。RGA是一种树状数据结构，包含曾插入的所有字符，每个字符表示为具有唯一稳定ID的节点。插入或删除文本的操作可以引用这些ID。我们将这些节点称为“文本项”，被引用的ID称为“来源”。树初始化时包含`起始`和`结束`两个项。让我们回顾最初的例子： 插入的字符表示如下： Notion CRDT系统中的字符表示 这是一个在来源`A@6`后插入“c”的操作： 我们看到ID为`A@6`的项是一个空格字符： Notion CRDT字符树版本2，Emma 以下是应用Emma插入“cool”和Charlie插入“quickly”操作后得到的树： 2026-09-15 字符树版本3，Emma和Charlie 删除操作会将项标记为已移除，但仍保留为“墓碑”。这是因为可能存在依赖于被删除字符ID的进行中或离线操作。若从树中移除这些项，我们将无法确定操作的应用位置。 以下是删除“cool”后的墓碑状态： 2026-09-15 字符树版本3墓碑 上述示例中使用的ID如`A@1`，其中`A`是简化的“会话ID”（用于区分客户端会话），`1`是Lamport时钟（递增的逻辑时间戳）。会话ID与Lamport时钟共同确保ID唯一性：两个客户端可能在Lamport时钟上冲突但会话ID不同，而单个客户端始终基于其已知的最高（严格说是最近的）时钟值递增Lamport时钟。 指向同一来源的项按逻辑时间戳降序排列，会话ID作为平局决胜依据。 以下是在`A@12`后插入ID为`E@18`和`C@13`的操作： 2026-09-15 字符树版本3 E@18与C@13 由于`18`大于`13`，结果总是解析为： 我们可以通过不为**每个字符**分配ID来提升存储效率。字符通常按词分组，因此可以为同一会话和Lamport时钟下的连续字符序列分配单个ID，并额外存储序列长度。 “cool”被删除的示例简化为： 2026-09-15 移除cool后的字符树 ## 支持富文本 Notion文档富含加粗、斜体和页面引用等格式。这意味着我们需要解决的冲突不仅来自文本编辑，还包括富文本标注的应用。 假设Charlie应用加粗： 同时Emma应用斜体： 我们希望最终文本同时包含两种标注： 为支持富文本，我们引入了基于Peritext(https://www.inkandswitch.com/peritext/)算法的操作。我们的CRDT树存储在文本项上添加和移除标注的操作。解析树时可以应用这些标注。 加粗“cool things”会创建如下操作，其中“起始”和“结束”定义标注范围： “起始”和“结束”锚点定义在项边界紧前或紧后的位置。此例中锚点分别位于`E@13`紧前和`C@13`紧前： 2026-09-15 字符树构建酷东西快速 这些锚点允许我们指定标注是否“可延伸”。加粗是可延伸标注，意味着在加粗文本末尾输入新内容时，新文本也会继承加粗格式。这就是为什么结束锚点是“在`C@13`之前”，因为`A@12`之后（`C@13`之前）的文本仍保持加粗。 2026-09-15 字符树可延伸加粗循环 相比之下，超链接不是可延伸标注。若“cool things”被设为超链接，结束锚点应是“在`A@12`之后”。因为当用户在“s”字符后输入时，我们**不希望**后续文本也带有超链接。 2026-09-15 字符树可延伸链接循环 2026-09-15 字符树超链接 一个文本项可能附加多个标注。为支持重叠标注，每个文本项可存储标注操作数组。标注可能跨越多个项，但我们仅在其首个项存储操作；ID范围用于标识后续项。 ## 并发拆分文本 在Notion中，用户在块中部按“回车”会创建新块，并将文本拆分到两个块中。 以下示例中，Emma在“Build”后拆分块： 同时Charlie追加空格和单词“quickly”： 结果应为： 若Emma的拆分先应用，Charlie的添加应落入新块（块B），**即使**Charlie是在原块（块A）中进行的编辑。这意味着我们需要识别用户编辑的块，因为并发编辑可能导致用户编辑指向已不在同一数据库记录中的来源。 为支持可能同时在块间移动的文本编辑，我们开发了几个新概念。 首先是“文本切片”。块中的文本项属于一个文本切片，每个块初始化时空文本切片。当Emma拆分块A时，其文本切片被分为两部分，第二部分移至块B。 2026-09-15 字符树文本切片 属于同一块的文本切片组织成“文本切片树”，代表该块中的文本。文本切片树可包含源自不同块的切片。 当Emma拆分块A时，两个块的文本切片树变化如下。重建每个树即可获得其块中的文本： 2026-09-15 字符树文本切片2 文本切片还属于“文本实例”——这是对源自同一初始切片的切片的概念分组，包含起始块的ID。即使切片被拆分或移动，它始终保留相同的文本实例。这意味着一个块可包含来自多个文本实例的切片： 2026-09-15 字符树含多个切片的块 我们可以将文本实例作为稳定标识符用于操作引用。这让我们维护了文本实例到包含该实例任意切片的块的映射。每当块接收来自新文本实例的切片时，我们就更新映射。当收到特定文本实例的操作时，我们通过此映射确定需获取哪些块来定位和编辑目标切片。 Emma拆分后，映射显示实例A的切片同时存在于块A和块B： 2026-09-15 文本实例与块映射表 Charlie插入“quickly”的操作仍可引用块A，但使用的是文本实例ID而非块ID： 然后我们可以利用文本实例↔块映射获取相关块（此例中同时包含块A**和块B**）来查找待编辑的文本切片。 此设计的局限性在于，为查找特定文本切片可能需获取**多个**块，因为无法直接通过文本切片查找块。服务器会加载**所有**包含相关实例**任意切片**的块。将块拆分99次，最终得到100个块，每个都包含同一文本实例的切片。这意味着要插入字符到其中某个切片，实例↔块映射会提示需获取100个块，之后还需遍历它们的文本切片树来定位目标切片。 为解决此问题，我们设计了“搜索标签”。每个文本切片都有搜索标签，用于在文本实例内唯一标识。文本切片初始为空标签，每次拆分时我们追加`L`或`R`。 以下是Emma拆分块A后的搜索标签： 2026-09-15 拆分块A后的搜索标签 若她继续将“things”拆分为“thing”和“s”，则“thing”的标签变为`RL`，“s”变为`RR`： 2026-09-15 搜索标签RL与RR 我们可以将搜索标签添加到文本实例↔块映射中，并在操作中包含它，然后用它来限制查询映射时返回的块数量。 回到之前的例子，Emma拆分“Build things”： 映射表包含以下标签： 2026-09-15 含搜索标签的映射表 假设Charlie的客户端已知晓更新，他插入“quickly”。他的操作将包含标签R： 查询映射时，我们搜索实例A中标签**以R开头**的块，实际只需获取一个块（之前需两个）。 之所以查找标签**以提供的标签开头**的块而非精确匹配，是因为目标切片可能已被并发拆分。若Emma在Charlie追加内容时拆分“things”（且她的修改先生效），他的操作仍会包含标签`R`，即使目标切片现已标记为`RR`。 实际实现中，我们并未在文本切片上存储`LRL`这样的标签并用Postgres查询`.. label LIKE 'LR%'`。而是使用紧凑编码，将存储效率提升了五倍。 尽管未经验证，我们推测处理块拆分的这种方法也可能适用于其他将文本块建模为独立节点的文本编辑系统。例如，在使用Yjs的ProseMirror编辑器中，拆分被建模为在第一块删除并在第二块插入。因此并发编辑可能仍留在原始节点，而我们的方法则保留其在拆分过程中的预期位置。 ## 试用 我们制作了这个交互组件来阐释本篇博客介绍的部分概念。希望您能享受探索过程，并增进对我们CRDT系统的理解。 ## 总结 在Notion，我们的规模和灵活数据模型为将CRDT研究的理念应用于现实世界的协作编辑器带来了有趣且实际的挑战。 2025年7月，我们将此系统投入生产，使其成为全球最大的CRDT部署之一——每分钟处理数百万次CRDT操作。 2026-09-15 CRDT事务量 我们的CRDT数据模型还支持离线模式和智能体协作，并为未来功能奠定了有用基础。我们期待利用这一基础来改进实时协作者状态显示，或实现批量建议的发布与接受。 编辑器是我们工作和协作的核心，但其背后技术常被忽视。希望本文能让您窥见“共同打字”这一简单行为背后的复杂性，并激发您对日常工具构建原理的好奇。 *这项工作离不开Angelique Nehmzow、Atul Varma、Ben Hughes、Charlie Andrews-Jubelt、Emma Guo、Fabricio Pontes Harsich、Jake Peyser、Kathleen Gao、Matthew Weidner、Michael Kuo、Rohit Valiveti、Ryan Billard、Shahan Khan、Slim Lim、Stephan Boyer和Yifei Shen的贡献。* *有志于参与此类问题的解决？我们持续寻找志在构建协作软件未来的优秀工程师。请查看我们在*notion.com/careers (https://notion.com/careers)*的职位空缺。*