5 ms·

Keeping Calm: When Distributed Consistency Is Easy

83 points by kiyanwang 6y ago

maxeonyx 6y ago
This is an extremely important result, which I have seen around before. What are the implications and follow-up research?
rektide 6y ago
I continue to want to dabble here-abouts, since at least the time of having seen "Anna: A Crazy Fast, Super-Scalable, Flexibly Consistent KVS"[1], which is now one[2] of the two major components of the Hydro project, alongside Cloudburst[3], a Python "stateful serverless platform". There's also some other pieces like a local Anna-cache[4] & a coordinated retry library, & kubernetes-centric cluster-manager. I have no idea how related the Hydro-Project work is to this recent publication on Calm, but I hope to find out! [1] https://rise.cs.berkeley.edu/blog/anna-kvs/ https://rise.cs.berkeley.edu/blog/anna-kvs/ [2] https://github.com/hydro-project/anna https://github.com/hydro-project/anna [3] https://github.com/hydro-project/cloudburst https://github.com/hydro-project/cloudburst [4] https://github.com/hydro-project/anna-cache https://github.com/hydro-project/anna-cache
- tjungblut 6y ago
  I think this is highly misleading. They state that they achieved high speed-ups from not doing any coordination because they encode each state as a "private field" in an actor. Actors then communicate via queues (assume ZeroMQ from their reference), which require coordination to scale at some point - so do the actors that contain the actual data. I do see some market for (eventual/in)-consistent databases though, so maybe that's something we are going to see much more often in the future.
doonesbury 6y ago
I've read this paper a couple of times without having learned everything. The modeling language Bloom looks to have died on the vine. It's a datalog descendant. Bloom is supposed to help tell one if their distributed system is calm compliant
bullen 6y ago
I made my own distributed database on top of my own HTTP app. server and I learned 2 things: 1) CRDTs and Paxos like protocols don't make any sense. Just send all data everywhere with both server and client async. transport and sync. "done" latch and your reads will load balance, you'll get 100% read uptime and "free" backup. That's about it. 2) Java can do joint (on shared memory) parallel stuff really well because of the VM GC and assembly cannot reclaim shared concurrent memory easily without those! Here is my implementation proved with a MMO with 250.000 players: http://root.rupy.se http://root.rupy.se Please comment if you down vote.
- alexisread 6y ago
  You're essentially describing a two-phase commit ie. commit the data to each node, and then to the whole cluster (or discard the transaction if not on every node). This is fine for some distributed tasks, but you have to wait for the whole cluster before you can use the committed data - not fast compared to single-phase commits with eventual consistency. This is what CRDTs, Paxos and CALM are trying to solve, a single phase commit where each node can then work out the order of transactions themselves, in order to reach an identical state to the next node. In your MMO case, it looks like an ideal problem for 2-phase commits to solve :) There's also a related problem, where the volume of data you're sending is such that you can't replicate it across the whole cluster, only some of it. You then have to a) sort out the redundancy of the data, and b) the consistency of the data bearing in mind that a node may have data reliant on data from another node. Many of these issues are somewhat related to GC, distributed hash (merkle) trees, CRDTs and actors operating on data (rather than the other way round). It's a rich problem area with many coordination applications for the good solutions!
  - bullen 6y ago
    You don't need speed when your transport is completely non-blocking async. end-to-end because your CPUs are not IO-waiting on anything. This scales way better and the time it takes to distribute over my global cluster is very little above the latency between the furthest nodes (~200ms). What user case do they have for a distributed system that is faster than 200ms for global persistent data? 200ms for a registration or purchase is not huge? You can obviously use the data before the transaction is complete anyway?! I think Java is going to have a very strong revival on the server side once the Google lawsuit is over. I cannot explain the performance I'm getting yet but I'm working on that: https://github.com/tinspin/rupy/wiki https://github.com/tinspin/rupy/wiki (Under "Why Rupy is using Java")
peterwwillis 6y ago
Another way to think of a distributed system is as a threaded application on a multi-core CPU. Break down the interactions within the application by all the logical boundaries and you have a basic distributed system. Typically the input and output are via a single controlled mechanism and state is handled in a single place in memory during the series of events for a particular operation, so consistency is just assumed. But give all the series of events their own state, and each event a different input and output in random ordering, and you have distributed system problems. Threaded apps have similar problems to solve and have their own mechanisms to deal with these problems, so you can compare them and see how multiple mechanisms may be needed to compute safely.
- maxeonyx 6y ago
  You're right, it's the same synchronisation/consistency problem at a different scale, which I honestly find pretty mindblowing. However there is one major difference. When you add fault tolerance requirements (which you typically do in distributed databases and web applications, but don't always in multithreaded applications) then it changes the approaches and algorithms.
eigenrick 6y ago
I know work is ongoing in the CRDT space (Kleppman's work gets posted here regularly). I'm assuming Hellerstein et al. are continuing work on distributed consistency, but "what and where" is not immediately obvious . Bloom/bud is being maintained, but that seems to be about it. It seems like event-sourcing draws a tiny bit from this well, but it could be much more powerful with some help from CALM or similar. Can anyone point to any other areas of active research and development in the area of reducing conflict in distributed systems?

83 points by kiyanwang 6y ago

This is an extremely important result, which I have seen around before. What are the implications and follow-up research?

rektide 6y ago

I continue to want to dabble here-abouts, since at least the time of having seen "Anna: A Crazy Fast, Super-Scalable, Flexibly Consistent KVS"[1], which is now one[2] of the two major components of the Hydro project, alongside Cloudburst[3], a Python "stateful serverless platform". There's also some other pieces like a local Anna-cache[4] & a coordinated retry library, & kubernetes-centric cluster-manager. I have no idea how related the Hydro-Project work is to this recent publication on Calm, but I hope to find out! [1] https://rise.cs.berkeley.edu/blog/anna-kvs/ https://rise.cs.berkeley.edu/blog/anna-kvs/ [2] https://github.com/hydro-project/anna https://github.com/hydro-project/anna [3] https://github.com/hydro-project/cloudburst https://github.com/hydro-project/cloudburst [4] https://github.com/hydro-project/anna-cache https://github.com/hydro-project/anna-cache

tjungblut 6y ago
I think this is highly misleading. They state that they achieved high speed-ups from not doing any coordination because they encode each state as a "private field" in an actor. Actors then communicate via queues (assume ZeroMQ from their reference), which require coordination to scale at some point - so do the actors that contain the actual data. I do see some market for (eventual/in)-consistent databases though, so maybe that's something we are going to see much more often in the future.

doonesbury 6y ago

I've read this paper a couple of times without having learned everything. The modeling language Bloom looks to have died on the vine. It's a datalog descendant. Bloom is supposed to help tell one if their distributed system is calm compliant

bullen 6y ago

I made my own distributed database on top of my own HTTP app. server and I learned 2 things: 1) CRDTs and Paxos like protocols don't make any sense. Just send all data everywhere with both server and client async. transport and sync. "done" latch and your reads will load balance, you'll get 100% read uptime and "free" backup. That's about it. 2) Java can do joint (on shared memory) parallel stuff really well because of the VM GC and assembly cannot reclaim shared concurrent memory easily without those! Here is my implementation proved with a MMO with 250.000 players: http://root.rupy.se http://root.rupy.se Please comment if you down vote.

alexisread 6y ago
You're essentially describing a two-phase commit ie. commit the data to each node, and then to the whole cluster (or discard the transaction if not on every node). This is fine for some distributed tasks, but you have to wait for the whole cluster before you can use the committed data - not fast compared to single-phase commits with eventual consistency. This is what CRDTs, Paxos and CALM are trying to solve, a single phase commit where each node can then work out the order of transactions themselves, in order to reach an identical state to the next node. In your MMO case, it looks like an ideal problem for 2-phase commits to solve :) There's also a related problem, where the volume of data you're sending is such that you can't replicate it across the whole cluster, only some of it. You then have to a) sort out the redundancy of the data, and b) the consistency of the data bearing in mind that a node may have data reliant on data from another node. Many of these issues are somewhat related to GC, distributed hash (merkle) trees, CRDTs and actors operating on data (rather than the other way round). It's a rich problem area with many coordination applications for the good solutions!
- bullen 6y ago
  You don't need speed when your transport is completely non-blocking async. end-to-end because your CPUs are not IO-waiting on anything. This scales way better and the time it takes to distribute over my global cluster is very little above the latency between the furthest nodes (~200ms). What user case do they have for a distributed system that is faster than 200ms for global persistent data? 200ms for a registration or purchase is not huge? You can obviously use the data before the transaction is complete anyway?! I think Java is going to have a very strong revival on the server side once the Google lawsuit is over. I cannot explain the performance I'm getting yet but I'm working on that: https://github.com/tinspin/rupy/wiki https://github.com/tinspin/rupy/wiki (Under "Why Rupy is using Java")

peterwwillis 6y ago

Another way to think of a distributed system is as a threaded application on a multi-core CPU. Break down the interactions within the application by all the logical boundaries and you have a basic distributed system. Typically the input and output are via a single controlled mechanism and state is handled in a single place in memory during the series of events for a particular operation, so consistency is just assumed. But give all the series of events their own state, and each event a different input and output in random ordering, and you have distributed system problems. Threaded apps have similar problems to solve and have their own mechanisms to deal with these problems, so you can compare them and see how multiple mechanisms may be needed to compute safely.

maxeonyx 6y ago
You're right, it's the same synchronisation/consistency problem at a different scale, which I honestly find pretty mindblowing. However there is one major difference. When you add fault tolerance requirements (which you typically do in distributed databases and web applications, but don't always in multithreaded applications) then it changes the approaches and algorithms.

eigenrick 6y ago

I know work is ongoing in the CRDT space (Kleppman's work gets posted here regularly). I'm assuming Hellerstein et al. are continuing work on distributed consistency, but "what and where" is not immediately obvious . Bloom/bud is being maintained, but that seems to be about it. It seems like event-sourcing draws a tiny bit from this well, but it could be much more powerful with some help from CALM or similar. Can anyone point to any other areas of active research and development in the area of reducing conflict in distributed systems?