5 ms·
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 centr
by mjb 2y ago
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.
- sbazerque 2y ago> 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. Yeah, this framework seems powerful. Something I find interesting is that you can get monotonic (and therefore coordination-free) relaxations of arbitrary problems. In extremis, you can derive a relaxed version P' thus P'(S) = {<s, P(s)> | s ⊆ S} and now P'(S) ⊆ P'(T) if S ⊆ T for _any_ (well defined) P This seems tautological but in some cases a relaxed version is good enough: it gives you convergence and eventual consistency in a coordination-free setting, at the cost of maybe having to roll back some results. And when it doesn't, it gives you a coherent model of what to make of the situation until coordination yields a definitive answer. I wrote about this idea here: https://www.hyperhyperspace.org/report.html#conflict-resolution https://www.hyperhyperspace.org/report.html#conflict-resolut... But that was like last week, haven't really put this in practice yet. In those examples what is being processed are partially-ordered operational logs, but it's essentially the same (just that whenever S ⊆ T there, what you're seeing is an extension of an op log, which is a bit more intuitive).
- j-pb 2y agoThis boils down to materalizing every possible nondeterministic outcome. I wouldn't call anything that involves a power set with 2^n space complexity "relaxed" tbh ^^'. While I do agree with the general sentiment, I do still think that going with states that can be reconciled/merged is a more realistic approach, than just wildy diverging.
- User23 2y agoThis is a great submission. The logic for taming unbounded nondeterminism has been around for decades though. As Dijkstra and Scholten admit, it’s basically just applied lattice theory. In fact, at a glance, this paper appears to be building on that foundation. It’s not hard to see how monotonicity makes reasoning about nondeterminism considerably more manageable!
- sbazerque 2y agoDid you read the remark at the end of my comment? In the practical cases I was exploring, that combinatorial explosion does not happen. It's relaxed in the sense that it is coordination-free.
- j-pb 2y agoNot sure what you mean. I'm talking about the "relaxed" P' being defined via the power set of S. 2^S= {s | s ⊆ S} Now if all your P is only a mapping then P'(S) = {<s, P(s)> | s ∈ S} but then your "coordination free" P was monotonic anyways.
- benreesman 2y agoWe built the KV backend at FB on the back of the research at Cal around logical monotonicity. If I had to say one person persuaded me it was Coda Hale. He spoke eloquently and passionately about this research 15 years ago.
- parentheses 2y agoCare to share what he said or a video or something? Would love to hear it!
- benreesman 2y agoThe first time I saw Coda Hale speak in person was at this meetup that is amazingly still online: https://vimeo.com/21598799 https://vimeo.com/21598799
- mattgreenrocks 2y agoIs this a good paper for people new to distributed systems?