4 ms·

Why are Paxos and/or Raft considered superior for distributed systems?

by pthread_t 5y ago

klysm 5y ago
Two phase commit has failure modes that paxos and raft address.
- azurelake 5y ago
  No, that's not correct. 2PC and paxos/raft solve different problems. 2PC is for distributed transactions across leaders / primaries. Paxos / Raft is for replication / consesus. Spanner is an example of a system that uses both.
  - skyde 5y ago
    I agree with you but a better explanation I think is. Raft/Paxos is to make sure majority of the replica for a partition have the latest version of the data and that you can keep writing even if minority of nodes in that partition are unavailable. while still giving guarantee that no write get lost and all read reflect the most recent write. While 2PC is to write 2 records atomically when the 2 record are located on 2 different partitions.
  - uvdn7 5y ago
    Yes, it is correct. At a distance both 2pc and paxos are solving the consensus problem - a group of entities agreeing on _something_. In the 2pc case, the _something_ is commit or not. In the paxos case, the _something_ is the chosen value. 2pc cannot handle coordinator failure, a single point of failure if you will. Transaction commit and replication are both consensus problems. You can use paxos for transaction commit as well. Lamport has a paper on a protocol called Paxos Commit.
    - azurelake 5y ago
      I see, guess I'm wrong then! What's the disadvantage of Paxos Commit vs 2PC? Presumably there's a reason that the Spanner team didn't use it for distributed transactions. edit: Looking at the paper, it looks like the tradeoff is increased amount of coordination needed. "The Two-Phase Commit protocol is thus the degenerate case of the Paxos Commit algorithm with a single acceptor." I suppose in Spanner, having more than one acceptor is redudant since each shard is a Paxos group anyways.
      - klysm 5y ago
        Spanner is in a rather unique technical position which enables it to sit outside the tradoff space of most distributed systems. You certainly pay for being robust against coordinator failure though.
uvdn7 5y ago
I don’t think Paxos is superior than 2pc. 2pc is dramatically simpler to implement. And if you layer 2pc on Paxos (something highly available) you can get the best of both worlds — simplicity and fault tolerance. The thing with Paxos is that it’s expensive and very hard to get right. So usually you have a very small but critical component that’s built on Paxos, then you compose the rest of the system on top with strong assumptions of the availability of the dependencies.
curtisf 5y ago
Two phase commit requires a coordinator. If the coordinator goes down, the system makes no progress. If the coordinator sends inconsistent commands (e.g., commit to one resource and abort to another), it's not serving its purpose. So in a system using two phase commit, your availability is limited by the availability of the coordinator. If the coordinator is a single server, you have a single point of failure in a distributed system. If you try using multiple servers to increase the availability of the coordinator, you risk sending inconsistent commands -- unless you implement a consensus system within the coordinator. Paxos and Raft let you combine the availability of multiple servers while still letting them behave consistently. (This is the "consensus problem", and correctly solving it is notoriously tricky).
dastbe 5y ago
if you think of paxos/raft as having fault tolerance of losing n nodes, then the "decide what happens" part of 2 phase commit can be thought of as distributed consensus with a fault tolerance of 0 nodes. iirc leslie lamport has a paper that goes over this, and demonstrates that at n = 0 parts of paxos are vestigial and removing them directly maps to 2pc. EDIT: found it! https://lamport.azurewebsites.net/video/consensus-on-transaction-commit.pdf https://lamport.azurewebsites.net/video/consensus-on-transac... i am being a bit hand-wavey here because what the paper is talking about is an application of paxos to generate a new algorithm (paxos commit) that devolves to 2pc.
baskethead 5y ago
With two phase commit, once each member pre-commits, the only next state is for both all parties to actually commit. The entire system will wait forever until everyone commits. If one node that pre-commits blows up, the entire system is frozen until it commits. So it’s inherently a fragile system with indefinite outages if nodes go down or if the coordinator goes down.

Why are Paxos and/or Raft considered superior for distributed systems?

klysm 5y ago

Two phase commit has failure modes that paxos and raft address.

azurelake 5y ago
No, that's not correct. 2PC and paxos/raft solve different problems. 2PC is for distributed transactions across leaders / primaries. Paxos / Raft is for replication / consesus. Spanner is an example of a system that uses both.
- skyde 5y ago
  I agree with you but a better explanation I think is. Raft/Paxos is to make sure majority of the replica for a partition have the latest version of the data and that you can keep writing even if minority of nodes in that partition are unavailable. while still giving guarantee that no write get lost and all read reflect the most recent write. While 2PC is to write 2 records atomically when the 2 record are located on 2 different partitions.
- uvdn7 5y ago
  Yes, it is correct. At a distance both 2pc and paxos are solving the consensus problem - a group of entities agreeing on _something_. In the 2pc case, the _something_ is commit or not. In the paxos case, the _something_ is the chosen value. 2pc cannot handle coordinator failure, a single point of failure if you will. Transaction commit and replication are both consensus problems. You can use paxos for transaction commit as well. Lamport has a paper on a protocol called Paxos Commit.
  - azurelake 5y ago
    I see, guess I'm wrong then! What's the disadvantage of Paxos Commit vs 2PC? Presumably there's a reason that the Spanner team didn't use it for distributed transactions. edit: Looking at the paper, it looks like the tradeoff is increased amount of coordination needed. "The Two-Phase Commit protocol is thus the degenerate case of the Paxos Commit algorithm with a single acceptor." I suppose in Spanner, having more than one acceptor is redudant since each shard is a Paxos group anyways.
    - klysm 5y ago
      Spanner is in a rather unique technical position which enables it to sit outside the tradoff space of most distributed systems. You certainly pay for being robust against coordinator failure though.

uvdn7 5y ago

I don’t think Paxos is superior than 2pc. 2pc is dramatically simpler to implement. And if you layer 2pc on Paxos (something highly available) you can get the best of both worlds — simplicity and fault tolerance. The thing with Paxos is that it’s expensive and very hard to get right. So usually you have a very small but critical component that’s built on Paxos, then you compose the rest of the system on top with strong assumptions of the availability of the dependencies.

curtisf 5y ago

Two phase commit requires a coordinator. If the coordinator goes down, the system makes no progress. If the coordinator sends inconsistent commands (e.g., commit to one resource and abort to another), it's not serving its purpose. So in a system using two phase commit, your availability is limited by the availability of the coordinator. If the coordinator is a single server, you have a single point of failure in a distributed system. If you try using multiple servers to increase the availability of the coordinator, you risk sending inconsistent commands -- unless you implement a consensus system within the coordinator. Paxos and Raft let you combine the availability of multiple servers while still letting them behave consistently. (This is the "consensus problem", and correctly solving it is notoriously tricky).

dastbe 5y ago

if you think of paxos/raft as having fault tolerance of losing n nodes, then the "decide what happens" part of 2 phase commit can be thought of as distributed consensus with a fault tolerance of 0 nodes. iirc leslie lamport has a paper that goes over this, and demonstrates that at n = 0 parts of paxos are vestigial and removing them directly maps to 2pc. EDIT: found it! https://lamport.azurewebsites.net/video/consensus-on-transaction-commit.pdf https://lamport.azurewebsites.net/video/consensus-on-transac... i am being a bit hand-wavey here because what the paper is talking about is an application of paxos to generate a new algorithm (paxos commit) that devolves to 2pc.

baskethead 5y ago

With two phase commit, once each member pre-commits, the only next state is for both all parties to actually commit. The entire system will wait forever until everyone commits. If one node that pre-commits blows up, the entire system is frozen until it commits. So it’s inherently a fragile system with indefinite outages if nodes go down or if the coordinator goes down.