Keeping CALM: when distributed consistency is easy

Keeping CALM: when distributed consistency is easy
blog.acolyer.org

> The second question is equally important:given a monotonic specification for a problem, how can I imple-ment it in practice?

Can anyone explain a good way to use these results?

The OP (acolyer.org) seems to suggest that this boils down to using CRDTs but that doesn't seem to be isn't really the answer but I can't figure out how to use/properly think about the results in this paper (as opposed to others that are a bit more practical). I've crawled through a bunch of paxos papers[0], and at this point it seems to that the distribution part of the problem is somewhat solved but the coordination required is what we're trying to attack now.

Whenever I see systems that use CRDTs it's usually either a K/V store or a concurrent editing application. Also, most articles will gloss over the fact that both types of CRDTs (cmRDTs and cvRDTS IIRC) are actually roughly equivalent (pure operation-based CRDTs[1]). IMO pure operation-based CRDTs are just distributed WAL by another name -- and if that's the case then we already have the solution for this (paxos-like quorum on the WAL segements).

All this boils down to the thought I've been holding lately that distributed consistency isn't hard in this day and age -- WAL (which you generally want for hard-disk-level consistency to start with, if you're not just waiting for big fsyncs) + synchronous commit (whether quorum or all nodes) is all you need to achieve a perfectly consistent distributed system, but what is hard is doing that with low latency and high throughput.

[0]: https://vadosware.io/post/paxosmon-gotta-concensus-them-all

[1]: https://www.researchgate.net/publication/320371248_Pure_Oper...

1) Increased availability

2) Ability to scale (better throughput)

3) Lower latency (get the data closer to the client)

As you said, WAL + Consensus solves the consistency problem in distributed systems. It does however go against all those desirable properties:

1) You lose availability when consensus cannot be reached

2) Throughput is decreased in the face of contention

3) Latency is worse because you need quorum between the separate locations

One way to go about this trade-off is to push for "raw power". Better networks, better clocks, etc.. This a commendable task and advances here should be celebrated, but there's a wall in the horizon: eventually we will hit actual physical limits (e.g.: speed of light doesn't let you lower latencies anymore). Google's spanner is probably close to those limits already. What can we do when this is not enough then?

The other approach is to work on reducing the need for coordination as much as possible. The paper fits in this realm. What it does is to identify a class of (sub)problem specifications that are solvable without coordination: monotonic specifications. It shows that CRDTs are monotonic, and I'm not sure whether any monotonic specification can be redefined as a CRDT (be it operational or state-based).

What CALM provides though is a "different way to think about the issue". If you can devise a monotonic specification of your problem, then you know that an implementation that provides consistent output without any coordination is possible. Furthermore, if your design is not monotonic, an implementation will require coordination or the output won't be consistent.

Finally, the paper dabbles in the realm of breaking your problem in monotonic and non-monotonic "pieces". The monotonic pieces you can implement without coordination. Non-monotonic pieces either require coordination OR "repair" (e.g.: send an e-mail to the customer apologizing that their item is actually unavailable and their order has been cancelled). Once a non-monotonic "piece" has been handled in this manner, the new piece that includes repair/coordination can be considered monotonic. Once all your system's pieces have gone through this process, you are guaranteed to have a "consistent" output.

An interesting analogy would be the "unsafe" blocks in rust. Rust in general is not safe because unsafe exists, but the fact that unsafe pieces are clearly identified makes it easier to reason about program safety as a whole. Similarly, the non-monotonic pieces of your system are where you risk losing consistency, whereas monotonic pieces are just not a problem (i.e.: you can get easily get good performance for those parts). By extension, if you can model your system so that all non-monotonic pieces are out of the critical path, your system is guaranteed to perform well in those scenarios!

All in all, this is just about giving better tools/thinking frameworks for system designers to minimize the use of coordination in a distributed system, which will invariably result in better performance without sacrificing output "consistency" (i.e.: without violating business rules).

Also, when using a system "with consensus" there is often no need to actually invoke consensus on the read side of the system, in which case you don't have to pay the throughput and latency penalties. I know you've sort of said this already, but it might be helpful to mention explicitly.