Building Conclave：一个去中心化的、实时的、协作的文本编辑器

在这里尝试 Conclave

点击此处阅读我们的深入案例研究

注意：Conclave 已停止维护，且未达到生产环境要求。不过，其代码已开源，可供学习使用。

2018 年，GitHub 发布了 TeleType。Teletype 是一个由三人远程团队构建的插件，允许在 Atom 代码编辑器中进行协作编辑。

Teletype 利用 WebRTC 和无冲突复制数据类型实现了这一点。这是一款非常酷的软件，你绝对应该尝试一下。

然而，这并不是 Teletype 诞生的故事。

这是另一个远程三人团队在同一时间段使用完全相同的技术构建不同的开源协作编辑器的描述。

这篇文章是关于秘密会议的。

Conclave 是一个去中心化的、实时的、协作的浏览器编辑器。本文将探讨我们面临的诸多挑战以及我们找到的解决方案。希望在本文结束时，你们中的许多人能够自己创建一个协作编辑器。这是一个非常有趣的项目，我们强烈推荐给所有感兴趣的开发者。

即使你对创建自己的编辑器不感兴趣，你仍然可以从本文中学到很多东西。创建和扩展实时应用程序的许多经验教训可以应用于软件工程的其他领域。

如果您对以下任一内容感兴趣：

分布式系统
高级数据结构
无需中央数据存储即可保持一致性

继续阅读。

认识团队

在我们开始之前，我想向创建 Conclave 的杂牌开发团队致以最崇高的敬意。

真是一群英俊的人。

他们是来自加州旧金山的Elise Olivares、来自明尼苏达州明尼阿波利斯的Nitin Savant，以及来自纽约布鲁克林的Sun-Li Beatteay。很高兴能一起打造这个项目。

现在，谈谈技术。

为什么要使用协作编辑器？

一个明智的问题是：为什么首先要构建协作编辑器？

我们团队经常使用 Google Docs，一直对它的底层工作原理很感兴趣。讽刺的是，用 Google 搜索 Google Docs 的工作原理却毫无头绪。他们对自己的专有软件讳莫如深。

最后我们决定，如果谷歌不告诉我们，那么下一个最好的学习方法就是我们自己构建它。

有趣的软件工程挑战

除了是一种了解 Google Docs 如何运作的创造性方式之外，创建一个实时协作的文本编辑器还带来了一些有趣的软件工程挑战：

在合并冲突操作的同时保持所有用户的一致性。
尽可能减少延迟以达到实时效果。
扩展实时应用程序。

让我们详细讨论一下每一个挑战。

挑战 1：保持一致性/合并冲突的操作

协作编辑器最重要的部分是保证所有用户的一致性。毕竟，如果文档不一致，它就毫无用处。

但这是如何实现的呢？

要回答这个问题，重要的是要准确了解文本编辑器是什么以及它如何工作。

什么是文本编辑器？

在我们的项目中，我们将文本编辑器定义为一个可以插入或删除文本字符的空间。每个字符都有一个值和一个数字索引，用于确定其在文档中的位置。

例如，对于文本“HAT”，第一个字符的值为“H”且位置为 0，“A”的位置为 1，“T”的位置为 2。

可以根据字符的位置索引插入或删除该字符。要在文本开头插入“C”，操作为 insert("C", 0)。此插入操作会导致所有其他字母的位置向右移动 1 位。

要删除“H”需要执行操作 delete(1)。

一个用户编辑一个文档很简单，但如果我们希望多个用户同时编辑同一个文档怎么办？

多个并发用户

首先，我们需要为每个用户提供文档的本地副本，并允许他们进行编辑。请记住，我们的目标是“实时”。我们希望用户能够像使用简单的文本编辑器一样立即应用他们的编辑。

接下来，我们需要一种方式让用户能够通知其他用户他们所做的编辑。我们将引入一个中央中继服务器来促进这种沟通。

两个用户通过中央中继服务器连接。

当用户尝试同时进行编辑时，就会出现这种情况的问题。

交换性

举个例子，假设有两个用户都以单词“HAT”开头。一个用户插入了“C”，而另一个用户删除了“H”，他们的编辑都会发送给另一个用户进行合并。

糟糕！一个用户有“HAT”，另一个用户有“CAT”。他们的文档没有收敛到同一个状态。

出现这种分歧的原因是插入和删除操作没有交换。

交换律是指不同的运算无论以何种顺序执行，结果都相同。加法和乘法都是交换律。

幂等性

让我们尝试另一个例子，用户同时决定他们要从“HAT”中删除“H”以获得“AT”。

文档确实收敛了，但我们遇到了另一个问题！两个用户最终得到的都是“T”，而不是“AT”。他们俩都不希望出现这样的结果。这是因为删除操作不是幂等的。

幂等性是指重复运算产生相同的结果。例如，乘以 1 就是一个幂等运算。无论将一个数乘以 1 多少次，结果都是相同的。

一致性要求

查看前面的两个示例，我们可以看到协作文本编辑器必须具有以下属性才能在所有用户之间保持一致：

交换性：无论应用的顺序如何，并发的插入和删除操作都会收敛到相同的结果。
幂等性：重复的删除操作产生相同的结果。

问题确定之后，我们该如何解决呢？我们的团队进行了大量的研究，最终找到了两个可行的解决方案。

运营转型（OT）

如果你熟悉分布式系统，你可能会认为“运营转型可以解决这个问题”。这也是我们找到的第一个解决方案。

为了尽量简洁起见，我们不会深入讨论 OT 是什么。为了让您了解我们为何决定不使用 OT，请阅读以下一位 Google 工程师的引言：

不幸的是，实现 OT 很糟糕。市面上有上百万种算法，它们各有优劣，但大多局限于学术论文。这些算法要想正确实现，难度极大，耗时耗力。[…] Wave 的开发耗时两年，如果我们今天重写，那么第二次编写也几乎需要同样长的时间。——
Joseph Gentle（Google Wave/ShareJS 工程师）

如果您有兴趣了解有关 OT 的更多信息，可以阅读我们的案例研究的运营转型部分。

无冲突复制数据类型（CRDT）

我们发现的另一个解决方案是无冲突复制数据类型 (CRDT)。CRDT 最初是由试图简化 OT 的研究人员创建的。OT 依赖于复杂的算法来保持一致性，而 CRDT 则采用了更先进的数据结构。

CRDT 通过将文档中的每个字符转换为具有特定属性的唯一对象来进行操作。

siteId：用于识别创建该站点的用户的 ID。
值：对象代表哪个字母。
位置：一个整数列表，表示字符在文档中的位置。此位置是相对于其周围字符的。

将字母转换为字符对象

由于每个字符都是唯一的，并且可以通过这些属性进行识别，因此我们可以防止任何字符被多次插入或删除。这实现了交换性和幂等性。

这种方法的缺点是元数据量很大。这会增加我们应用程序的内存消耗。不过，由于 CRDT 的整体复杂度明显低于 OT，我们对这种权衡还是比较满意的。

如何创建相对位置

除非您已经熟悉 CRDT，否则您可能会想“他提到的‘相对位置’属性是什么？它是如何创建的？”请允许我们详细说明。

相对位置是区分 CRDT 和 OT 的关键概念。即使删除周围的字符，CRDT 中字符的位置也不会改变。此外，相对位置始终可用于确定字符在文档中的位置。

现在的问题是：我们如何创建这些相对位置？

我们可以把字符及其位置想象成树上的节点。当我们输入一个字母时，它的位置大于它前面的字符，但小于它后面的字符。

如果我们写单词“CAT”，每个字母可能会获得如下图所示的位置。

示例职位

但是，如果我们想在两个相邻的位置之间插入一个字符怎么办？如果我们想把“CAT”变成“CHAT”，那么2到3之间没有整数。为此，我们需要向下移动到树的下一层，并在该层选择一个位置。

在相邻位置之间插入字符。

这会创建一个小数索引。“C”的位置为 1，“A”的位置为 2，“H”的位置为 1.5。在代码中，我们将这个小数表示为一个整数数组。

分数位置作为整数数组。

CRDT 交换性和幂等性

如果我们回到前面的例子，我们可以看到 CRDT 是如何保持交换性和幂等性的。字符的小数索引也包含在内以供参考。

CRDT 交换性

使用相对位置可以让我们更明确地确定要删除哪个字母以及它的位置。由于这种特殊性，交换性就不再是问题了。

CRDT 幂等性

此外，由于每个字符都是唯一的，我们不能从 CRDT 中多次删除它。

要了解有关如何在代码中实现 CRDT 的更多信息，请查看我们的案例研究的“编写 CRDT代码”部分。

挑战 2 和 3：减少延迟并扩展实时应用程序

现在我们已经讨论了如何合并冲突并保持一致的文档，现在是时候解决剩下的两个问题了：延迟和扩展。

我们当前的系统架构依赖于客户端-服务器通信模型。每个用户通过 WebSocket 连接连接到中央服务器。中央服务器充当中继，将每个用户的操作转发给网络中的所有其他用户。

多个用户通过中央中继服务器连接。

这个模型还有什么改进空间吗？为了找到改进方法，我们必须首先明确其局限性。

中央中继服务器的局限性

第一个限制是用户之间不必要的高延迟。所有操作都通过服务器进行。即使用户坐在一起，他们仍然必须通过服务器进行通信。

加州的两个用户通过纽约的服务器进行通信大约需要 200 到 300 毫秒。这个延迟直接影响了我们应用程序的“实时性”。如果他们可以直接互相发送消息，那么只需要几毫秒。

美国各地的延迟。

第二个限制是中央服务器的扩展成本可能很高。随着用户数量的增加，服务器必须处理的工作量也相应增加。为了支持这一点，服务器需要额外的资源，这需要花费成本。

对于资金充足的初创公司来说，这不是问题。作为创建开源项目的团队，我们希望尽可能地降低财务成本。

最后，依赖中央服务器会造成单点故障。一旦服务器宕机，所有用户将立即失去相互协作的能力。

对等架构

我们可以通过切换到点对点架构来消除这些限制。这样，每个用户都可以同时充当客户端和服务器，而不是像以前那样只拥有一个服务器和多个客户端。

每当用户进行更改或接收来自其他用户的操作时，他们都可以将该操作转发给与其连接的所有用户。这将允许消息在网络两端的用户之间直接传递。

在分布式系统中，这被称为Gossip 协议。

P2P架构

如何创建P2P系统？

为了让用户能够直接相互发送和接收消息，我们使用了一种名为WebRTC的技术。WebRTC 是“Web 实时通信”的缩写，是一种专为点对点连接通信而设计的协议。

虽然 WebRTC 使我们的用户能够直接连接，但需要一个小型服务器来启动这些点对点连接，这个过程称为“信令”。

值得一提的是，虽然 WebRTC 依赖于此信令服务器，但不会通过它发送任何文档内容。它仅用于发起连接。一旦连接建立，信令服务器就不再需要了。

在用户之间建立 WebRTC 连接。

为了简洁起见，我们不会深入探讨 WebRTC 的工作原理。对于 Conclave，我们使用了一个名为PeerJS的库来处理大部分繁琐的工作。

要了解有关创建 P2P 系统、WebRTC 以及 WebRTC 安全性的更多信息，请查看我们的案例研究的P2P 部分。

因果关系

我们尚未涉及的一个概念是如何维持因果关系。因果关系是指原因与结果之间的关系。维持因果关系就是在有原因的情况下保证结果的发生。

在协作文本编辑器的环境中，保证因果关系意味着所有操作都将按照其执行的顺序接收。

在服务器-客户端模型中维持因果关系已经够难了，但在使用 WebRTC 的 P2P 系统中，这更是难上加难。原因在于 WebRTC 使用UDP传输协议。

UDP 有助于降低延迟，因为它允许用户快速发送消息，而无需接收方响应。但其缺点是它无法保证数据包按序投递。

这就带来了一个潜在的问题。如果用户在插入某个字符之前收到删除该字符的消息，该怎么办？

下图中，有三个节点正在协作处理一个文档。其中两个节点彼此相邻，而第三个节点距离较远。Peer1 输入“A”，并将操作发送给两个节点。由于 Peer2 就在附近，它很快就收到了该操作，但觉得它不喜欢，于是立即将其删除。

Peer1 插入一个字符，Peer2 立即将其删除。

现在插入和删除操作都正在前往对等点 3。由于互联网的不可预测性，删除操作比插入操作更快。

删除操作先于插入操作到达Peer3。

如果删除操作在插入操作之前到达 Peer3，会发生什么情况？我们不希望先执行删除操作，因为这样就没有任何内容可删除，操作就会丢失。之后，当执行插入操作时，Peer3 的文档看起来会与其他文档不同。因果关系就会丢失。

我们需要找到一种方法来延迟删除操作，直到我们应用插入之后。

版本向量

为了解决这个问题，我们实现了所谓的“版本向量”。这听起来很花哨，但它实际上是一种跟踪每个用户操作的策略。

每当发出操作时，除了角色对象和操作类型（插入/删除）之外，我们还会包含角色的站点 ID和站点计数器值。站点 ID 指示最初发送该操作的用户，而计数器指示该操作来自该特定用户的操作编号。

当对等体收到删除操作时，它会立即被放入删除缓冲区。如果是插入操作，我们可以立即应用它。但是，对于删除操作，我们必须先确保字符已经插入。

每次收到其他用户的操作后，都会对删除缓冲区进行“处理”，检查相应的字符是否已经插入。如果已经插入，则可以执行删除操作。

在此示例中，待删除的字符的站点 ID 为 1，计数器为 24。为了检查该字符是否已插入，Peer3 会查询其版本向量。由于 Peer3 仅看到了来自 Peer1 的 23 个操作，因此删除操作将保留在缓冲区中。

第一次处理缓冲区时，删除操作尚未准备好由 Peer3 应用。

又过了一段时间，插入操作终于到达 Peer3，并且其版本向量已更新，以反映它已从 Peer1 看到了 24 个操作。

由于我们收到了新的操作，我们再次处理删除缓冲区。这一次，当将删除操作的字符与版本向量进行比较时，我们发现补码插入已完成。删除操作可以从缓冲区中移除并应用。

这次删除操作可以由Peer3应用。

最终系统架构

有了版本向量，协作文本编辑器就可以完全正常运行了。我们最终构建的应用程序的系统架构如下所示。

最终系统架构

示例用户流程可能如下所示：

用户将一封信插入到他们的文本编辑器中
该更改被添加到他们的 CRDT 并转换为角色对象。
该本地插入通过 Messenger 类广播给其余用户——该类本质上是 WebRTC 的包装器。
同一个 Messenger 类还负责接收来自其他用户的操作。这些接收到的操作会根据 Version Vector 和 CRDT 进行验证，然后才会被合并到编辑器中。

控制器类用于所有不同组件之间的通信并确保一切顺利运行。

结论

我们希望您喜欢阅读我们的旅程，就像我们享受旅程本身一样！如果您想了解更多关于 Conclave 的信息，并学习如何自己实现协作编辑器，请点击此处查看我们的完整案例研究。

感谢您的阅读，祝您编码愉快！

鏂囩珷鏉ユ簮锛�https://dev.to/sunnyb/building-conclave-a-decentralized-real-time-collaborative-text-editor-1jl0