Fugue: A Basic List CRDT
赋格：基本列表 CRDT

Matthew Weidner | Oct 21st, 2022
马修·韦德纳 | 2022 年 10 月 21 日
Home | RSS Feed
主页 | RSS 订阅
Keywords: collaborative text editing, CRDTs, Lists, Fugue, Plain Tree
关键词：协作文本编辑，CRDTs，列表，Fugue，普通树

Update: This post was previously titled “Plain Tree: A Basic List CRDT”. Since posting, I and Martin Kleppmann wrote a paper about this list CRDT and renamed it Fugue.
更新：此帖子以前的标题是“Plain Tree: A Basic List CRDT”。发布后，我和 Martin Kleppmann 撰写了一篇关于这个列表 CRDT 的论文，并将其更名为 Fugue。

The main ideas in this post are described in slides here.
这篇帖子中的主要观点在这些幻灯片中描述。

Collaborative text editing was the original motivation for Conflict-free Replicated Data Types (CRDTs) (WOOT 2005), and it is still a popular use case. It is also the most difficult CRDT application: the underlying List CRDTs have complicated algorithms and implementations, and there are a lot of them spread throughout academic papers and software libraries. This makes them intimidating to study.
协作文本编辑是冲突自由复制数据类型（CRDTs）（WOOT 2005）的最初动机，仍然是一个流行的使用案例。它也是最困难的 CRDT 应用程序：底层的列表 CRDT 具有复杂的算法和实现，而且它们分布在许多学术论文和软件库中。这使得它们令人望而生畏。

In this post, I describe Fugue, a basic List CRDT that I find fairly easy to understand, plus some simple implementations. My goal is that you will also understand it, filling in a gap from my previous post. Despite its simplicity, the CRDT described here is my preferred List CRDT. In particular, Collabs uses it for all list implementations.
在这篇文章中，我描述了 Fugue，这是一种基本的列表 CRDT，我发现它相当容易理解，还有一些简单的实现。我的目标是让您也能理解它，填补我之前文章中的空白。尽管它很简单，但这里描述的 CRDT 是我首选的列表 CRDT。特别是，Collabs 将其用于所有列表实现。

You don’t need to have read the previous post, Designing Data Structures for Collaborative Apps, but its introduction may be useful if you are new to CRDTs and collaborative editing.
您不需要阅读先前的帖子《为协作应用设计数据结构》，但如果您对 CRDT 和协作编辑不熟悉，它的介绍可能会有所帮助。

# What We Need: A “Uniquely Dense Total Order”
＃我们需要什么：一个“独特密集的全序”

To start, let’s think about making a collaborative plain text editor, like this Collabs demo. The editor’s state is a text string, replicated on each user’s device, such that any user can insert (type) or delete characters from the string.
首先，让我们考虑制作一个协作纯文本编辑器，就像这个 Collabs 演示。编辑器的状态是一个文本字符串，在每个用户的设备上复制，以便任何用户都可以在字符串中插入（输入）或删除字符。

In usual CRDT style, we mandate that all users see their own changes immediately, but also reflect other users’ changes once they receive them, possibly after an unbounded network delay. The end result must be consistent across all users (CRDT correctness/strong eventual consistency) and should also be “reasonable”, e.g., edits to two different parts of the text each show up as expected.
在通常的 CRDT 风格中，我们要求所有用户立即看到自己的更改，但也要在收到其他用户的更改后反映这些更改，可能会有无限的网络延迟。最终结果必须在所有用户之间保持一致（CRDT 正确性/强最终一致性），并且还应该是“合理的”，例如，对文本的两个不同部分进行编辑应该如预期那样显示。

We can generalize this problem to collaborating on arbitrary lists of immutable values. Collaborating text editing is a special case: a list of characters. A List CRDT is a CRDT for such lists, with insert and delete operations. Formally, the operations on a List CRDT are:
我们可以将这个问题推广到协作处理任意不可变值列表。协作文本编辑是一个特例：字符列表。列表 CRDT 是用于这种列表的 CRDT，具有插入和删除操作。形式上，列表 CRDT 上的操作是：

• insert(i, x): Inserts a new element with value x at index i, between the existing elements at indices i and i+1. All later elements (index >= i+1) are shifted one to the right.
  insert(i, x) ：在索引 i 处插入具有值 x 的新元素，位于现有索引 i 和 i+1 之间的元素之间。所有后续元素（索引 >= i+1 ）向右移动一个位置。
• delete(i): Deletes the element at index i. All later elements (index >= i+1) are shifted one the left.
  delete(i) ：删除索引为 i 的元素。所有后续元素（索引 >= i+1 ）向左移动一个位置。

Handling concurrent operations—while ensuring that the results are consistent for all users and also reasonable—is tricky because concurrent operations mess up each others’ indices.
处理并发操作——同时确保结果对所有用户一致且合理——是棘手的，因为并发操作会混乱彼此的索引。

Alice typed " the" at index 17, but concurrently, Bob typed " gray" in front of her. From Bob's perspective, Alice's insert should happen at index 22.
爱丽丝在索引 17 处键入了“the”，但与此同时，鲍勃在她前面键入了“gray”。从鲍勃的角度来看，爱丽丝的插入应该发生在索引 22 处。

To handle this, most List CRDTs abandon indices internally. Instead, they assign each list element a unique immutable position at the time of insertion, which abstractly describes how to sort elements relative to each other. The user-visible state of the List CRDT is just the elements sorted by their positions. insert and delete internally operate on positions, only using their index argument i to look up the current positions at/near that index.
为了处理这个问题，大多数列表 CRDT 在内部放弃索引。相反，它们在插入时为每个列表元素分配一个唯一的不可变位置，这个位置抽象地描述了如何相对于其他元素对元素进行排序。列表 CRDT 的用户可见状态只是按照它们的位置排序的元素。内部操作位置，只使用它们的索引参数来查找接近该索引的当前位置。

If two users insert elements concurrently, then those elements are sorted based on their positions. Since all users see the same positions (and the same sort order on positions), they all sort these concurrent elements identically, ensuring CRDT correctness. Deleting one element doesn’t affect the positions of any other elements, so it is easy to ensure correctness for delete operations as well (see my previous post for details).
如果两个用户同时插入元素，则这些元素将根据它们的位置进行排序。由于所有用户看到相同的位置（以及相同的位置排序顺序），他们都以相同的方式对这些并发元素进行排序，确保 CRDT 的正确性。删除一个元素不会影响任何其他元素的位置，因此很容易确保 delete 操作的正确性（有关详细信息，请参阅我的先前帖子）。

So, to make our List CRDT (hence our collaborative plain text editor), all we need is a way to sort and create these unique immutable positions. In other words, we need an implementation of the following TypeScript interface (also on GitHub):
因此，要创建我们的列表 CRDT（因此是我们的协作纯文本编辑器），我们只需要一种方法来排序和创建这些独特的不可变位置。换句话说，我们需要实现以下 TypeScript 接口（也在 GitHub 上）：

/**
 * Helper interface for sorting and creating unique immutable positions,
 * suitable for use in a List CRDT.
 *
 * @type P The type of positions. Treated as immutable.
 */
export interface UniquelyDenseTotalOrder<P> {
  /**
   * Usual compare function for sorts: returns negative if a < b in
   * their sort order, positive if a > b.
   */
  compare(a: P, b: P): number;

  /**
   * Returns a globally unique new position c such that a < c < b.
   *
   * "Globally unique" means that the created position must be distinct
   * from all other created positions, including ones created concurrently
   * by other users.
   *
   * When a is undefined, it is treated as the start of the list, i.e.,
   * this returns c such that c < b. Likewise, undefined b is treated
   * as the end of the list.
   */
  createBetween(a: P | undefined, b: P | undefined): P;
}

Mathematically, this interface says that positions must be drawn from a total order, with two extra requirements:
数学上，该接口表示位置必须从一个全序中绘制，并且还有两个额外要求：

• It is dense: between any two elements a < b, there is a c such that a < c < b.
  它是密集的：在任意两个元素 a < b 之间，存在一个 c ，使得 a < c < b 。
• Furthermore, it is uniquely dense: users can request a new globally unique such c between any a < b. (Unlike “dense total order”, this is not a standard math term.)
  此外，它是独特密集的：用户可以在任何 a < b 之间请求一个新的全局唯一的 c 。（与“密集全序”不同，这不是一个标准的数学术语。）

A few notes about the UniquelyDenseTotalOrder interface:
关于 UniquelyDenseTotalOrder 接口的一些注释：

• An implementation may choose to have state that it uses in compare and createBetween. For example, an optimized implementation will often store all the positions it has seen in a sorted data structure, then use that to answer compare calls quickly.
  一个实现可以选择在 compare 和 createBetween 中使用的状态。例如，优化的实现通常会将其看到的所有位置存储在排序的数据结构中，然后使用它来快速回答 compare 的调用。
• An implementation may choose to behave like a CRDT itself, e.g,. by broadcasting messages to replicas of the UniquelyDenseTotalOrder on different devices (op-based CRDT) and/or by implementing a merge function (state-based CRDT). For example, an implementation might broadcast newly-created positions to other users in createBetween, together with metadata needed to compare them to existing positions.
  一个实现可以选择像 CRDT 本身一样行为，例如，通过向不同设备上 UniquelyDenseTotalOrder 的副本广播消息（基于操作的 CRDT），和/或通过实现合并函数（基于状态的 CRDT）。例如，一个实现可以将新创建的位置与所需的元数据一起广播给 createBetween 中的其他用户，以便将它们与现有位置进行比较。

You may be familiar with fractional indexing, which uses a dense total order, and wonder how UniquelyDenseTotalOrder differs. The answer is our added “globally unique” requirement: if two users call createBetween(a, b) concurrently for the same a and b, then we require both users to get different results. That way, it’s later possible to createBetween those two results.
您可能熟悉使用密集全序的分数索引，想知道 UniquelyDenseTotalOrder 有何不同。答案在于我们增加的“全局唯一”要求：如果两个用户同时为相同的 a 和 b 调用 createBetween(a, b) ，则我们要求两个用户获得不同的结果。这样，以后就可以 createBetween 这两个结果。

Starting from text "ab", two users concurrently type 'c' and 'd' at the same place. After syncing, the order of 'c' and 'd' is arbitrary but must be consistent across all users; suppose 'c' is first, so the text is now "acdb". Later, a user might try to type 'e' in between 'c' and 'd'. This doesn't work with fractional indexing because 'c' and 'd' have the same position - there are no positions "between" them. But it does work in a UniquelyDenseTotalOrder-based List CRDT, due to our global uniqueness requirement.
从文本“ab”开始，两个用户同时在同一位置键入'c'和'd'。同步后，'c'和'd'的顺序是任意的，但必须在所有用户之间保持一致；假设'c'在前，所以文本现在是"acdb"。稍后，用户可能会尝试在'c'和'd'之间键入'e'。这在分数索引中不起作用，因为'c'和'd'具有相同的位置-没有“在它们之间”的位置。但在基于列表 CRDT 的 UniquelyDenseTotalOrder 中可以工作，这是由于我们的全局唯一性要求。

# A Basic Uniquely Dense Total Order
＃基本唯一密集全序

It remains to implement UniquelyDenseTotalOrder. That’s what most List CRDT papers do, although they usually wrap it in the UniquelyDenseTotalOrder-to-List-CRDT conversion.
还需要实现 UniquelyDenseTotalOrder 。这是大多数 List CRDT 论文所做的，尽管它们通常将其包装在 UniquelyDenseTotalOrder -to-List-CRDT 转换中。

The rest of this post introduces a basic UniquelyDenseTotalOrder that I especially like. Update: You can find more info in the paper “The Art of the Fugue: Minimizing Interleaving in Collaborative Text Editing” by myself and Martin Kleppmann.
本文的其余部分介绍了一个我特别喜欢的基本 UniquelyDenseTotalOrder 。更新：您可以在我和 Martin Kleppmann 合著的论文“赋格的艺术：最小化协作文本编辑中的交错”中找到更多信息。

I’ll focus on describing its semantics—how its created positions compare to each other, independent of their literal representation—and two simple, unoptimized implementations. In future posts, I hope to go into detail about properties, comparisons to other List CRDTs, and optimized implementations.
我将专注于描述其语义——如何比较创建的位置，而不考虑它们的字面表示——以及两种简单的、未经优化的实现。在未来的帖子中，我希望详细讨论属性、与其他列表 CRDT 的比较以及优化实现。

# Intro: String Implementation
# 介绍：字符串实现

Strings make good positions because they are already ordered, immutable, and can be made arbitrarily long. You can even sort them in CRDT-unaware contexts, e.g., sorting a List CRDT’s elements in a database using ORDER BY positions.
字符串很适合作为位置，因为它们已经被排序，是不可变的，并且可以任意延长。甚至可以在不了解 CRDT 的情况下对它们进行排序，例如，在数据库中对 List CRDT 的元素进行排序使用 ORDER BY positions 。

To make a UniquelyDenseTotalOrder<string>, we really just need to implement createBetween: given strings a and b with a < b in the lexicographic order, return a unique new string in between.
要创建一个 UniquelyDenseTotalOrder<string> ，我们只需要实现 createBetween ：给定字符串 a 和 b ，按照字典顺序，返回一个介于两者之间的唯一新字符串。

Here’s a simple way to do this:
这是一个简单的方法来做到这一点：

• For convenience, we require that all positions end in 'R'.
  为了方便起见，我们要求所有位置都以 'R' 结尾。
• If a is not a prefix of b, append a globally unique new string to a (see next paragraph) and return that plus 'R'. This will be greater than a because it’s longer, and less than b for the same reason that a < b.
  如果 a 不是 b 的前缀，则将全局唯一的新字符串附加到 a （请参见下一段），然后返回该字符串加上 'R' 。这将大于 a ，因为它更长，且小于 b ，原因是 a < b 。
• If a is a prefix of b (necessarily strictly shorter):
  如果 a 是 b 的前缀（必然严格较短）：
  1. Replace the 'R' at the end of b with an 'L'.
     用 'L' 替换 b 末尾的 'R' 。
  2. Append a globally unique new string to that (see next paragraph) and return it plus 'R'. This will be less than b because 'L' < 'R', and greater than a because a is still a strictly-shorter prefix.
     将一个全局唯一的新字符串附加到其中（请参见下一段），然后返回它加上 'R' 。这将小于 b ，因为 'L' < 'R' ，并且大于 a ，因为 a 仍然是一个严格较短的前缀。

How do we get a globally unique new string? One strategy is to make it random and sufficiently long, e.g., a UUID. However, UUIDs are rather long, making it inefficient to send positions over the network. Instead, we use a causal dot: a pair (replicaID, counter), where replicaID is a reasonably short ID for the local replica (device)—say 10 random characters—and counter is a local counter incremented for each causal dot.
我们如何获得一个全局唯一的新字符串？一种策略是使其随机且足够长，例如，UUID。但是，UUID 相当长，使得通过网络发送位置变得低效。相反，我们使用因果点：一对 (replicaID, counter) ，其中 replicaID 是本地副本（设备）的一个相当短的 ID，比如 10 个随机字符， counter 是每个因果点递增的本地计数器。

In code (complete code here):
在代码中（完整代码在此处）：

class StringFugue implements UniquelyDenseTotalOrder<string> {
  /**
   * Local replica ID, set in constructor.
   * All replicaIDs have the same length.
   */
  readonly replicaID: string;
  // Local counter.
  private counter = 0;

  createBetween(a: string | undefined, b: string | undefined): string {
    // A globally unique new string, in the form of a causal dot.
    const uniqueStr = `${this.replicaID}${this.counter++}`;
    
    if (a !== undefined && b !== undefined) {
      if (!b.startsWith(a)) {
        // a is not a prefix of b.
        return a + uniqueStr + 'R';
      } else {
        // a is a strict prefix of b.
        const bWithL = b.slice(0, -1) + 'L';
        return bWithL + uniqueStr + 'R';
      }
    } else {
      // Edge cases...
    }
  }
  
  // compare...
}

Or, a code golf version (note: slightly different positions):
或者，一个代码高尔夫版本（注意：位置略有不同）：

class GolfStringFugue implements UniquelyDenseTotalOrder<string> {
  readonly id: string;
  private c = 0;

  createBetween(a = "R", b = "Z"): string {
    return (
      // "One line" List CRDT :)
      (b.startsWith(a) ? b.slice(0, -1) + "L" : a) + `${this.id}${this.c++}R`
    );
  }

  // ...
}

I wouldn’t recommend using these exact implementations due to their large position sizes, but they could be useful in a pinch.
我不建议使用这些确切的实现，因为它们的位置尺寸很大，但在紧急情况下可能会有用。

# Semantics # 语义

The string implementation above works, but we’d like to understand it better.
上面的字符串实现是有效的，但我们希望更好地理解它。

I claim that mathematically, we can model our uniquely dense total order as a rooted binary-ish tree:
我声称，在数学上，我们可以将我们独特密集的全序模拟为一个根二进制树：

• Each node in the tree, except for the root, has a parent and a side (left or right child). Multiple nodes can have the same parent and side, which is why it is “binary-ish” instead of binary.
  树中的每个节点（除了根节点）都有一个父节点和一个侧面（左侧或右侧子节点）。多个节点可以有相同的父节点和侧面，这就是为什么它是“类二进制”而不是二进制。
• Each node is labelled by a causal dot.
  每个节点都由一个因果点标记。
• The sort order on nodes is given by the tree walk (in-order traversal): first traverse a node’s left children, then visit the node, then traverse its right children. Ties between children on the same side are broken using the causal dots.
  节点的排序顺序由树遍历（中序遍历）给出：首先遍历节点的左子节点，然后访问节点，然后遍历其右子节点。同一侧子节点之间的关系使用因果点来解决。
• Positions are given by nodes in the tree.
  位置由树中的节点给出。

Example of a tree with corresponding text "abcde". Observe that the root has two left children, sorted by their causal dots; this can happen due to concurrent insertions.
带有相应文本“abcde”的树示例。请注意，根节点有两个左子节点，按其因果点排序；这可能是由于并发插入而发生的。

The same tree with a new node ("alice", 2), inserted as a right child of ("alice", 0). Its text is now "afbcde". Note that this insertion corresponds to the hard case above (though with different text).
具有新节点（“alice”，2）的相同树，插入为（“alice”，0）的右子节点。现在它的文本是“afbcde”。请注意，此插入对应于上面的困难情况（尽管文本不同）。

In our string implementation, each string position describes a path in this tree, starting at the root: it alternates between listing the next node’s ID, and an 'L' or 'R' indicating whether the following node is a left or right child.
在我们的字符串实现中，每个字符串位置描述了树中的一条路径，从根开始：它在列出下一个节点的 ID 和 'L' 或 'R' 指示接下来的节点是左子节点还是右子节点之间交替。

You can check that the lexicographic order on strings then matches our sort order on tree nodes: the 'L's and 'R's ensure that a string position is sorted in between its left and right descendants in the tree (since "L..." < "R" < "R..."), and the lexicographic order on IDs matches the tree’s tie-breaking rule.
您可以检查字符串的词典顺序是否与树节点的排序顺序匹配： 'L' 和 'R' 确保字符串位置在树中的左右子节点之间排序（因为 "L..." < "R" < "R..." ），而 ID 的词典顺序与树的打破平局规则匹配。

Finally, createBetween(a, b) works as follows:
最后， createBetween(a, b) 的工作原理如下：

• If a is not an ancestor of b, create a new node as a right child of a, labeled by a new causal dot, and return that. (Example above.)
  如果 a 不是 b 的祖先，则创建一个新节点作为 a 的右子节点，标记为一个新的因果点，并返回该节点。（示例如上。）
• If a is an ancestor of b, create a new node as a left child of b, labeled by a new causal dot, and return that. (Example immediately below.)
  如果 a 是 b 的祖先，则创建一个新节点作为 b 的左子节点，标记为一个新的因果点，并返回该节点。（示例立即下方。）

The tree from above with another new node, ("david", 1). This time, it is a *left* child of ("alice", 1), since its left neighbor ("alice", 0) already has a right descendant. The text is now "agfbcde".
从上面的树上另一个新节点，("david", 1)。这一次，它是("alice", 1)的*左*子节点，因为它的左邻居("alice", 0)已经有一个右子孙。现在的文本是"agfbcde"。

# Tree Implementation # 树实现

We can implement our tree-based description literally. That is, we can program a UniquelyDenseTotalOrder using an explicit tree data stucture, instead of using the string implementation’s implicit tree.
我们可以按照字面意思实现我们基于树的描述。也就是说，我们可以使用显式树数据结构来编写 UniquelyDenseTotalOrder ，而不是使用字符串实现的隐式树。

The last section’s description is not quite an actual algorithm: it describes Fugue in terms of a single, global view of the tree, but in reality, each user has their own local copy of the tree. These local copies may be out of sync: there can be an arbitrary delay between when one user calls createBetween and when other users hear about the created position.
最后一节的描述并不完全是一个实际的算法：它描述了 Fugue，以单一的全局树视图的方式，但实际上，每个用户都有自己的本地树副本。这些本地副本可能不同步：当一个用户调用 createBetween 时，其他用户得知所创建位置之间可能存在任意延迟。

The real algorithm is:
真正的算法是：

• A position is represented as a causal dot.
  一个位置被表示为一个因果点。
• Each user has, as local state, a binary-ish tree of the above form.
  每个用户都有一个类似二进制树状结构的本地状态。
• In createBetween, the user creates a new node in its local tree as described above. It broadcasts the node’s causal dot, parent causal dot, and side (left or right child) to all other users; upon receiving this message, the other users add that node to their own local tree. createBetween returns the node’s label (causal dot) as the created position.
  在 createBetween 中，用户根据上述描述在其本地树中创建一个新节点。它将节点的因果点、父因果点和侧面（左侧或右侧子节点）广播给所有其他用户；收到此消息后，其他用户将该节点添加到自己的本地树中。 createBetween 返回节点的标签（因果点）作为创建的位置。
• In compare(a, b), the user finds nodes with labels a and b in its local tree. It then compares those nodes by their sort order in the tree walk.
  在 compare(a, b) 中，用户在其本地树中找到带有标签 a 和 b 的节点。然后通过树遍历中的排序顺序比较这些节点。

The implicit global tree we described in Semantics corresponds to the union of all users’ local trees. Describing things in terms of this global tree makes sense because (1) local trees and the global tree both only grow over time—they don’t remove or modify existing nodes—and (2) a user only receives calls to compare or createBetween on nodes that it has in its local tree, and it returns the same answer as the global tree.
我们在语义中描述的隐式全局树对应于所有用户本地树的并集。以这个全局树的术语描述事物是有意义的，因为（1）本地树和全局树都只会随着时间增长，它们不会删除或修改现有节点，（2）用户只会在其本地树中拥有的节点上接收到 compare 或 createBetween 的调用，并且返回的答案与全局树相同。

Here we assume message delivery in causal order, to ensure that when a user receives a node broadcast by createBetween, it has already received the parent node.
在这里，我们假设消息按因果顺序传递，以确保当用户接收到由 createBetween 广播的节点时，它已经接收到父节点。

Code for this algorithm is here.
此算法的代码在这里。

We can summarize the resulting List CRDT with a single slide:
我们可以用一张幻灯片总结得出的列表 CRDT：

# Comparing the Implementations
＃比较实现

Relative to our first string implementation, this tree implementation has much better network efficiency: its positions - which the corresponding List CRDT will broadcast to other clients over the network - have small constant size (~15 bytes), and likewise for the messages broadcast by createBetween (~30 bytes with optimized encoding). This contrasts with the string positions, which can become arbitrarily long.
相对于我们的第一个字符串实现，这个树实现具有更好的网络效率：它的位置 - 将广播到网络上其他客户端的相应列表 CRDT - 具有较小的常量大小（~15 字节），同样适用于由 createBetween 广播的消息（优化编码后约 30 字节）。这与字符串位置形成对比，后者可能变得任意长。

However, the tree implementation has worse memory usage: each user needs to store a copy of the entire tree, including positions that are no longer used by the outer List CRDT (tombstones). Also, it is hard to use the tree implementation’s positions in CRDT-unaware contexts, since they can’t be compared directly like strings.
然而，树实现具有更糟糕的内存使用情况：每个用户都需要存储整个树的副本，包括外部列表 CRDT（墓碑）不再使用的位置。此外，在不了解 CRDT 的情况下很难在树实现的位置中使用，因为它们不能像字符串那样直接进行比较。

See also: the LSEQ paper’s discussion of tombstones vs variable-size identifiers for List CRDTs.
另请参阅 LSEQ 论文中关于墓碑与可变大小标识符在列表 CRDT 中的讨论。

In practice, you’ll want to use a more optimized implementation than either of the two described here. I hope to discuss these later, but for now, note that Collabs’s list data structures (e.g. CText) all use an optimized version of the tree implementation.
在实践中，您会希望使用比这两种更优化的实现。我希望以后讨论这些，但现在请注意，Collabs 的列表数据结构（例如 CText）都使用了树实现的优化版本。

Aside. I think of both implementations as variations on “the same” Fugue List CRDT. However, the CRDT literature sometimes assigns different names to List CRDTs that are substantially similar except for (say) different optimizations, e.g., LSEQ vs. Logoot. At the other extreme, it is sometimes to possible to find two very different algorithms with the same user-visible behavior: given a (distributed) trace of compare and createBetween (or insert and delete) operations, they assign positions with the same sort orders. The example I have in mind is Seph Gentle’s description of a YATA-style algorithm implementing RGA’s behavior (section “Improving the data structure”). An old version of the Fugue paper described a similar algorithm equivalent to Fugue (“List-Fugue”); it’s omitted from the current version for length reasons, but we (myself, Seph, and Martin) hope to formalize it in a future tech report.
除此之外。我认为这两种实现都是对“相同”的 Fugue 列表 CRDT 的变体。然而，CRDT 文献有时会为在（比如）不同的优化方面有实质性相似之处的列表 CRDT 分配不同的名称，例如 LSEQ 与 Logoot。在另一个极端，有时可能会找到两种非常不同的算法，但具有相同的用户可见行为：给定 compare 和 createBetween （或 insert 和 delete ）操作的（分布式）跟踪，它们会以相同的排序方式分配位置。我心中的例子是 Seph Gentle 描述的实现 RGA 行为的 YATA 风格算法（“改进数据结构”部分）。Fugue 论文的旧版本描述了一个类似的算法，等效于 Fugue（“List-Fugue”）；由于篇幅原因，它被省略在当前版本中，但我们（我自己、Seph 和 Martin）希望在未来的技术报告中将其正式化。

# Conclusion ＃结论

I hope the above description of the Fugue List CRDT made sense and was not too intimidating. If you’ve also read Designing Data Structures for Collaborative Apps, you now know what I consider the fundamentals of CRDTs-for-collaboration.
我希望上面对 Fugue List CRDT 的描述是有意义的，而且不会太吓人。如果你也读过《为协作应用设计数据结构》，那么你现在知道我认为 CRDTs-for-collaboration 的基本原理是什么了。

As I mentioned, Fugue is my preferred List CRDT. In future posts, I hope to detail why this is, and also put it in context within the List CRDT literature. So look forward to posts on:
正如我所提到的，Fugue 是我首选的列表 CRDT。在未来的帖子中，我希望详细说明为什么，同时也将其放在列表 CRDT 文献的背景中。因此，期待以下帖子：

• Fugue’s “non-interleaving” guarantees.
  赋格的“非交错”保证。
• Other List CRDTs: Logoot, Treedoc, RGA, LSEQ, YATA, and how they relate to Fugue.
  其他列表 CRDT：Logoot、Treedoc、RGA、LSEQ、YATA，以及它们与 Fugue 的关系。
• Efficient implementations.
  高效实现。

Update: You can find info about most of these topics (non-interleaving guarantees, relation to RGA and YATA/Yjs, and efficient implementations) in the Fugue paper.
更新：您可以在《赋格》论文中找到关于大多数这些主题（非交错保证、与 RGA 和 YATA/Yjs 的关系以及高效实现）的信息。

In the meantime, feel free to ask me about these directly.
同时，随时可以直接问我这些问题。

Working TypeScript code for the above snippets is on GitHub.
上述片段的工作 TypeScript 代码在 GitHub 上。

⭐️ I'm on the market for a software engineering job.
⭐️ 我正在寻找软件工程师的工作。

Home • Matthew Weidner • PhD student at CMU CSD • mweidner037@gmail.com • @MatthewWeidner3 • LinkedIn • GitHub
主页 • Matthew Weidner • 卡内基梅隆大学计算机科学系博士生 • mweidner037@gmail.com • @MatthewWeidner3 • 领英 • GitHub