State machine replication, and why you should care

State machine replication, and why you should care(signalsandthreads.com)

166 points by yminsky 4 years ago | 19 comments

crdrost 4 years ago |

There's a whole database, Datomic, that works roughly this way -- not the UDP multicast but the idea of having a slightly more nuanced consistency/availability/partition tolerance tradeoff by having a thin transaction organizer which is not partition tolerant and officially states which one came first and second, upstream of the replicas that grant normal availability.

I would have liked the discussion about Raft/Paxos that they said they'd leave out of this episode though :(

refset 4 years ago | |

CORFU and Tango are interesting research implementations in this general area, with emphasis on a dedicated "sequencer" - see https://rebeccabilbro.github.io/the-shared-log-abstraction/

Facebook's LogDevice had a similar sequencer component too https://engineering.fb.com/2017/08/31/core-data/logdevice-a-...

jasonwatkinspdx 4 years ago | | |

Yeah, and the key idea here is that the sequencer is soft state that can be recovered from the log at any time. It acts to improve throughput while it's up, but if it's down the system can still make progress. The key to this is that the log is the ultimate ground source of truth, and individual entries in the log are write once. This means racing writers can detect and work around each other in the absence of a sequencer, via the hole filling protocol.

bitbckt 4 years ago | | |

FaunaDB (fauna.com) is a commercial system based on Calvin.

Disclosure: I work on FaunaDB.

michael_j_ward 4 years ago | |

Sounds similar to xtdb

https://github.com/xtdb/xtdb

tekacs 4 years ago | | |

Yeah as I understand it XTDB was built by Juxt after using Datomic for a long while, to make a different set of trade-off choices.

Whenever one comes up, the other is likely to be mentioned close at hand:

https://docs.xtdb.com/resources/faq/#comparisons

runevault 4 years ago | |

What's the state of Datomic these days? I stopped keeping up with it a while back when I stopped really paying attention to the Clojure space in general. Last I remember hearing it was still a purely pay to use their instances sort of deal.

capableweb 4 years ago | | |

> What's the state of Datomic these days?

Continuous, minor improvements over time (just like Clojure). Nothing too groundbreaking lately AFAIK, but still worthy to use if you have the use cases for it. Changelog can be found here: https://docs.datomic.com/on-prem/changes.html

fulafel 4 years ago | | |

There's on-prem which is the original model, and then the newer Datomic Cloud (came about in ~2018) which is installed from AWS Marketplace and billed through AWS. There are some feature differences between them. With on-prem there are free and $$ licensing options. Might be that the on-prem gratis licensing options were more limited before.

Some of the cool kids in Clojure world seem to have moved over to XTDB these days.

simonpure 4 years ago |

If you're interested in this topic, I highly suggest some of the talks and papers about the LMAX Disruptor [0] and Martin Thompson's latest project Aeron [1]. It targets the JVM, but the lessons are generally applicable since I don't think Concord/Aria are open source.

[0] https://lmax-exchange.github.io/disruptor/ [1] https://github.com/real-logic/aeron

bob1029 4 years ago | |

The LMAX disruptor (and the principles behind it) are quite amazing.

We are using it right now as the foundation for a new business administration platform.

It's even more ridiculous in .NET due to enhancements relative to value types:

https://medium.com/@ocoanet/improving-net-disruptor-performa...

In .NET6, this is potentially one of the fastest ways to serialize an arbitrary # of threads.

spacemanmatt 4 years ago | |

As a Vert.x fanatic, LMAX Disruptor is one of the few technologies for JVM that makes my jaw drop. So cool.

gumby 4 years ago |

This is somewhat interesting but note they start by saying they use the word "state machine" not in fact to refer to a state machine, but rather something more like a closure or class instance (they weren't really clear).

samsin 4 years ago |

Blockchain is also an example of SMR with less assumptions: ip addresses and public keys unknown upfront (permissionless), asynchronous model, and byzantine actors.

brian_cloutier 4 years ago | |

Someday it might even become the canonical example, SMR is the only thing blockchain is!

The Bitcoin blockchain is just a list of transactions, the hard part is getting everybody to agree on which transactions happened and which order they happened in. Once that happens everybody can run all the transactions in order to figure out what the current state is. The bitcoin state is mostly implicit. In order to figure out the current set of balances you have to run every transaction.

lbhdc 4 years ago |

This was an interesting episode. However, I thought this pattern was called actors. Did anyone else get that sense? I have never heard that called a state machine.

brian_cloutier 4 years ago | |

I can see how you would think they are similar!

Actors usually refers to a scheme with multiple coroutines which communicate via message passing. The emphasis is on the fact that there is no shared state: all communication happens via message passing. It's usually something which comes up in programming language design.

State Machine Replication usually refers to a scheme where all operations are serialized to a log and have a completely deterministic result, allowing you to reach the same state on any other machine simply by replaying the log. The emphasis is on existence of that persistence log, and on the deterministic result of applying it. It's usually something which comes up in distributed systems. It's also a common pattern in databases though it's usually just called "replication".

Erlang is the classic actor model example. Most erlang deployments do not keep persistent logs of messages. There are "inbox"es but those are transient and message disappear as soon as they are processed, actors are also not required to have deterministic responses to incoming messages. So, most erlang programs do not resemble state machine replication!

The classic example of SMR is something like Postgres streaming replication. One machine saves all changes to a log before it commits any transactions, and another machine is continuously processing that log. This gives you two instances of the database, making it easy to switch over to the second machine if the first one ever fails. This kind of looks like actors, if you squint, but usually when we talk about actors we don't think of each of the processes running on each of our machines as actors.

samiskin 4 years ago | |

This seems like a more restrictive version where the "Actors" must also be entirely deterministic and single threaded without really blocking in the middle of processing something.

oxff 4 years ago |

This is the only "podcast" I've bothered to actually "listen" to (I read the transcripts). Each episode is very informative often about several subjects.