4 ms·

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

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.

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.