9 ms·

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 b

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
- senderista 6y ago
  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.62&rep=rep1&type=pdf 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).
  - senderista 6y ago
    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 https://pdos.csail.mit.edu/6.824/papers/craq.pdf).
  - judofyr 6y ago
    > 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.

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

senderista 6y ago
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.62&rep=rep1&type=pdf 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).
- senderista 6y ago
  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 https://pdos.csail.mit.edu/6.824/papers/craq.pdf).
- judofyr 6y ago
  > 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.