5 ms·

In Search of an Understandable Consensus Algorithm (2014) [pdf]

81 points by alokrai 6y ago

ignoramous 6y ago
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. Paxos: https://www.youtube-nocookie.com/embed/JEpsBg0AO6o https://www.youtube-nocookie.com/embed/JEpsBg0AO6o Raft: https://www.youtube-nocookie.com/embed/YbZ3zDzDnrw 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/ http://thesecretlivesofdata.com/raft/ [0] https://web.stanford.edu/~ouster/cgi-bin/home.php https://web.stanford.edu/~ouster/cgi-bin/home.php
- kohtatsu 6y ago
  I really enjoyed the presentation. And yeah wow, Raft is dead simple.
  - otoolep 6y ago
    Yes, Ben Johnson's (https://github.com/benbjohnson https://github.com/benbjohnson) presentation on Raft is great. He is also the creator of BoltDB (https://github.com/boltdb/bolt https://github.com/boltdb/bolt) which is a core component of Hashiscorp's Raft implementation (https://github.com/hashicorp/raft https://github.com/hashicorp/raft).
    - philips 6y ago
      FWIW, etcd uses a forked version of boltdb with bug fixes and features: https://github.com/etcd-io/bbolt https://github.com/etcd-io/bbolt
- afarrell 6y ago
  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.
  - neonate 6y ago
    I have it and tried several times to get into it but nothing grabbed me. Can you recommend one or two sections that you think might draw me in?
    - ignoramous 6y ago
      I haven't read the book, but this presentation from professor John Ousterhout on the book was pretty good: https://youtu.be/bmSAYlu0NcY https://youtu.be/bmSAYlu0NcY
      - neonate 6y ago
        Ooh thanks!
- vlovich123 6y ago
  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? [1] https://arxiv.org/abs/2004.05074 https://arxiv.org/abs/2004.05074 [2] https://news.ycombinator.com/item?id=22994420 https://news.ycombinator.com/item?id=22994420
  - senderista 6y ago
    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".
judofyr 6y ago
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 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/ 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 (https://www.usenix.org/system/files/nsdi20-paper-ding.pdf https://www.usenix.org/system/files/nsdi20-paper-ding.pdf) is an example of a system which uses a consensus algorithm in a constant way (i.e. regardless of load of the system). Once again: Focus on how you can avoiding using a consensus algorithm due to the way your system works. TL;DR: Hard problems are still hard. Don't think that Raft is a magical piece of software which solves all of your problems. [1]: There are some nuances between Raft and "standard" MultiPaxos as mentioned in https://arxiv.org/abs/2004.05074 https://arxiv.org/abs/2004.05074. I would still consider Raft to be in the same class as MultiPaxos (compared to other solutions of consensus).
karterk 6y ago
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 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.
- riffraff 6y ago
  forgive the question, but why did you choose to implement a coordination solution yourself rather than use an off the shelf system like Zookeeper?
  - karterk 6y ago
    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.
AlexCoventry 6y ago
Bryan Ford's Threshold Logical Clocks[0] is a great read. [0] https://arxiv.org/pdf/1907.07010.pdf https://arxiv.org/pdf/1907.07010.pdf
senderista 6y ago
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.
- judofyr 6y ago
  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! [1]: https://dl.acm.org/doi/abs/10.1145/3269981 https://dl.acm.org/doi/abs/10.1145/3269981 [2]: https://infoscience.epfl.ch/record/114767 https://infoscience.epfl.ch/record/114767 [3]: https://ieeexplore.ieee.org/abstract/document/5544272 https://ieeexplore.ieee.org/abstract/document/5544272

81 points by alokrai 6y ago

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. Paxos: https://www.youtube-nocookie.com/embed/JEpsBg0AO6o https://www.youtube-nocookie.com/embed/JEpsBg0AO6o Raft: https://www.youtube-nocookie.com/embed/YbZ3zDzDnrw 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/ http://thesecretlivesofdata.com/raft/ [0] https://web.stanford.edu/~ouster/cgi-bin/home.php https://web.stanford.edu/~ouster/cgi-bin/home.php

kohtatsu 6y ago
I really enjoyed the presentation. And yeah wow, Raft is dead simple.
- otoolep 6y ago
  Yes, Ben Johnson's (https://github.com/benbjohnson https://github.com/benbjohnson) presentation on Raft is great. He is also the creator of BoltDB (https://github.com/boltdb/bolt https://github.com/boltdb/bolt) which is a core component of Hashiscorp's Raft implementation (https://github.com/hashicorp/raft https://github.com/hashicorp/raft).
  - philips 6y ago
    FWIW, etcd uses a forked version of boltdb with bug fixes and features: https://github.com/etcd-io/bbolt https://github.com/etcd-io/bbolt
afarrell 6y ago
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.
- neonate 6y ago
  I have it and tried several times to get into it but nothing grabbed me. Can you recommend one or two sections that you think might draw me in?
  - ignoramous 6y ago
    I haven't read the book, but this presentation from professor John Ousterhout on the book was pretty good: https://youtu.be/bmSAYlu0NcY https://youtu.be/bmSAYlu0NcY
    - neonate 6y ago
      Ooh thanks!
vlovich123 6y ago
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? [1] https://arxiv.org/abs/2004.05074 https://arxiv.org/abs/2004.05074 [2] https://news.ycombinator.com/item?id=22994420 https://news.ycombinator.com/item?id=22994420
- senderista 6y ago
  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".

judofyr 6y ago

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 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/ 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 (https://www.usenix.org/system/files/nsdi20-paper-ding.pdf https://www.usenix.org/system/files/nsdi20-paper-ding.pdf) is an example of a system which uses a consensus algorithm in a constant way (i.e. regardless of load of the system). Once again: Focus on how you can avoiding using a consensus algorithm due to the way your system works. TL;DR: Hard problems are still hard. Don't think that Raft is a magical piece of software which solves all of your problems. [1]: There are some nuances between Raft and "standard" MultiPaxos as mentioned in https://arxiv.org/abs/2004.05074 https://arxiv.org/abs/2004.05074. I would still consider Raft to be in the same class as MultiPaxos (compared to other solutions of consensus).

karterk 6y ago

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 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.

riffraff 6y ago
forgive the question, but why did you choose to implement a coordination solution yourself rather than use an off the shelf system like Zookeeper?
- karterk 6y ago
  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.

AlexCoventry 6y ago

Bryan Ford's Threshold Logical Clocks[0] is a great read. [0] https://arxiv.org/pdf/1907.07010.pdf https://arxiv.org/pdf/1907.07010.pdf

senderista 6y ago

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.

judofyr 6y ago
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! [1]: https://dl.acm.org/doi/abs/10.1145/3269981 https://dl.acm.org/doi/abs/10.1145/3269981 [2]: https://infoscience.epfl.ch/record/114767 https://infoscience.epfl.ch/record/114767 [3]: https://ieeexplore.ieee.org/abstract/document/5544272 https://ieeexplore.ieee.org/abstract/document/5544272