有序序列的实时编辑

One of the problems we had to solve when we added multiplayer editing to Figma was supporting simultaneous editing of ordered sequences of objects. We have many compound object types in Figma (the document, groups, components, etc.) and each compound object has an ordered list of children. Users can insert new children, remove children, or drag them around to reorder them and everything updates in realtime:

在为 Figma 添加多人编辑时，我们必须解决的一个问题是支持同时编辑对象的有序序列。我们在 Figma 中有许多复合对象类型（文档、组、组件等），每个复合对象都有一个有序的子列表。用户可以插入新的子对象，删除子对象，或者拖动子对象来重新排序，一切都在实时更新。

Realtime collaborative editing of an ordered sequence in Figma

在Figma中实时协作编辑一个有序的序列

The core problem is maintaining eventual-consistency. Each client instantaneously applies its edits locally and then sends them off to the server, which then sends the edits to other connected clients. This means edits may be applied in a different order on each client. When designing the algorithm, we have to make sure the document ends up looking identical regardless of the order in which edits are applied.

核心问题是保持最终的一致性。每个客户端都会在本地即时应用其编辑内容，然后将其发送到服务器，服务器再将编辑内容发送给其他连接的客户端。这意味着每个客户端的编辑可能以不同的顺序应用。在设计算法时，我们必须确保文件最终看起来是一样的，无论编辑的顺序是什么。

Operational Transformation

业务转型

We initially considered using a technique called Operational Transformation to solve this. It’s an old algorithm that was originally developed for text and was popularized by early collaborative text editors such as Google Wave. While we didn’t end up using OT, it’s perhaps the most common approach to this type of problem and it’s useful to contrast OT with our approach. In OT, new operations are carefully transformed past other concurrent operations such that the resulting operation has the same effect:

我们最初考虑使用一种叫做操作转换的技术来解决这个问题。这是一种古老的算法，最初是为文本开发的，被早期的协作式文本编辑器（如Google Wave）所推广。虽然我们最终没有使用OT，但它也许是解决这类问题的最常见的方法，将OT与我们的方法进行对比是很有用的。在OT中，新的操作被小心翼翼地转化为其他并发的操作，以便产生的操作具有相同的效果。

An example of concurrent text editing using OT

使用OT进行并发性文本编辑的一个例子

In the picture above, transforming the operation Delete(at: 1, n: 2) past the operation Insert(at: 0, text...