## 二、理论

### 1. Two-phase commit protocol

In transaction processing, databases, and computer networking, the two-phase commit protocol (2PC) is a type of atomic commitment protocol (ACP).

It is a distributed algorithm that coordinates all the processes that participate in a distributed atomic transaction on whether to commit or abort (roll back) the transaction (it is a specialized type of consensus protocol).

2PC是一种 协调所有参与分布式原子事务的进程 是否 提交或者放弃提交事务 的分布式算法。

The protocol achieves its goal even in many cases of temporary system failure (involving either process, network node, communication, etc. failures), and is thus widely used.[1][2][3] However, it is not resilient to all possible failure configurations, and in rare cases, user (e.g., a system’s administrator) intervention is needed to remedy an outcome.

To accommodate recovery from failure (automatic in most cases) the protocol’s participants use logging of the protocol’s states.

Log records, which are typically slow to generate but survive failures, are used by the protocol’s recovery procedures.

Many protocol variants exist that primarily differ in logging strategies and recovery mechanisms.

Though usually intended to be used infrequently, recovery procedures compose a substantial portion of the protocol,

due to many possible failure scenarios to be considered and supported by the protocol.

In a “normal execution” of any single distributed transaction ( i.e., when no failure occurs, which is typically the most frequent situation), the protocol consists of two phases:

1. The commit-request phase (or voting phase), in which a coordinator process attempts to prepare all the transaction’s participating processes (named participants, cohorts, or workers) to take the necessary steps for either committing or aborting the transaction and to vote, either “Yes”: commit (if the transaction participant’s local portion execution has ended properly), or “No”: abort (if a problem has been detected with the local portion),

1. and The commit phase, in which, based on voting of the cohorts, the coordinator decides whether to commit (only if all have voted “Yes”) or abort the transaction (otherwise), and notifies the result to all the cohorts. The cohorts then follow with the needed actions (commit or abort) with their local transactional resources (also called recoverable resources; e.g., database data) and their respective portions in the transaction’s other output (if applicable).

Note that the two-phase commit (2PC) protocol should not be confused with the two-phase locking (2PL) protocol, a concurrency control protocol.

#### Assumptions

The protocol works in the following manner: one node is a designated coordinator, which is the master site, and the rest of the nodes in the network are designated the cohorts.

The protocol assumes that there is stable storage at each node with a write-ahead log, that no node crashes forever, that the data in the write-ahead log is never lost or corrupted in a crash, and that any two nodes can communicate with each other.

The last assumption is not too restrictive, as network communication can typically be rerouted. The first two assumptions are much stronger; if a node is totally destroyed then data can be lost.

The protocol is initiated by the coordinator after the last step of the transaction has been reached. The cohorts then respond with an agreement message or an abort message depending on whether the transaction has been processed successfully at the cohort.

#### Basic algorithm

1. Commit request phase or voting phase

The coordinator sends a query to commit message to all cohorts and waits until it has received a reply from all cohorts.

coordinator 给所有的 cohorts 发送一个commit message 然后等到所有的 cohorts 回复。

The cohorts execute the transaction up to the point where they will be asked to commit. They each write an entry to their undo log and an entry to their redo log.

cohorts执行事务，那是他们将会被要求提交，他们各自写一个条目到他们的撤销日志和一个条目到他们的重做日志。

Each cohort replies with an agreement message (cohort votes Yes to commit), if the cohort’s actions succeeded, or an abort message (cohort votes No, not to commit), if the cohort experiences a failure that will make it impossible to commit.

1. Commit phase or Completion phase
• Success：If the coordinator received an agreement message from all cohorts during the commit-request phase:

The coordinator sends a commit message to all the cohorts.

coordinator 给所有的 cohorts 发送一个 commit message

Each cohort completes the operation, and releases all the locks and resources held during the transaction.

Each cohort sends an acknowledgment to the coordinator.

The coordinator completes the transaction when all acknowledgments have been received.

coordinator 收到所有的 acknowledgments 完成 transaction 。

• Failure：If any cohort votes No during the commit-request phase (or the coordinator’s timeout expires):

The coordinator sends a rollback message to all the cohorts.

Each cohort undoes the transaction using the undo log, and releases the resources and locks held during the transaction.

Each cohort sends an acknowledgement to the coordinator.

The coordinator undoes the transaction when all acknowledgements have been received.

1. Message flow
Coordinator                                         Cohort
QUERY TO COMMIT
-------------------------------->
VOTE YES/NO           prepare*/abort*
<-------------------------------
commit*/abort*                COMMIT/ROLLBACK
-------------------------------->
ACKNOWLEDGMENT        commit*/abort*
<--------------------------------
end


An * next to the record type means that the record is forced to stable storage.[4]

* 代表 record 已经强制刷新到 stable storage。

The greatest disadvantage of the two-phase commit protocol is that it is a blocking protocol. If the coordinator fails permanently, some cohorts will never resolve their transactions: After a cohort has sent an agreement message to the coordinator, it will block until a commit or rollback is received.

### Three-phase commit protocol

status Coordinator                              Cohort status
can COMMIT ?
-------------------------------->
VOTE YES/NO           Uncertain
<-------------------------------    timeout cause abort
commit authorized
precommit
-------------------------------->    prepare to commit
ACKNOWLEDGMENT
<--------------------------------
finalize commit               do COMMIT
timeout cause abort -------------------------------->
have COMMITED           commited
<--------------------------------
end