Keeping CALM: When distributed consistency is easy (2019)
arxiv.org
arxiv.org
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.
> 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-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).
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!
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.
If I had to say one person persuaded me it was Coda Hale.
He spoke eloquently and passionately about this research 15 years ago.
Examples on non-monotonic computation (i.e. that don't fit) include aggregations, in particular those that include time series with windows. The answer depends on what is in the window. So, if you take an average and only include a subset of the data in a window, the output will change when you add more data in the window. At least, that's how I interpret the monotonic requirement.
if you compartmentalize data in such a way, that most of your computations are done locally on a node (with the data that can fit a single node) - then you don't need global coordination.
for example, if you have two nodes: one in the US and one in the EU, and all customer data is stored in the corresponding geo region => you dont need global coordination. EU users and all their related computations can be perfectly done without coordinating with US node.
US node => serves US customers and all compute done locally. same logic applies to EU node, and Asia node.
for a subset of computations that require global consensus you can either broadcast shared data to regions, and do some sort of scatter/gather, map/reduce
but partitioning by geo is one of the many possible ways, there could be many other ways to partition your global working set in a way to minimize global coordination.
I call this "many small worlds" approach, where each small world can fit a single node and does not need global coordination.
Contrast it to "a single large world" - where you have a planet-scale globally distributed, replicated system with a consensus. You spend a lot of resources on duplication, and coordination, and end up wasting the 80% capabilities of this system by storing the data that could be perfectly served from a single cheap EC2 host.
even for computation that require global coordination, let's say you need to calc global AVG():
you can rewrite it in scatter/gather algorithm by splitting it into 1) TotalSum and 2) TotalCount
scatter this across node, compute locally, gather results (2 fields per node) and compute global average.
a lot of global consensus algos can be rewritten in scatter/gather manner to parallelize and offload work to nodes without global synchronization
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?
- looking at the larger system, you are preventing scale by creating interconnects between these services
- looking at the services themselves, it makes the logical boundary smaller, thus giving opportunity to find monotonicity more easily
How do others think of this?
Consistency between two accumulators is easy, they just sum their states.
for example as you said: global_sum() = accum1.sum() + accum2.sum()
global_min():
accum3 = [accum1.min(), accum2.min()]
global_min = accum3.min()
A better example would be reachability analysis in a DAG - here you really do have monotonicity failure when merging results from multiple workers.
for example global AVG can be expressed as SUM()/COUNT()
although AVG is not commutative, SUM() and COUNT() are commutative and can be run in scatter/gather mode and offloaded to individual nodes