Announcing list-positions
公告列表位置

Matthew Weidner | Apr 29th, 2024
马修·韦德纳 | 2024 年 4 月 29 日
Home | RSS Feed
首页 | RSS 订阅
Keywords: list-positions, collaborative text editing, Fugue
关键词：列表位置，协作文本编辑，赋格

The main ideas in this post are described in slides here.
此帖中的主要思想在此幻灯片中描述。

# Motivation # 动机

Suppose you’re implementing a text editor. A key choice you must make is what data structure to use for the text. Traditionally, this is an array of characters, or an optimized equivalent like a rope. These data structures all implement a sequence abstraction: your mental model of the text is a map (index -> char).
假设你正在实现一个文本编辑器。你必须做出的一个关键选择是使用什么数据结构来存储文本。传统上，这是一组字符，或者是像绳索一样的优化等价物。这些数据结构都实现了一个序列抽象：你对文本的心理模型是一个映射 (index -> char) 。

In a sequence like this, insertions and deletions “shift” the indices of later characters. For example, if a user types “E-“ in front of the text “Bike route”, the index of “B” increases by 2:
在这样的序列中，插入和删除会“移动”后续字符的索引。例如，如果用户在文本“Bike route”前输入“E-”，则“B”的索引增加了 2：

With that in mind, let’s consider various features that you might add to your text editor.
考虑到这一点，让我们来看看您可能会添加到文本编辑器中的各种功能。

1. Comments. The user can add a comment to a range of text.
   评论。用户可以对一段文本添加评论。

   It’s easy to store each comment in the form { from: 40, to: 49, comment: "Or ..." }, where from and to are indices indicating the range of text. But you’ll need to remember to update from and to whenever future edits shift the text’s range.
   将每条评论存储为 { from: 40, to: 49, comment: "Or ..." } 的形式很简单，其中 from 和 to 是指示文本范围的索引。但是，每当未来的编辑改变文本范围时，您需要记得更新 from 和 to 。

2. History and blame. The user can view how historical edits map to the current state, like with git blame.
   历史和责任。用户可以查看历史编辑如何映射到当前状态，类似于 git blame。

   You can compute blame from a log of changes like { op: "insert", index: 23, chars: "my house" }. However, it will take some effort to correlate the original insertion/deletion index with a character’s current index in the text, due to shifting caused by subsequent edits.
   您可以从像 { op: "insert", index: 23, chars: "my house" } 这样的更改日志中计算责任。然而，由于后续编辑导致的位移，将原始插入/删除索引与字符在文本中的当前索引相关联将需要一些努力。

3. Collaborative editing. Multiple users can collaborate on a text document.
   协作编辑。多个用户可以共同编辑一个文本文件。

   An obvious strategy is to send edits like Insert " the" at index 17 to a central server, which applies them to its own copy of the text in receipt order. There is a problem you’ll need to address, though: By the time an edit makes it to the server, the server may have applied a concurrent edit from another user that invalidates its indices.
   一个明显的策略是将像 Insert " the" at index 17 这样的编辑发送到中央服务器，服务器按接收顺序将其应用到自己文本的副本中。不过，您需要解决一个问题：当编辑到达服务器时，服务器可能已经应用了来自其他用户的并发编辑，这会使其索引失效。

Bob submits the edit Insert " the" at index 17 to a central server. But before his edit arrives, the server applies Alice's concurrent edit Insert " gray" at index 3. So it no longer makes sense to apply Bob's edit at index 17; it must be shifted to index 22.
鲍勃将编辑 Insert " the" at index 17 提交到中央服务器。但在他的编辑到达之前，服务器应用了爱丽丝的并发编辑 Insert " gray" at index 3 。因此，在索引 17 应用鲍勃的编辑就没有意义了；它必须移到索引 22。

Overall, while implementing these features, you’re going to spend a lot of effort transforming array indices to account for other insertions and deletions. What if you could avoid this effort, by assigning each character an immutable identifier that’s always “in the right place”?
总体而言，在实现这些功能时，您将花费大量精力来转换数组索引，以考虑其他插入和删除。如果您可以通过为每个字符分配一个始终“在正确位置”的不可变标识符来避免这种努力，那会怎么样？

# list-positions # 列表位置

list-positions is a new TypeScript library designed to do exactly that. It models text as an ordered map (position -> char), where each character’s position is unique, immutable, and totally ordered. So if you insert a new entry (position, char) into the map, the other entries stay the same, even though their array indices change:
list-positions 是一个新的 TypeScript 库，旨在实现这一目标。它将文本建模为一个有序映射 (position -> char) ，其中每个字符的位置是唯一的、不可变的，并且完全有序。因此，如果你将一个新条目 (position, char) 插入到映射中，其他条目保持不变，即使它们的数组索引发生变化：

Before:

Index    | 0       1       2
Position | pos123  posLMN  posXYZ
Value    | 'C'     'a'     't'

After calling list.set(posABC, 'h') where pos123 < posABC < posLMN:

Index    | 0       1       2       3
Position | pos123  posABC  posLMN  posXYZ
Value    | 'C'     'h'     'a'     't'

More generally, you can use list-positions for lists of arbitrary values: items in a todo-list, spreadsheet rows and columns, slides in a slideshow, etc.
更一般地说，您可以对任意值的列表使用列表位置：待办事项列表中的项目、电子表格的行和列、幻灯片放映中的幻灯片等。

List-positions is a library of local data structures: it provides list-as-ordered-map types that you can manipulate however you like. However, lists on different devices can share positions, and positions are guaranteed to be unique and totally ordered even if they are generated concurrently on different devices. So you can use list-positions to implement collaborative lists and text, on top of a variety of network architectures.
List-positions 是一个本地数据结构库：它提供了可以随意操作的有序映射类型的列表。然而，不同设备上的列表可以共享位置，并且即使在不同设备上并发生成，位置也保证是唯一且完全有序的。因此，您可以使用 list-positions 在各种网络架构之上实现协作列表和文本。

For example, you can send edits to a central server like above, just using positions instead of array indices. Each position will be “in the right place” even if a concurrent edit arrives first:
例如，您可以像上面那样将编辑发送到中央服务器，只需使用位置而不是数组索引。即使并发编辑先到达，每个位置也会“在正确的位置”。

Alice and Bob submits edits to a central server like above, but this time, they use positions instead of array indices. When the server receives Bob's edit, it looks up the index corresponding to posDEF and finds that it is now 22. Thus Bob's text ends up in the right place.
爱丽丝和鲍勃向中央服务器提交编辑，如上所示，但这次他们使用位置而不是数组索引。当服务器接收到鲍勃的编辑时，它查找与 posDEF 对应的索引，发现现在是 22。因此，鲍勃的文本最终出现在正确的位置。

# Why This Library?
# 为什么选择这个库？

If you’ve read my previous blog posts, you probably expected me to announce a CRDT library - not a local data structures library. List-positions does indeed get its core algorithm from the Fugue list CRDT, and you can easily implement traditional list CRDTs on top of the library.
如果你读过我之前的博客文章，你可能会期待我宣布一个 CRDT 库，而不是一个本地数据结构库。List-positions 确实从 Fugue 列表 CRDT 获取其核心算法，并且你可以很容易地在这个库的基础上实现传统的列表 CRDT。

However, the motivation section above shows that immutable positions are not just for collaboration: they are a general way of thinking about sequences that help you implement single-user functionality as well. Collaboration is merely where the challenges of mutable array indices become too large to ignore. (Though you can make them work, using Operational Transformation.)
然而，上述动机部分表明，不可变位置不仅仅用于协作：它们是一种通用的思考序列的方式，有助于您实现单用户功能。协作只是可变数组索引的挑战变得无法忽视的地方。（尽管您可以通过操作变换使它们正常工作。）

I’ll admit that my own motivation for list-positions comes from various collaboration-related problems. In particular, I could not figure out how to solve the following problems with traditional CRDTs:
我承认我对列表位置的动机来源于各种与协作相关的问题。特别是，我无法用传统的 CRDT 解决以下问题：

• Server authority. If your collaborative app has a central server, it should be able to understand clients’ updates and choose to accept, modify, or reject them, like in a traditional CRUD app. This is tricky with existing CRDTs because their updates are often opaque binary blobs, and it is hard to “reject” an update without also rejecting all future updates from that client. With list-positions, you choose the format and meaning of network messages, and your server can choose exactly how to update its local data structures.
  服务器权限。如果您的协作应用程序有一个中央服务器，它应该能够理解客户端的更新，并选择接受、修改或拒绝这些更新，就像在传统的 CRUD 应用程序中一样。这在现有的 CRDT 中是棘手的，因为它们的更新通常是不可见的二进制数据块，拒绝一个更新往往也意味着拒绝来自该客户端的所有未来更新。通过列表位置，您可以选择网络消息的格式和含义，您的服务器可以精确选择如何更新其本地数据结构。
• Complex data types. Some data structures are just plain difficult to model as a CRDT. The example I have in mind is a ProseMirror document, which is an XML-like tree where users can split and merge nodes. Instead of figuring out a proper CRDT, you can just say “Apply everyone’s ProseMirror steps in a fixed order (e.g., a server’s receipt order)”, except that array indices will get messed up like above. By replacing the array indices with positions, I got a schema-agnostic ProseMirror collaboration prototype working in a few days.
  复杂数据类型。一些数据结构很难建模为 CRDT。我想到的例子是 ProseMirror 文档，它是一个类似 XML 的树，用户可以拆分和合并节点。与其找出一个合适的 CRDT，不如直接说“按固定顺序（例如，服务器的接收顺序）应用每个人的 ProseMirror 步骤”，只是数组索引会像上面那样混乱。通过用位置替换数组索引，我在几天内实现了一个与模式无关的 ProseMirror 协作原型。
• Cherry-picking. Git lets you “cherry-pick” updates from one branch to another, without also applying all previous updates. CRDTs struggle with this because their internal metadata assumes causality/monotonicity. With list-positions, you can manage metadata yourself, independent of user-visible changes. Thus with some setup, you can implement CRDT-style rich-text editing on top of git in a way that supports cherry-picking.
  挑选更新。Git 允许你从一个分支“挑选”更新到另一个分支，而不必应用所有先前的更新。CRDT 在这方面存在困难，因为它们的内部元数据假设因果关系/单调性。通过列表位置，你可以独立于用户可见的更改自行管理元数据。因此，通过一些设置，你可以在 Git 之上实现 CRDT 风格的富文本编辑，支持挑选更新。

As an added bonus, separating the position abstraction from a particular sync strategy makes it possible to implement collaborative text/list editing on top of various data stores (without merely storing an append-only log of CRDT messages). That way, not every data store implementer needs to become an expert on list CRDTs/OT. For example, I’ve made prototypes of collaborative rich-text editing on top of the Triplit NoSQL DB, Replicache client-side sync framework, and ElectricSQL database sync service - see list-positions-demos.
作为额外的好处，将位置抽象与特定的同步策略分离，使得在各种数据存储之上实现协作文本/列表编辑成为可能（而不仅仅是存储一个仅追加的 CRDT 消息日志）。这样，并不是每个数据存储实现者都需要成为列表 CRDT/OT 的专家。例如，我已经在 Triplit NoSQL 数据库、Replicache 客户端同步框架和 ElectricSQL 数据库同步服务之上制作了协作富文本编辑的原型 - 请参见 list-positions-demos。

Relative to my position-strings library, list-positions implements the same abstraction (unique immutable positions), but with actually practical performance for text and large lists. List-positions also has a more convenient, non-minimalist API. On the other hand, its positions are less portable than lexicographically-ordered strings.
相对于我的位置字符串库，列表位置实现了相同的抽象（唯一不可变的位置），但在文本和大型列表中具有实际的性能。列表位置还具有更方便的非极简主义 API。另一方面，它的位置比按字典序排列的字符串的可移植性差。

# Performance # 性能

Performance is always a concern for text-editing libraries that assign a unique immutable ID to each character. If you naively store each character’s ID as an object, you’ll have excessive memory usage and saved state sizes.
性能始终是文本编辑库关注的问题，这些库为每个字符分配一个唯一的不可变 ID。如果你天真地将每个字符的 ID 存储为一个对象，你将会有过高的内存使用和保存状态的大小。

To avoid this, list-positions groups together “runs” of characters, similar to a rope. Like a rope, the runs form a tree, but unlike a rope, the tree is never rebalanced; that aids positions’ immutability. You can find more detail in internals.md.
为了避免这种情况，列表位置将字符的“运行”组合在一起，类似于绳索。像绳索一样，这些运行形成一棵树，但与绳索不同的是，这棵树从不重新平衡；这有助于位置的不可变性。您可以在 internals.md 中找到更多详细信息。

The resulting performance is more than adequate in my (admittedly basic) benchmarks. E.g., constructing a traditional CRDT on top of the library and applying the automerge-perf 260k edit text trace gives the following results, which are competitive with state-of-the-art CRDT libraries on crdt-benchmarks B4:
生成的性能在我（诚然是基本的）基准测试中是相当充足的。例如，在库的基础上构建一个传统的 CRDT，并应用 automerge-perf 260k 编辑文本跟踪，得到以下结果，这些结果与 crdt-benchmarks B4 上的最先进 CRDT 库具有竞争力：

- Sender time (ms): 655                 (400k ops/sec)
- Avg update size (bytes): 92.7
- Receiver time (ms): 369               (700k ops/sec)
- Save time (ms): 11
- Save size (bytes): 599817             (Naive JSON encoding; 6x plain text size)
- Load time (ms): 10
- Save time GZIP'd (ms): 42
- Save size GZIP'd (bytes): 87006       (GZIP'd JSON encoding; 3x GZIP'd text size)
- Load time GZIP'd (ms): 30
- Mem used estimate (MB): 1.8           (<20 bytes/char)

# Conclusion # 结论

There’s much more info in the docs: github.com/mweidner037/list-positions#readme.
文档中有更多信息：github.com/mweidner037/list-positions#readme。
You can also check out @list-positions/formatting, @list-positions/crdts, and list-positions-demos.
您还可以查看 @list-positions/formatting、@list-positions/crdts 和 list-positions-demos。

Going forward, I’d like to convert the demos into polished “bindings” for various rich-text editors, in the style of Yjs’s editor bindings. Let me know if you are interested in collaborating on this. I also welcome general questions or comments (preferably as issues).
接下来，我想将演示转换为各种富文本编辑器的精致“绑定”，类似于 Yjs 的编辑器绑定。如果您有兴趣合作，请告诉我。我也欢迎一般问题或评论（最好作为问题提交）。

Home • Matthew Weidner • PhD student at CMU CSD • mweidner037 [at] gmail.com • @MatthewWeidner3 • LinkedIn • GitHub
主页 • 马修·韦德纳 • 卡内基梅隆大学计算机科学与工程博士生 • mweidner037 [at] gmail.com • @MatthewWeidner3 • LinkedIn • GitHub