系统与数据库2024arxiv.org
使用 Eg-Walker 的协同文本编辑：更好、更快、更小
Collaborative text editing with Eg-Walker: Better, faster, smaller
进阶 · 约 50 分钟读完前置知识：OT 与 CRDT 基础、文本编辑数据结构、分布式一致性
导读
这篇论文提出 Eg-Walker，一种协作文本编辑算法，试图兼取 OT（操作转换）与 CRDT 两类方案的长处：操作不可变、仅追加，从而更便于与生产数据库集成。标题声称它在性能、速度和空间占用上都更优；作者 Joseph Gentle（Seph）另提供了 TypeScript 参考实现。
HN 关注点：是否能解决协作文本/序列 CRDT 长期难以落地到生产数据库的问题，以及它与 OT、Yjs、DiamondTypes 等现有方案的比较。
HN 评论精选
这几条评论里：质疑 1 补充 1 亲历 1
亲历核心瓶颈是与生产数据库集成，而 Eg-walker 的不可变追加式操作可能更适合嵌入数据库
作者 Seph 还有一个 TypeScript 参考实现（链接）。我之前就说过，阻碍协作文本/序列 CRDT 落地的主要问题是与生产数据库的集成。Eg-walker 有意思的地方在于它可能容易集成进数据库，因为操作是不可变的、只追加的。但要证明这些算法的有效性，库作者（如 Yjs、DiamondTypes）往往自己造独立数据结构（通常是专门的搜索树），而很多数据库本就提供这类结构。我个人一直在尝试把 Piece Table 改造成可协作的，并存入 Triplit（它同时跑在客户端和服务端，且已实现逻辑时钟），不过我也可能转而试试这个算法。
matlin查看英文原文
Seph (author) also has a reference implementation in Typescript: https://github.com/josephg/eg-walker-reference I've stated before that I think the main thing holding back collaborative text / sequence CRDTs is integration with a production database. Eg-walker looks interesting because it might lend itself to be integrated into a database because the operations are immutable and only appended. However, to demonstrate the effectiveness of these algorithms library authors (see Yjs, DiamondTypes, etc) build stand-alone data structures (usually specialized search trees) that most databases already provide. Personally, I've been trying to adapt a Piece Table[1] to be collaborative and stored in Triplit[2] which runs on both client and server and already implements logical clocks but I might see how well I can adapt this algorithm instead! 1. https://en.wikipedia.org/wiki/Piece_table 2. https://github.com/aspen-cloud/triplit
补充补充了作者的视频讲解，并评价其融合了 OT 与 CRDT 的优点
Joseph 也在 YouTube 上讲解了这个算法（链接）。这是很棒的工作，结合了 OT 和 CRDT 各自的优点。
britannio查看英文原文
Joseph explains the algorithm on YouTube too: https://www.youtube.com/watch?v=rjbEG7COj7o It's great work, combining the best of OT and CRDTs.
质疑追问该算法是否适用于协作白板/图片类场景
像协作白板这类软件用的是同样的算法吗？还是说图片协作有更合适的算法？
abdullahkhalids查看英文原文
Do collaborative whiteboard like software use the same algorithms, or are there more suitable algorithms for picture collaborations?
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2024Hacker News 讨论帖251 分 · 31 评
同领域还值得读
I/O 比 CPU 更快——让我们划分资源并消除操作系统抽象
I/O Is Faster Than CPU – Let’s Partition Resources and Eliminate OS Abstractions
指出在现代服务器硬件上 I/O 速度已接近甚至超过 CPU，传统操作系统抽象反而成为瓶颈。
系统与数据库2019 · 817 分 · 277 评进阶 · 约 30 分钟编辑精选使用 io_uring 的高效 I/O
Efficient IO with io_uring
由 Linux 内核开发者 Jens Axboe 撰写，介绍 Linux 新的异步 I/O 接口 io_uring。
系统与数据库2019 · 426 分 · 96 评进阶 · 约 45 分钟编辑精选线程对大多数用途而言是个坏主意（1995）
Threads Are a Bad Idea for Most Purposes (1995)
这篇 1995 年的文章由 John Ousterhout 撰写，讨论为什么线程对大多数用途而言是坏主意，并主张事件驱动编程通常更简单、更高效。
系统与数据库2017 · 423 分 · 382 评进阶 · 约 25 分钟编辑精选学习型索引结构之论证
The Case for Learned Index Structures
提出把索引看作一种"模型"：既然 B-tree 等结构本质上是在学习数据的分布，就可以用机器学习模型（如回归模型、神经网络）来近似键到位置的映射，从而替代 B-tree、哈希索引…
系统与数据库2017 · 398 分 · 66 评 · 引用 25进阶 · 约 60 分钟编辑精选FoundationDB：一个分布式、解耦的事务型键值存储
FoundationDB: A distributed, unbundled, transactional key value store
介绍 FoundationDB：一个分布式、解耦设计的事务性键值存储。
系统与数据库2021 · 283 分 · 99 评进阶 · 约 90 分钟编辑精选