1 of 42

CS W186 Exam Prep 11

Distributed Transactions

2 of 42

Distributed

Transactions

3 of 42

Distributed Computing

In shared-nothing parallelism, data is partitioned over multiple nodes

Operations may span multiple nodes

Spread the locks with the data to the different machines

Each machine tracks its own waits-for graph
Use union of these graphs to check global deadlock

How do we commit/abort a transaction?

If any node has a problem (e.g. there’s a deadlock on one node’s pages, and the transaction has to be aborted), we cannot get all changes saved

Atomicity: either all or nothing

Need consensus on whether to commit the transaction

Primarily, we use a shared-nothing parallel architecture. That means we have no shared memory or disk, and data is partitioned over multiple nodes in a network.

As we discussed in parallel query processing, operations may span multiple nodes

As a result, all concurrency protocols like locks are spread across multiple machines, and each machine tracks its own waits-for graph.

We must union these graphs to check for a global deadlock across multiple machines.

Given these constraints, the question we want to answer is, “How do we get all nodes to agree on something? For 186, the motivating problem is, how do we implement a distributed commit or abort?”.

If any node has a problem, like if there’s a deadlock on one node or it becomes unresponsive, we must globally abort all nodes.

The reason for this is we still want to guarantee atomicity of our transactions––it’s either all or nothing!

So, we need a protocol for multiple machines to reach a consensus.

4 of 42

2 Phase Commit (2PC)

Solution: Distributed voting: 2 Phase Commit (2PC)

Agreement
Finality (atomicity)

5 of 42

2 Phase Commit (Algorithm)

Setup

One coordinator
Set of participants

6 of 42

2 Phase Commit (Algorithm)

Phase 1: Prepare (Agreement)

Coordinator receives request
Coordinator broadcasts “PREPARE”
Participants log + flush their decision
Participants send decision to coordinator

7 of 42

2 Phase Commit (Algorithm)

Phase 2: Commit (Finality)

Coordinator log + flush decision (all or nothing)
Coordinator broadcasts “COMMIT”
Participants log + flush “COMMIT”
Participants send “ACK”

8 of 42

2 Phase Commit (Algorithm)

Participant Algorithm

9 of 42

Handling Failures

Assume ARIES recovery

Participant “down”
Coordinator “down”

10 of 42

Handling Failures: Participant “down”

Abort

Wait….

11 of 42

Handling Failures: Coordinator “down”

NO

???

12 of 42

Two-Phase Commit (2PC): Logging

Phase 1 (voting)

Coordinator → Participants: PREPARE message
Participants: log and flush either a PREPARE or ABORT record to log

log entry keeps track of coordinator ID
if a participant votes NO, it knows for sure the transaction will abort, and can begin cleaning up the transaction immediately

Participants → Coordinator: VOTE YES or VOTE NO
Coordinator: log and flush either a COMMIT or ABORT record to log

commit and abort log entry contains all participant IDs

13 of 42

Two-Phase Commit (2PC): Logging

Phase 2 (results)

Coordinator → Participants: COMMIT or ABORT message
Participants: log and flush COMMIT or ABORT record to log
Participants → Coordinator: ACK message
Coordinator: log (no immediate flush required) END record to log and remove from transaction table

14 of 42

Two-Phase Commit (2PC): Logging

Coordinator

commit* or abort*

(with participant IDs)

end

Participant

prepare* or abort*

(with coordinator ID)

commit* or abort*

* indicates that the record must be flushed to disk immediately

PREPARE

VOTE YES/NO

COMMIT/ABORT

ACK

15 of 42

Two-Phase Commit (2PC): Optimization

Problem: ACK message is used by coordinator to decide when we can “forget” about a transaction (delete from transaction table)

Must keep transaction around until it receives all ACKs

Opt: If coordinator crashes after sending out PREPARE messages, we unilaterally abort the transaction (coordinator can vote no on it), and tell anyone that asks that it has aborted

We abort in absence of information

16 of 42

Two-Phase Commit (2PC): Optimization

Presumed abort: assume that a transaction aborts if we have no log records (and reduce messages sent/logging as a result)
When a transaction aborts,

Coordinator cleans up locally, and can remove transaction from table
Participants that receive ABORT messages do not send ACKs
If Participants don’t hear from Coordinator about status, send inquiry - if transaction not in coordinator’s transaction table, return ABORT
Participant IDs do not need to be stored in abort records (since we aren’t waiting for ACKs)
Abort records do not need to be flushed (if we crash, and don’t see an abort record, we still assume it aborts)

Presumed abort says to assume a transaction aborts if we have no log records.

The benefit is we reduce messages sent and minimize memory usage for each node’s log manager.

It works like this: when a transaction aborts,

The coordinator cleans up locally and removes the transaction from their table. The coordinator then broadcasts a global abort message to the participant nodes
Participants don’t need to send ACK statements back
If a participant was down, they can send an inquiry to the coordinator. The coordinator then responds with an ABORT message since the transaction isn’t in her transaction table
The participant IDs don’t need to be stored in abort records, since we aren’t waiting for acknowledge responses.
Abort records also don’t need to be flushed, since we presume abort!

17 of 42

Two-Phase Commit (2PC): Optimization

Coordinator

commit*

(with participant IDs)

or abort

end

(if commit)

Participant

prepare* or abort

(with coordinator ID)

commit* or abort

* indicates that the record must be flushed to disk immediately

PREPARE

VOTE YES/NO

COMMIT/ABORT

ACK (if commit)

18 of 42

Two-Phase Commit (2PC): Blocking

What happens when a node goes down during the first phase?

Any participant that voted yes has to keep locks, waiting for commit/abort message

What if a participant doesn’t recover?

Coordinator can respawn participant + recover from log, and we can continue
(if old participant comes up again, tell it to recycle itself)

What if the coordinator doesn’t recover?

Pretty much screwed
See: 3PC (not in scope), Paxos (in scope)

The last note I want to make is that 2PC is a blocking protocol.

If a node goes down during the phase one of 2PC, any participant that voted has to keep their locks while they wait for the global commit or global abort message from the coordinator.

If a participant never recovers, the coordinator can respawn a new participant, recover the log from disk, then we can easily continue with the transaction. If that old participant revives some time later, we can tell it to recycle itself as we no longer need him.

However, if the coordinator doesn’t recover after a commit, we’re pretty much screwed! However, there are 3 phase commit algorithms like Paxos that handle the case where the coordinator fails. These protocols, however, are not in scope for this class.

---------------

For coordinator node going down before commit, with all participants up:

It’s possible to handle this case, by having the participants all agree to abort after some timeout (since all participants are up: can see that no one has received a COMMIT message)

If coordinator + participant down:

We can’t continue - we can’t tell if the participant that went down received a COMMIT message and carried it out or not - have to wait until they come back up

Participants all vote YES, coordinator sends out COMMIT to one participant then dies, the participant that receives the COMMIT writes commit to log then dies - remaining participants cannot tell if this is the case, or if coordinator died before sending out COMMITs

19 of 42

Last tip: Solving 2PC Problems

In this class, it’s most often the case that we ask you how long it takes to commit or abort a transaction under certain conditions. Because of this component of time, here is my recommended way of working through problems.

Here’s a common question that we ask to test your understanding:

“Suppose we have one coordinator and three participants”. At this point, I immediately visualize a setup like so, where the top line is the coordinator and the bottom three lines are the participants.
Then, we’ll get some information on how long messages take to send. To visualize time, I draw lines from the coordinator to the participants where the horizontal width is our component of time. In this case, we know that it takes 30 ms for a coordinator to send messages to all participants.
Assuming no failures, we can draw out our participants logging in their commit decisions, each taking 10 ms to do so. Then, they proceed to send their response to the coordinator. The first takes 5 ms, the second takes 10 ms, the third takes 15 ms.

For the sake of time, I won’t go through the entire problem, but hopefully this gives you all an idea of how to practically approach and solve 2PC problems.

20 of 42

Worksheet

21 of 42

Question 1

22 of 42

Question 1a

True or False: Resolving a deadlock at a local node will always resolve distributed deadlock.

False. Distributed deadlock occurs whenever the union of waits-for graphs across different nodes contains cycles. Resolving one deadlock may not solve deadlock in the union of the nodes' waits-for graphs.

23 of 42

Question 1b

True or False: Suppose we make the changes needed so only a majority of participants need to vote yes for a transaction to commit. Participants can write an ABORT record in phase 1 of 2PC.

False. Participants can't unilaterally abort anymore in this new scenario. The aborting participant can't determine the result of the vote by itself, so the participant must receive the result of the vote from the leader.

24 of 42

Question 1c

True or False: Presumed abort as presented in lecture no longer works in the scenario described in 1b.

True. If a participant crashes after voting no in phase 1, with presumed abort, no ABORT record will be flushed to disk. Coming back online, the participant would ordinarily presume abort, but in the scenario described, this may not be the case if the majority still votes to commit.

25 of 42

Question 1d

True or False: If any machine sees COMMIT record in its log upon recovery, the transaction will commit. Additionally, describe how to distinguish whether a machine with a COMMIT record is a coordinator or participant.

True. Whether participant or coordinator, a node seeing a COMMIT record in its log on recovery must take the actions.

If the commit record holds the participantIDs, then we know the machine must be a coordinator. Additionally, if this coordinator doesn't have an END record and only a COMMIT, it must send the result of the vote to all the participants. If there is a PREPARE record alongside the COMMIT record, then we know the node must be a participant.

26 of 42

Question 2a

Describe what happens in the following scenario with and without presumed abort: Participant recovers and sees just a phase 1 ABORT record.

Without presumed abort: Send "no" to the coordinator.

With presumed abort: Nothing! The coordinator will presume abort.

27 of 42

Question 2b

Describe what happens in the following scenario with and without presumed abort: Participant recovers and sees a PREPARE record.

The case is the same with or without presumed abort. The participant will ask the coordinator the result of the vote and continue the process.

28 of 42

Question 2c

Describe what happens in the following scenario with and without presumed abort: Participant recovers and sees a PREPARE and phase 2 ABORT record

Without presumed abort: Participant will send ACK back to the coordinator.

With presumed abort: Participants don't need to do anything after an abort record that was the result of the vote.

29 of 42

Question 2d

Describe what happens in the following scenario with and without presumed abort: Coordinator recovers and sees an ABORT record

Without presumed abort: Inform the participants about the outcome of the vote.

With presumed abort: Nothing! (Participants who don’t know the decision will just ask later.)

30 of 42

Question 2

31 of 42

Question 1

What is the first message Machine 1 sends?

VOTE YES
PREPARE
COMMIT
None of the above

Answer: (b) PREPARE. The coordinator (i.e. Machine 1) begins the first round of two-phase commit by sending a PREPARE message to all of the subordinates.

M1: Coordinator M2-4: Participants

32 of 42

Question 2

What is the second message Machine 1 sends?

VOTE YES
PREPARE
COMMIT
None of the above

Answer: (c) COMMIT. The coordinator (i.e. Machine 1) begins the second phase of two-phase commit by sending a COMMIT message to all of the subordinates. Note that the problem states that all subordinates vote yes in the first round which is why the coordinator sends a COMMIT message (instead of an ABORT message) to start the second round.

M1: Coordinator M2-4: Participants

33 of 42

Question 3

How much time passes from when Machine 1 sends its first message to when Machine 1 sends its second message?

Answer: This is just the maximum time for a round-trip between Machine 1 and Machines 2–4, since Machine 1 sends its second message (COMMIT) once its first message (PREPARE) reaches each of the other machines and each of the machines respond back with a VOTE YES message.

The time for a round-trip between Machine 1 and Machine i is 2 · 100 · i, and the largest of these is with Machine 4: 2 · 100 · 4 = 800ms.

M1: Coordinator M2-4: Participants

34 of 42

Question 4

What is the first message Machine 2 sends?

VOTE YES
PREPARE
COMMIT
None of the above

Answer: (a) VOTE YES. A subordinate (e.g. Machine 2) responds to a PREPARE message from the coordinator with a VOTE YES or VOTE NO. The problem states that all subordinates vote yes, so Machine 2 sends a VOTE YES message.

M1: Coordinator M2-4: Participants

35 of 42

Question 5

What is the second message Machine 2 sends?

VOTE YES
PREPARE
COMMIT
None of the above

Answer: (d) None of the above. The second message Machine 2 (a participant) sends is an ACK.

M1: Coordinator M2-4: Participants

36 of 42

Question 6

How much time passes from when Machine 2 sends its first message to when Machine 2 sends its second message?

Answer: Let’s have Machine 1 send the PREPARE message at time 0. This PREPARE message will reach Machine 2 at time 200ms, so Machine 2 sends its first message (VOTE YES) at time 200ms.

Machine 1 sends the COMMIT message at time 800ms (when it hears back from Machine 4), and this message takes 200ms to reach Machine 2. Machine 2 therefore receives the COMMIT message at time 1000ms, and sends its second message (ACK).

The time passed is therefore 1000ms - 200ms = 800ms.

M1: Coordinator M2-4: Participants

37 of 42

Question 7

True or False. A transaction is considered committed even if over half of the participants do not acknowledge the commit.

Answer: True. A transaction must commit once the COMMIT message is sent out, even if all the participants promptly crash repeatedly and do not respond with ACKs as a result.

M1: Coordinator M2-4: Participants

38 of 42

Question 8

Now suppose that our implementation of 2-Phase Commit has an off-by-one bug where the Coordinator receives, but does not use, Machine 4’s vote. That is, Machine 4’s vote does not affect whether or not the transaction commits or aborts. Answer True or False for the following questions:

A transaction that should normally commit may be aborted instead.

Answer: False. If the transaction would normally commit, then Machines 2 and 3 must have been functional and voted yes, so the transaction would still have to commit with this bug.

M1: Coordinator M2-4: Participants

39 of 42

Question 9

Now suppose that our implementation of 2-Phase Commit has an off-by-one bug where the Coordinator receives, but does not use, Machine 4’s vote. That is, Machine 4’s vote does not affect whether or not the transaction commits or aborts. Answer True or False for the following questions:

A transaction that should normally abort may be committed instead.

Answer: True. If Machine 4 votes no and other participants vote yes, then the transaction should be aborted but commits anyways.

M1: Coordinator M2-4: Participants

40 of 42

Question 10

Now suppose that our implementation of 2-Phase Commit has an off-by-one bug where the Coordinator receives, but does not use, Machine 4’s vote. That is, Machine 4’s vote does not affect whether or not the transaction commits or aborts. Answer True or False for the following questions:

A transaction that should normally commit may be committed properly.

Answer: True. If all machines vote yes, then the transaction commits even if we ignore Machine 4’s vote.

M1: Coordinator M2-4: Participants

41 of 42

Question 11

Now suppose that our implementation of 2-Phase Commit has an off-by-one bug where the Coordinator receives, but does not use, Machine 4’s vote. That is, Machine 4’s vote does not affect whether or not the transaction commits or aborts. Answer True or False for the following questions:

A transaction that should normally abort may be aborted properly.

Answer: True. If Machine 2 or 3 votes no, then the transaction aborts in both cases.

M1: Coordinator M2-4: Participants

42 of 42

Attendance Link

https://cs186berkeley.net/attendance