5 ms·

“Paxos is one of the first and most celebrated ideas that laid the foundation for how different things come to an agreement asynchronously” “Most—if not all—co

by _vvhw 5y ago

“Paxos is one of the first and most celebrated ideas that laid the foundation for how different things come to an agreement asynchronously” “Most—if not all—consensus algorithms fundamentally derive concepts from Paxos” It's not well known (even in the field of distributed systems) that in fact Viewstamped Replication pioneered the field of consensus in 1988, a year before Paxos, with an intuitive algorithm essentially identical to Raft, so that Raft is more within the family and tradition of Viewstamped Replication (as is Multi-Paxos state machine replication) than the other way round. Viewstamped Replication is significantly easier to implement correctly in the presence of real world storage faults, which formal proofs often do not take into account in their fault model. For example, Paxos and Raft proofs typically assume only pristine stable storage, and the correctness unfortunately rapidly breaks down when physical disks are used, since these may misdirect reads and writes. UW-Madison have done some excellent research in this area in particular, the intersection of consensus protocol correctness and storage faults, and I would recommend reading "Protocol-Aware Recovery for Consensus-Based Storage" if you'd like to dive into some of this: https://www.usenix.org/conference/fast18/presentation/alagappan https://www.usenix.org/conference/fast18/presentation/alagap... Aleksey Charapko's DistSys Reading Group also recently covered Viewstamped Replication as a foundational paper, focusing on the crystal clear 2012 revision by Barbara Liskov and James Cowling, which I was able to present, covering some of our experience implementing the protocol for TigerBeetle, a distributed database with a strict storage fault model: http://charap.co/reading-group-viewstamped-replication-revisited/ http://charap.co/reading-group-viewstamped-replication-revis...

hawk_ 5y ago
> correctness unfortunately rapidly breaks down when physical disks are used, since these may misdirect reads and writes. Isn't the whole point of consensus to get around discrepancies due to faults in individual devices. With high enough quorum in Raft for example you can lower the probability of dataloss to an arbitrarily low point to not matter at all in practice.
- _vvhw 5y ago
  "Isn't the whole point of consensus to get around discrepancies due to faults in individual devices" Yes, but only with respect to the fault models actually adopted, proven, implemented and tested. Again, most formal proofs, papers and implementations are not actually incorporating any kind of a storage fault model, yet this is essential for correctness in a production deployment. If you look closely at Paxos and RAFT, they only attempt correctness for the network fault model {packets may be reordered/lost/delayed/replayed/redirected} and process fault model {crash failure}, nothing else. For example, there's no mention of what to do if your disk forgets some writes either because of a misdirected write, or because of a latent sector error, or because of corruption in the middle of the committed consensus log. Unfortunately, simply increasing quorum will also not actually lower the probability of data loss. In fact, there are trivial cases where even a single local disk sector failure on one replica can cause an entire Paxos or RAFT cluster to experience global cluster data loss. Protocol-Aware Recovery for Consensus-Based Storage from UW-Madison goes into this in detail, showing where well-known distributed systems are not correct, and also showing how this can be fixed. It won best paper at FAST '18 but is still catching on in industry. We implemented Protocol-Aware Recovery for TigerBeetle [1], and use deterministic simulation testing to inject all kinds of storage faults on all replicas in a cluster, even as high as 20% simultaneously on all 5 replicas, including the leader. It was pretty magical for us to watch TigerBeetle just keep on running the first time, with high availability and no loss of data, despite radioactively high levels of corruption across the cluster. [1] https://www.tigerbeetle.com https://www.tigerbeetle.com
_benedict 5y ago
What people think of as Paxos was not originally intended to be called Paxos by Lamport, but the leader election phase for what is now called Multi-Paxos (and he intended to call Paxos). So I don't think there's a difference for algorithmic heritage between Paxos and Multi-Paxos (perhaps you know this, but for those reading your comment it might help clarify). I think it is anyway reasonable to say that most consensus algorithms derive concepts from Paxos, since (despite how terribly it was presented by Lamport) it is the consensus protocol that captured most attention. Most recent advances in distributed consensus derive from Paxos, not Viewstamped Replication. As far as I know all leaderless distributed consensus protocols derive from Paxos, and most protocol optimisations that have been developed apply to Paxos or one of its derivatives. I also happen to think Paxos is pretty easy to implement correctly, particularly by comparison to the other protocols, in large part due to its active replication semantics, permitting that commands may be processed by replicas in any order. This means failover is much less complicated to negotiate, as the new leader does not expect to have a complete view of the log. Though of course membership changes remain complicated, and it may be beneficial for the leader to be able to assume it has a complete view of the log - but this is an optimisation rather than an inherent property for correct implementation. > correctness unfortunately rapidly breaks down when physical disks are used, since these may misdirect reads and writes What do you mean by "misdirect" here?
- _vvhw 5y ago
  I would say that the majority of leader-based state machine replication protocols today are based on the more popular RAFT, which is itself a derivative of Viewstamped Replication. At least most leader-based consensus implementations that I know of seem to be derived from RAFT these days? I would also guess that leaderless distributed protocols derived from Paxos tend to be more niche than leader-based state machine replication? While Viewstamped Replication as contributed by Brian M. Oki certainly established all the foundational elements of consensus that Paxos would later reiterate and generalize, Viewstamped Replication also immediately showed how to use consensus to do leader-based state machine replication, and to do this simply and practically, as seen in RAFT's massive success in industry. > What do you mean by "misdirect" here? A misdirected read/write I/O. This is a rare kind of storage fault in the literature where the disk device redirects the I/O to a different sector. It's rare, but it happens. > I also happen to think Paxos is pretty easy to implement correctly What was especially interesting about the PAR paper from UW-Madison was how even fairly common single disk sector faults such as latent sector errors or corruption could cause global cluster data loss for implementations based on Paxos and RAFT as specified, where they depend on pristine fault-free stable storage for correctness. The PAR paper further motivated why simple checksums are not enough and why local storage and global protocol need to be aware of each other if cluster availability is to be maximized. Implementing Paxos correctly in the presence of a realistic storage fault model is certainly non-trivial. I believe Viewstamped Replication (VSR), and in particular the 2012 revision by Liskov and Cowling, is a much better place to start when implementing a state machine replication protocol, since it places absolutely no demands on the disk for correctness of the protocol. In fact, this was the key reason we picked VSR for TigerBeetle, it's not only elegant, but it's one of the very few protocols that actually make sense in a production context where a realistic storage fault model is at play. For example, the VSR view change is entirely correct without any reliance on disk, whereas most other protocols would need significant deviations (and proofs) to make the same guarantee.
hawk_ 5y ago
do you happen to have a mirror for the vr-revisited paper? This link doesn't work https://pmg.csail.mit.edu/papers/vr-revisited.pdf https://pmg.csail.mit.edu/papers/vr-revisited.pdf
- _vvhw 5y ago
  I think the issue is with the scheme, this works: http://pmg.csail.mit.edu/papers/vr-revisited.pdf http://pmg.csail.mit.edu/papers/vr-revisited.pdf
  - hawk_ 5y ago
    you're right. Firefox wouldn't let me click the http link and automatically convert it to https. however if I click download directly instead of just loading it, it works.

by _vvhw 5y ago

hawk_ 5y ago

> correctness unfortunately rapidly breaks down when physical disks are used, since these may misdirect reads and writes. Isn't the whole point of consensus to get around discrepancies due to faults in individual devices. With high enough quorum in Raft for example you can lower the probability of dataloss to an arbitrarily low point to not matter at all in practice.

_vvhw 5y ago
"Isn't the whole point of consensus to get around discrepancies due to faults in individual devices" Yes, but only with respect to the fault models actually adopted, proven, implemented and tested. Again, most formal proofs, papers and implementations are not actually incorporating any kind of a storage fault model, yet this is essential for correctness in a production deployment. If you look closely at Paxos and RAFT, they only attempt correctness for the network fault model {packets may be reordered/lost/delayed/replayed/redirected} and process fault model {crash failure}, nothing else. For example, there's no mention of what to do if your disk forgets some writes either because of a misdirected write, or because of a latent sector error, or because of corruption in the middle of the committed consensus log. Unfortunately, simply increasing quorum will also not actually lower the probability of data loss. In fact, there are trivial cases where even a single local disk sector failure on one replica can cause an entire Paxos or RAFT cluster to experience global cluster data loss. Protocol-Aware Recovery for Consensus-Based Storage from UW-Madison goes into this in detail, showing where well-known distributed systems are not correct, and also showing how this can be fixed. It won best paper at FAST '18 but is still catching on in industry. We implemented Protocol-Aware Recovery for TigerBeetle [1], and use deterministic simulation testing to inject all kinds of storage faults on all replicas in a cluster, even as high as 20% simultaneously on all 5 replicas, including the leader. It was pretty magical for us to watch TigerBeetle just keep on running the first time, with high availability and no loss of data, despite radioactively high levels of corruption across the cluster. [1] https://www.tigerbeetle.com https://www.tigerbeetle.com

_benedict 5y ago

What people think of as Paxos was not originally intended to be called Paxos by Lamport, but the leader election phase for what is now called Multi-Paxos (and he intended to call Paxos). So I don't think there's a difference for algorithmic heritage between Paxos and Multi-Paxos (perhaps you know this, but for those reading your comment it might help clarify). I think it is anyway reasonable to say that most consensus algorithms derive concepts from Paxos, since (despite how terribly it was presented by Lamport) it is the consensus protocol that captured most attention. Most recent advances in distributed consensus derive from Paxos, not Viewstamped Replication. As far as I know all leaderless distributed consensus protocols derive from Paxos, and most protocol optimisations that have been developed apply to Paxos or one of its derivatives. I also happen to think Paxos is pretty easy to implement correctly, particularly by comparison to the other protocols, in large part due to its active replication semantics, permitting that commands may be processed by replicas in any order. This means failover is much less complicated to negotiate, as the new leader does not expect to have a complete view of the log. Though of course membership changes remain complicated, and it may be beneficial for the leader to be able to assume it has a complete view of the log - but this is an optimisation rather than an inherent property for correct implementation. > correctness unfortunately rapidly breaks down when physical disks are used, since these may misdirect reads and writes What do you mean by "misdirect" here?

_vvhw 5y ago
I would say that the majority of leader-based state machine replication protocols today are based on the more popular RAFT, which is itself a derivative of Viewstamped Replication. At least most leader-based consensus implementations that I know of seem to be derived from RAFT these days? I would also guess that leaderless distributed protocols derived from Paxos tend to be more niche than leader-based state machine replication? While Viewstamped Replication as contributed by Brian M. Oki certainly established all the foundational elements of consensus that Paxos would later reiterate and generalize, Viewstamped Replication also immediately showed how to use consensus to do leader-based state machine replication, and to do this simply and practically, as seen in RAFT's massive success in industry. > What do you mean by "misdirect" here? A misdirected read/write I/O. This is a rare kind of storage fault in the literature where the disk device redirects the I/O to a different sector. It's rare, but it happens. > I also happen to think Paxos is pretty easy to implement correctly What was especially interesting about the PAR paper from UW-Madison was how even fairly common single disk sector faults such as latent sector errors or corruption could cause global cluster data loss for implementations based on Paxos and RAFT as specified, where they depend on pristine fault-free stable storage for correctness. The PAR paper further motivated why simple checksums are not enough and why local storage and global protocol need to be aware of each other if cluster availability is to be maximized. Implementing Paxos correctly in the presence of a realistic storage fault model is certainly non-trivial. I believe Viewstamped Replication (VSR), and in particular the 2012 revision by Liskov and Cowling, is a much better place to start when implementing a state machine replication protocol, since it places absolutely no demands on the disk for correctness of the protocol. In fact, this was the key reason we picked VSR for TigerBeetle, it's not only elegant, but it's one of the very few protocols that actually make sense in a production context where a realistic storage fault model is at play. For example, the VSR view change is entirely correct without any reliance on disk, whereas most other protocols would need significant deviations (and proofs) to make the same guarantee.

hawk_ 5y ago

do you happen to have a mirror for the vr-revisited paper? This link doesn't work https://pmg.csail.mit.edu/papers/vr-revisited.pdf https://pmg.csail.mit.edu/papers/vr-revisited.pdf

_vvhw 5y ago
I think the issue is with the scheme, this works: http://pmg.csail.mit.edu/papers/vr-revisited.pdf http://pmg.csail.mit.edu/papers/vr-revisited.pdf
- hawk_ 5y ago
  you're right. Firefox wouldn't let me click the http link and automatically convert it to https. however if I click download directly instead of just loading it, it works.