这是用户在 2024-6-1 23:28 为 https://mattweidner.com/2023/09/26/crdt-survey-2.html 保存的双语快照页面，由 沉浸式翻译 提供双语支持。了解如何保存？

CRDT Survey, Part 2: Semantic Techniques
CRDT 调查，第 2 部分：语义技术

Matthew Weidner | Oct 17th, 2023
马修·韦德纳 | 2023 年 10 月 17 日
Home | RSS Feed
主页 | RSS 订阅
Keywords: CRDTs, collaborative apps, semantics
关键词：CRDT，协作应用程序，语义

This blog post is Part 2 of a series.
本博客文章是系列的第 2 部分。

# Semantic Techniques # 语义技术

In Part 1, I defined a collaborative app’s semantics as an abstract definition of what the app’s state should be, given the operations that users have performed.
在第 1 部分中，我将协作应用程序的语义定义为对应用程序状态应该是什么的抽象定义，考虑到用户执行的操作。

Your choice of semantics should be informed by users’ intents and expectations: if one user does X while an offline user concurrently does Y, what do the users want to happen when they sync up? Even after you figure out specific scenarios, though, it is tricky to design a strategy that is well-defined in every situation (multi-way concurrency, extensive offline work, etc.).
您选择的语义应该受用户意图和期望的启发：如果一个用户在做 X 的同时，一个离线用户同时在做 Y，当它们同步时用户希望发生什么？即使您找出了具体的场景，设计一个在每种情况下都明确定义的策略也是棘手的（多路并发，大量离线工作等）。

CRDT semantic techniques help you with this goal. Like the data structures and design patterns that you learn about when programming single-user apps, these techniques provide valuable guidance, but they are not a replacement for deciding what your app should actually do.
CRDT 语义技术可以帮助您实现这一目标。就像您在编写单用户应用程序时学习的数据结构和设计模式一样，这些技术提供了宝贵的指导，但它们并不能取代确定您的应用程序实际应该做什么。

The techniques come in various forms:
技术以各种形式呈现：

Some of these techniques will be familiar if you’ve read Designing Data Structures for Collaborative Apps, but I promise there are new ones here as well.
如果您阅读过《为协作应用设计数据结构》，那么您可能会对其中一些技术感到熟悉，但我保证这里也有一些新的技术。

# Table of Contents
# 目录

This post is meant to be usable as a reference. However, some techniques build on prior techniques. I recommend reading linearly until you reach Composed Examples, then hopping around to whatever interests you.
这篇帖子旨在作为参考资料使用。然而，一些技术是基于先前的技术构建的。我建议您线性阅读，直到您到达组合示例，然后随意浏览您感兴趣的内容。

# Describing Semantics # 描述语义

I’ll describe a CRDT’s semantics by specifying a pure function of the operation history: a function that inputs the history of operations that users have performed, and outputs the current app-visible state.
我将通过指定操作历史记录的纯函数来描述 CRDT 的语义：一个输入用户执行的操作历史记录并输出当前应用程序可见状态的函数。

A box with six "+1"s labeled "Operation history", an arrow labeled "Semantic function", and a large 6 labeled "App state".

Note that I don’t expect you to implement a literal “operation history + pure function”; that would be inefficient. Instead, you are supposed to implement an algorithm that gives the same result. E.g., an op-based CRDT that satisfies: whenever a user has received the messages corresponding to operations S, the user’s state matches the pure function applied to S. I’ll give a few of these algorithms below, and more in Part 3.
请注意，我不希望您实现一个字面上的“操作历史+纯函数”；那样会很低效。相反，您应该实现一个能够给出相同结果的算法。例如，一个基于操作的 CRDT，满足以下条件：每当用户接收到与操作 S 对应的消息时，用户的状态与应用于 S 的纯函数相匹配。我将在下面给出一些这些算法，并在第三部分中提供更多内容。

More precisely, I’ll describe a CRDT’s semantics as:
更准确地说，我将描述 CRDT 的语义为：

  1. A collection of operations that users are allowed to perform on the CRDT. Example: Call inc() to increment a counter.
    CRDT 上允许用户执行的操作集合。示例：调用 inc() 来增加计数器。
  2. For each operation, a translated version that gets stored in the (abstract) operation history. Example: When a user deletes the ingredient at index 0 in an ingredients list, we might instead store the operation Delete the ingredient with unique ID <xyz>.
    对于每个操作，都会存储在（抽象）操作历史记录中的翻译版本。例如：当用户删除配料列表中索引为 0 的配料时，我们可能会存储操作 Delete the ingredient with unique ID <xyz> 。
  3. A pure function that inputs a set of translated operations and some ordering metadata (next paragraph), and outputs the intended state of a user who is aware of those operations. Example: A counter’s semantic function inputs the set of inc() operations and outputs its size, ignoring ordering metadata.
    一个纯函数，输入一组已翻译操作和一些排序元数据（下一段），并输出了了解这些操作的用户的预期状态。示例：计数器的语义函数输入 inc() 操作集，并输出其大小，忽略排序元数据。

The “ordering metadata” is a collection of arrows indicating which operations were aware of each other. E.g., here is a diagram representing the operation history from Part 1:
“订购元数据”是一组箭头的集合，指示哪些操作彼此知晓。例如，这里是一个代表第一部分操作历史的图表：

Operations A-G with arrows A to B, B to C, C to D, D to E, C to F, F to G. The labels are: "Add ingr 'Broc: 1 ct' w/ UID <xyz>"; "Add ingr 'Oil: 15 mL' w/ UID <abc>"; "Add ingr 'Salt: 2 mL' w/ UID <123>"; "Delete ingr <xyz>"; "Set amt <123> to 3 mL"; "Prepend 'Olive ' to ingr <abc>"; "Halve the recipe".

I’ll use diagrams like this throughout the post to represent operation histories. You can think of them like git commit graphs, except that each point is labeled with its operation instead of its state/hash, and parallel “heads” (the rightmost points) are implicitly merged.
我将在整个帖子中使用这样的图表来表示操作历史。您可以将它们视为 git 提交图，不同之处在于每个点都标有其操作，而不是其状态/哈希，并行的“头”（最右边的点）会被隐式合并。

Example: A user who has received the above operation history already sees the result of both heads Set amt <123> to 3 mL and <Halve the recipe>, even though there is no “merge commit”. If that user performs another operation, it will get arrows from both heads, like an explicit merge commit:
示例：已收到上述操作历史记录的用户已经看到了 Set amt <123> to 3 mL 和 <Halve the recipe> 的结果，即使没有“合并提交”。如果该用户执行另一个操作，它将从两个头部获得箭头，就像一个明确的合并提交：

Previous figure with an additional operation H labeled "Delete ingr <abc>" and arrows E to H, G to H.

Describing semantics in terms of a pure function of the operation history lets us sidestep the usual CRDT rules like “concurrent messages must commute” and “the merge function must be idempotent”. Indeed, the point of those rules is to guarantee that a given CRDT algorithm corresponds to some pure function of the operation history (cf. Part 1’s definition of a CRDT). We instead directly say what pure function we want, then define CRDTs to match (or trust you to do so).
用操作历史的纯函数来描述语义，让我们避开了通常的 CRDT 规则，比如“并发消息必须可交换”和“合并函数必须幂等”。事实上，这些规则的目的是确保给定的 CRDT 算法对应于操作历史的某个纯函数（参见第 1 部分对 CRDT 的定义）。相反，我们直接说明我们想要的纯函数，然后定义 CRDT 以匹配（或信任您这样做）。

Strong convergence is the property that a CRDT’s state is a pure function of the operation history - i.e., users who have received the same set of ops are in equivalent states. Strong Eventual Consistency (SEC) additionally requires that two users who stop performing operations will eventually be in equivalent states; it follows from strong convergence in any network where users eventually exchange operations (Shapiro et al. 2011b).
强收敛是指 CRDT 的状态是操作历史的纯函数的属性 - 即，接收相同操作集的用户处于等效状态。强最终一致性（SEC）另外要求停止执行操作的两个用户最终将处于等效状态；在任何最终交换操作的网络中，这是强收敛的结果（Shapiro 等人，2011b）。


These properties are necessary for collaborative apps, but they are not sufficient: you still need to check that your CRDT’s specific semantics are reasonable for your app. It is easy to forget this if you get bogged down in e.g. a proof that concurrent messages commute.
这些属性对于协作应用程序是必要的，但并不充分：您仍然需要检查您的 CRDT 的特定语义是否适合您的应用程序。如果您陷入例如并发消息可交换的证明中，很容易忘记这一点。

# Causal Order ＃因果顺序

Formally, arrows in our operation history diagrams indicate the “causal order” on operations. We will use the causal order to define the multi-value register and some later techniques, so if you want a formal definition, read this section first (else you can skip ahead).
在我们的操作历史图中，箭头正式表示操作的“因果顺序”。我们将使用因果顺序来定义多值寄存器和一些后续技术，因此如果您想要正式定义，请先阅读本节（否则您可以跳过）。

The causal order is the partial order < on pairs of operations defined by:
因果顺序是由以下方式定义的操作对上的偏序 < ：

  1. If a user had received operation o before performing their own operation p, then o < p. This includes the case that they performed both o and p in that order.
    如果用户在执行自己的操作 p 之前收到操作 o ，那么 o < p 。这包括他们按顺序执行 o 和 p 的情况。
  2. (Transitivity) If o < p and p < q, then o < q.
    （传递性）如果 o < p 和 p < q ，那么 o < q 。

Our operation histories indicate o < p by drawing an arrow from o to p. Except, we omit arrows that are implied by transitivity - equivalently, by following a sequence of other arrows.
我们的操作历史表明 o < p 通过从 o 到 p 绘制箭头。除此之外，我们省略了由传递性暗示的箭头 - 同样地，通过跟随其他箭头的序列。

Operations A, B, C, D, with arrows from A to B, B to C, A to D, and D to C.

Figure 1. One user performs operations A, B, C in sequence. After receiving A but not B, another user performs D; the first user receives that before performing D. The causal order is then A < B, A < C, A < D, B < C, D < C. In the figure, the arrow for A < C is implied.
图 1. 一个用户按顺序执行操作 A，B，C。在收到 A 但未收到 B 后，另一个用户执行 D；第一个用户在执行 D 之前收到了那个。因果顺序是 A < B，A < C，A < D，B < C，D < C。在图中，A < C 的箭头是暗示的。

Some derived terms: 一些派生术语：

In the above figure, B is causally greater than A, causally prior to C, and concurrent to D. The immediate causal predecessors of C are B and D; A is a causal predecessor, but not an immediate one.
在上图中，B 在因果上大于 A，在 C 之前，在 D 同时发生。C 的直接因果前驱是 B 和 D；A 是一个因果前驱，但不是一个直接前驱。

It is easy to track the causal order in a CRDT setting: label each operation by IDs for its immediate causal predecessors (the tails of its incoming arrows). Thus when choosing our “pure function of the operation history”, it is okay if that function queries the causal order. We will see an example of this in the multi-value register.
在 CRDT 设置中很容易跟踪因果顺序：为每个操作标记 ID，以表示其直接因果前任（传入箭头的尾部）。因此，在选择我们的“操作历史的纯函数”时，如果该函数查询因果顺序，那是可以的。我们将在多值寄存器中看到一个例子。

Often, CRDT-based apps choose to enforce causal-order delivery: a user’s app will not process an operation (updating the app’s state) until after processing all causally-prior operations. (An op may be processed in any order relative to concurrent operations.) In other words, operations are processed in causal order. This simplifies programming and makes sense to users, by providing a guarantee called causal consistency. For example, it ensures that if one user adds an ingredient to a recipe and then writes instructions for it, all users will see the ingredient before the instructions. However, there are times when you might choose to forgo causal-order delivery - e.g., when there are undone operations. (More examples in Part 4).
通常，基于 CRDT 的应用程序选择强制因果顺序传递：用户的应用程序在处理所有因果先前操作之后才会处理操作（更新应用程序的状态）。 （相对于并发操作，可以以任何顺序处理操作。）换句话说，操作按因果顺序处理。 这简化了编程并对用户有意义，通过提供称为因果一致性的保证。 例如，它确保如果一个用户向食谱添加了一种配料，然后为其编写说明，所有用户都将在说明之前看到该配料。 但是，有时您可能选择放弃因果顺序传递 - 例如，当存在未完成的操作时。 （第 4 部分中有更多示例）。

In Collabs: CRuntime (causal-order delivery), vectorClock (causal order access)
在 Collabs 中：CRuntime（因果顺序传递），vectorClock（因果顺序访问）

References: Lamport 1978 参考文献：Lamport 1978

# Basic Techniques # 基本技术

We begin with basic semantic techniques. Most of these were not invented as CRDTs; instead, they are database techniques or programming folklore. It is often easy to implement them yourself or use them outside of a traditional CRDT framework.
我们从基本的语义技术开始。这些大多数并非作为 CRDTs 而发明；相反，它们是数据库技术或编程传说。通常很容易自己实现它们或在传统 CRDT 框架之外使用它们。

# Unique IDs (UIDs)
＃唯一标识符（UIDs）

To refer to a piece of content, assign it an immutable Unique ID (UID). Use that UID in operations involving the content, instead of using a mutable descriptor like its index in a list.
为了引用一段内容，请为其分配一个不可变的唯一标识符（UID）。在涉及内容的操作中使用该 UID，而不是使用可变的描述符，比如列表中的索引。

Example: In a recipe editor, assign each ingredient a UID. When a user edits an ingredient’s amount, indicate which ingredient using its UID. This solves Part 1’s example.
示例：在配方编辑器中，为每个成分分配一个 UID。当用户编辑成分的数量时，使用其 UID 指示哪个成分。这解决了第 1 部分的示例。

By “piece of content”, I mean anything that the user views as a distinct “thing”, with its own long-lived identity: an ingredient, a spreadsheet cell, a document, etc. Note that the content may be internally mutable. Other analogies:
通过“内容片段”，我指的是用户视为独立“事物”的任何东西，具有自己长期存在的身份：一个成分，一个电子表格单元，一个文档等。请注意，内容可能在内部是可变的。其他类比：

To ensure that all users agree on a piece of content’s UID, the content’s creator should assign the UID at creation time and broadcast it. E.g., include a new ingredient’s UID in the corresponding “Add Ingredient” operation. The assigned UID must be unique even if multiple users create UIDs concurrently; you can ensure that by using UUIDs, or Part 3’s dot IDs.
为了确保所有用户都同意某一内容的 UID，内容的创建者应在创建时分配 UID 并进行广播。例如，在相应的“添加成分”操作中包含新成分的 UID。即使多个用户同时创建 UID，分配的 UID 也必须是唯一的；您可以通过使用 UUID 或第 3 部分的点 ID 来确保这一点。

UIDs are useful even in non-collaborative contexts. For example, a single-user spreadsheet formula that references cell B3 should store the UIDs of its column (B) and row (3) instead of the literal string “B3”. That way, the formula still references “the same cell” even if a new row shifts the cell to B4.
UID 在非协作环境中也很有用。例如，引用单元格 B3 的单用户电子表格公式应该存储其列（B）和行（3）的 UID，而不是字面字符串“B3”。这样，即使新行将单元格移至 B4，公式仍然引用“相同的单元格”。

# Append-Only Log # 追加日志

Use an append-only log to record events indefinitely. This is a CRDT with a single operation add(x), where x is an immutable value to store alongside the event. Internally, add(x) gets translated to an operation add(id, x), where id is a new UID; this lets you distinguish events with the same values. Given an operation history made of these add(id, x) events, the current state is just the set of all pairs (id, x).
使用追加日志记录事件，使其无限期持续。这是一个带有单个操作 add(x) 的 CRDT，其中 x 是一个不可变值，可与事件一起存储。在内部， add(x) 被转换为一个操作 add(id, x) ，其中 id 是一个新的 UID；这样可以区分具有相同值的事件。给定由这些 add(id, x) 事件组成的操作历史，当前状态只是所有配对 (id, x) 的集合。

Example: In a delivery tracking system, each package’s history is an append-only log of events. Each event’s value describes what happened (scanned, delivered, etc.) and the wall-clock time. The app displays the events directly to the user in wall-clock time order. Conflicting concurrent operations indicate a real-world conflict and must be resolved manually.
示例：在交付跟踪系统中，每个包裹的历史记录是一个仅追加的事件日志。每个事件的值描述了发生了什么（扫描、交付等）和墙钟时间。应用程序以墙钟时间顺序直接向用户显示事件。冲突的并发操作表示真实世界的冲突，必须手动解决。

I usually think of an append-only log as unordered, like a set (despite the word “append”). If you do want to display events in a consistent order, you can include a timestamp in the value and sort by that, or use a list CRDT (below) instead of an append-only log. Consider using a logical timestamp like in LWW, so that the order is compatible with the causal order: o < p implies o appears before p.
我通常将只追加日志视为无序的，就像一个集合一样（尽管有“追加”这个词）。如果您想以一致的顺序显示事件，可以在值中包含时间戳并按照时间戳排序，或者使用列表 CRDT（如下）而不是只追加日志。考虑使用类似 LWW 中的逻辑时间戳，以使顺序与因果顺序兼容： o < p 意味着 o 出现在 p 之前。

Refs: Log in Shapiro et al. 2011b
参考文献：登录 Shapiro 等人 2011b

# Unique Set ＃独特集合

A unique set is like an append-only log, but it also allows deletes. It is the basis for any collection that grows and shrinks dynamically: sets, lists, certain maps, etc.
一个独特的集合就像一个只追加日志，但它也允许删除。它是任何动态增长和收缩的集合的基础：集合，列表，某些映射等。

Its operations are: 它的操作是:

Given an operation history, the unique set’s state is the set of pairs (id, x) such that there is an add(id, x) operation but no delete(id) operations.
给定一个操作历史，唯一集合的状态是一组成对的集合 (id, x) ，其中存在一个 add(id, x) 操作但没有 delete(id) 操作。

Operations A-F with arrows A to B, A to D, B to C, B to E, D to E, E to F. The labels are: add(ac63, "doc/Hund"); add(x72z, "cat/Katze"); delete(ac63); delete(ac63); add(8f8x, "chicken/Huhn"); delete(x72z).

Figure 2. In a collaborative flash card app, you could represent the deck of cards as a unique set, using x to hold the flash card's value (its front and back strings). Users can edit the deck by adding a new card or deleting an existing one, and duplicate cards are allowed. Given the above operation history, the current state is { (8f8x, "chicken/Huhn") }.
图 2. 在一个协作的记忆卡应用程序中，您可以将卡组表示为一个唯一的集合，使用 x 来保存记忆卡的值（其正面和背面字符串）。用户可以通过添加新卡或删除现有卡来编辑卡组，并且允许重复卡。根据上述操作历史记录，当前状态为 { (8f8x, "chicken/Huhn") } 。

You can think of the unique set as an obvious way of working with UID-labeled content. It is analogous to a database table with operations to insert and delete rows, using the UID (= primary key) to identify rows. Or, thinking of UIDs like distributed pointers, add and delete are the distributed versions of new and free.
您可以将唯一集视为处理带有 UID 标签内容的明显方式。这类似于具有插入和删除行操作的数据库表，使用 UID（=主键）来标识行。或者，将 UID 视为分布式指针， add 和 delete 是 new 和 free 的分布式版本。

It’s easy to convert the unique set’s semantics to an op-based CRDT.
将唯一集的语义转换为基于操作的 CRDT 很容易。

  • Per-user state: The literal state, which is a set of pairs (id, x).
    每个用户的状态：字面状态，即一组成对的集合 (id, x) 。
  • Operation add(x): Generate a new UID id, then broadcast add(id, x). Upon receiving this message, each user (including the initiator) adds the pair (id, x) to their local state.
    操作 add(x) ：生成一个新的 UID id ，然后广播 add(id, x) 。收到此消息后，每个用户（包括发起者）将该对 (id, x) 添加到其本地状态中。
  • Operation delete(id): Broadcast delete(id). Upon receiving this message, each user deletes the pair with the given id, if it is still present. Note: this assumes causal-order delivery - otherwise, you might receive delete(id) before add(id, x), then forget that the element is deleted.
    操作 delete(id) ：广播 delete(id) 。收到此消息后，每个用户删除具有给定 id 的对，如果仍然存在。注意：这假定是因果顺序传递 - 否则，您可能会在 add(id, x) 之前收到 delete(id) ，然后忘记删除该元素。

A state-based CRDT is more difficult; Part 3 will give a nontrivial optimized algorithm.
基于状态的 CRDT 更加困难；第 3 部分将提供一个非平凡的优化算法。


Refs: U-Set in Shapiro et al. 2011a
参考文献：Shapiro 等人 2011a 中的 U-Set

# Lists and Text Editing
# 列表和文本编辑

In collaborative text editing, users can insert (type) and delete characters in an ordered list. Inserting or deleting a character shifts later characters’ indices, in the style of JavaScript’s Array.splice.
在协作文本编辑中，用户可以在有序列表中插入（键入）和删除字符。插入或删除字符会移动后续字符的索引，类似于 JavaScript 的 Array.splice 风格。

The CRDT way to handle this is: assign each character a unique immutable list CRDT position when it’s typed. These positions are a special kind of UID that are ordered: given two positions p and q, you can ask whether p < q or q < p. Then the text’s state is given by:
处理这个的 CRDT 方法是：在键入时为每个字符分配一个唯一的不可变列表 CRDT 位置。这些位置是一种有序的特殊 UID：给定两个位置 p 和 q ，您可以询问 p < q 或 q < p 。然后文本的状态由以下给出：

Classic list CRDTs have operations insert and delete, which are like the unique set’s add and delete operations, except using positions instead of generic UIDs. A text CRDT is the same but with individual text characters for values. See a previous blog post for details.
经典列表 CRDT 具有操作 insert 和 delete ，类似于唯一集合的 add 和 delete 操作，只是使用位置而不是通用 UID。文本 CRDT 相同，但值为单个文本字符。有关详细信息，请参阅先前的博客文章。

But the real semantic technique is the positions themselves. Abstractly, they are “opaque things that are immutable and ordered”. To match users’ expectations, list CRDT positions must satisfy a few rules (Attiya et al. 2016):
但真正的语义技术是位置本身。抽象地说，它们是“不透明的、不可变的和有序的事物”。为了符合用户的期望，CRDT 位置列表必须满足一些规则（Attiya 等，2016 年）。

  1. The order is total: if p and q are distinct positions, then either p < q or q < p, even if p and q were created by different users concurrently.
    订单是总的：如果 p 和 q 是不同的位置，那么 p < q 或 q < p ，即使 p 和 q 是由不同的用户同时创建的。
  2. If p < q on one user’s device at one time, then p < q on all users’ devices at all times. Example: characters in a collaborative text document do not reverse order, no matter what happens to characters around them.
    如果 p < q 在一个用户设备上的某个时间，则 p < q 在所有用户设备上的所有时间。例如：协作文本文档中的字符不会改变顺序，无论周围的字符发生了什么。
  3. If p < q and q < r, then p < r. This holds even if q is not currently part of the app’s state.
    如果 p < q 和 q < r ，那么 p < r 。即使 q 目前不是应用程序状态的一部分，也是如此。

This definition still gives us some freedom in choosing <. The Fugue paper (myself and Martin Kleppmann, 2023) gives a particular choice of < and motivates why we think you should prefer it over any other. Seph Gentle’s Diamond Types and the Braid group’s Sync9 each independently chose nearly identical semantics (thanks to Michael Toomim and Greg Little for bringing the latter to our attention).
这个定义仍然让我们在选择 < 时有一些自由。Fugue 论文（我和 Martin Kleppmann，2023 年）给出了一个特定的 < 选择，并解释了为什么我们认为您应该偏爱它而不是其他任何选择。Seph Gentle 的 Diamond Types 和 Braid group 的 Sync9 分别选择了几乎相同的语义（感谢 Michael Toomim 和 Greg Little 提醒我们注意后者）。

List CRDT positions are our first “real” CRDT technique - they don’t come from databases or programming folklore, and it is not obvious how to implement them. Their algorithms have a reputation for difficulty, but you usually only need to understand the “unique immutable position” abstraction, which is simple. You can even use list CRDT positions outside of a traditional CRDT framework, e.g., using my list-positions library.
CRDT 列表位置是我们的第一个“真正”的 CRDT 技术 - 它们不是来自数据库或编程传说，如何实现它们并不明显。它们的算法以难度著称，但通常只需要理解“唯一不可变位置”抽象，这很简单。甚至可以在传统 CRDT 框架之外使用 CRDT 列表位置，例如使用我的 list-positions 库。

Collabs: CValueList, Position.
合作：CValueList，Position。

Refs: Many - see “Background and Related Work” in the Fugue paper
参考文献：许多-请参阅《Fugue 论文》中的“背景和相关工作”

# Last Writer Wins (LWW)
# 最后写入者获胜（LWW）

If multiple users set a value concurrently, and there is no better way to resolve this conflict, just pick the “last” value as the winner. This is the Last Writer Wins (LWW) rule.
如果多个用户同时设置一个值，并且没有更好的方法来解决这种冲突，只需选择“最后”值作为获胜者。这就是“最后写入者获胜”（LWW）规则。

Example: Two users concurrently change the color of a pixel in a shared whiteboard. Use LWW to pick the final color.
示例：两个用户同时更改共享白板中像素的颜色。使用 LWW 选择最终颜色。

Traditionally, “last” meant “the last value to reach the central database”. In a CRDT setting, instead, when a user performs an operation, their own device assigns a timestamp for that operation. The operation with the greatest assigned timestamp wins: its value is the one displayed to the user.
传统上，“last” 意味着“最后一个值到达中央数据库”。然而，在 CRDT 环境中，当用户执行操作时，他们自己的设备为该操作分配一个时间戳。具有最大分配时间戳的操作获胜：其值是显示给用户的值。

Formally, an LWW register is a CRDT representing a single variable, with sole operation set(value, timestamp). Given an operation history made of these set operations, the current state is the value with the largest timestamp.
正式来说，一个 LWW 寄存器是一个 CRDT，代表一个单一变量，具有唯一操作 set(value, timestamp) 。给定由这些 set 操作组成的操作历史，当前状态是具有最大 timestamp 的 value 。

Operations A-E with arrows A to B, A to D, B to C, D to C, and D to E. The labels are: none; set("blue", (3, alice)); set("blue", (6, alice)); set("red", (5, bob)); set("green", (7, bob)).

Figure 3. Possible operation history for an LWW register using logical timestamps (the pairs (3, "alice")). The greatest assigned timestamp is (7, bob), so the current state is "green".
图 3. 使用逻辑时间戳的 LWW 寄存器可能的操作历史记录（对 (3, "alice") ）。最大分配的时间戳是 (7, bob) ，因此当前状态为“绿色”。

The timestamp should usually be a logical timestamp instead of literal wall-clock time (e.g., a Lamport timestamp. Otherwise, clock skew can cause a confusing situation: you try to overwrite the current local value with a new one, but your clock is behind, so the current value remains the winner. Lamport timestamps also build in a tiebreaker so that the winner is never ambiguous.
时间戳通常应该是逻辑时间戳，而不是字面上的挂钟时间（例如，Lamport 时间戳）。否则，时钟偏差可能会导致混乱的情况：您试图用新值覆盖当前本地值，但您的时钟落后，因此当前值仍然是获胜者。Lamport 时间戳还内置了一个决胜者，以确保获胜者永远不会有歧义。

Let’s make these semantics concrete by converting them to a hybrid op-based/state-based CRDT. Specifically, we’ll do an LWW register with value type T.
让我们通过将这些语义转换为混合操作/基于状态的 CRDT 来使其具体化。具体来说，我们将使用值类型为 T 的 LWW 寄存器。

  • Per-user state: state = { value: T, time: LogicalTimestamp }. 每个用户的状态: state = { value: T, time: LogicalTimestamp } 。
  • Operation set(newValue): Broadcast an op-based CRDT message { newValue, newTime }, where newTime is the current logical time. Upon receiving this message, each user (including the initiator) does:
    操作 set(newValue) ：广播基于操作的 CRDT 消息 { newValue, newTime } ，其中 newTime 是当前逻辑时间。收到此消息后，每个用户（包括发起者）执行：
    • If newTime > state.time, set state = { value: newValue, time: newTime }.
      如果 newTime > state.time ，则设置 state = { value: newValue, time: newTime } 。
  • State-based merge: To merge in another user’s state other = { value, time }, treat it like an op-based message: if other.time > state.time, set state = other.
    基于状态的合并：要合并另一个用户的状态 other = { value, time } ，请将其视为基于操作的消息：如果 other.time > state.time ，则设置 state = other 。

You can check that state.value always comes from the received operation with the greatest assigned timestamp, matching our semantics above.
您可以检查 state.value 始终来自具有最大分配时间戳的接收操作，与上述语义相匹配。


When using LWW, pay attention to the granularity of writes. For example, in a slide editor, suppose one user moves an image while another user resizes it concurrently. If you implement both actions as writes to a single LWWRegister<{ x, y, width, height }>, then one action will overwrite the other - probably not what you want. Instead, use two different LWW registers, one for { x, y } and one for { width, height }, so that both actions can take effect.
在使用 LWW 时，注意写操作的粒度。例如，在幻灯片编辑器中，假设一个用户移动图像，而另一个用户同时调整大小。如果将这两个操作都实现为对单个 LWWRegister<{ x, y, width, height }> 的写操作，那么一个操作将覆盖另一个操作 - 这可能不是您想要的结果。相反，使用两个不同的 LWW 寄存器，一个用于 { x, y } ，另一个用于 { width, height } ，以便两个操作都能生效。

Collabs: lamportTimestamp
合作：lamportTimestamp

Refs: Johnson and Thomas 1976; Shapiro et al. 2011a
参考文献：Johnson 和 Thomas 1976 年；Shapiro 等 2011a

# LWW Map # LWW 地图

An LWW map applies the last-writer-wins rule to each value in a map. Formally, its operations are set(key, value, timestamp) and delete(key, timestamp). The current state is given by:
一个 LWW 映射将最后写入者获胜规则应用于映射中的每个值。形式上，其操作为 set(key, value, timestamp) 和 delete(key, timestamp) 。当前状态由以下给出：

Observe that a delete operation behaves just like a set operation with a special value. In particular, when implementing the LWW map, it is not safe to forget about deleted keys: you have to remember their latest timestamps as usual, for future LWW comparisons. Otherwise, your semantics might be ill-defined (not a pure function of the operation history), as pointed out by Kleppmann (2022).
观察到 delete 操作的行为就像具有特殊值的 set 操作一样。特别是，在实现 LWW 映射时，忘记删除的键是不安全的：您必须像往常一样记住它们的最新时间戳，以便将来进行 LWW 比较。否则，您的语义可能会被定义不清楚（不是操作历史的纯函数），正如 Kleppmann（2022）所指出的那样。

In the next section, we’ll see an alternative semantics that does let you forget about deleted keys: the multi-value map.
在下一节中，我们将看到一种替代语义，它确实让您忘记已删除的键：多值映射。

# Multi-Value Register # 多值寄存器

This is another “real” CRDT technique, and our first technique that explicitly references the arrows in an operation history (formally, the causal order).
这是另一种“真实”的 CRDT 技术，也是我们第一种明确引用操作历史中箭头（形式上是因果顺序）的技术。

When multiple users set a value concurrently, sometimes you want to preserve all of the conflicting values, instead of just applying LWW.
当多个用户同时设置一个值时，有时您希望保留所有冲突的值，而不仅仅应用 LWW。

Example: One user enters a complex, powerful formula in a spreadsheet cell. Concurrently, another user figures out the intended value by hand and enters that. The first user will be annoyed if the second user’s write erases their hard work.
例子：一个用户在电子表格单元格中输入一个复杂而强大的公式。与此同时，另一个用户通过手工计算出预期值并输入。如果第二个用户的输入擦除了第一个用户的辛勤工作，第一个用户会感到恼火。

The multi-value register does this, by following the rule: its current value is the set of all values that have not yet been overwritten. Specifically, it has a single operation set(x). Its current state is the set of all values whose operations are at the heads of the operation history (formally, the maximal operations in the causal order). For example, here the current state is { "gray", "blue" }:
多值寄存器通过遵循以下规则来实现：其当前值是尚未被覆盖的所有值的集合。具体而言，它有一个单一操作 set(x) 。其当前状态是所有操作位于操作历史记录头部的值的集合（形式上，是因果顺序中的最大操作）。例如，在这里，当前状态是 { "gray", "blue" } ：

Operations A-F with arrows A to B, B to C, B to F, C to D, E to B. The labels are: set("green"); set("red"); set("green"); set("gray"); set("purple"); set("blue").

Multi-values (also called conflicts) are hard to display, so you should have a single value that you show by default. This displayed value can be chosen arbitrarily (e.g. LWW), or by some semantic rule. For example:
多值（也称为冲突）很难显示，因此您应该有一个默认显示的单个值。可以任意选择要显示的该值（例如 LWW），或者根据某些语义规则选择。例如：

Other multi-values can be shown on demand, like in Pixelpusher, or just hidden.
其他多值可以根据需要显示，例如在 Pixelpusher 中，或者只是隐藏。

As with LWW, pay attention to the granularity of writes.
与 LWW 一样，注意写入的粒度。

The multi-value register sounds hard to implement because it references the causal order. But actually, if your app enforces causal-order delivery, then you can easily implement a multi-value register on top of a unique set.
多值寄存器听起来很难实现，因为它引用了因果顺序。但实际上，如果您的应用程序强制执行因果顺序传递，那么您可以很容易地在唯一集合之上实现多值寄存器。

  • Per-user state: A unique set uSet of pairs (id, x). The multi-values are all of the x’s.
    每个用户状态：一个独特的一组 uSet 对 (id, x) 。这些多值都是 x 的。
  • Operation set(x): Locally, loop over uSet calling uSet.delete(id) on every existing element. Then call uSet.add(x).
    操作 set(x) ：在本地，循环遍历 uSet ，对每个现有元素调用 uSet.delete(id) 。然后调用 uSet.add(x) 。

Convince yourself that this gives the same semantics as above.
说服自己，这与上面的语义相同。


Collabs: CVar 合作：CVar

Refs: Shapiro et al. 2011a; Zawirski et al. 2016
参考文献：Shapiro 等人 2011a；Zawirski 等人 2016

# Multi-Value Map # 多值映射

Like the LWW map, a multi-value map applies the multi-value register semantics to each value in a map. Formally, its operations are set(key, value) and delete(key). The current state is given by:
与 LWW 映射类似，多值映射将多值寄存器语义应用于映射中的每个值。形式上，其操作为 set(key, value) 和 delete(key) 。当前状态由以下给出：

Operations A-G with arrows A to B, C to D, C to F, E to D, E to F, F to G. The labels are: set("display", "block"); delete("display"); set("margin", "0"); set("margin", "10px"); set("margin", "20px"); set("height", "auto"); delete("margin").

Figure 4. Multi-value map operations on a CSS class. Obviously key "height" maps to the single value "auto", while key "display" is not present in the map. For key "margin", observe that when restricting to its operations, only set("margin", "10px") and delete("margin") are heads of the operation history (i.e., not overwritten); thus "margin" maps to the single value "10px".
图 4.CSS 类上的多值映射操作。显然，键“height”映射到单个值“auto”，而键“display”不在映射中。对于键“margin”，请注意，当限制其操作时，只有 set("margin", "10px") 和 delete("margin") 是操作历史的头部（即未被覆盖）；因此，“margin”映射到单个值“10px”。

As with the multi-value register, each present key can have a displayed value that you show by default. For example, you could apply LWW to the multi-values. That gives a semantics similar to the LWW map, but when you implement it as an op-based CRDT, you can forget about deleted values. (Hint: Implement the multi-value map on top of a unique set like above.)
与多值寄存器一样，每个现有键都可以具有默认显示的值。例如，您可以将 LWW 应用于多个值。这样就会给出类似于 LWW 映射的语义，但当您将其实现为基于操作的 CRDT 时，可以忘记已删除的值。（提示：在唯一集合的基础上实现多值映射。）

Collabs: CValueMap 合作：CValueMap

Refs: Kleppmann 2022 参考文献：Kleppmann 2022

# Composition Techniques
# 组合技术

We next move on to composition techniques. These create new CRDTs from existing ones.
接下来我们将转向构成技术。这些技术可以从现有的 CRDTs 中创建新的。

Composition has several benefits over making a CRDT from scratch:
组合比从头开始制作 CRDT 具有几个优点：

  1. Semantically, you are guaranteed that the composed output is actually a CRDT: its state is always a pure function of the operation history (i.e., users who have received the same set of ops are in equivalent states).
    从语义上讲，您可以确保组合输出实际上是一个 CRDT：其状态始终是操作历史的纯函数（即，接收相同一组操作的用户处于等效状态）。
  2. Algorithmically, you get op-based and state-based CRDT algorithms “for free” from the components. Those components are probably already optimized and tested.
    从算法上讲，您可以从组件中“免费”获得基于操作和基于状态的 CRDT 算法。这些组件可能已经经过优化和测试。
  3. It is much easier to add a new system feature (e.g., undo/redo) to a few basic CRDTs and composition techniques, than to add it to your app’s top-level state directly.
    将新系统功能（例如，撤销/重做）添加到一些基本的 CRDT 和组合技术要比直接将其添加到应用程序的顶层状态要容易得多。

In particular, it is safe to use a composed algorithm that appears to work well in the situations you care about (e.g., all pairs of concurrent operations), even if you are not sure what it will do in arbitrarily complex scenarios. You are guaranteed that it will at least satisfy strong convergence and have equivalent op-based vs state-based behaviors.
特别是，在您关心的情况下，使用一个看起来在您关心的情况下工作良好的组合算法是安全的（例如，所有并发操作对）。即使您不确定在任意复杂的情况下它会做什么，您可以放心，它至少会满足强收敛并具有等效的基于操作与基于状态的行为。

Like most of our basic techniques, these composition techniques are not really CRDT-specific, and you can easily use them outside of a traditional CRDT framework. Figma’s collaboration system is a good example of this.
与我们大多数基本技术一样，这些构图技术并不是真正特定于 CRDT 的，您可以轻松地在传统 CRDT 框架之外使用它们。Figma 的协作系统就是一个很好的例子。

# Views ＃浏览次数

Not all app states have a good CRDT representation. But often you can store some underlying state as a CRDT, then compute your app’s state as a view (pure function) of that CRDT state.
并非所有应用程序状态都具有良好的 CRDT 表示。但通常您可以将一些基础状态存储为 CRDT，然后将您的应用程序状态计算为该 CRDT 状态的视图（纯函数）。

Example: Suppose a collaborative text editor represents its state as a linked list of characters. Storing the linked list directly as a CRDT would cause trouble: concurrent operations can easily cause broken links, partitions, and cycles. Instead, store a traditional list CRDT, then construct the linked list representation as a view of that at runtime.
示例：假设协作文本编辑器将其状态表示为字符的链表。将链表直接存储为 CRDT 会导致问题：并发操作很容易导致断开的链接、分区和循环。相反，将传统列表 CRDT 存储，然后在运行时将链表表示构造为该视图。

At runtime, one way to obtain the view is to apply a pure function to your CRDT state each time that CRDT state changes, or each time the view is requested. This should sound familiar to web developers (React, Elm, …).
在运行时，获取视图的一种方法是每当 CRDT 状态发生变化时，或每当请求视图时，将纯函数应用于您的 CRDT 状态。这应该对 Web 开发人员（React、Elm 等）听起来很熟悉。

Another way is to “maintain” the view, updating it incrementally each time the CRDT state changes. CRDT libraries usually emit “events” that make this possible. View maintainence is a known hard problem, but it is not hard in a CRDT-specific way. Also, it is easy to unit test: you can always compare to the pure-function approach.
另一种方法是“维护”视图，每次 CRDT 状态更改时逐步更新它。 CRDT 库通常会发出使此成为可能的“事件”。 视图维护是一个已知的难题，但在 CRDT 特定的方式上并不难。 而且，它很容易进行单元测试：您始终可以与纯函数方法进行比较。

Collabs: Events 合作：事件

# Objects # 对象

It is natural to wrap a CRDT in an app-specific API: when the user performs an operation in the app, call a corresponding CRDT operation; in the GUI, render an app-specific view of the CRDT’s state.
将 CRDT 封装在特定于应用程序的 API 中是很自然的：当用户在应用程序中执行操作时，调用相应的 CRDT 操作；在 GUI 中，呈现 CRDT 状态的特定于应用程序的视图。

More generally, you can create a new CRDT by wrapping multiple CRDTs in a single API. I call this object composition. The individual CRDTs (the components) are just used side-by-side; they don’t affect each others’ operations or states.
更一般地说，您可以通过在单个 API 中包装多个 CRDT 来创建新的 CRDT。我称之为对象组合。各个 CRDT（组件）只是并排使用；它们不会影响彼此的操作或状态。

Example: An ingredient like we saw in Part 1 (reproduced below) can be modeled as the object composition of three CRDTs: a text CRDT for the text, an LWW register for the amount, and another LWW register for the units.
示例：像我们在第 1 部分中看到的成分（如下所示）可以建模为三个 CRDT 的对象组合：一个用于文本的文本 CRDT，一个用于数量的 LWW 寄存器，以及另一个用于单位的 LWW 寄存器。

An ingredient with contents Olive Oil, 15, mL.

To distinguish the component CRDTs’ operations, assign each component a distinct name. Then tag each component’s operations with its name:
为了区分组件 CRDT 的操作，请为每个组件分配一个独特的名称。然后使用其名称为每个组件的操作打标签：

Operations on an ingredient, labeled by component name. "text: insert(...)", "amount: set(15, (5, alice))", "units: set('mL', (6, alice))", "units: set('g', (3, bob))".

One way to think of the composed CRDT is as a literal CRDT object - a class whose instance fields are the component CRDTs:
将组合的 CRDT 视为一个字面上的 CRDT 对象的一种方式 - 一个类，其实例字段是组件 CRDT：

class IngredientCRDT extends CRDTObject {
    text: TextCRDT;
    amount: LWWRegister<number>;
    units: LWWRegister<Unit>;
    
    setAmount(newAmount: number) {
        this.amount.set(newAmount);
    }
    
    ...
}

Another way to think of the composed state is as a JSON object mapping names to component states:
另一种思考组合状态的方式是将其视为将名称映射到组件状态的 JSON 对象：

{
    text: {<text CRDT state...>},
    amount: { value: number, time: LogicalTimestamp },
    units: { value: Unit, time: LogicalTimestamp }
}

Collabs: CObject 合作：CObject

Refs: See Map-Like Object refs below
参考文献：请参见下面的类似地图对象参考

# Nested Objects # 嵌套对象

You can nest objects arbitrarily. This leads to layered object-oriented architectures:
您可以任意嵌套对象。这导致了分层的面向对象架构：

class SlideImageCRDT extends CRDTObject {
    dimensions: DimensionCRDT;
    contents: ImageContentsCRDT;
}

class DimensionCRDT extends CRDTObject {
    position: LWWRegister<{ x: number, y: number }>;
    size: LWWRegister<{ width: number, height: number }>;
}

class ImageContentsCRDT ...

or to JSON-like trees:
或者转换为类似 JSON 的树形结构：

{
    dimensions: {
        height: { value: number, time: LogicalTimestamp },
        width: { value: number, time: LogicalTimestamp }
    },
    contents: {
        ...
    }
}

Either way, tag each operation with the tree-path leading to its leaf CRDT. For example, to set the width to 75 pixels: { path: "dimensions/width", op: "set('75px', (11, alice))" }.
无论哪种方式，都要使用树路径标记每个操作，指向其叶子 CRDT。例如，将宽度设置为 75 像素： { path: "dimensions/width", op: "set('75px', (11, alice))" } 。

# Map-Like Object # 映射对象

Instead of a fixed number of component CRDTs with fixed names, you can allow names drawn from some large set (possibly infinite). This gives you a form of CRDT-valued map, which I will call a map-like object. Each map key functions as the name for its own value CRDT.
与固定数量和固定名称的组件 CRDT 不同，您可以允许从某个大集合（可能是无限的）中选择名称。这为您提供了一种 CRDT 值映射的形式，我将其称为类似地图的对象。每个地图键都作为其自身值 CRDT 的名称。

Example: A geography app lets users add a description to any address on earth. You can model this as a map from address to text CRDT. The map behaves the same as an object that has a text CRDT instance field per address.
示例：地理应用程序允许用户向地球上的任何地址添加描述。您可以将此建模为从地址到文本 CRDT 的地图。该地图的行为与具有每个地址的文本 CRDT 实例字段的对象相同。

The difference from a CRDT object is that in a map-like object, you don’t store every value CRDT explicitly. Instead, each value CRDT exists implicitly, in some default state, until used. In the JSON representation, this leads to behavior like Firebase RTDB, where
与 CRDT 对象的区别在于，在类似地图的对象中，您不会显式存储每个值 CRDT。相反，每个值 CRDT 都隐式存在于某个默认状态中，直到被使用。在 JSON 表示中，这会导致类似 Firebase RTDB 的行为。

{ foo: {/* Empty text CRDT */}, bar: {<text CRDT state...>} }

is indistinguishable from
与不可区分

{ bar: {<text CRDT state...>} }

Note that unlike an ordinary map, a map-like object does not have operations to set/delete a key; each key implicitly always exists, with a pre-set value CRDT. We’ll see a more traditional map with set/delete operations later.
请注意，与普通地图不同，类地图对象没有设置/删除键的操作；每个键都隐式存在，并具有预设值 CRDT。稍后我们将看到一个具有设置/删除操作的更传统的地图。

The map-like object and similar CRDTs are often referred to as “map CRDTs” or “CRDT-valued maps” (I’ve done so myself). To avoid confusion, in this blog series, I will reserve those terms for maps with set/delete operations.
类似地图对象和类似的 CRDT 通常被称为“地图 CRDT”或“CRDT 值地图”（我自己也这样做）。为了避免混淆，在这个博客系列中，我将保留这些术语用于具有设置/删除操作的地图。


Collabs: CLazyMap 合作：CLazyMap

Refs: Riak Map; Conway et al. 2012; Kuper and Newton 2013
参考文献：Riak Map；Conway 等人 2012 年；Kuper 和 Newton 2013 年

# Unique Set of CRDTs
＃唯一的 CRDT 集合

Another composition technique uses UIDs as the names of value CRDTs. This gives the unique set of CRDTs.
另一种构图技术使用 UID 作为值 CRDT 的名称。这提供了唯一的 CRDT 集合。

Its operations are: 其操作为：

Given an operation history, the unique set of CRDT’s current state consists of all added value CRDTs, minus the deleted ones, in their own current states (according to the value CRDT operations). Formally:
给定一个操作历史，CRDT 的唯一集合当前状态包括所有已添加值的 CRDT，减去已删除的 CRDT，在它们自己的当前状态中（根据值 CRDT 操作）。形式上：

for each add(id, initialState) operation:
    if there are no delete(id) operations:
        valueOps = all value CRDT operations tagged with id
        currentState = result of value CRDT's semantics applied to valueOps and initialState
        Add (id, currentState) to the set's current state

Example: In a collaborative flash card app, you could represent the deck of cards as a unique set of “flash card CRDTs”. Each flash card CRDT is an object containing text CRDTs for the front and back text. Users can edit the deck by adding a new card (with initial text), deleting an existing card, or editing a card’s front/back text. This extends our earlier flash card example.
示例：在一个协作式的记忆卡应用程序中，您可以将卡组表示为一组独特的“记忆卡 CRDTs”。每个记忆卡 CRDT 是一个包含正面和背面文本 CRDT 的对象。用户可以通过添加新卡（带有初始文本）、删除现有卡或编辑卡的正面/背面文本来编辑卡组。这扩展了我们之前的记忆卡示例。

Observe that once a value CRDT is deleted, it is deleted permanently. Even if another user operates on the value CRDT concurrently, it remains deleted. That allows an implementation to reclaim memory after receiving a delete op - it only needs to store the states of currently-present values. But it is not always the best semantics, so we’ll discuss alternatives below.
观察到一旦值 CRDT 被删除，它将被永久删除。即使另一个用户同时对值 CRDT 进行操作，它仍然被删除。这允许实现在接收到 delete 操作后回收内存 - 它只需要存储当前存在值的状态。但这并不总是最佳语义，因此我们将在下面讨论替代方案。

Like the unique set of (immutable) values, you can think of the unique set of CRDTs as an obvious way of working with UIDs in a JSON tree. Indeed, Firebase RTDB’s push method works just like add.
就像一组独特的（不可变）值一样，您可以将 CRDT 的独特集合视为在 JSON 树中处理 UID 的一种明显方式。实际上，Firebase RTDB 的推送方法的工作方式就像 add 。

// JSON representation of the flash card example:
{
    "uid838x": {
        front: {<text CRDT state...>},
        back: {<text CRDT state...>}
    },
    "uid7b9J": {
        front: {<text CRDT state...>},
        back: {<text CRDT state...>}
    },
    ...
}

The unique set of CRDTs also matches the semantics you would get from normalized database tables: UIDs in one table; value CRDT operations in another table with the UID as a foreign key. A delete op corresponds to a foreign key cascade-delete.
CRDT 的独特集合也与从规范化数据库表中获得的语义相匹配：一个表中的 UID；另一个表中以 UID 为外键的值 CRDT 操作。 delete 操作对应于外键级联删除。

Firebase RTDB differs from the unique set of CRDTs in that its delete operations are not permanent - concurrent operations on a deleted value are not ignored, although the rest of the value remains deleted (leaving an awkward partial object). You can work around this behavior by tracking the set of not-yet-deleted UIDs separately from the actual values. When displaying the state, loop over the not-yet-deleted UIDs and display the corresponding values (only). Firebase already recommends this for performance reasons.
Firebase RTDB 与一组独特的 CRDT 不同之处在于，其删除操作并非永久性的 - 对已删除值的并发操作不会被忽略，尽管值的其余部分仍然被删除（留下一个尴尬的部分对象）。您可以通过单独跟踪尚未删除的 UID 集合来解决此行为。在显示状态时，循环遍历尚未删除的 UID 并显示相应的值（仅此）。出于性能原因，Firebase 已经推荐这样做。


Collabs: CSet 合作：CSet

Refs: Yjs’s Y.Array 参考文献：Yjs 的 Y.Array

# List of CRDTs
# CRDT 清单

By modifying the unique set of CRDTs to use list CRDT positions instead of UIDs, we get a list of CRDTs. Its value CRDTs are ordered.
通过修改一组独特的 CRDT，使用列表 CRDT 位置而不是 UID，我们得到一组 CRDT。其值 CRDT 是有序的。

Example: You can model the list of ingredients from Part 1 as a list of CRDTs, where each value CRDT is an ingredient object from above. Note that operations on a specific ingredient are tagged with its position (a kind of UID) instead of its index, as we anticipated in Part 1.
示例：您可以将第 1 部分的配料列表建模为 CRDT 列表，其中每个值 CRDT 是上述的一个配料对象。请注意，对特定配料的操作标记有其位置（一种 UID），而不是其索引，正如我们在第 1 部分中预期的那样。

Collabs: CList 合作：C 列表

Refs: Yjs’s Y.Array 参考文献：Yjs 的 Y.Array

# Composed Examples # 组合示例

We now turn to semantic techniques that can be described compositionally.
我们现在转向可以以组合方式描述的语义技术。

In principle, if your app needed one of these behaviors, you could figure it out yourself: think about the behavior you want, then make it using the above techniques. In practice, it’s good to see examples.
原则上，如果您的应用程序需要其中一种行为，您可以自己找出解决方法：考虑您想要的行为，然后使用上述技术进行制作。实际操作中，看到示例是很有帮助的。

# Add-Wins Set # 添加-Wins 设置

The add-wins set represents a set of (non-unique) values. Its operations are add(x) and remove(x), where x is an immutable value of type T. Informally, its semantics are:
添加-获胜集表示一组（非唯一）值。其操作为 add(x) 和 remove(x) ，其中 x 是类型 T 的不可变值。非正式地，其语义为：

Example: A drawing app includes a palette of custom colors, which users can add or remove. You can model this as an add-wins set of colors.
示例：一个绘图应用程序包括一组自定义颜色的调色板，用户可以添加或删除。您可以将其建模为一组颜色的添加优先集合。

The informal semantics do not actually cover all cases. Here is a formal description using composition:
非正式语义实际上并未涵盖所有情况。以下是使用组合的正式描述：

Operations A-F with arrows A to B, A to D, B to C, B to E, D to E, E to F. The labels are: "add('red') -> red: set(true)"; "add('blue') -> blue: set(true)"; "remove('blue') -> blue: set(false)"; "add('blue') -> blue: set(true)"; "remove('red') -> red: set(false)"; "add('gray') -> gray: set(true)".

Figure 5. Operation history for a color palette's add-wins set of colors, showing (original op) -> (translated op). The current state is { "blue", "gray" }: the bottom add("blue") op wins over the concurrent remove("blue") op.
图 5. 为调色板的添加窗口颜色集显示的操作历史，显示 (original op) -> (translated op) 。当前状态为{"蓝色"，"灰色"}：底部 add("blue") 操作胜过并发 remove("blue") 操作。

There is a second way to describe the add-wins set’s semantics using composition, though you must assume causal-order delivery:
有第二种方法可以使用组合来描述添加-获胜集的语义，尽管您必须假设因果顺序传递：

The name observed-remove set - a synonym for add-wins set - reflects how this remove(x) operation works: it deletes all entries (id, x) that the local user has “observed”.
观察删除集的名称 - 也称为添加获胜集 - 反映了此 remove(x) 操作的工作原理：它删除了所有本地用户“观察”过的条目。


Collabs: CValueSet 合作：CValueSet

Refs: Shapiro et al. 2011a; Leijnse, Almeida, and Baquero 2019
参考文献：Shapiro 等人 2011a；Leijnse，Almeida 和 Baquero 2019

# List-with-Move # 列表与移动

The lists above fix each element’s position when it is inserted. This is fine for text editing, but for other collaborative lists, you often want to move elements around. Moving an element shouldn’t interfere with concurrent operations on that element.
上述列表在插入元素时固定每个元素的位置。这对于文本编辑来说很好，但对于其他协作列表，通常希望移动元素。移动元素不应干扰对该元素的并发操作。

Example: In a collaborative recipe editor, users should be able to rearrange the order of ingredients using drag-and-drop. If one user edits an ingredient’s text while someone else moves it concurrently, those edits should show up on the moved ingredient, like the typo fix “Bredd” -> “Bread” here:
示例：在协作食谱编辑器中，用户应能够使用拖放重新排列配料的顺序。如果一个用户在另一个人同时移动配料时编辑了配料的文本，那些编辑应该显示在移动的配料上，就像这里的拼写错误修正“Bredd” -> “Bread”一样：

An ingredients list starts with "Bredd" and "Peanut butter". One user swaps the order of ingredients. Concurrently, another user corrects the typo "Bredd" to "Bread". In the final state, the ingredients list is "Peanut butter", "Bread".

In the example, intuitively, each ingredient has its own identity. That identity is independent of the ingredient’s current position; instead, position is a mutable property of the ingredient.
在这个例子中，直观地说，每个成分都有自己的身份。该身份独立于成分当前的位置；相反，位置是成分的可变属性。

Here is a general way to achieve those semantics, the list-with-move:
这里是实现这些语义的一般方法，即列表与移动：

  1. Assign each list element a UID, independently of its position. (E.g., store the elements in a unique set of CRDTs, not a list of CRDTs.)
    为每个列表元素分配一个 UID，与其位置无关。（例如，将元素存储在一组独特的 CRDT 中，而不是 CRDT 列表中。）
  2. To each element, add a position property, containing its current position in the list.
    对于每个元素，添加一个包含其在列表中当前位置的 position 属性。
  3. Move an element by setting its position to a new list CRDT position at the intended place. In case of concurrent move operations, apply LWW to their positions.
    通过将其 position 设置为新列表 CRDT 位置，将元素移动到预期位置。在并发移动操作的情况下，将 LWW 应用于它们的位置。

Sample pseudocode: 示例伪代码：

class IngredientCRDT extends CRDTObject {
    position: LWWRegister<Position>; // List CRDT position
    text: TextCRDT;
    ...
}

class IngredientListCRDT {
    ingredients: UniqueSetOfCRDTs<IngredientCRDT>;
    
    move(ingr: IngredientCRDT, newIndex: number) {
        const newPos = /* new list CRDT position at newIndex */;
        ingr.position.set(newPos);
    }
}

Collabs: CList.move 合作：CList.move

Refs: Kleppmann 2020 参考文献：Kleppmann 2020

# Internally-Mutable Register
# 内部可变寄存器

The registers above (LWW register, multi-value register) each represent a single immutable value. But sometimes, you want a value that is internally mutable, but can still be blind-set like a register - overriding concurrent mutations.
上面的寄存器（LWW 寄存器，多值寄存器）分别代表一个不可变的单个值。但有时，您可能需要一个在内部可变的值，但仍然可以像寄存器一样被盲目设置 - 覆盖并发变化。

Example: A bulletin board has an “Employee of the Month” section that shows the employee’s name, photo, and a text box. Coworkers can edit the text box to give congratulations; it uses a text CRDT to allow simultaneous edits. Managers can change the current employee of the month, overwriting all three fields. If a manager changes the current employee while a coworker concurrently congratulates the previous employee, the latter’s edits should be ignored.
示例：公告板上有一个“本月员工”部分，显示员工的姓名、照片和文本框。同事可以编辑文本框以表示祝贺；它使用文本 CRDT 允许同时编辑。经理可以更改本月员工，覆盖所有三个字段。如果经理在同事同时祝贺上一个员工时更改当前员工，应忽略后者的编辑。

An internally-mutable register supports both set operations and internal mutations. Its state consists of:
一个可内部变动的寄存器支持 set 操作和内部变动。其状态包括：

The register’s visible state is the value CRDT indicated by reg. You internally mutate the value by performing operations on that value CRDT. To blind-set the value to initialState (overriding concurrent mutations), create a new value CRDT using uSet.add(initialState), then set reg to its UID.
寄存器的可见状态是由 reg 指示的值 CRDT。您通过对该值 CRDT 执行操作来内部改变该值。要将值盲设置为 initialState （覆盖并发变化），请使用 uSet.add(initialState) 创建一个新值 CRDT，然后将 reg 设置为其 UID。

Creating a new value CRDT is how we ensure that concurrent mutations are ignored: they apply to the old value CRDT, which is no longer shown. The old value CRDT can even be deleted from uSet to save memory.
创建新值 CRDT 是我们确保并发变异被忽略的方法：它们应用于旧值 CRDT，该值不再显示。 旧值 CRDT 甚至可以从 uSet 中删除以节省内存。

The CRDT-valued map (next) is the same idea applied to each value in a map.
CRDT 值映射（next）是将相同的想法应用于映射中的每个值。

Collabs: CVar with CollabID values
合作：带有 CollabID 值的 CVar

Refs: true blind updates in Braun, Bieniusa, and Elberzhager (2021)
参考文献：Braun、Bieniusa 和 Elberzhager（2021）中的真盲更新

# CRDT-Valued Map # CRDT-值映射

The map-like object above does not have operations to set/delete a key - it is more like an object than a hash map.
上面的类似地图的对象没有设置/删除键的操作 - 它更像一个对象而不是哈希映射。

Here is a CRDT-valued map that behaves more like a hash map. Its state consists of:
这是一个行为更像哈希映射的 CRDT 值映射。它的状态包括：

The map’s visible state is: key maps to the value CRDT with UID lwwMap[key]. (If key is not present in lwwMap, then it is also not present in the CRDT-valued map.)
地图的可见状态为： key 映射到值 CRDT，带有 UID lwwMap[key] 。（如果 key 不在 lwwMap 中，则它也不在 CRDT 值映射中。）

Operations: 操作：

Note that if two users concurrently set a key, then one of their set ops will “win”, and the map will only show that user’s value CRDT. (The other value CRDT still exists in uSet.) This can be confusing if the two users meant to perform operations on “the same” value CRDT, merging their edits.
请注意，如果两个用户同时设置一个键，那么它们的 set 操作中将会有一个“获胜”，并且地图只会显示该用户的值 CRDT。（另一个值 CRDT 仍然存在于 uSet 中。）如果这两个用户本意是对“相同”的值 CRDT 执行操作并合并它们的编辑，这可能会令人困惑。

Example: A geography app lets users add a photo and description to any address on earth. Suppose you model the app as a CRDT-valued map from each address to a CRDT object { photo: LWWRegister<Image>, desc: TextCRDT }. If one user adds a photo to an unused address (necessarily calling map.set first), while another user adds a description concurrently (also calling map.set), then one CRDT object will overwrite the other:
示例：一个地理应用程序允许用户向地球上的任何地址添加照片和描述。假设您将该应用程序建模为从每个地址到 CRDT 对象 { photo: LWWRegister<Image>, desc: TextCRDT } 的 CRDT 值映射。如果一个用户向未使用的地址添加照片（必须首先调用 map.set ），而另一个用户同时添加描述（也调用 map.set ），那么一个 CRDT 对象将覆盖另一个：

The address 5000 Forbes Ave starts with a blank description and photo. One user adds the description "Looks like a school?". Concurrently, another user adds a photo of a building. In the final state, the description is "Looks like a school?" but the photo is blank again.

To avoid this, consider using a map-like object, like the previous geography app example.
为了避免这种情况，请考虑使用类似于之前地理应用示例的地图对象。

More composed constructions that are similar to the CRDT-valued map:
更加稳健的构造，类似于 CRDT 值映射：

  • Same, except you don’t delete value CRDTs from uSet. Instead, they are kept around in an archive. You can “restore” a value CRDT by calling set(key, id) again later, possibly under a different key.
    相同，除了您不会从 uSet 中删除值 CRDT。相反，它们会被保留在存档中。您可以通过稍后再次调用 set(key, id) 来“恢复”值 CRDT，可能在不同的 key 下。
  • A unique set of CRDTs where each value CRDT has a mutable key property, controlled by LWW. That way, you can change a value CRDT’s key - e.g., renaming a document. Note that your display must handle the case where multiple value CRDTs have the same key.
    每个值 CRDT 都有一个可变的 key 属性的独特集合，由 LWW 控制。这样，您可以更改值 CRDT 的键 - 例如，重命名文档。请注意，您的显示必须处理多个值 CRDT 具有相同键的情况。


Collabs: CMap, CollabID 合作：CMap，CollabID

Refs: Yjs’s Y.Map; Automerge’s Map
参考：Yjs 的 Y.Map；Automerge 的 Map

# Archiving Collections # 存档集合

The CRDT-valued collections above (unique set, list, map) all have a delete operation that permanently deletes a value CRDT. It is good to have this option for performance reasons, but you often instead want an archive operation, which merely hides an element until it’s restored. (You can recover most of delete’s performance benefits by swapping archived values to disk/cloud.)
上述的 CRDT 值集合（唯一集、列表、映射）都有一个 delete 操作，可以永久删除一个值 CRDT。出于性能原因，拥有这个选项是很好的，但通常您更希望一个 archive 操作，它仅仅隐藏一个元素，直到它被恢复。（您可以通过将存档值交换到磁盘/云来恢复大部分 delete 的性能优势。）

Example: In a notes app with cross-device sync, the user should be able to view and restore deleted notes. That way, they cannot lose a note by accident.
示例：在具有跨设备同步功能的笔记应用中，用户应能够查看和恢复已删除的笔记。这样，他们就不会因为意外而丢失笔记。

To implement archive/restore, add an isPresent field to each value. Values start with isPresent = true. The operation archive(id) sets it to false, and restore(id) sets it to true. In case of concurrent archive/restore operations, you can apply LWW, or use a multi-value register’s displayed value.
要实现存档/恢复，需要为每个值添加一个 isPresent 字段。 值以 isPresent = true 开头。 操作 archive(id) 将其设置为 false， restore(id) 将其设置为 true。 在并发存档/恢复操作的情况下，可以应用 LWW，或使用多值寄存器的显示值。

Alternate implementation: Use a separate add-wins set to indicate which values are currently present.
备用实现：使用单独的添加-获胜集合来指示当前存在哪些值。

Collabs: CList.archive/restore
合作：CList.archive/恢复

# Update-Wins Collections
＃更新-Wins 集合

If one user archives a value that another user is still using, you might choose to “auto-restore” that value.
如果一个用户存档了另一个用户仍在使用的值，您可以选择“自动恢复”该值。

Example: In a spreadsheet, one user deletes a column while another user edits some of that column’s cells concurrently. The second user probably wants to keep that column, and it’s easier if the column restores automatically (Yanakieva, Bird, and Bieniusa 2023).
示例：在电子表格中，一个用户删除了一列，而另一个用户同时编辑了该列的一些单元格。第二个用户可能希望保留该列，如果该列可以自动恢复，那将更容易（Yanakieva，Bird 和 Bieniusa 2023）。

To implement this on top of an archiving collection, merely call restore(id) each time the local user edits id’s CRDT. So each local operation translates to two ops in the history: the original (value CRDT) operation and restore(id).
要在归档集合之上实现这一点，只需在本地用户编辑 id 的 CRDT 时每次调用 restore(id) 。因此，每个本地操作都会转换为历史记录中的两个操作：原始（值 CRDT）操作和 restore(id) 。

To make sure that these “keep” operations win over concurrent archive operations, use an enable-wins flag to control the isPresent field. (I.e., a multi-value register whose displayed value is true if any of the multi-values are true.) Or, use the last section’s alternate implementation: an add-wins set of present values.
为了确保这些“保持”操作胜过并发的归档操作，请使用一个启用胜利标志来控制 isPresent 字段。（即，一个多值寄存器，其显示值为 true，如果任何一个多值为 true。）或者，使用上一节的备用实现：一个添加胜利的当前值集合。

Collabs: supported by CList.restore
合作：由 CList.restore 支持

Refs: Yanakieva, Bird, and Bieniusa 2023
参考文献：Yanakieva，Bird 和 Bieniusa 2023

# Spreadsheet Grid # 电子表格网格

In a spreadsheet, users can insert, delete, and potentially move rows and columns. That is, the collection of rows behaves like a list, as does the collection of columns. Thus the cell grid is the 2D analog of a list.
在电子表格中，用户可以插入、删除和可能移动行和列。也就是说，行的集合的行为类似于列表，列的集合也是如此。因此，单元格网格是列表的二维模拟。

It’s tempting to model the grid as a list-of-lists. However, that has the wrong semantics in some scenarios. In particular, if one user creates a new row, while another user creates a new column concurrently, then there won’t be a cell at the intersection.
诱人的做法是将网格建模为列表的列表。然而，在某些情况下，这种方法的语义是错误的。特别是，如果一个用户创建了新行，而另一个用户同时创建了新列，那么交叉点处将不会有单元格。

Instead, you should think of the state as:
相反，您应该将状态视为：

  1. A list of rows.
    一系列行。
  2. A list of columns.
    列的列表。
  3. For each pair (row, column), a single cell, uniquely identified by the pair (row id, column id). row id and column id are unique IDs.
    对于每对（行，列），由一对 (row id, column id) . row id 和 column id 唯一标识的单元格是唯一的 ID。

The cells are not explicitly created; instead, the state implicitly contains such a cell as soon as its row and column exist. Of course, until a cell is actually used, it remains in a default state (blank) and doesn’t need to be stored in memory. Once a user’s app learns that the row or column was deleted, it can forget the cell’s state, without an explicit “delete cell” operation - like a foreign key cascade-delete.
细胞并非明确创建；相反，状态隐含地包含这样一个细胞，只要其行和列存在即可。当然，直到细胞实际被使用之前，它仍处于默认状态（空白），无需存储在内存中。一旦用户的应用程序了解到行或列已被删除，它可以忘记细胞的状态，而无需显式的“删除细胞”操作 - 就像外键级联删除。

In terms of the composition techniques above (objects, list-with-move, map-like object):
就上述组合技术（对象、带移动的列表、类似地图的对象）而言：

class CellCRDT extends CRDTObject {
    formula: LWWRegister<string>;
    ...
}

rows: ListWithMoveCRDT<Row>;
columns: ListWithMoveCRDT<Column>;
cells: MapLikeObject<(rowID: UID, columnID: UID), CellCRDT>;

// Note: if you use this compositional construction in an implementation,
// you must do extra work to forget deleted cells' states.

# Advanced Techniques # 高级技术

The techniques in this section are more advanced. This really means that they come from more recent papers and I am less comfortable with them; they also have fewer existing implementations, if any.
本节中的技术更加先进。这实际上意味着它们来自更近期的论文，我对它们的掌握程度较低；它们的现有实现也较少，如果有的话。

Except for undo/redo, you can think of these as additional composed examples. However, they have more complex views than the previous composed examples.
除了撤销/重做之外，您可以将这些视为额外的组合示例。但是，它们比先前的组合示例更复杂。

# Formatting Marks (Rich Text)
# 格式标记（富文本）

Rich text consists of plain text plus inline formatting: bold, font size, hyperlinks, etc. (This section does not consider block formatting like blockquotes or bulleted lists, discussed later.)
富文本由普通文本加上内联格式组成：粗体、字体大小、超链接等。（本节不考虑块格式，如块引用或项目列表，稍后讨论。）

Inline formatting traditionally applies not to individual characters, but to spans of text: all characters from index i to j. E.g., atJSON (not a CRDT) uses the following to represent a bold span that affects characters 5 to 11:
传统上，内联格式应用于文本范围，而不是单个字符：从索引 i 到 j 的所有字符。例如，atJSON（不是 CRDT）使用以下内容表示影响字符 5 到 11 的粗体文本范围：

{
    type: "-offset-bold",
    start: 5,
    end: 11,
    attributes: {}
}

Future characters inserted in the middle of the span should get the same format. Likewise for characters inserted at the end of the span, for certain formats. You can override (part of) the span by applying a new formatting span on top.
未来插入到跨度中间的字符应该具有相同的格式。同样，对于插入到跨度末尾的字符，对于某些格式也是如此。您可以通过在顶部应用新的格式跨度来覆盖（部分）跨度。

The inline formatting CRDT lets you use formatting spans in a CRDT setting. (I’m using this name for a specific part of the Peritext CRDT (Litt et al. 2021).) It consists of:
内联格式 CRDT 允许您在 CRDT 设置中使用格式化跨度。(我正在为 Peritext CRDT 的特定部分使用这个名称(Litt 等人，2021)。)它包括：

  1. An append-only log of CRDT-ified formatting spans, called marks.
    CRDT-化的格式跨度的只追加日志，称为标记。
  2. A view of the mark log that tells you the current formatting at each character.
    告诉您每个字符的当前格式的标记日志视图。

Each mark has the following form:
每个标记的形式如下：

{
    key: string;
    value: any;
    timestamp: LogicalTimestamp;
    start: { pos: Position, type: "before" | "after" }; // anchor
    end: { pos: Position, type: "before" | "after" }; // anchor
}

Here timestamp is a logical timestamp for LWW, while each Position is a list CRDT position. This mark sets key to value (e.g. "bold": true) for all characters between start and end. The endpoints are anchors that exist just before or just after their pos:
这里 timestamp 是 LWW 的逻辑时间戳，而每个 Position 是一个列表 CRDT 位置。这个标记将 key 设置为 value （例如 "bold": true ）所有在 start 和 end 之间的字符。端点是锚点，它们存在于它们的 pos 之前或之后：

"Some text" with before and after anchors on each character. The middle text "me te" is bold due to a mark labeled 'Bold mark from { pos: (m's pos), type: "before" } to { pos: (x's pos), type: "before" }'.

LWW takes effect when multiple marks affect the same character and have the same key: the one with the largest timestamp wins. In particular, new marks override (causally) older ones. Note that a new mark might override only part of an older mark’s range.
LWW 在多个标记影响相同字符且具有相同 key 时生效：具有最大 timestamp 的标记获胜。特别是，新标记会覆盖（因果关系）旧标记。请注意，新标记可能仅覆盖旧标记范围的一部分。

Formally, the view of the mark log is given by: for each character c, for each format key key, find the mark with the largest timestamp satisfying
正式地，标记日志的视图由以下内容给出：对于每个字符 c ，对于每个格式键 key ，找到具有最大时间戳的标记

Then c’s format value at key is mark.value.
然后 c 在 key 的格式值为 mark.value 。

Remarks: 备注：

  1. To unformat, apply a formatting mark with a null value, e.g., { key: "bold", value: null, ... }. This competes against other “bold” marks in LWW.
    取消格式，请使用值为 null 的格式标记，例如 { key: "bold", value: null, ... } 。这与 LWW 中的其他“粗体”标记竞争。
  2. A formatting mark affects not just (causally) future characters in its range, but also characters inserted concurrently:
    格式标记不仅影响其范围内的未来字符，还影响同时插入的字符：    Text starts as "The cat jumped on table.", unbold. One user highlights the entire range and bolds it. Concurrently, another user inserts " the" after "on". The final state is "The cat jumped on the table.", all bold.
  3. Anchors let you choose whether a mark “expands” to affect future and concurrent characters at the beginning or end of its range. For example, the bold mark pictured above expands at the end: a character typed between e and x will still be within the mark’s range because the mark’s end is attached to x.
    锚点允许您选择标记“扩展”以影响其范围开头或结尾的未来和同时字符。例如，上面显示的粗体标记在结尾处扩展：在 e 和 x 之间键入的字符仍将在标记范围内，因为标记的结尾附加到 x 。
  4. The view of the mark log is difficult to compute and store efficiently. Part 3 will describe an optimized view that can be maintained incrementally and doesn’t store metadata on every character.
    标记日志的视图难以高效计算和存储。第三部分将描述一种优化的视图，可以逐步维护，并且不会在每个字符上存储元数据。
  5. Sometimes a new character should be bold (etc.) according to local rules, but existing formatting marks don’t make it bold. E.g., a character inserted at the beginning of a paragraph in MSWord inherits the following character’s formatting, but the inline formatting CRDT doesn’t do that automatically.
    有时根据本地规则，新字符应该加粗（等等），但现有的格式标记并没有使其加粗。例如，在 MSWord 中段落开头插入的字符会继承后面字符的格式，但内联格式 CRDT 并不会自动执行这一操作。
    To handle this, when a user types a new character, compute its formatting according to local rules. (Most rich-text editor libraries already do so.) If the inline formatting CRDT currently assigns different formatting to that character, fix it by adding new marks to the log.
    为了处理这个问题，当用户输入新字符时，根据本地规则计算其格式。(大多数富文本编辑器库已经这样做了。)如果内联格式 CRDT 当前为该字符分配了不同的格式，则通过向日志添加新标记来修复它。

Fancy extension to (5): Usually the local rules are “extending” a formatting mark in some direction - e.g., backwards from the paragraph’s previous starting character. You can figure out which mark is being extended, then reuse its timestamp instead of making a new one. That way, LWW behaves identically for your new mark vs the one it’s extending.
花哨的扩展到（5）：通常，本地规则是在某个方向上“扩展”格式标记，例如，从段落的前一个起始字符向后。您可以找出哪个标记正在被扩展，然后重用其 timestamp ，而不是制作一个新的。这样，LWW 对于您的新标记与它正在扩展的标记的行为是相同的。


Collabs: CRichText 合作：CRichText

Refs: Litt et al. 2021 (Peritext)
参考文献：Litt 等人。2021 年（周边文本）

# Spreadsheet Formatting
# 电子表格格式化

You can also apply inline formatting to non-text lists. For example, Google Sheets lets you bold a range of rows, with similar behavior to a range of bold text: new rows at the middle or end of the range are also bold. A cell in a bold row renders as bold, unless you override the formatting for that cell.
您还可以对非文本列表应用内联格式。例如，Google 表格允许您将一系列行设置为粗体，其行为类似于一系列粗体文本：范围中间或末尾的新行也会是粗体的。粗体行中的单元格呈现为粗体，除非您覆盖该单元格的格式设置。

In more detail, here’s an idea for spreadsheet formatting:
更详细地说，这是关于电子表格格式的一个想法：

Use two inline formatting CRDTs, one for the rows and one for the columns. Also, for each cell, store an LWW map of format key-value pairs; mutate the map when the user formats that individual cell. To compute the current bold format for a cell, consider:
使用两个内联格式的 CRDT，一个用于行，一个用于列。此外，对于每个单元格，存储一个格式键值对的 LWW 映射；当用户格式化该单元格时，变异映射。要计算单元格的当前粗体格式，请考虑：

  1. The current (largest timestamp) bold mark for the cell’s row.
    单元格行的当前（最大时间戳）粗体标记。
  2. The current bold mark for its column.
    其列的当前粗体标记。
  3. The value at key “bold” in the cell’s own LWW map.
    单元格自己的 LWW 映射中键“bold”的值。

Then render the mark/value with the largest timestamp out of these three.
然后将这三个中具有最大时间戳的标记/值呈现出来。

This idea lets you format rows, columns, and cells separately. Sequential formatting ops interact in the expected way: for example, if a user bolds a row and then unbolds a column, the intersecting cell is not bold, since the column op has a larger timestamp.
这个想法允许您分别格式化行、列和单元格。顺序格式化操作按预期方式交互：例如，如果用户将一行加粗，然后取消加粗一列，则交叉的单元格不会加粗，因为列操作具有较大的时间戳。

# Global Modifiers # 全局修饰符

Often you want an operation to do something “for each” element of a collection, including elements added concurrently.
通常，您希望一个操作针对集合中的每个元素执行某些操作，包括同时添加的元素。

Example: An inline formatting mark affects each character in its range, including characters inserted concurrently (see above).
示例：内联格式标记影响其范围内的每个字符，包括同时插入的字符（见上文）。

Example: Suppose a recipe editor has a “Halve the recipe” button, which halves every ingredient’s amount. This should have the semantics: for each ingredient amount, including amounts set concurrently, halve it. If you don’t halve concurrent set ops, the recipe can get out of proportion:
示例：假设食谱编辑器有一个“减半食谱”按钮，可以将每种食材的数量减半。这应该具有语义：对于每种食材的数量，包括同时设置的数量，都要减半。如果不减半同时设置的操作，食谱可能会失去比例。

An ingredients list starts with 100 g Flour and 80 g Milk. One user edits the amount of Milk to 90 g. Concurrently, another user halves the recipe (50 g Flour, 40 g Milk). The final state is: 50 g Flour, 90 g Milk.

I’ve talked about these for-each operations before and co-authored a paper formalizing them (Weidner et al. 2023). However, the descriptions so far query the causal order (below), making them difficult to implement.
我之前已经谈到了这些 for-each 操作，并与其他人合著了一篇正式论文（Weidner 等人，2023 年）。然而，到目前为止，描述都是查询因果顺序（如下），这使得它们难以实现。

Instead, I currently recommend implementing these examples using global modifiers. By “global modifier”, I mean a piece of state that affects all elements of a collection/range: causally prior, concurrent, and (causally) future.
相反，我目前建议使用全局修饰符来实现这些示例。通过“全局修饰符”，我指的是影响集合/范围中所有元素的状态片段：因果先前，同时发生和（因果）未来。

The inline formatting marks above have this form: a mark affects each character in its range, regardless of when it was inserted. If a user decides that a future character should not be affected, that user can override the formatting mark with a new one.
上面的内联格式标记具有这种形式：一个标记影响其范围内的每个字符，而不管何时插入。如果用户决定未来的字符不受影响，用户可以用新的标记覆盖格式标记。

To implement the “Halve the recipe” example:
实施“减半食谱”示例：

  1. Store a global scale alongside the recipe. This is a number controlled by LWW, which you can think of as the number of servings.
    将一个全局规模与食谱一起存储。这是由 LWW 控制的数字，您可以将其视为份数。
  2. Store each ingredient’s amount as a scale-independent number. You can think of this as the amount per serving.
    将每种成分的数量存储为与比例无关的数字。您可以将其视为每份的数量。
  3. The app displays the product ingrAmount.value * globalScale.value for each ingredient’s amount.
    该应用程序显示每种成分数量的产品 ingrAmount.value * globalScale.value 。
  4. To halve the recipe, merely set the global scale to half of its current value: globalScale.set(0.5 * globalScale.value). This halves all displayed amounts, including amounts set concurrently and concurrently-added ingredients.
    要将食谱减半，只需将全局比例设置为当前值的一半： globalScale.set(0.5 * globalScale.value) 。这将使所有显示的数量减半，包括同时设置的数量和同时添加的配料。
  5. When the user sets an amount, locally compute the corresponding scale-independent amount, then set that. E.g. if they change flour from 50 g to 55 g but the global scale is 0.5, instead call ingrAmount.set(110).
    当用户设置金额时，先在本地计算相应的独立于比例尺的金额，然后进行设置。例如，如果他们将面粉从 50 克更改为 55 克，但全局比例为 0.5，则调用 ingrAmount.set(110) 。

In the recipe editor, you could even make the global scale non-collaborative: each user chooses how many servings to display on their own device. But all collaborative edits affect the same single-serving recipe internally.
在配方编辑器中，您甚至可以使全局比例非协作：每个用户可以选择在自己的设备上显示多少份。但所有协作编辑都会影响同一份单人份配方。


Refs: Weidner, Miller, and Meiklejohn 2020; Weidner et al. 2023
参考文献：Weidner，Miller 和 Meiklejohn 2020；Weidner 等人 2023

# Forests and Trees
＃森林和树

Many apps include a tree or forest structure. (A forest is a collection of disconnected trees.) Typical operations are creating a new node, deleting a node, and moving a node (changing its parent).
许多应用程序包括树或森林结构。（森林是一组不相连的树的集合。）典型操作包括创建新节点、删除节点和移动节点（更改其父节点）。

Examples: A file system is a tree whose leaves are files and inner nodes are folders. A Figma document is a tree of rendered objects.
示例：文件系统是一棵树，其叶子是文件，内部节点是文件夹。Figma 文档是呈现对象的树。

The CRDT way to represent a tree or forest is: Each node has a parent node, set via LWW. The parent can either be another node, a special “root” node (in a tree), or “none” (in a forest). You compute the tree/forest as a view of these child->parent relationships (edges) in the obvious way.
CRDT 表示树或森林的方式是：每个节点都有一个通过 LWW 设置的父节点。父节点可以是另一个节点，一个特殊的“根”节点（在树中），或“无”（在森林中）。您可以通过这些子->父关系（边缘）的视图来计算树/森林，方法显而易见。

When a user deletes a node - implicitly deleting its whole subtree - don’t actually loop over the subtree deleting nodes. That would have weird results if another user concurrently moved some nodes into or out of the subtree. Instead, only delete the top node (or archive it - e.g., set its parent to a special “trash” node). It’s a good idea to let users view the deleted subtree and move nodes out of it.
当用户删除一个节点时 - 隐式删除其整个子树 - 不要实际循环遍历子树删除节点。如果另一个用户同时将一些节点移入或移出子树，那将产生奇怪的结果。相反，只删除顶部节点（或将其存档 - 例如，将其父节点设置为特殊的“垃圾”节点）。让用户查看已删除的子树并将节点移出是一个好主意。

Everything I’ve said so far is just an application of basic techniques. Cycles are what make forests and trees advanced: it’s possible that one user sets B.parent = A, while concurrently, another user sets A.parent = B. Then it’s unclear what the computed view should be.
到目前为止，我所说的一切只是基本技术的应用。循环是使森林和树变得先进的原因：可能一个用户设置 B.parent = A ，同时，另一个用户设置 A.parent = B 。那么计算出的视图应该是什么就不清楚了。

A tree starts with root C and children A, B. One user moves A under B (sets A.parent = B). Concurrently, another user moves B under A. The final state has C, and A-B cycle, and "??".

Figure 6. Concurrent tree-move operations - each valid on their own - may create a cycle. When this happens, what state should the app display, given that cycles are not allowed in a forest/tree?
图 6. 并发树移动操作 - 每个操作本身都是有效的 - 可能会创建一个循环。当这种情况发生时，考虑到森林/树中不允许存在循环，应用程序应该显示什么状态？

Some ideas for how to handle cycles:
如何处理循环的一些建议：

  1. Error. Some desktop file sync apps do this in practice (Kleppmann et al. (2022) give an example).
    错误。一些桌面文件同步应用程序在实践中会这样做（Kleppmann 等人（2022 年）提供了一个例子）。
  2. Render the cycle nodes (and their descendants) in a special “time-out” zone. They will stay there until some user manually fixes the cycle.
    将循环节点（及其后代）呈现在特殊的“超时”区域。它们将一直停留在那里，直到某个用户手动修复循环。
  3. Use a server to process move ops. When the server receives an op, if it would create a cycle in the server’s own state, the server rejects it and tells users to do likewise. This is what Figma does. Users can still process move ops optimistically, but they are tentative until confirmed by the server. (Optimistic updates can cause temporary cycles for users; in that case, Figma uses strategy (2): it hides the cycle nodes.)
    使用服务器处理移动操作。当服务器接收到一个操作时，如果它会在服务器自身状态中创建一个循环，服务器会拒绝该操作并告诉用户做同样的事情。这就是 Figma 的做法。用户仍然可以乐观地处理移动操作，但在服务器确认之前，它们是暂时的。 （乐观更新可能会导致用户出现临时循环；在这种情况下，Figma 使用策略（2）：隐藏循环节点。）
  4. Similar, but use a topological sort (below) instead of a server’s receipt order. When processing ops in the sort order, if an op would create a cycle, skip it (Kleppmann et al. 2022).
    类似，但使用拓扑排序（如下）而不是服务器的接收顺序。在按排序顺序处理操作时，如果一个操作会创建循环，请跳过它（Kleppmann 等人，2022 年）。
  5. For forests: Within each cycle, let B.parent = A be the edge whose set operation has the largest LWW timestamp. At render time, “hide” that edge, instead rendering B.parent = "none", but don’t change the actual CRDT state. This hides one of the concurrent edges that created the cycle.
    对于森林：在每个周期内，让 B.parent = A 成为具有最大 LWW 时间戳的 set 操作的边缘。在渲染时，“隐藏”该边缘，而不是渲染 B.parent = "none" ，但不要更改实际的 CRDT 状态。这样可以隐藏创建循环的并发边缘之一。
    • To prevent future surprises, users’ apps should follow the rule: before performing any operation that would create or destroy a cycle involving a hidden edge, first “affirm” that hidden edge, by performing an op that sets B.parent = "none".
      为了防止未来的意外，用户的应用程序应遵循以下规则：在执行任何可能创建或破坏涉及隐藏边缘的循环的操作之前，首先通过执行设置 B.parent = "none" 的操作来“确认”该隐藏边缘。
  6. For trees: Similar, except instead of rendering B.parent = "none", render the previous parent for B - as if the bad operation never happened. More generally, you might have to backtrack several operations. Both Hall et al. (2018) and Nair et al. (2022) describe strategies along these lines.
    对于树：类似，只是不是渲染 B.parent = "none" ，而是为 B 渲染前一个父级 - 就好像坏操作从未发生过一样。更一般地说，您可能需要回溯多个操作。Hall 等人（2018 年）和 Nair 等人（2022 年）描述了沿着这些方向的策略。

Refs: Graphs in Shapiro et al. 2011a; Martin, Ahmed-Nacer, and Urso 2011; Hall et al. (2018); Nair et al. 2022; Kleppmann et al. 2022; Wallace 2022
参考文献：Shapiro 等人 2011a 中的图表；Martin，Ahmed-Nacer 和 Urso 2011；Hall 等人（2018）；Nair 等人 2022；Kleppmann 等人 2022；Wallace 2022

# Undo/Redo # 撤销/重做

In most apps, users should be able to undo and redo their own operations in a stack, using Ctrl+Z / Ctrl+Shift+Z. You might also allow selective undo (undo operations anywhere in the history) or group undo (users can undo each others’ operations) - e.g., for reverting changes.
在大多数应用程序中，用户应该能够使用 Ctrl+Z / Ctrl+Shift+Z 在堆栈中撤消和重做自己的操作。您还可以允许选择性撤消（在历史记录中的任何位置撤消操作）或组撤消（用户可以撤消彼此的操作）- 例如，用于恢复更改。

A simple way to undo an operation is: perform a new operation whose effect locally undoes the target operation. For example, to undo typing a character, perform a new operation that deletes that character.
撤消操作的简单方法是：执行一个新操作，其效果在本地撤销目标操作。例如，要撤销输入一个字符，执行一个删除该字符的新操作。

However, this “local undo” has sub-optimal semantics. For example, suppose one user posts an image, undoes it, then redoes it; concurrently to the undo/redo, another user comments on the image. If you implement the redo as “make a new post with the same contents”, then the comment will be lost: it attaches to the original post, not the re-done one.
然而，这种“本地撤销”具有次优语义。例如，假设一个用户发布了一张图片，然后撤销了它，然后重新发布了它；与此同时，另一个用户对该图片发表了评论。如果您将重做实现为“使用相同内容发布新帖子”，那么评论将丢失：它将附加到原始帖子，而不是重新发布的帖子。

Exact undo instead uses the following semantics:
确切的撤销改为使用以下语义：

  1. In addition to normal app operations, there are operations undo(opID) and redo(opID), where opID identifies a normal operation.
    除了正常的应用程序操作外，还有操作 undo(opID) 和 redo(opID) ，其中 opID 标识正常操作。
  2. For each opID, consider the history of undo(opID) and redo(opID) operations. Apply some boolean-value CRDT to that operation history to decide whether opID is currently (re)done or undone.
    对于每个 opID ，考虑 undo(opID) 和 redo(opID) 操作的历史。将一些布尔值 CRDT 应用于该操作历史，以决定 opID 当前是已完成还是未完成。
  3. The current state is the result of applying your app’s semantics to the (re)done operations only.
    当前状态是将您的应用程序语义仅应用于已完成的操作的结果。

Top: Operations A-F with arrows A to B, A to D, B to C, B to E, D to E, E to F. The labels are: "op1x7: add(red)"; "op33n: add(blue)"; "undo(op33n)"; "undo(op1x7)"; "op91k: add(green)"; "redo(op1x7)". Bottom: Only operations A and D, with an arrow A to D.

Figure 7. Top: Operation history for an add-wins set with exact undo. Currently, op1x7 is redone, op33n is undone, and op91k is done.
图 7. 顶部：具有精确撤销的添加获胜集的操作历史。当前，op1x7 被重做，op33n 被撤消，op91k 已完成。
Bottom: We filter the (re)done operations only and pass the filtered operation history to the add-wins set's semantics, yielding state { "red", "green" }.
底部：我们仅筛选（重新）完成的操作，并将筛选后的操作历史传递给添加获胜集合的语义，生成状态{"red"，"green"}。

For the boolean-value CRDT, you can use LWW, or a multi-value register’s displayed value (e.g., redo-wins). Or, you can use the maximum causal length: the first undo operation is undo(opID, 1); redoing it is redo(opID, 2); undoing it again is undo(opID, 3), etc.; and the winner is the op with the largest number. (Equivalently, the head of the longest chain of causally-ordered operations - hence the name.)
对于布尔值 CRDT，您可以使用 LWW，或多值寄存器的显示值（例如，redo-wins）。或者，您可以使用最大因果长度：第一个撤销操作是 undo(opID, 1) ；重新执行它是 redo(opID, 2) ；再次撤销它是 undo(opID, 3) ，依此类推；获胜者是具有最大编号的操作。（等效地，是因果有序操作链的最长链的头部 - 因此得名。）

Maximum causal length makes sense as a general boolean-value CRDT, but I’ve only seen it used for undo/redo.
最大因果长度作为一种通用的布尔值 CRDT 是有意义的，但我只看到它用于撤消/重做。


Step 3 is more difficult that it sounds. Your app might assume causal-order delivery, then give weird results when undone operations violate it. (E.g., our multi-value register algorithm above will not match the intended semantics after undos.) Also, most algorithms do not support removing past operations from the history. But see Brattli and Yu (2021) for a multi-value register that is compatible with exact undo.
第 3 步比听起来更困难。您的应用程序可能假定因果顺序交付，然后在撤消操作违反它时产生奇怪的结果。（例如，我们上面的多值寄存器算法在撤消后将不符合预期的语义。）此外，大多数算法不支持从历史记录中删除过去的操作。但请参阅 Brattli 和 Yu（2021 年）以获取与精确撤消兼容的多值寄存器。

Refs: Weiss, Uros, and Molli 2010; Yu, Elvinger, and Ignat 2019
参考文献：Weiss, Uros 和 Molli 2010；Yu, Elvinger 和 Ignat 2019

# Other Techniques # 其他技术

This section mentions other techniques that I personally find less useful. Some are designed for distributed data stores instead of collaborative apps; some give reasonable semantics but are hard to implement efficiently; and some are plausibly useful but I have not yet found a good example app.
本节提到了其他一些我个人认为不太有用的技术。有些是为分布式数据存储而设计的，而不是为协作应用程序设计的；有些提供合理的语义，但难以高效实现；还有一些可能有用，但我还没有找到一个好的示例应用程序。

# Remove-Wins Set ＃删除-Wins 设置

The remove-wins set is like the add-wins set, except if there are concurrent operations add(x) and remove(x), then the remove wins: x is not in the set. You can implement this similarly to the add-wins set, using a disable-wins flag instead of enable-wins flag. (Take care that the set starts empty, instead of containing every possible value.) Or, you can implement the remove-wins set using:
删除获胜集类似于添加获胜集，不同之处在于如果存在并发操作 add(x) 和 remove(x) ，则删除获胜： x 不在集合中。您可以类似于添加获胜集来实现这一点，使用禁用获胜标志而不是启用获胜标志。（请注意，集合应该从空开始，而不是包含每个可能的值。）或者，您可以使用以下方式实现删除获胜集：

In general, any implementation must store all values that have ever been added; this is a practical reason to prefer the add-wins set instead. I also do not know of an example app where I prefer the remove-wins set’s semantics. The exception is apps that already store all values elsewhere, such as an archiving collection: I think a remove-wins set of present values would give reasonable semantics. That is equivalent to using an add-wins set of archived values, or to using a disable-wins flag for each value’s isPresent field.
通常情况下，任何实现都必须存储曾经添加过的所有值；这是偏好使用“添加获胜”集合的实际原因。我也不知道有哪个示例应用程序我更喜欢“移除获胜”集合的语义。例外是已经在其他地方存储所有值的应用程序，比如一个存档集合：我认为一个包含当前值的“移除获胜”集合会提供合理的语义。这相当于使用一个包含存档值的“添加获胜”集合，或者对每个值的 isPresent 字段使用一个“禁用获胜”标志。

Refs: Bieniusa et al. 2012; Baquero, Almeida, and Shoker 2017; Baquero et al. 2017
参考文献：Bieniusa 等人 2012 年；Baquero，Almeida 和 Shoker 2017 年；Baquero 等人 2017 年

# PN-Set

The PN-Set (Positive-Negative Set) is another alternative to the add-wins set. Its semantics are: for each value x, count the number of add(x) operations in the operation history, minus the number of remove(x) operations; if it’s positive, x is in the set.
PN-Set（正负集）是另一种替代 add-wins 集的选择。其语义是：对于每个值 x ，在操作历史记录中计算 add(x) 操作的次数，减去 remove(x) 操作的次数；如果结果为正，则 x 在集合中。

This semantics give strange results in the face of concurrent operations, as described by Shapiro et al. (2011a). For example, if two users call add(x) concurrently, then to remove x from the set, you must call remove(x) twice. If two users do that concurrently, it will interact strangely with further add(x) operations, etc.
这种语义在面对并发操作时会产生奇怪的结果，正如 Shapiro 等人(2011a)所描述的。例如，如果两个用户同时调用 add(x) ，那么要从集合中移除 x ，您必须调用 remove(x) 两次。如果两个用户同时执行此操作，它将与后续的 add(x) 操作产生奇怪的交互等。

Like the maximum causal length semantics, the PN-Set was originally proposed for undo/redo.
与最大因果长度语义类似，PN-Set 最初是为撤销/重做而提出的。

Refs: Weiss, Urso, and Molli 2010; Shapiro et al. (2011a)
参考文献：Weiss，Urso 和 Molli 2010；Shapiro 等人（2011a）

# Observed-Reset Operations
# 观察-重置操作

An observed-reset operation cancels out all causally prior operations. That is, when looking at the operation history, you ignore all operations that are causally prior to any reset operation, then compute the state from the remaining operations.
观察重置操作会取消所有因果先前的操作。也就是说，在查看操作历史时，您会忽略所有因果先于任何 reset 操作的操作，然后从剩余的操作中计算状态。

Six +1 operations, and one reset() operation that is causally greater than three of the +1 operations (underlined).

Figure 8. Operation history for a counter with +1 and observed-reset operations. The reset operation cancels out the underlined +1 operations, so the current state is 3.
图 8. 具有+1 和观察重置操作的计数器的操作历史。 重置操作取消了下划线+1 操作，因此当前状态为 3。

Observed-reset operations are a tempting way to add a delete(key) operation to a map-like object: make delete(key) be an observed-reset operation on the value CRDT at key. Thus delete(key) restores a value CRDT to its original, unused state, which you can treat as the “key-not-present” state. However, then if one user calls delete(key) while another user operates on the value CRDT concurrently, you’ll end with an awkward partial state:
观察重置操作是向类似地图对象添加 delete(key) 操作的一种诱人方式：使 delete(key) 成为值 CRDT 在 key 上的观察重置操作。因此 delete(key) 将值 CRDT 恢复到其原始未使用状态，您可以将其视为“键不存在”状态。然而，如果一个用户在另一个用户同时操作值 CRDT 时调用 delete(key) ，则最终会得到尴尬的部分状态：

In a collaborative todo-list with observed-reset deletes, concurrently deleting an item and marking it done results in a nonsense list item with no text field.

Image credit: Figure 6 by Kleppmann and Beresford. That paper describes a theoretical JSON CRDT, but Firebase RTDB has the same behavior.
图像来源：Kleppmann 和 Beresford 的第 6 图。该论文描述了一种理论上的 JSON CRDT，但 Firebase RTDB 具有相同的行为。

I instead prefer to omit delete(key) from the map-like object entirely. If you need deletions, instead use a CRDT-valued map or similar. Those ultimately treat delete(key) as a permanent deletion (from the unique-set of CRDTs) or as an archive operation.
我更喜欢完全从类似地图的对象中省略 delete(key) 。如果您需要删除，请改用值为 CRDT 的地图或类似地图。这些最终将 delete(key) 视为永久删除（从 CRDT 的唯一集合中）或作为归档操作。

Refs: Deletes in Riak Map
Refs: 在 Riak Map 中删除

# Querying the Causal Order
# 查询因果顺序

Most of our techniques so far don’t use the causal order on operations (arrows in the operation history). However, the multi-value register does: it queries the set of causally-maximal operations, displaying their values. Observed-reset operations also query the causal order, and the add-wins set/remove-wins set reference it indirectly.
到目前为止，我们大多数的技术并未使用操作的因果顺序（操作历史中的箭头）。然而，多值寄存器会查询一组因果最大的操作，并显示它们的值。观察重置操作也会查询因果顺序，而添加获胜集/移除获胜集会间接引用它。

One can imagine CRDTs that query the causal order in many more ways. However, I find these too complicated for practical use:
人们可以想象到以更多方式查询因果顺序的 CRDT。然而，我发现这些对于实际应用来说过于复杂。

  1. It is expensive to track the causal order on all pairs of operations.
    跟踪所有操作对的因果顺序是昂贵的。
  2. Semantics that ask “is there an operation concurrent to this one?” generally need to store operations forever, in case a concurrent operation appears later.
    通常需要永久存储操作，以防以后出现并发操作的语义会询问“是否有与此操作并发的操作？”
  3. It is easy to create semantic rules that don’t behave well in all scenarios.
    在所有情况下都表现不佳的语义规则很容易创建。

(The multi-value register and add-wins set occupy a special case that avoids (1) and (2).)
多值寄存器和加法器集占据了一个特殊情况，避免了（1）和（2）。

As an example of (3), it is tempting to define an add-wins set by: an add(x) operation overrules any concurrent remove(x) operation, so that the add wins. But then in Figure 9’s operation history, both remove(x) operations get overruled by concurrent add(x) operations. That makes x present in the set when it shouldn’t be.
作为（3）的一个例子，诱人的定义是：通过一个 add(x) 操作来覆盖任何并发的 remove(x) 操作，这样添加就会获胜。但是在图 9 的操作历史中，两个 remove(x) 操作都被并发的 add(x) 操作覆盖。这使得 x 出现在集合中，而它本不应该出现。

Operations A-D with arrows A to B, C to D. The labels are: add(x), remove(x), add(x), remove(x).

Figure 9. Operation history for an add-wins set. One user calls add(x) and then remove(x); concurrently, another user does likewise. The correct current state is the empty set: the causally-maximal operations on x are both remove(x).
图 9. 添加胜者集的操作历史。一个用户调用 add(x)，然后调用 remove(x)；与此同时，另一个用户也这样做。正确的当前状态是空集：对 x 的因果最大操作都是 remove(x)。

As another example, you might try to define an add-wins set by: if there are concurrent add(x) and remove(x) operations, apply the remove(x) “first”, so that add(x) wins; otherwise apply operations in causal order. But then in the above operation history, the intended order of operations contains a cycle:
作为另一个例子，您可以尝试通过以下方式定义一个 add-wins 集合：如果存在并发的 add(x) 和 remove(x) 操作，则应用“first” remove(x) ，以便 add(x) 胜出；否则按因果顺序应用操作。但是在上述操作历史中，操作的预期顺序包含一个循环：

Operations A-D with "causal order" arrows A to B, C to D, and "remove-first rule" arrows B to C, D to A. The labels are: add(x), remove(x), add(x), remove(x).

I always try out this operation history when a paper claims to reproduce/understand the add-wins set in a new way.
每当一篇论文声称以新的方式复制/理解添加胜利集时，我总是尝试这个操作历史。

# Topological Sort # 拓扑排序

A topological sort is a general way to “derive” CRDT semantics from an ordinary data structure. Given an operation history made out of ordinary data structure operations, the current state is defined by:
拓扑排序是一种从普通数据结构“推导”CRDT 语义的一般方法。给定由普通数据结构操作组成的操作历史，当前状态由以下定义：

  1. Sort the operations into some consistent linear order that is compatible with the causal order (o < p implies o appears before p). E.g., sort them by Lamport timestamp.
    将操作按照与因果顺序兼容的一致线性顺序进行排序（ o < p 意味着 o 出现在 p 之前）。例如，按照 Lamport 时间戳对它们进行排序。
  2. Apply those operations to the starting state in order, returning the final state. If an operation would be invalid (e.g. it would create a cycle in a tree), skip it.
    按顺序将这些操作应用于起始状态，返回最终状态。如果某个操作无效（例如，在树中创建循环），请跳过它。

The problem with these semantics is that you don’t know what result you will get - it depends on the sort order, which is fairly arbitrary.
这些语义的问题在于你不知道会得到什么结果 - 这取决于排序顺序，而排序顺序是相当任意的。

However, topological sort can be useful as a fallback in complex cases, like tree cycles or group-chat permissions. You can think of it like asking a central server for help: the sort order stands in for “the order in which ops reached the server”. (If you do have a server, you can use that instead.)
然而，在复杂情况下，拓扑排序可以作为一种后备方案，比如树循环或群聊权限。您可以将其视为向中央服务器请求帮助：排序顺序代表“操作到达服务器的顺序”。（如果您有服务器，可以使用该服务器代替。）

Ref: Kleppmann et al 2018
参考：Kleppmann 等人 2018

# Capstones # 顶石

Let’s finish by designing novel semantics for two practical but complex collaborative apps.
让我们通过为两个实用但复杂的协作应用程序设计新颖的语义来完成。

# Recipe Editor # 配方编辑器

I’ve mentioned a collaborative recipe editor in several examples. It’s implemented as a Collabs demo: live demo, talk slides, talk video, source code.
我在几个示例中提到了一个协作食谱编辑器。它被实现为一个 Collabs 演示：实时演示，演讲幻灯片，演讲视频，源代码。

Recipe editor screenshot showing a recipe for roast broccoli.

The app’s semantics can be described compositionally using nested objects. Here is a schematic:
应用程序的语义可以使用嵌套对象进行组合描述。这里是一个示意图：

{
    ingredients: UniqueSetOfCRDTs<{
        text: TextCRDT,
        amount: LWWRegister<number>, // Scale-independent amount
        units: LWWRegister<Unit>,
        position: LWWRegister<Position>, // List CRDT position, for list-with-move
        isPresent: EnableWinsFlag // For update-wins semantics
    }>,
    globalScale: LWWRegister<number>, // For scale ops
    description: {
        text: TextCRDT,
        formatting: InlineFormattingCRDT
    }
}

(Links by class name: UniqueSetOfCRDTs, TextCRDT, LWWRegister, EnableWinsFlag, InlineFormattingCRDT.)
（按类名链接：UniqueSetOfCRDTs、TextCRDT、LWWRegister、EnableWinsFlag、InlineFormattingCRDT。）

Most GUI operations translate directly to operations on this state, but there are some edge cases.
大多数 GUI 操作直接转换为对此状态的操作，但也有一些边缘情况。

# Block-Based Rich Text
# 基于块的富文本

We described inline rich-text formatting above, like bold and italics. Real rich-text editors also support block formatting: headers, lists, blockquotes, etc. Fancy apps like Notion even let you rearrange the order of blocks using drag-and-drop:
我们在上面描述了内联富文本格式，比如粗体和斜体。真正的富文本编辑器还支持块格式化：标题、列表、块引用等。像 Notion 这样的高级应用甚至可以让您使用拖放重新排列块的顺序：

Notion screenshot of moving block "Lorem ipsum dolor sit amet" from before to after "consectetur adipiscing elit".

Let’s see if we can design a CRDT semantics that has all of these features: inline formatting, block formatting, and movable blocks. Like the list-with-move, moving a block should not affect concurrent edits within that block. We’d also like nice behavior in tricky cases - e.g., one user moves a block while a concurrent user splits it into two blocks.
让我们看看是否可以设计一个具有以下所有特性的 CRDT 语义：内联格式、块格式和可移动块。就像带有移动功能的列表一样，移动一个块不应影响该块内的并发编辑。我们还希望在棘手情况下表现良好 - 例如，一个用户移动一个块，同时另一个并发用户将其拆分为两个块。

This section is experimental; I’ll update it in the future if I learn of improvements (suggestions are welcome).
本节是实验性的；如果我了解到改进的地方，我会在未来更新它（欢迎提出建议）。

Refs: Ignat, André, and Oster 2017 (similar Operational Transformation algorithm); Quill line formatting; unpublished notes by Martin Kleppmann (2022); Notion’s data model
参考文献：Ignat、André和 Oster 2017（类似的操作转换算法）；Quill 行格式化；Martin Kleppmann（2022 年）的未发表笔记；Notion 的数据模型

# CRDT State # CRDT 状态

The CRDT state is an object with several components:
CRDT 状态是一个具有多个组件的对象：

# Rendering the App State
# 渲染应用程序状态

Let’s ignore blockCRDT.placement for now. Then rendering the rich-text state resulting from the CRDT state is straightforward:
让我们暂时忽略 blockCRDT.placement 。然后，呈现由 CRDT 状态产生的富文本状态是直接的：

  1. Each block marker defines a block.
    每个块标记定义一个块。
  2. The block’s contents are the text immediately following that block marker in text, ending at the next block marker.
    块的内容是紧随 text 中的块标记之后的文本，直到下一个块标记结束。
  3. The block is displayed according to its blockType and indent.
    根据其 blockType 和 indent 显示块。
    • For ordered list items, the leading number (e.g. “3.”) is computed at render time according to how many preceding blocks are ordered list items. Unlike in HTML, the CRDT state does not store an explicit “list start” or “list end”.
      对于有序列表项，前导数字（例如“3.”）在呈现时根据前面有多少个有序列表项块来计算。与 HTML 不同，CRDT 状态不存储显式的“列表开始”或“列表结束”。
  4. The text inside a block is inline-formatted according to format. Note that formatting marks might cross block boundaries; this is fine.
    块内的文本根据 format 进行内联格式化。请注意，格式标记可能会跨越块边界；这没问题。

Top: "text: _Hello_Okay" with underscores labeled "Block marker n7b3", "Block marker ttx7". Bottom left: 'n7b3: { blockType: “ordered list item”, indent: 0 }', 'ttx7: { blockType: “blockquote”, indent: 0 }'. Bottom right: two rendered blocks, "1. Hello" and "(blockquote) Okay".

Figure 10. Sample state and rendered text, omitting blockList, hooks, and blockCRDT.placement.
图 10。示例状态和渲染文本，省略 blockList ，钩子和 blockCRDT.placement 。

Now we need to explain blockCRDT.placement. It tells you how to order a block relative to other blocks, and whether it is merged into another block.
现在我们需要解释 blockCRDT.placement 。它告诉您如何相对于其他块订购一个块，并且它是否合并到另一个块中。

Top: "blockList: [p32x, p789]". Middle: "text: _Hel^lo_Ok^_ay" with underscores labeled "Block marker n7b3", "Block marker ttx7", "Block marker x1bc", and carets labeled "Hook @ pbj8", "Hook @ p6v6". Bottom left: 'n7b3.placement: { case: “pos”, target: p32x }', 'ttx7.placement: { case: “origin”, target: pbj8 }', 'x1bc.placement: { case: “parent”, target: p6v6 }'. Bottom right: two rendered blocks, "1. Hello" and "(blockquote) Okay".

Figure 11. Repeat of Figure 10 showing blockList, hooks, and blockCRDT.placement. Observe that "Okay" is the merger of two blocks, "Ok" and "ay".
图 11. 重复图 10，显示 blockList ，挂钩和 blockCRDT.placement 。请注意，“Okay”是两个块“Ok”和“ay”的合并。

You might notice some dangerous edge cases here! We’ll address those shortly.
您可能会注意到这里有一些危险的边缘情况！我们很快会解决这些问题。

# Move, Split, and Merge
＃移动、拆分和合并

Now we can implement the three interesting block-level operations:
现在我们可以实现三个有趣的块级操作：

  1. Move. To move block B so that it immediately follows block A, first create a new position in blockList that is immediately after A’s position (or its origin’s (origin’s…) position). Then set block B’s placement to { case: "pos", target: <new blockList position> }.
    移动。要将块 B 移动到紧跟在块 A 之后的位置，首先在 blockList 中创建一个紧跟在 A 位置之后（或其原点位置）的新位置。然后将块 B 的 placement 设置为 { case: "pos", target: <new blockList position> } 。
    • If there are any blocks with origin B that you don’t want to move along with B, perform additional move ops to keep them where they currently appear.
      如果有任何与原点 B 相关的块，您不希望随 B 一起移动，执行额外的移动操作以保持它们当前的位置。
    • If there are any blocks with origin A, perform additional move ops to move them after B, so that they aren’t rendered between A and B.
      如果有任何来自 A 原点的块，请执行额外的移动操作，将它们移动到 B 之后，以便它们不会在 A 和 B 之间呈现。
    • Edge case: to move block B to the start, create the position at the beginning of blockList.
      边缘情况：将块 B 移动到开头，创建位置在 blockList 的开始处。
  2. Split. To split a block in two, insert a new hook and block marker at the splitting position (in that order). Set the new block’s placement to { case: "origin", target: <new hook's position> }, and set its blockType and indent as you like.
    拆分。要将一个块分成两个部分，在分割位置插入一个新的钩子和块标记（按顺序）。将新块的 placement 设置为 { case: "origin", target: <new hook's position> } ，并根据需要设置其 blockType 和 indent 。
    • Why do we point to a hook instead of the previous block’s block header? Basically, we want to follow the text just prior to the split, which might someday end up in a different block. (Consider the case where the previous block splits again, then one half moves without the other.)
      为什么我们指向一个挂钩而不是前一个区块的区块头？基本上，我们想要遵循在分裂之前的文本，这可能最终会出现在不同的区块中。（考虑前一个区块再次分裂的情况，然后一半移动而另一半不移动。）
  3. Merge. To merge block B into the previous block, first find the previous block A in the current rendered state. (This might not be the previous block marker in text.) Insert a new hook at the end of A’s rendered text, then set block B’s placement to { case: "parent", target: <new hook's position>, prevPlacement: <block B's previous placement value> }.
    合并。要将块 B 合并到前一个块中，首先在当前呈现状态中找到前一个块 A。（这可能不是 text 中的前一个块标记。）在 A 的呈现文本末尾插入一个新的钩子，然后将块 B 的 placement 设置为 { case: "parent", target: <new hook's position>, prevPlacement: <block B's previous placement value> } 。
    • The “end of A’s rendered text” might be in a block that was merged into A.
      “A 的渲染文本的末尾”可能在合并到 A 中的块中。

# Edge Cases # 边缘情况

It remains to address some dangerous edge cases during rendering.
在渲染过程中仍然需要处理一些危险的边缘情况。

First, it is possible for two blocks B and C to have the same origin block A. So according to the above rules, they should both be rendered immediately after block A, which is impossible. Instead, render them one after the other, in the same order that their hooks appear in the rendered text. (This might differ from the hooks’ order in text.)
首先，两个块 B 和 C 可能具有相同的起始块 A。因此根据上述规则，它们应该紧随块 A 之后立即呈现，这是不可能的。相反，按照它们在呈现文本中出现的钩子的顺序依次呈现它们。 （这可能与 text 中钩子的顺序不同。）

More generally, the relationships “block B has origin A” form a forest. (I believe there will never be a cycle, so we don’t need our advanced technique above.) For each tree in the forest, render that tree’s blocks consecutively, in depth-first pre-order traversal order.
更普遍地说，“块 B 具有起源 A”的关系形成了一棵森林。（我相信永远不会出现循环，所以我们不需要上面提到的高级技术。）对于森林中的每棵树，按照深度优先的先序遍历顺序连续渲染该树的块。

Top: "blockList: [p32x, p789]. Bottom: "Forest of origins" with nodes A-E and edges B to A, C to B, D to A. Nodes A and E have lines to p32x and p789, respectively.

Figure 12. A forest of origin relationships. This renders as block order A, B, C, D, E. Note that the tree roots A, E are ordered by their positions in blockList.
图 12. 一个起源关系的森林。这被渲染为块顺序 A, B, C, D, E 。请注意，树根 A, E 按照它们在 blockList 中的位置排序。

Second, it is likewise possible for two blocks B and C to have the same parent block A. In that case, render both blocks’ text as part of block A, again in order by their hooks.
其次，两个块 B 和 C 有可能有相同的父块 A。在这种情况下，按照它们的挂钩顺序，将两个块的文本呈现为块 A 的一部分。

More generally, we would like the relationships “block B has parent A” to form a forest. However, this time cycles are possible!
更一般地说，我们希望关系“块 B 有父级 A”形成一片森林。然而，这次循环是可能的！

Staring state: A then B. Top state: AB. Bottom state: (B then A) with an arrow to (BA). Final state: A and B with arrows in a cycle and "??".

Figure 13. One user merges block B into A. Concurrently, another user moves B above A, then merges A into B. Now their parent relationships form a cycle.
图 13. 一个用户将块 B 合并到 A 中。 与此同时，另一个用户将 B 移动到 A 上方，然后将 A 合并到 B 中。 现在它们的父关系形成了一个循环。

To solve this, use any of the ideas from forests and trees to avoid/hide cycles. I recommend a variant of idea 5: within each cycle, “hide” the edge with largest LWW timestamp, instead rendering its prevPlacement. (The prevPlacement always has case "pos" or "origin", so this won’t create any new cycles. Also, I believe you can ignore idea 5’s sentence about “affirming” hidden edges.)
为了解决这个问题，可以使用来自森林和树的任何想法来避免/隐藏循环。我建议使用想法 5 的一个变体：在每个循环中，“隐藏”具有最大 LWW 时间戳的边缘，而不是渲染其 prevPlacement 。（ prevPlacement 总是具有案例 "pos" 或 "origin" ，因此这不会创建任何新的循环。此外，我相信您可以忽略有关“确认”隐藏边缘的想法 5 的句子。）

Third, to make sure there is always at least one block, the app’s initial state should be: blockList contains a single position; text contains a single block marker with placement = { case: "pos", target: <the blockList position> }.
第三，为了确保始终至少有一个块，应用程序的初始状态应为： blockList 包含一个位置； text 包含一个带有 placement = { case: "pos", target: <the blockList position> } 的块标记。

Why does moving a block set its placement.target to a position within blockList, instead of a hook like Split/Merge? This lets us avoid another cycle case: if block B is moved after block A, while concurrently, block A is moved after block B, then blockList gives them a definite order without any fancy cycle-breaking rules.
为什么移动一个块会将其 placement.target 设置为 blockList 内的位置，而不是像 Split/Merge 那样设置为挂钩？这样我们就可以避免另一个循环情况：如果块 B 在块 A 之后移动，同时，块 A 在块 B 之后移动，那么 blockList 会给它们一个明确的顺序，而不需要任何花哨的循环打破规则。

# Validation ＃验证

I can’t promise that these semantics will give a reasonable result in every situation. But following the advice in Composition Techniques, we can check all interesting pairs of concurrent operations, then trust that the general case at least satisfies strong convergence (by composition).
我不能保证这些语义在每种情况下都能给出合理的结果。但是，遵循《组合技术》中的建议，我们可以检查所有有趣的并发操作对，然后相信至少满足强收敛性（通过组合）的一般情况。

The following figure shows what I believe will happen in various concurrent situations. In each case, it matches my preferred behavior. Lines indicate blocks, while A/B/C indicate chunks of text.
以下图显示了我认为在各种并发情况下会发生的情况。在每种情况下，它都符合我的首选行为。线表示块，而 A/B/C 表示文本块。

Split vs Split: ABC to (A BC / AB C) to A B C. Merge vs Merge: A B C to (A BC / AB C) to ABC. Split vs Merge 1: AB C to (A B C / ABC) to A BC. Split vs Merge 2: A BC to (A B C / ABC) to AB C. Move vs Merge: A B C to (B A C / A BC) to BC A. Move vs Split: A BC to (BC A / A B C) to B C A.

# Conclusion ＃结论

A CRDT-based app’s semantics describe what the state of the app should be, given a history of collaborative operations. Choosing semantics is ultimately a per-app problem, but the CRDT literature provides many ideas and examples.
基于 CRDT 的应用程序语义描述了应用程序状态应该是什么，考虑到协作操作的历史。选择语义最终是一个每个应用程序的问题，但 CRDT 文献提供了许多想法和示例。

This blog post was long because there are indeed many techniques. However, we saw that they are mostly just a few basic ideas (UIDs, list CRDT positions, LWW, multi-value register) plus composed examples.
这篇博客文章很长，因为确实有许多技术。然而，我们看到它们大多只是一些基本思想（UID、列表 CRDT 位置、LWW、多值寄存器）加上组合示例。

It remains to describe algorithms implementing these semantics. Although we gave some basic CRDT algorithms in-line, there are additional nuances and optimizations. Those will be the subject of the next post, Part 3: Algorithmic Techniques.
还需要描述实现这些语义的算法。虽然我们在内联中提供了一些基本的 CRDT 算法，但还有其他微妙之处和优化。这些将是下一篇文章《第 3 部分：算法技术》的主题。

This blog post is Part 2 of a series.
本博客文章是系列的第 2 部分。

⭐️ 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