3 ms·

Perhaps I'm not getting the main point right. Looks like the proposal is a minor optimization of the 2PC protocol, where a worker ACKs the transaction as soon a

by pacala 8y ago

Perhaps I'm not getting the main point right. Looks like the proposal is a minor optimization of the 2PC protocol, where a worker ACKs the transaction as soon as possible, presumably somewhere between updating the durable log and updating the durable data. However, said worker cannot proceed to execute a subsequent transaction depending on the updated data until the 2PC protocol completes, because _another_ worker may abort the original transaction for perfectly logical reasons, as opposed to transient failure reasons.

abadid 8y ago
I should have made this point clearer in the post. 2PC requires 2 round trip messages per worker (i.e. 4 total messages per worker), of which the 3rd message cannot be sent until there is a global synchronization point. The proposal replaces the 2 round trip messages with a half a round trip, which is overlapped with transaction processing. And there is no global synchronization point.
bothra90 8y ago
The author is arguing that we can always rewrite the txn logic such that (at least in the deterministic case) if one worker decides to commit, all others will do so too. So a worker can proceed independently without other workers needing to finish their share of work and entering the commit protocol. The article doesn't go into exactly how this could work in the case of non-deterministic txns, but the linked papers may have an answer.
- pacala 8y ago
  Perhaps I'm not getting the setup right. Assuming that data is partitioned between worker A and worker B, I see no way to rewrite a distributed transaction to proceed based strictly on information available to A or to B. T( A.x = A.x - 1, B.y = B.y - 1, ) under constraints: A.x >= 0 B.y >= 0 What is the rewrite for the above transaction?
  - abadid 8y ago
    On A: temp = remote read of y; if (temp >=1 && x >= 1) A.x = A.x - 1; On B: temp = remote read of x; if (temp >=1 && y >= 1) B.y = B.y - 1; I simplified the code a little by checking on the old value of x and y instead of the new one, but I could have written the code to check on the new value instead.
    - j16sdiz 8y ago
      We can't do this on a modern NUMA computer. Good luck trying across different system.
    - lurker458 8y ago
      Is the cost of doing these remote reads worth the savings in this case ? After all to be correct, they need to run in the same transaction at the sending side and need to be persisted at the receiving side. Also, consider the effort if this gets scaled up to 10 cases (each node would have to do 9 remote reads)
      - abadid 8y ago
        They don't need to be persisted at the received side, but yes, there could be 9 remote reads if each of 10 shards are running code that may result in state-based aborts. Usually, however, only a subset of the shards run such code. But remember, 2PC requires 4 messages per worker (so 40 messages total in your example).
        lurker458 8y ago
        True, but it's O(n^2) complexity instead of O(n) complexity (1000 shards would lead to 1M reads instead of 4k) If they're not persisted at the receiving side, how does it handle a crash before committing on the receiving node ? Keeping previous versions indefinitely on sending nodes to permit requesting the old values doesn't work, so this introduces a time bound on how long a crashed node has to recover (granted, this could still mean weeks)

by pacala 8y ago

abadid 8y ago

I should have made this point clearer in the post. 2PC requires 2 round trip messages per worker (i.e. 4 total messages per worker), of which the 3rd message cannot be sent until there is a global synchronization point. The proposal replaces the 2 round trip messages with a half a round trip, which is overlapped with transaction processing. And there is no global synchronization point.

bothra90 8y ago

The author is arguing that we can always rewrite the txn logic such that (at least in the deterministic case) if one worker decides to commit, all others will do so too. So a worker can proceed independently without other workers needing to finish their share of work and entering the commit protocol. The article doesn't go into exactly how this could work in the case of non-deterministic txns, but the linked papers may have an answer.

pacala 8y ago
Perhaps I'm not getting the setup right. Assuming that data is partitioned between worker A and worker B, I see no way to rewrite a distributed transaction to proceed based strictly on information available to A or to B. T( A.x = A.x - 1, B.y = B.y - 1, ) under constraints: A.x >= 0 B.y >= 0 What is the rewrite for the above transaction?
- abadid 8y ago
  On A: temp = remote read of y; if (temp >=1 && x >= 1) A.x = A.x - 1; On B: temp = remote read of x; if (temp >=1 && y >= 1) B.y = B.y - 1; I simplified the code a little by checking on the old value of x and y instead of the new one, but I could have written the code to check on the new value instead.
  - j16sdiz 8y ago
    We can't do this on a modern NUMA computer. Good luck trying across different system.
  - lurker458 8y ago
    Is the cost of doing these remote reads worth the savings in this case ? After all to be correct, they need to run in the same transaction at the sending side and need to be persisted at the receiving side. Also, consider the effort if this gets scaled up to 10 cases (each node would have to do 9 remote reads)
    - abadid 8y ago
      They don't need to be persisted at the received side, but yes, there could be 9 remote reads if each of 10 shards are running code that may result in state-based aborts. Usually, however, only a subset of the shards run such code. But remember, 2PC requires 4 messages per worker (so 40 messages total in your example).
      - lurker458 8y ago
        True, but it's O(n^2) complexity instead of O(n) complexity (1000 shards would lead to 1M reads instead of 4k) If they're not persisted at the receiving side, how does it handle a crash before committing on the receiving node ? Keeping previous versions indefinitely on sending nodes to permit requesting the old values doesn't work, so this introduces a time bound on how long a crashed node has to recover (granted, this could still mean weeks)