John Ousterhout [0], Raft's co-inventor, did a user study (to hammer home the point that raft is easier to understand than paxos), and those presentations, presumably filmed to explain the two protocols to the users part of the study, are up on YouTube.
If y'all haven't read John Osterhout's book A Philosophy of Software Design, I highly recommend it.
It is concise and presents a clear view of what makes code easier to work with. I've found its concepts useful when trying to think of what to say during code reviews.
That's interesting because the recent arxiv paper[1] by Heidi Howard indicated that Raft just has a clearer presentation rather than some technical superiority of being simpler (discussion here [2]). So perhaps people who believe in Paxos need to come up with similarly easy explanations for the community that learn from the presentation that Raft focused on?
I don't think Raft is more clearly specified or presented than Multi-Paxos in, say, "Paxos for System Builders" or "Paxos Made Moderately Complex" or "Paxos Made Practical".
I'll have to admit that over time I've ended up with mixed feelings about this paper. This is mainly due to people reading this paper without knowing much about consensus and drawing conclusions like "Raft is better than Paxos" or "Raft is the best consensus algorithm" though. Some thoughts (please elaborate if you think I'm simplifying it too much or if you disagree with me!):
First of all remember that Paxos is a family of protocols for solving consensus. When doing research it's useful to reduce a problem into smaller and smaller parts. The "standard" Paxos algorithm is a very simple consensus algorithm which can only decide a single value once. It's not practical at all, but provides a good framework for thinking about consensus.
When this article proposes "Raft vs Paxos" they are actually comparing Raft against a standard way of configuring Paxos with a leader (MultiPaxos). Note that MultiPaxos allows a lot of nuances in the implementations while still being called "MultiPaxos". MultiPaxos is not a spec you implement; it's a set of ideas.
Raft on the other hand is a concrete protocol with well-defined, specified behavior. In fact, Raft is essentially an implementation of MultiPaxos[1]. This is a very good thing! Paxos provides a framework for thinking about consensus, while Raft puts some of these ideas into a concrete specification which is easy to implement. And it is a good point that we should make the knowledge in the field of consensus available for a wider audience. Yay, Raft is good!
And here comes the problem: A lot of people have read the Raft paper and made the conclusion that "Raft is the best way of solving consensus". Raft is (relatively) easy to implement and get started with and gives you a very simple model to program for (a log of commands), but it's far from a panacea.
The most important thing to know about Raft is that it's not performant (every command has to be sent to a single leader which becomes a bottleneck) nor scalable (every command needs to be processed by all nodes). Etcd supports "1000s of writes" and recommends up to "7 nodes".
This doesn't mean that Raft is bad; it's just a trade-off you need to be aware of. Simplicity vs performance. If you're integrating Raft into your stack and aim for scalability/performance you must always be very weary of when you use it. You should minimize writes at all costs. Unfortunately many developers gets the impression that you can just plug Raft into an existing system and suddenly have a performant and scalable distributed system.
A good example is CockrouchDB: They're using plain Raft for writes, but uses "leader leases" for scaling reads. Suddenly things become a lot more complicated (for instance see this issue about how leader leases are implemented in the Go library for Raft: https://github.com/hashicorp/raft/issues/108). I'm sorry, but you're going to have to get your hands dirty if you want something that's both fast and correct.
The end result is that you have two choices: (1) You can use a library which provides a simple model (a log of commands), but doesn't scale well or (2) you can use a more complicated consensus algorithm and then deal with all of the Hard Problems™ that comes with it. If you're going for the second option, you might as well take advantage of all of the research discovered in the last few years (see https://vadosware.io/post/paxosmon-gotta-concensus-them-all/)
It should also be noted that even though the consensus algorithm doesn't scale, it doesn't mean your system can't scale. Scalog (otoolep↗
If people are interested in studying a combination of Raft and SQLite, you could check out this Raft-based database I created:
Your point about "the impression that you can just plug Raft into an existing system and suddenly have a performant and scalable distributed system" is an excellent one. One the biggest misconceptions I come across is that rqlite is distributed for performance when it's actually all about reliability. In fact performance is significantly reduced versus just writing to SQLite itself.
> First of all remember that Paxos is a family of protocols for solving consensus... Raft on the other hand is a concrete protocol with well-defined, specified behavior. In fact, Raft is essentially an implementation of MultiPaxos... You have two choices: (1) You can use a library which provides a simple model (a log of commands), but doesn't scale well or (2) You can use a more complicated consensus algorithm and then deal with all of the Hard Problems™ that comes with it.
At AWS [0], everyone (I spoke to) who worked on distributed consensus had this exact same opinion, so you're not at all off the mark.
> A good example is CockroachDB: They're using plain Raft for writes, but uses "leader leases" for scaling reads.
The Chubby paper by Google [1] goes in to excruciating details of running a production Paxos system.
> Focus on how you can avoiding using a consensus algorithm due to the way your system works.
Amazon SQS may be one such example: I'd presume, it scales by avoiding consensus, in a way, simply maintaining multiple copies [2] and by placing guard-rails around delivery [3][4], ingestion, and duration of storage [5].
Yours is an excellent comment, factual and even handed. As someone who had to delve into these things and had to implement e.g. a variant of MultiPaxos for work (this was before Raft existed), I agree that there is a bit of unhealthy confusion going around.
We generalize every day because everyone can't be expected to learn everything, so we abstract away, define constraints and best practices and we select our library-fied tools and apply them. We do this with operating systems, file systems, encryption, and also with distributed systems. The basics of distributed systems and their invariants and trade offs are not that hard if you give yourself time to study them properly, but when you want high performance and scale it does get Challenging.
It is important that any abstractions we make, any generalizations, constraint definitions and best practices that we expect people to read, accept and adhere to are as correct as possible without breaking that abstraction. So thank you for your comment. Please note that mine is not a pro-Paxos comment either, just one appreciating good information being spread so that people can make good choices and trade offs.
Distributed systems are hard. To paraphrase: In the data flow, no one can hear your canary msg scream.
Raft has spawned a huge ecosystem of consensus libraries across various languages. This has 'democratized' the consensus algorithm and has made it easier to build distributed systems.
Is it perfect? No, as another comment here points out, Raft might not be as fast as some other more complicated Paxos variants but that's okay for most use cases and is much easier to reason about.
To give an example of how powerful this is, I started implementing high availability for an opensource instant search engine I've been working on (https://github.com/typesense/typesense) and was able to get a basic clustering solution working in just a few days.
Pre-raft this would have taken a few weeks or would have required an external coordinator like Zookeeper. This way, Raft has unlocked so many opportunities.
To reduce deployment complexity. One or the primary goals of Typesense is simplicity. While writing a raft implementation myself would have been tricky, integrating with a consensus library made sense.
A pet peeve I have about this space is that "consensus" is not actually a practically interesting problem. The interesting problem for applications is "atomic broadcast" or "total order broadcast", which is theoretically equivalent to consensus but much closer to the needs of applications. The result has been that many important atomic broadcast algorithms have been ignored while Paxos and Raft steal the spotlight in "distsys" pop culture. Some of these algorithms need only f+1 nodes to tolerate f faults (rather than 2f+1 as with Paxos or Raft), at the cost of requiring an external reconfiguration service (almost certainly Paxos- or Raft-based). Two examples: chain replication (relatively well-known and widely deployed in at least one major cloud provider), and LCR, a provably write-throughput-optimal, fully symmetric ring-overlay protocol that achieves total ordering with no sequencer. The latter can serve linearizable reads from any replica, with none of the complex consistency concerns of read replicas in Paxos/Raft (or Zookeeper). Also, read throughput scales linearly with the size of the cluster (while write throughput stays roughly constant). Write latency and transient fault tolerance are strictly inferior to quorum-based protocols like Paxos/Raft, but this is less of a concern in LAN environments, where write throughput tends to matter more. Both chain replication and LCR support much higher write throughput than Paxos/Raft, and are thus more suitable for data plane applications in a LAN (specialized Paxos variants like SDPaxos are more appropriate for a WAN). If your system needs to be able to reconfigure itself, though, or you need to mask tail latency/transient faults, then Paxos/Raft are still the way to go.
You're bringing up good points. Chain replication seems neat and I haven't quite figured out why it's so rarely used. Maybe it's partly because it's not request/response-oriented (the tail is supposed reply directly to the client)?
I hadn't heard about LCR before so thanks for the pointer. It seems to be first described in "The complexity of reliable distributed storage"[2]. I found one reference to it in the Ring-Paxos paper[3] and they explain the disadvantages as follows:
> Of special interest is LCR, which arranges processes along a ring and uses vector clocks for message ordering. This protocol has slightly better throughput than Ring Paxos but exhibits a higher latency, which increases linearly with the number of processes in the ring, and requires perfect failure detection: erroneously suspecting a process to have crashed is not tolerated. Perfect failure detection implies strong synchrony assumptions about processing and message transmission times.
I'll definitely read the paper and try to understand how LCR works!
Ron Levy's thesis, as you mentioned, has a pretty complete description of LCR, as well as a related atomic register protocol (analog of ABD). The canonical reference for LCR, I think, is "Throughput Optimal Total Order Broadcast
for Cluster Environments" (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.177...). If nothing else, LCR contains probably the most elegant and surprising application of vector clocks I've seen (they are used to establish a total order on messages, rather than the usual partial order, with no sequencer required!).
Ring Paxos uses similar ideas (ring overlay for the acceptors), but requires IP-multicast (to minimize bandwidth for broadcasting values to the acceptors and learners), and hence isn't practical in most public cloud environments. (The variant of Ring Paxos that doesn't use IP-multicast doesn't seem to me to have any significant advantages over LCR, while being less symmetric and more complicated.) I do think that Ring Paxos is probably the best approach I've seen to improving the throughput of Paxos while preserving its latency advantages (but it still has issues with tail latency and transient faults because the acceptors communicate via a ring rather than quorums).
Oh, to address your question about chain replication, normally acks travel backward along the chain, from the tail to the head, so the head acks to the client when it's received an ack from its successor. So the usual client interface is still request/response, but of course the latency is considerably higher than a quorum-based protocol, since the messages have to travel the full length of the chain before being made durable on all nodes, and then acks have to travel all the way backward. There are various optimizations to try to reduce this latency, and also reduce the load on the tail in read-heavy workloads (probably the best-known is CRAQ: https://pdos.csail.mit.edu/6.824/papers/craq.pdf).
> If nothing else, LCR contains probably the most elegant and surprising application of vector clocks I've seen (they are used to establish a total order on messages, rather than the usual partial order, with no sequencer required!).
Very interesting! I'll definitely have to check this out. Thanks for the references/links.
26 comments
[ 3.5 ms ] story [ 57.5 ms ] threadPaxos: https://www.youtube-nocookie.com/embed/JEpsBg0AO6o
Raft: https://www.youtube-nocookie.com/embed/YbZ3zDzDnrw
Then there's this presentation-animation, too, which I find to be pretty nifty: http://thesecretlivesofdata.com/raft/
[0] https://web.stanford.edu/~ouster/cgi-bin/home.php
And yeah wow, Raft is dead simple.
It is concise and presents a clear view of what makes code easier to work with. I've found its concepts useful when trying to think of what to say during code reviews.
[1] https://arxiv.org/abs/2004.05074 [2] https://news.ycombinator.com/item?id=22994420
First of all remember that Paxos is a family of protocols for solving consensus. When doing research it's useful to reduce a problem into smaller and smaller parts. The "standard" Paxos algorithm is a very simple consensus algorithm which can only decide a single value once. It's not practical at all, but provides a good framework for thinking about consensus.
When this article proposes "Raft vs Paxos" they are actually comparing Raft against a standard way of configuring Paxos with a leader (MultiPaxos). Note that MultiPaxos allows a lot of nuances in the implementations while still being called "MultiPaxos". MultiPaxos is not a spec you implement; it's a set of ideas.
Raft on the other hand is a concrete protocol with well-defined, specified behavior. In fact, Raft is essentially an implementation of MultiPaxos[1]. This is a very good thing! Paxos provides a framework for thinking about consensus, while Raft puts some of these ideas into a concrete specification which is easy to implement. And it is a good point that we should make the knowledge in the field of consensus available for a wider audience. Yay, Raft is good!
And here comes the problem: A lot of people have read the Raft paper and made the conclusion that "Raft is the best way of solving consensus". Raft is (relatively) easy to implement and get started with and gives you a very simple model to program for (a log of commands), but it's far from a panacea.
The most important thing to know about Raft is that it's not performant (every command has to be sent to a single leader which becomes a bottleneck) nor scalable (every command needs to be processed by all nodes). Etcd supports "1000s of writes" and recommends up to "7 nodes".
This doesn't mean that Raft is bad; it's just a trade-off you need to be aware of. Simplicity vs performance. If you're integrating Raft into your stack and aim for scalability/performance you must always be very weary of when you use it. You should minimize writes at all costs. Unfortunately many developers gets the impression that you can just plug Raft into an existing system and suddenly have a performant and scalable distributed system.
A good example is CockrouchDB: They're using plain Raft for writes, but uses "leader leases" for scaling reads. Suddenly things become a lot more complicated (for instance see this issue about how leader leases are implemented in the Go library for Raft: https://github.com/hashicorp/raft/issues/108). I'm sorry, but you're going to have to get your hands dirty if you want something that's both fast and correct.
The end result is that you have two choices: (1) You can use a library which provides a simple model (a log of commands), but doesn't scale well or (2) you can use a more complicated consensus algorithm and then deal with all of the Hard Problems™ that comes with it. If you're going for the second option, you might as well take advantage of all of the research discovered in the last few years (see https://vadosware.io/post/paxosmon-gotta-concensus-them-all/)
It should also be noted that even though the consensus algorithm doesn't scale, it doesn't mean your system can't scale. Scalog ( otoolep ↗ If people are interested in studying a combination of Raft and SQLite, you could check out this Raft-based database I created: ignoramous ↗ You make super important points. ignoramous ↗ ...and parley ↗ Yours is an excellent comment, factual and even handed. As someone who had to delve into these things and had to implement e.g. a variant of MultiPaxos for work (this was before Raft existed), I agree that there is a bit of unhealthy confusion going around. philips ↗ FWIW, CockroachDB uses and co-maintains etcd/raft not hashicorp/raft. judofyr ↗ Huh, I wasn't aware of that. Somehow I always thought that hashicorp/raft was used in etcd. Thanks for the correction!
https://github.com/rqlite/rqlite
Your point about "the impression that you can just plug Raft into an existing system and suddenly have a performant and scalable distributed system" is an excellent one. One the biggest misconceptions I come across is that rqlite is distributed for performance when it's actually all about reliability. In fact performance is significantly reduced versus just writing to SQLite itself.
> First of all remember that Paxos is a family of protocols for solving consensus... Raft on the other hand is a concrete protocol with well-defined, specified behavior. In fact, Raft is essentially an implementation of MultiPaxos... You have two choices: (1) You can use a library which provides a simple model (a log of commands), but doesn't scale well or (2) You can use a more complicated consensus algorithm and then deal with all of the Hard Problems™ that comes with it.
At AWS [0], everyone (I spoke to) who worked on distributed consensus had this exact same opinion, so you're not at all off the mark.
> A good example is CockroachDB: They're using plain Raft for writes, but uses "leader leases" for scaling reads.
The Chubby paper by Google [1] goes in to excruciating details of running a production Paxos system.
> Focus on how you can avoiding using a consensus algorithm due to the way your system works.
Amazon SQS may be one such example: I'd presume, it scales by avoiding consensus, in a way, simply maintaining multiple copies [2] and by placing guard-rails around delivery [3][4], ingestion, and duration of storage [5].
[0] https://aws.amazon.com/builders-library/leader-election-in-d...
[1] https://blog.acolyer.org/2015/02/13/the-chubby-lock-service-...
[2] https://docs.aws.amazon.com/AWSSimpleQueueService/latest/SQS...
[3] https://docs.aws.amazon.com/AWSSimpleQueueService/latest/SQS...
[4] https://patents.google.com/patent/US10362131B1/en
[5] https://patents.google.com/patent/US8261286B1/en
[5b] https://patents.google.com/patent/US8370395B1/en?q=queue
We generalize every day because everyone can't be expected to learn everything, so we abstract away, define constraints and best practices and we select our library-fied tools and apply them. We do this with operating systems, file systems, encryption, and also with distributed systems. The basics of distributed systems and their invariants and trade offs are not that hard if you give yourself time to study them properly, but when you want high performance and scale it does get Challenging.
It is important that any abstractions we make, any generalizations, constraint definitions and best practices that we expect people to read, accept and adhere to are as correct as possible without breaking that abstraction. So thank you for your comment. Please note that mine is not a pro-Paxos comment either, just one appreciating good information being spread so that people can make good choices and trade offs.
Distributed systems are hard. To paraphrase: In the data flow, no one can hear your canary msg scream.
https://github.com/etcd-io/etcd/tree/master/raft#raft-librar...
Users:
- cockroachdb A Scalable, Survivable, Strongly-Consistent SQL Database
- dgraph A Scalable, Distributed, Low Latency, High Throughput Graph Database
- etcd A distributed reliable key-value store
- tikv A Distributed transactional key value database powered by Rust and Raft
- swarmkit A toolkit for orchestrating distributed systems at any scale.
https://github.com/etcd-io/etcd/tree/master/raft#notable-use...
Go docs
https://pkg.go.dev/go.etcd.io/etcd/raft?tab=doc
Is it perfect? No, as another comment here points out, Raft might not be as fast as some other more complicated Paxos variants but that's okay for most use cases and is much easier to reason about.
To give an example of how powerful this is, I started implementing high availability for an opensource instant search engine I've been working on (https://github.com/typesense/typesense) and was able to get a basic clustering solution working in just a few days.
Pre-raft this would have taken a few weeks or would have required an external coordinator like Zookeeper. This way, Raft has unlocked so many opportunities.
[0] https://arxiv.org/pdf/1907.07010.pdf
I hadn't heard about LCR before so thanks for the pointer. It seems to be first described in "The complexity of reliable distributed storage"[2]. I found one reference to it in the Ring-Paxos paper[3] and they explain the disadvantages as follows:
> Of special interest is LCR, which arranges processes along a ring and uses vector clocks for message ordering. This protocol has slightly better throughput than Ring Paxos but exhibits a higher latency, which increases linearly with the number of processes in the ring, and requires perfect failure detection: erroneously suspecting a process to have crashed is not tolerated. Perfect failure detection implies strong synchrony assumptions about processing and message transmission times.
I'll definitely read the paper and try to understand how LCR works!
[1]: https://dl.acm.org/doi/abs/10.1145/3269981
[2]: https://infoscience.epfl.ch/record/114767
[3]: https://ieeexplore.ieee.org/abstract/document/5544272
Ring Paxos uses similar ideas (ring overlay for the acceptors), but requires IP-multicast (to minimize bandwidth for broadcasting values to the acceptors and learners), and hence isn't practical in most public cloud environments. (The variant of Ring Paxos that doesn't use IP-multicast doesn't seem to me to have any significant advantages over LCR, while being less symmetric and more complicated.) I do think that Ring Paxos is probably the best approach I've seen to improving the throughput of Paxos while preserving its latency advantages (but it still has issues with tail latency and transient faults because the acceptors communicate via a ring rather than quorums).
Very interesting! I'll definitely have to check this out. Thanks for the references/links.