算法与计算机科学archagon.net
为领域定制的 CRDT：无需服务器的协作
Show HN: Domain-tailored CRDTs for collaboration without server involvement
2018 — 2021，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
这是作者（archagon）对一种「领域定制 CRDT（Data Laced with History）」的研究与思考：他提出一类几乎可称为「元 CRDT」的通用结构，把协作能力直接内建在数据层，与网络架构彻底解耦，并顺带支持历史版本回看与增量补丁。作为概念验证，他做了一个 iOS 实时协同文本编辑器（在 iCloud 同步、CloudKit Sharing 和离线场景下都能工作），以及一个支持协同文本编辑与简单贝塞尔曲线编辑的 macOS mesh 网络模拟器，代码当时仅供学习。
为什么经久不衰：它把「数据即操作历史」这个分布式协作的核心洞见讲得既通俗又成体系，是理解 CRDT 与本地优先协作的经典入门文章，多年后仍被反复翻出。
HN 评论精选
iCloud 生态封闭且早期可靠性极差，是开发者不愿采用的实际原因。
作者疑惑为什么用 iCloud Sharing 的开发者这么少；我提醒一句：除了这个 API 本身意味着「我永远做不出能与它互操作的 Android 应用」（对多数开发者来说已经足够致命），iCloud 最初几个版本还烂到文档甚至整个客户端会卡进开发者无法替用户修复的死状态；有一年 WWDC 的开发者讲话上，苹果负责 iCloud 的人还上台为 iCloud 的糟糕道歉、求大家再给一次机会。
saurik查看英文原文
The author is wondering why iCloud Sharing is used by so few developers; I will point out / remind that, in addition to fundamentally being an API whose usage implies "I will never be able to build an Android app which interoperates with this data" (which is already pretty damning for most developers as a door they don't want to permanently close), the first few releases of iCloud were so bad that documents and even entire clients would end up in permanently wedged states that developers could not fix for users and were so bad that at WWDC one year I remember the Apple iCloud person on stage during the "developer state of the union" talk apologizing for iCloud being so broken and begging the audience for another chance.
无冲突编辑与自动合并的承诺之间存在根本矛盾。
「用户应当立刻能编辑文档，甚至不用碰网络」和「用户永远不该面对『请选择正确版本』的对话框」这两个目标无法调和。如果我们同步文档后又各自离线做出冲突修改，总得有人来消解冲突。
codetrotter查看英文原文
> Most obviously, users should be able to edit their documents immediately, without even touching the network [...] > The user should never be faced with a “pick the correct revision” dialog box. These two goals cannot be reconciled. If we both synchronize a document with content and then we both go offline and we make conflicting edits then someone will have to resolve the conflict.
Merkle DAG 天然擅长细粒度版本与缓存，但边界情况极难处理。
我和弟弟折腾过一个想法叫「Merkle DAG」。我们公司有一套很花哨的工作流/流程图设计器，问题永远是怎么把它做成协作式的（因为这在 PPT 上能大卖，不管用户是否真的会用）。另一个关注点是版本控制，而 Git 就是一个 Merkle DAG。我们最终没做完，因为遇到了一些非常难的问题，判定失败是最合理的结果。但也有很酷的地方：如果两个用户各自独立地用同样的两条线连了同样的两个流程步骤，系统会自然地把这两处改动理解为同一个；快照一致性也非常细粒度，推理起来极简单。另一个好处是 CAS（同样是 Git 的概念）对缓存极其友好。最终失败是因为我们某处搞错了，留下一堆边界情况。
zamalek查看英文原文
One idea me and my brother messed about with was "Merkel DAGs". The place we worked at had, what amounted to, a really fancy workflow/flowchart designer and the question was always how to make it collaborative (because that would sell like hotcakes on a slide deck, irrespective of whether people used it). Another concern was versioning, and Git is a Merkel DAG; great problems think alike. We never finished it because of some truly difficult questions, and decided that failure was the most reasonable result. There were some truly awesome things though. For example, if two users independently connected the same two flowchart steps with the same two lines, those two changes would be understood as identical by the system (by nature/emergence). It was also very granular snapshot consistency, which is incredibly simple to reason about. The other cool thing was that CAS (again, a Git concept) is absurdly cache friendly, and all forms of fancy stuff can be done there. We ultimately failed it because we had messed up somewhere and wound up with tons of borderline cases (and the hope was that we wouldn't need them). I still think, given the absence of our mistakes, it could work and would be really elegant code.
「操作即数据」与函数式编程、事件溯源一脉相承，是理解该系统哲学的关键。
精彩。作者的七条规则读起来很像一份函数式编程的宣言，尤其是「操作就是数据」这一条——这像是斩断分布式状态戈尔迪之结的一剑：数据不是往里面塞变更、再读出来的可变黑盒，数据就是构造它所用的那组操作。这也隐含着「一块数据就是它的因果历史」。有趣的部分在于，如何从「领土」（一个数据块上的所有操作）优化到「地图」（实现出来的数据视图）。
kortex查看英文原文
This is brilliant. One of the best things I've read in a while. I find it striking that the author's 7 rules (at about 3/4 of the scrollbar on desktop) read much like a manifest on functional programming. In particular: > The operations are the data. That strikes me as a sword to the Gordian Knot of distributed state. Data isn't some mutable black box you poke mutations into and prod and read. Data is the set of operations used to construct it. This feels to me like the principle underlying FP in general, event sourcing, reactor pattern, and of course these RDTs. Of course, this implies a chunk of Data is the causal history of the data (which in the physical world is strictly true). C'est ne pas un byte[]. The fun part comes in all the different ways to optimize going from the territory (all the operations on a data blob) to the map (the "realized" data blob, or view into the system). This also has flavors of quantum mechanics to me. Causality is anything you can get away with mutating before a meaningful observation occurs.
历次讨论
同类还值得读
位运算技巧集
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编辑精选