7 ms·

Two Phase Commit

97 points by clockworksoul 5y ago

pthread_t 5y ago
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.
The_rationalist 5y ago
amdelamar 5y ago
I think there's a good analogy to a wedding ceremony I read from DDIA. "Do you take X? I do. And do you take Y? I do. I now pronounce you X+Y".
- hashimotonomora 5y ago
  Not all religions follow two phase commit protocols.
  - tpoacher 5y ago
    By all means, feel free to come up with a throuple git analogy xD
deleted 5y ago
[deleted]
cyounkins 5y ago
Is there any documented pattern or middleware for doing transactional updates across multiple HTTP services? That is, commit a write to serviceA and a write to serviceB together, atomically?
- dilatedmind 5y ago
  depending on how you define transaction, this doesn't seem possible? my approach has been to make all operations idempotent and ensure they are all ran at least once.
  - adanto6840 5y ago
    I'm probably out of my element here, it's been a while, but... does that not scream "race condition" concern? Obviously it's going to be application-specific; given the context though, are you just expecting "validation" from the 'other' side (ie reject requests with old checksums/timestamps) maybe? Or is this just a highly-theoretical example/mindset?
    - hderms 5y ago
      I think an example of what the commenter is describing is something like: 1. User clicks "buy now" for whatever is in their shopping cart 2. Client generates some kind of transaction ID representing that they wanted to purchase the contents of the shopping cart (could be deterministic ID) 3. Client submits this request to the server 4. Server persists the intention to start processing the purchasing of the shopping cart with transaction ID of X 5. Server synchronously or asynchronously starts handling the side effects of the purchase 6. If at some point the client got an error message it can still submit the same request with the same transaction ID to retry and even if the initial request was received (but perhaps lost before getting to the client) it's cheap and easy to make it idempotent by using the transaction ID Race conditions would be made more difficult by having everything idempotent based on the transaction ID and having the transaction ID (optionally) generated deterministically. 2 phase commit is an extremely heavy weight pattern and finds far less use than something like the above.
olalonde 5y ago
I always wondered how 2 phase commit fits in with the CAP theorem. What if one node receives the commit message but the transaction manager crashes before it can send the other commit messages? Won't the system be (at least temporarily) inconsistent?
- dagenix 5y ago
  Even without a crash, one of the transactions will be completed before the other ones. If the coordinator crashes, one (or all) of the transactions will be stuck until the coordinator comes back - or, if it never does - until someone manually rolls them all back of commits them all.
- judofyr 5y ago
  This might be a bit confusing, but "consistency" in CAP doesn't have one "strict" definition. It can be roughly defined as "a request will either return the correct response or return an error", but you'll find that the CAP theorem will apply to different variations of "correct response". There are some super exact definitions where we've formally proved it, but there are also plenty of variations where the theorem "obviously" applies as well. If your definition of "consistency" is "read will always returns the latest value which is accepted by all nodes in the first phase" you'll always have to contact all nodes when you're reading the data (since as you mentioned you can't actually depend on if it's been "committed"). This is "CP" because you "tolerate" a network partitioning by having the read return an error if it can't reach all nodes. But you can "tweak" your definition of "consistency" to be "reads will read the latest committed value on that node". CAP still applies for the system as a whole (with writes), but now you can serve fast reads from a single node. Many systems defines "read consistency" as "snapshot isolation" which means (roughly) that all requests inside a single transaction will be executed against a single snapshot (which possibly isn't the "latest" one). This will also allow you to execute reads against a single node.
  - righttoolforjob 5y ago
    Have to disagree here. In CAP C means linearizable, meaning the operation happens somewhere in the time between you sending the request and receiving the response. That's why you have to select between C or A, because in the presence of P you cannot get both. If the node with the latest value is unavailable to you, then you cannot fetch it, thus either you get nothing (C, not A) or you accept the stale value (A, not C).

Two Phase Commit

97 points by clockworksoul 5y ago

pthread_t 5y ago

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.

The_rationalist 5y ago

amdelamar 5y ago

I think there's a good analogy to a wedding ceremony I read from DDIA. "Do you take X? I do. And do you take Y? I do. I now pronounce you X+Y".

hashimotonomora 5y ago
Not all religions follow two phase commit protocols.
- tpoacher 5y ago
  By all means, feel free to come up with a throuple git analogy xD

deleted 5y ago

[deleted]

cyounkins 5y ago

Is there any documented pattern or middleware for doing transactional updates across multiple HTTP services? That is, commit a write to serviceA and a write to serviceB together, atomically?

dilatedmind 5y ago
depending on how you define transaction, this doesn't seem possible? my approach has been to make all operations idempotent and ensure they are all ran at least once.
- adanto6840 5y ago
  I'm probably out of my element here, it's been a while, but... does that not scream "race condition" concern? Obviously it's going to be application-specific; given the context though, are you just expecting "validation" from the 'other' side (ie reject requests with old checksums/timestamps) maybe? Or is this just a highly-theoretical example/mindset?
  - hderms 5y ago
    I think an example of what the commenter is describing is something like: 1. User clicks "buy now" for whatever is in their shopping cart 2. Client generates some kind of transaction ID representing that they wanted to purchase the contents of the shopping cart (could be deterministic ID) 3. Client submits this request to the server 4. Server persists the intention to start processing the purchasing of the shopping cart with transaction ID of X 5. Server synchronously or asynchronously starts handling the side effects of the purchase 6. If at some point the client got an error message it can still submit the same request with the same transaction ID to retry and even if the initial request was received (but perhaps lost before getting to the client) it's cheap and easy to make it idempotent by using the transaction ID Race conditions would be made more difficult by having everything idempotent based on the transaction ID and having the transaction ID (optionally) generated deterministically. 2 phase commit is an extremely heavy weight pattern and finds far less use than something like the above.

olalonde 5y ago

I always wondered how 2 phase commit fits in with the CAP theorem. What if one node receives the commit message but the transaction manager crashes before it can send the other commit messages? Won't the system be (at least temporarily) inconsistent?

dagenix 5y ago
Even without a crash, one of the transactions will be completed before the other ones. If the coordinator crashes, one (or all) of the transactions will be stuck until the coordinator comes back - or, if it never does - until someone manually rolls them all back of commits them all.
judofyr 5y ago
This might be a bit confusing, but "consistency" in CAP doesn't have one "strict" definition. It can be roughly defined as "a request will either return the correct response or return an error", but you'll find that the CAP theorem will apply to different variations of "correct response". There are some super exact definitions where we've formally proved it, but there are also plenty of variations where the theorem "obviously" applies as well. If your definition of "consistency" is "read will always returns the latest value which is accepted by all nodes in the first phase" you'll always have to contact all nodes when you're reading the data (since as you mentioned you can't actually depend on if it's been "committed"). This is "CP" because you "tolerate" a network partitioning by having the read return an error if it can't reach all nodes. But you can "tweak" your definition of "consistency" to be "reads will read the latest committed value on that node". CAP still applies for the system as a whole (with writes), but now you can serve fast reads from a single node. Many systems defines "read consistency" as "snapshot isolation" which means (roughly) that all requests inside a single transaction will be executed against a single snapshot (which possibly isn't the "latest" one). This will also allow you to execute reads against a single node.
- righttoolforjob 5y ago
  Have to disagree here. In CAP C means linearizable, meaning the operation happens somewhere in the time between you sending the request and receiving the response. That's why you have to select between C or A, because in the presence of P you cannot get both. If the node with the latest value is unavailable to you, then you cannot fetch it, thus either you get nothing (C, not A) or you accept the stale value (A, not C).