网络与分布式2024arxiv.org
Keeping CALM：何时分布式一致性变得容易
Keeping CALM: When distributed consistency is easy (2019)
进阶 · 约 90 分钟读完前置知识：分布式一致性基础、数据库事务与隔离级别、单调逻辑基础
导读
这篇论文（CALM 定理）研究分布式系统中一个核心问题：什么样的计算可以不需要协调（coordination）就能保证一致性。核心结论是：一个程序拥有无协调的一致性分布式实现，当且仅当它是单调的——即输入越多，输出集合只会增长而不会收缩。这为设计可扩展、容错的分布式系统提供了理论边界和实用判据。
HN 关注点：是因为可扩展性的关键在于避免协调，而 CALM 定理给出了判断何时必须协调、何时可以免协调的理论工具，直接关系到分布式系统设计的根本权衡。
HN 评论精选
这几条评论里：支持 1 质疑 2 补充 1
支持认为这是十年来最重要的分布式系统工作，单调性给出了免协调设计的实用判据
我非常喜欢这项工作，可以说它是过去十年最重要的分布式系统研究之一。它回答了分布式（和多线程）系统设计的核心问题：什么时候需要在系统之间协调？正如 James Hamilton 所说，成功的扩展性要求避免协调；可扩展、高效的系统就是把协调降到其保证所必需的最低程度的系统。单调程序的定义对大多数程序员都很好理解：在输入子集上运行得到输出的子集，数据越多，为真的事实只会增长、永不收缩。由此得到实用路线图：程序拥有一致且免协调的分布式实现，当且仅当它是单调的。
mjb查看英文原文
I love this work. I might claim it (and some of its antecedents) is the most important distributed systems work of the last decade. Why? It addresses the central question in distributed (and multi-threaded!) system design: when do we need to coordinate between systems? This is important for exactly the reason that the James Hamilton quote says. Successful scalability requires avoiding coordination. Scalable systems (and efficient systems, and fast systems) are the ones that minimize scalability to the level absolutely required by the guarantees they want to offer. As the authors say: > As system builders, of course, we are interested in the complement of this space: what can be achieved, and, importantly, how can we achieve it while minimizing complexity and cost? The CALM Theorem presents a positive result that delineates the frontier of the possible. This tool for thinking about what possible systems we can build is one that's very understandable to most programmers: > A program P is monotonic if for any input sets S,T where S ⊆ T, P(S) ⊆ P(T). A program is monotonic if, when you run it on a subset of its inputs, you get a subset of its outputs. As you run it on more data, the set of true things may grow, but it never shrinks. > A program has a consistent, coordination-free distributed implementation if and only if it is monotonic. Now we have a useful roadmap to designing scalable distributed system, fault tolerant distributed systems, scalable parallel compute code, and fast multi-threaded code. Using the definition we can identify whether a program is monotonic, and if it is we know we can implement it without coordination. If it is not, we can decompose a program into monotonic and non-monotonic parts, and (if all goes well) take advantage of the non-monotonicity. In many cases, we can do tons of parallel work and only coordinate a couple times. > Conflict-free replicated data types (CRDTs) provide an object- oriented framework for monotonic programming More conceptual clarity! CRDTs are widely used, and widely talked about. Why do they work? Because they provide ADTs for writing monotonic programs.
补充用 groupby 这个具体例子来检验单调性概念
为了让讨论不那么抽象：groupby 操作是单调的吗？
MeteorMarc查看英文原文
Just to make this discussion less abstract: is a groupby operation monotonic?
质疑补充资料并质疑该理论的实际影响力
这是 2019 年初的论文。CACM 在 2020 年也发过一篇很长的相关博客（附链接）。我记得它发表时引起过一点关注，但之后就没再听说了。有人知道它现在是否被实际使用，还是已被其他方法取代？
Groxx查看英文原文
early 2019 fwiw. CACM has a (large) 2020 blog post about it too: https://cacm.acm.org/research/keeping-calm/ I remember seeing a blip of this when it came out, but I haven't heard anything since. Anyone know if it's known / used / ??, or has it been subsumed by some other thing?
质疑质疑 CALM 只适用于集合操作，并提出可分解为偏序的推广猜想
这是几位知名数据库专家得出的漂亮结果。不过，满足 CALM 性质的实用程序似乎只有数据库系统中的集合类操作，表达力不足以覆盖所有计算。那么问题来了：是否所有计算都可以分解为一个 CALM 程序的偏序，只在序的边界处需要协调？如果是，这是否类似于 Lamport 在 Generalized Consensus 中的 CStructs？
mehulashah查看英文原文
This is a cool result from a couple of famous database experts. Though, it seems that the only set of practical programs that satisfy the CALM property are set-based operations found in database systems. These are expressive, but not expressive enough to cover all possible computations. So, is it the case that all computations can be decomposed into a partial order of CALM programs each of which don’t need coordination except at the points of order. If so, is this approach analogous to Lamport’s CStructs in Generalized Consensus?
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
- 视频与演讲
历次讨论
- 2024Hacker News 讨论帖139 分 · 27 评
同领域还值得读
Paxos vs. Raft：分布式共识是否已达成共识？
Paxos vs. Raft: Have we reached consensus on distributed consensus?
重新审视了 Paxos 与 Raft 两种分布式共识算法之间的差异，试图在一个统一的框架下比较它们，并论证二者的相似程度远高于通常的认知，许多所谓的差别只是表述层面的。
网络与分布式2020 · 343 分 · 65 评 · 引用 10进阶 · 约 28 分钟编辑精选Stellar 协议：互联网级共识的联邦模型
Stellar Protocol: A Federated Model for Internet-Level Consensus (2016)
提出 Stellar Consensus Protocol（SCP），一种面向互联网级共识的联邦拜占庭协议模型。
网络与分布式2018 · 301 分 · 61 评专业 · 约 90 分钟编辑精选拜占庭将军问题（1982）
The Byzantine Generals Problem (1982)
这篇 1982 年论文提出并形式化了拜占庭将军问题：在分布式系统中，部分节点可能叛变或故障、通信不可完全信任时，忠诚节点如何达成一致行动。
网络与分布式2018 · 290 分 · 77 评进阶 · 约 75 分钟编辑精选Google 变差了吗？对搜索引擎中 SEO 垃圾的纵向调查
Is Google Getting Worse? A Longitudinal Investigation of SEO Spam in Search
对搜索引擎结果中的 SEO 垃圾内容做了纵向追踪：作者团队在一段时间内持续采集 Google、Bing、DuckDuckGo 等引擎针对商品评测类查询的结果，用分类器识别联盟营销…
网络与分布式2024 · 276 分 · 274 评入门 · 约 45 分钟编辑精选使 CRDT 能够容忍拜占庭故障
Making CRDTs Byzantine Fault Tolerant
Martin Kleppmann 等人的论文研究如何让 CRDT（无冲突复制数据类型）抵御拜占庭故障节点，即部分参与者恶意篡改数据时仍能保证一致性。
网络与分布式2022 · 266 分 · 40 评进阶 · 约 90 分钟编辑精选