Module 10c - Distributed Commit and Checkpoints

Question 1

ACID is a collection of properties that we expect in a database. What does ACID stand for? What does each letter mean?

Answer 1

Atomicity - All the updates take effect or none of them do

Consistency - Constraints are preserved

Isolation - Concurrent transactions are unaware of each other

Durability - Updates made by committed transactions are not lost in the event of a failure

Question 2

The distributed commit problem concerns transaction _______ in a ________ environment

Answer 2

atomicity

distributed

Question 3

Achieving atomicity is easy in a centralized database, but it is harder in a distributed database. Why?

Answer 3

Different components of the database could fail independently during a transaction. that makes it difficult to make sure that updates took place at either all of them or none of them

Question 4

The coordinator is a _______ node which is responsible for ensuring ________

Answer 4

separate/independent

atomicity

Question 5

In a distributed database system, transaction commitment is initiated by a _________ after the transaction _________ phase, during which each _________ discovers whether they are able to commit the transaction or not

Answer 5

coordinator
execution
participant

Question 6

How do participants communicate to the coordinator on whether they should commit or abort a transaction?

Answer 6

The coordinator asks each participant for a vote on whether they should commit or abort the transaction globally

Question 7

What happens after the coordinator collects the votes from the participants?

Answer 7

The coordinator computes the global decision after collecting votes, and then shares the decision with the participants

Question 8

What must happen to the transaction if ANY of the participants vote to abort?

Answer 8

The transaction must abort globally whenever ANY participant votes to abort

Question 9

If there are no failures in the system, and every participant votes to commit, what must happen?

Answer 9

The transaction must commit globally whenever all participants vote to commit

Question 10

Two-phase commit (2PC) is a common solution based on two phases.

What happens during phase 1 of 2PC?

Answer 10

Phase 1:

Coordinator asks participants whether they are ready to commit. Participants respond with votes

Question 11

Two-phase commit (2PC) is a common solution based on two phases.

What happens during phase 2 of 2PC?

Answer 11

Phase 2:
Coordinator examines votes and decides the outcome of the transaction. If all participants vote to commit, then the transaction is committed successfully.

Otherwise it is aborted

Question 12

What are the 4 assumptions made with Two-phase commit (2PC)?

Answer 12

• Synchronous processes (can be executed without interruption from start to finish)
• Bounded communication delays
• Crash-recovery failures
• Processes have access to stable storage for logging recovery information

Question 13

What does the state transition diagram look like for the <strong>coordinator</strong> in Two-Phase commit (2PC)?

Answer 13

https://media.discordapp.net/attachments/213179086351106048/1003046928721924207/unknown.png

Question 14

What does the state transition diagram look like for the <strong>participant</strong> in Two-Phase commit (2PC)?

Answer 14

https://media.discordapp.net/attachments/213179086351106048/1003047663886929960/unknown.png

Question 15

In 2PC, what are the set of actions committed by a coordinator that can be used to create a coordinator program?

Answer 15

1. multicast “vote request” to all participants
2. listen in on all the votes from all the participants, record all the incoming votes.
3. If a timeout has been invoked, multicast “global abort” to all participants, and exit the program/process
4. If all participants sent “vote commit” to the coordinator AND the coordinator votes “commit”, then multicast “global commit” to all participants
5. Else (if #4 is not true), multicast “global abort” to all participants

Question 16

In 2PC, what are the set of actions committed by a participant that can be used to create a participant program?

Don’t include the daemon process that executes in the participant

Answer 16

1. Listen in on the coordinator, wait for a message from the coordinator
2. If a timeout is invoked, then abort and exit the program/process
3. Vote either commit or abort
4. If vote was to abort, then send “vote abort” to coordinator, abort the commit, and terminate the program
5. If vote was to commit, then send “vote commit” to coordinator, and then wait for decision from coordinator on whether a commit should be made or not. Decide to commit or abort accordingly
6. If a timeout is invoked while waiting for the coordinator to make a decision (no decision made), then multicast “decision request” to other participants, wait until decision is received, and commit or abort accordingly. Note that in this case, the participant may remain blocked forever while waiting for a decision from other participants.

Question 17

In 2PC, the participant executes a daemon process in the background in addition to its core procedure. What are the set of actions executed by this separate process?

Answer 17

Run the following in an infinite loop:

1. Block on waiting for an incoming “decision request” to come in from other participants
2. When unblocked, read the most recently recorded state from the local log
3. If the local log state is “global commit”, then send “global commit” back to that participant which the request was received from
4. If the local log state is “init” or “global abort”, then send a “global abort” back to the participant which the request was received from
5. Repeat step 1 infinitely

Question 18

In 2PC, if a participant does not receive a commit or abort decision from the _______, within a ________ period of time, then it may learn the decision from another ________

Answer 18

coordinator
bounded
participant

Question 19

In 2PC, when a participant P tries to learn the decision (or commit or abort) from another participant Q, what are the set of actions that P would make based on Q’s state being:

1. COMMIT
2. ABORT
3. INIT
4. READY

note that Q is the remote participant, whereas P is the local participant

Answer 19

1. On commit, P will make a transition to commit
2. On abort, P will make a transition to abort
3. On init, P will make a transition to abort
4. On ready, P will contact another participant

Note: whenever all participants are in state READY and they are asking around to see what the decision should be, the system will wait forever

Question 20

In 2PC, if the coordinator crashes, is a participant able to make progress?

How would the participant know what the decision should be to make progress on?

Answer 20

Yes the participant can make progress.

The participant would have to have received the decision from the coordinator despite the crash, or learn the decision from other participants

Question 21

In 2PC, Following a coordinator crashing, under what condition is it safe for a transaction to be committed?

Answer 21

If all participants voted to commit (all are in READY or COMMIT state), then it is safe to commit

Question 22

In 2PC, Following a coordinator crashing, under what condition is it safe for a transaction to be aborted?

Answer 22

If ANY of the participants are not in the COMMIT or READY state, then it is safe to abort

Question 23

In 2PC, what happens if both a coordinator and a participant crash?

Answer 23

A smarter implementation of 2PC is needed (outside the scope of this course)

Generally, the coordinator or the participant needs to wait for the other party to recover, reload its logs, and continue

Question 24

What is a distributed checkpoint?

Answer 24

A collection of checkpoints taken by numerous processes.

Allows inter-process communication and coordination

Question 25

What is a distributed snapshot in context to distributed checkpoints?

Answer 25

In a distributed snapshot, if a process P has recorded the receipt of a message, then there should also be a process Q that has recorded the sending of that message

Question 26

Why do we need distributed checkpoints?

Answer 26

If a part of a distributed system or the entire distributed system fails, then the checkpoint is used for recovery

Question 27

For distributed checkpoints, in what case is recovery possible?

Answer 27

Recovery is possible only if the collection of checkpoints taken by individual processes forms a distributed snapshot

Question 28

What is the most recent distributed snapshot is known as?

Answer 28

recovery line We use it in backwards error recovery

Question 29

How do we check if two checkpoints from two processes form an inconsistent collection of checkpoints? (not a distributed snapshot)

Answer 29

- We take the two process-local checkpoints in a distributed checkpoint. - We then connect them using a dashed line - If there is a message that is sent on the RIGHT side of the dashed line, but then is received on the LEFT side, then we have a violation of the distributed snapshot Otherwise, we have a distributed snapshot

Question 30

In distributed checkpoints, what is the domino effect?

Answer 30

If the most recent checkpoints taken by processes do not provide a recovery line, then successively earlier checkpoints must be considered. This can keep cascading back all the way until the initial states are reaches as the most recent distributed snapshot

Question 31

The "coordinated checkpointing algorithm" is used to deal with the ______ ______ in distributed checkpoints. It ensures that a ______ _____ is created

Answer 31

``` domino effect recovery line (or distributed snapshot) ```

Question 32

What happens in the 1st phase of the "coordinated checkpointing algorithm"?

Answer 32

Phase 1: 1. The coordinator sends a CHECKPOINT_REQUEST message to all processes 2. A process, upon receiving this message pauses sending new messages (temporarily creates a queue for all outgoing messages) 3. The process takes a local checkpoint (excluding messages in the queue since it is paused) 4. The process returns an acknowledgement to the coordinator that the checkpoint has been created

Question 33

What happens in the 2nd phase of the "coordinated checkpointing algorithm"?

Answer 33

Phase 2: 1. The coordinator will receive acknowledgements from all the processes that their checkpoints have been created 2. The coordinator multicasts CHECKPOINT_DONE to all processes 3. All processes resume processing messages (unpause their blocked queue)

Question 34

How does "coordinated checkpointing algorithm" ensure that there will always be a distributed snapshot created?

Answer 34

The coordinator sending a CHECKPOINT_REQUEST flag, and the receiving processes pausing all new messages until the CHECKPOINT_DONE flag is sent ensures that there cannot be any messages in between the dashed line when connecting checkpoints across processes