系统与数据库2016arxiv.org编辑精选
一种无冲突复制的 JSON 数据类型
A Conflict-Free Replicated JSON Datatype
进阶 · 约 60 分钟读完前置知识：分布式系统基础、CRDT/最终一致性、JSON 数据结构
导读
这篇论文提出一种用于 JSON 文档的无冲突复制数据类型（CRDT），让多个用户或设备可以离线并发修改同一 JSON 结构，并在同步时自动合并而不丢失更新。论文给出算法与最终一致性等形式化保证，并讨论合并语义、墓碑垃圾回收等问题；作者还用基于该 CRDT 的实验性协同文本编辑器撰写了论文的 LaTeX 源文件。
HN 关注点：CRDT 在协同编辑与离线同步中的可落地性：合并结果是否反直觉、墓碑回收如何做，以及 CRDT 与 OT、P2P 方案之间的取舍。
后来怎么样
为 JSON 文档的 CRDT 合并提供了后续实现广泛参考的算法基础，并直接催生了 Automerge 等项目，推动了本地优先协作软件的发展。
HN 评论精选
这几条评论里：质疑 2 补充 1 亲历 1
质疑批评合并可能产生应用层意外甚至无效的结构，并指出墓碑回收和字符串编辑实现仍是落地关键。
我们“不因并发修改丢失输入”的原则看似合理，但如图 4 所示，它会导致合并后的文档状态让更熟悉顺序程序的应用程序员感到意外。这个决定对我来说有点奇怪：他们不仅展示了合并系统能产生应用程序认为无效的数据，甚至能在没有任何显式创建列表的操作下把字符串转换成列表。此外，为了防止数据结构无界增长，需要进行垃圾回收（删除墓碑）。这一直是 CRDT 系统痛苦的部分；在这部分完成之前，它还不能真正用于生产。尽管如此，之前 CRDT 的工作让我相信它可以以最小开销实现。字符串编辑在论文中被一带而过。我很想看看他们的实现，有人知道它在哪里吗？
espadrine查看英文原文
> Our principle of not losing input due to concurrent modifications appears reasonable, but as illustrated in Figure 4, it leads to merged document states that may be surprising to application programmers who are more familiar with sequential programs. That decision is a bit odd to me. Not only do they show that their merge system can produce data that the application considers invalid, it can even convert a string to a list without having any operation creating a list explicitly. > Moreover, garbage collection (tombstone removal) is required in order to prevent unbounded growth of the datastructure That is always the painful part of a CRDT system. Until that part is done, it cannot really be used in production. That said, previous work on CRDTs give me confidence that it can be implemented with minimal overhead. > In fact, we wrote the LATEX source text of this paper using an experimental collaborative text editor that is based on our implementation of this CRDT. We are making the character-by-character editing trace of this document available as supplemental data of this paper String editing is brushed over in the paper. I'd love to see their implementation. Does anyone know where it all is?
亲历分享自建 JSON CRDT 的经验：递归和 JSON 的灵活性可能没必要，单层追加集合更实用。
我在自己的内容寻址系统项目中开发了一个“通用”的基于 JSON 的 CRDT。想法是有一个“只追加树”，其中子树可被各个应用用于不同目的，例如计数器或可变集合。事后看，它不需要支持递归；单层的只追加集合就足够通用，也更容易建立索引。使用 JSON 也过头了，因为过多灵活性对内容寻址不利。
btrask查看英文原文
I developed a "general purpose" JSON-based CRDT[1] as a part of my content addressing system project. The idea was to have an "append-only tree", where subtrees could be used by individual applications for different purposes, for example as counters or mutable sets. In retrospect, it didn't need to support recursion. A single-level append-only set is enough to be fully general and easier to perform indexing on. Using JSON was also overkill, since too much flexibility is bad for content-addressing. [1] https://github.com/btrask/stronglink/blob/master/client/README.md#meta-files
质疑质疑 CRDT 无法理解协作意图、可能产生一致但错误的数据，并指出离线冲突和前端全量缓存的代价。
不可能有完全准确的 conflict-free replicated data。除非让用户手动解决冲突，否则永远不会 100% 准确——错误数据会不时混入（但至少错误数据在各节点上是一致的）。根源在于系统无法理解并发用户的协作意图：如果两个用户同时做了修改且不知道彼此，就必须考虑 UserB 若知道 UserA 的输入可能会做出不同行为；用户离线一段时间后可能积累很多冲突，让用户逐个手动解决很繁琐。此外这种方法往往迫使前端缓存该登录用户整个应用的所有数据，大应用会占很多内存。有些情况下最好的方案是直接告诉用户“当前离线，不能修改此数据”，而不是给他们数据已正确备份到云端的错觉。我认为用 CRDT 时，很重要的一点是告知用户……
jondubois查看英文原文
It is impossible to have accurate conflict-free replicated data. Unless the users are given the opportunity to manually resolve conflicts, it will never be 100% accurate - Incorrect data will creep in from time to time (but at least the incorrect data will be consistent across all nodes). The root of the problem is that the system cannot understand the collaborative intent of concurrent users - If you have 2 users who made a change at the same time (without being aware of each other); you have to account for the fact that maybe UserB would have behaved differently if they had been aware of UserA's input (which happened at the same time while one or both users were offline). If the user has been offline for a while - Many such conflicts could arise (maybe by the time the internet comes back on, the user is looking at a completely different page than the one they made the change on) and it's tedious to make the user resolve them all manually. Also with this approach, it tends to force you to keep a copy/cache of all the data in your entire app (for that logged-in user) on the frontend - If you have a big app with lots of pages, that could consume a lot of memory. There are cases where the best solution is to simply tell the user "Sorry, you do not have an internet connection at the moment, so you cannot modify this data" rather than giving them a false sense that the data are correctly backed up in the cloud. I think with CRDTs, it's really important to inform the user when they are offline and when their data are not synced/backed up in the cloud (so they don't get any bad surprises when the internet suddenly comes back on). CRDTs are good where the accuracy of the data is not critical (E.g. bank transactions). One could argue that they improve the user experience, but at the core, developers like them because they make life easier.
补充GUN 作者补充：论文算法是去中心化/P2P 的，OT 不是；并称 P2P CRDT 上做富文本协同编辑可行。
我是一个可存储 JSON 的 CRDT 数据库作者。这里是 Kyle Kingsbury（Aphyr）对它的看法：https://twitter.com/aphyr/status/646302398575587332 。针对这里关于 OT 的评论，大家应该知道 OT 不是 P2P 或去中心化的；而论文中的算法是，GUN（https://github.com/amark/gun）也是。对讨论可能更重要的是，在 P2P CRDT 系统之上实现协同富文本编辑是可能的。虽然我还没听说有现成的，但我正在做一个使用链表 DAG 的，早期演示：https://www.youtube.com/watch?v=rci89p0o2wQ 。
marknadal查看英文原文
I am the author of a CRDT database that can store JSON. Here are Kyle Kingsbury's (Aphyr) thoughts on it: https://twitter.com/aphyr/status/646302398575587332 . In response to the OT comments here in the thread, people should be aware that OT is not P2P or decentralized. The algorithm in the paper is, however, and so is GUN (https://github.com/amark/gun) . Probably more important to the discussion, is that it IS possible to implement collaborative rich text editing on top of P2P CRDT systems. Although I do not know of any yet, I am working towards one which uses a linked-list DAG, early demo: https://www.youtube.com/watch?v=rci89p0o2wQ .
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
历次讨论
- 2016Hacker News 讨论帖132 分 · 59 评
同领域还值得读
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 分钟编辑精选