算法与计算机科学josephg.com
CRDT 是未来
CRDTs are the future
2020 — 2022，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
这是 Joseph Gentle（josephg）的博客文章，他在文中论证 CRDT（无冲突复制数据类型）在协同编辑等场景下优于长期主流的 OT（操作变换），并讨论了实现中的性能与设计取舍。作者本人写过多个 OT 协同编辑系统，后来又开发了自己的 CRDT 实现 Diamond Types。文章在 2020 和 2022 年两次登上 Hacker News 首页，评论区围绕 OT 与 CRDT 的实际取舍展开了不少讨论。
为什么经久不衰：它出自一位既做过 OT 系统、又亲手实现 CRDT 的工程师之手，把两种路线的工程取舍讲得具体而不过时，是理解协同编辑技术演进的一份长期有效的参考。
HN 评论精选
来自 Zoho Writer 团队的实践者认为，在有中心服务器的富文本编辑场景下，OT 仍然比 CRDT 更合适，CRDT 更适合数据库节点同步这类场景。
我是 Zoho Writer（Google Docs 的替代品）团队的成员。我们在 2010 年为实时同步编辑选择了 OT，十年后仍然坚持 OT，理由我之前说过。不过本着「没有完美方案，只有取舍」的精神，CRDT 在某些类型的同步中绝对必要，比如在多个数据库节点之间同步。但对于已经必须依赖中心服务器的系统（SaaS/云），尤其是富文本编辑这种复杂问题（语义树），我仍然认为 OT 的取舍比 CRDT 更好。我尊重 Joseph 关于 CRDT 是未来的信念，这个问题的答案大概很快就能见分晓。
lewisjoe查看英文原文
I'm part of the team that makes Zoho Writer (a Google Docs alternative) - https://writer.zoho.com We went with OT for our real-time syncing of edits in 2010 and a decade later, we are still sticking with OT for reasons I already stated sometime back - https://news.ycombinator.com/item?id=24186883 However, in the spirit of "There are no solutions, only trade-offs" CRDTs are absolutely necessary for certain type of syncing - like syncing a set of database nodes. But for systems which already mandate a central server (SaaS/Cloud) and especially for a complex problem like rich-text editing (i.e semantic trees) I still think OT provides better trade-offs than CRDT. I respect Joseph's conviction on CRDTs being the future, so I guess we'll figure this out sometime soon.
一位 Web 工程师自嘲被「够用就好」的实践惯坏，渴望掌握 CRDT 这类有理论保证的方案，感叹自己没有余力补上数学和分布式系统基础。
坦白说，我是个糟糕的软件工程师。我本希望在架构技术方案时能把 CRDT 这类东西纳入考虑范围，但我并没有做到。近十年来，我一直被「够用就好」的 Web 开发文化所麻痹，我觉得这一点会永远困扰我。我渴望采用有数学证明的方案，但我不仅已经十多年没碰过计算机科学（以及相关的数学），而且我连大学都没毕业。所以，我这个没受过足够教育、拿着高薪、只有高中同等学力文凭的 Rails 工程师，就在这里拼凑着我知道迟早会出问题的方案。说了这么多，我有没有希望把这类东西加入自己的工具箱？该从哪里开始？现在有生活了，脱产回学校读书基本不现实。网课？我很想听听那些有类似困境、或者能理解我在说什么的人的想法。知道自己的产出不够理想，却没有足够的知识去阻止这种情况反复发生，这真的很悲哀。这就是我给自己选定的职业吗？
corytheboyd查看英文原文
I'm going to come clean, I am a shitty software engineer. I'd like to have things like CRDTs under my radar to pull from when architecting technical solutions. But I don't. I have been coddled by the bullshit of "just-good-enough" web development for nearly a decade, and I feel like I will be haunted by it forever at this point. I WANT to employ mathematically proven solutions, but not only has it been 10+ years since studying computer science (and with it, the relevant mathematics) but I never even graduated. So here I am, another under-educated over-paid GED holding Rails engineer putting together shit solutions I know will eventually leak. So, having said all of that, is there hope for adding things like this to my toolbelt? And where do I even start? I feel like going back to school full-time is out of the question, because I have a life now. Maybe online classes? I'm curious to hear thoughts from people who maybe came from a similar pit of despair, or otherwise understand what I am talking about. It's just... sad to know enough that I produce less than optimal work but don't know enough to confidently prevent it from happening over and over and over again. Is this just the profession I have locked myself into?
整理了三个由浅入深的 CRDT 学习资源，并提醒 CRDT 不只是协同文本编辑，本身就是构建分布式系统的基本工具。
HN 上最近三次关于 CRDT 的讨论都值得一读。[1] 是很好的教程，不要求事先了解 CRDT 或其背后的数学，会同时讲形式化定义和实现，这对理解为什么让真实世界的 CRDT 灵活到能处理富文本编辑这么难很关键。[2] 是一场更深入讨论难点所在的演讲。[3] 更深入地比较了 OT 与 CRDT。值得一提的是，许多 CRDT 讨论都聚焦在协同文本编辑上，那是个非常难的问题；而 CRDT 作为一种构建分布式系统的有用原语，早就存在很久了。
lpage查看英文原文
The three most recent HN discussions on CRDTs are all worth perusing. [1] is an excellent tutorial that assumes no initial familiarity with CRDTs or the math that underpins them. It walks you through both the formalisms and the implementation, which is pretty key to understanding why making real-world CRDTs flexible enough to handle things like rich text editing is hard. [2] is a talk that goes more in-depth on the hard parts [3] goes deeper on OT vs. CRDT It's worth noting that many of the CRDT discussions focus on collaborative text editing. That's a really hard problem. CRDTs are (and have been for some time) a useful primitive for building distributed systems. [1] https://news.ycombinator.com/item?id=23737639 [2] https://news.ycombinator.com/item?id=23802208 [3] https://news.ycombinator.com/item?id=22039950
作者本人回顾：文章写后几年里他做了 Diamond Types，性能大幅提升并带动了 Yjs、Automerge 等实现的发展；他先专注文本编辑，是因为性能是通用 CRDT 的关键。
大家好！我是作者，很乐意回答问题。这篇文章写于几年前。此后我一直在做自己的 CRDT，叫 Diamond Types，它用了文中很多思路，速度快得惊人。我构建过好几个基于 OT 的协同编辑系统，Diamond Types 比其中任何一个都快得多，不过 Rust 和 WASM 可能才是真正的功臣。去年它跑通后我写了一篇后续，讲部分优化是怎么做的。写那篇文章以来变化不小：Yjs 开始用 Rust 重写（叫 yrs），Automerge 据说也根据文中的一些思路大幅提升了性能；Diamond Types 则彻底重写，通过完全改变内部结构，现在比去年快约 5 倍。不过这些改天再说。遗憾的是我目前仍然只支持协同文本编辑，完整的 JSON 支持会在记录更多技巧之后加上。为什么只支持文本编辑？因为我在乎性能，而文本 CRDT 难就难在改动数量太多，通常每按一次键就是一个改动。把文本编辑（以及一般的列表 CRDT）做快，能为通用 CRDT 打开很多设计思路。
josephg查看英文原文
Hi everyone! Author here. I'm happy to answer questions. I wrote this a couple years ago. Since then I've been working on my own CRDT called Diamond Types[1], which uses a lot of these ideas to be bonkers fast. I've built several OT based collaborative editing systems, and diamond types is much faster than any of them - though rust and wasm might be the real MVPs here. I wrote a follow-up to this article last year when I got that working, talking about how some of the optimizations work. That article is here[2]. A fair bit has changed since I wrote that article. Yjs has started a rewrite in rust (called yrs[3]). And Automerge has apparently dramatically improved performance based on some of the ideas I talk about in this article. Oh, and diamond types has been rewritten from the ground up. Its now about 5x faster than it was last year, by completely changing the internal structure. But thats a story for another day. Unfortunately I still only support collaborative text editing. Adding full JSON support comes soon, after I document some more of the tricks I'm doing. Its really fun work! Why do I only support collaborative text editing? Because I care about performance, and text CRDT performance is hard because you have so many individual changes - generally one for each keystroke! Making text editing (and list CRDTs in general) fast opens up a lot of other design approaches for a general purpose CRDT. But we've still got to do the work itself. To make that happen, my plan is to add full JSON editing support to diamond types using shelf[4]. Shelf is a super simple CRDT which fits in 100 lines of javascript. The next piece of work is marrying them together. [1] https://github.com/josephg/diamond-types/ [2] https://josephg.com/blog/crdts-go-brrr/ [3] https://github.com/y-crdt/y-crdt/tree/main/yrs [4] https://github.com/dglittle/shelf
历次讨论
同类还值得读
位运算技巧集
Bit Twiddling Hacks
斯坦福页面上的经典位运算技巧合集，收录了 popcount、前导/尾随零、位反转、交换、舍入等大量技巧，并附有解释和性能讨论。
算法与计算机科学上首页 8 次 · 2011–2024graphics.stanford.edu编辑精选如何不按平均评分排序
How Not To Sort By Average Rating
经典文章解释了为什么按平均评分排序不可靠：只有少量评价的条目（比如仅一条五星）会轻易排到最前，而评价数量的差异被忽略。
算法与计算机科学上首页 7 次 · 2009–2024evanmiller.org编辑精选数据结构可视化
Data Structure Visualizations
旧金山大学 David Galles 教授制作的数据结构与算法交互式可视化网站，涵盖 B 树、红黑树、排序、图算法等，可逐步操作观察其运行过程。
算法与计算机科学上首页 6 次 · 2011–2021cs.usfca.edu编辑精选1996 年以来的计算机科学最佳论文奖
Best Paper Awards in Computer Science since 1996
Jeff Huang 维护的一个汇总页面，收录了自 1996 年以来计算机科学各主要会议的“最佳论文奖”获奖名单，并按年份和会议整理，方便读者一站式浏览历届获奖论文。
算法与计算机科学上首页 6 次 · 2010–2018jeffhuang.com编辑精选算法（Jeff Erickson）
Algorithms, by Jeff Erickson
伊利诺伊大学 Jeff Erickson 教授的算法课教材，免费在线开放。
算法与计算机科学上首页 5 次 · 2018–2022jeffe.cs.illinois.edu编辑精选