Two-Phase Commit
The overall idea of my implementation is pretty simple: the server is a coordinator, and all user nodes listen to its commands and response accordingly.
I will use 2 parts to analyze 2 Phase Commit. 2 Phase Commit is divided by a recording decision on the server side. Anything before this point is in Phase 1, anything else is in Phase 2. This point is so special because it is a promise the server made. Once the promise is made, the whole system would achieve this goal with all efforts.
The divide point is point 3 in Figure 1. Therefore, Phase 1 is before point 3, and including and after point 3 is Phase 2.
Figure 1. Tow Phase Commit
Phase 1
Analysis
[1] Anything before Point 1 is fine ⟾ Things are like never happened.
[2] Any network problem between Point 1 and Point 3 is fine ⟾ Phase 2 abort.
[3] The server dies between Point 1 and Point 3 ⟾ Phase 2 abort.
[4] User Nodes die between Point 1 and Point 2 ⟾ Phase 2 abort.
[5] User Nodes die between Point 2 and Point 3 ⟾ Server informs a decision in Phase 2.
[6] Everything works perfectly.
Summary
Server: crash before Point 3 ⟾ Phase 2 abort.
User Node: (1) Crash before Point 2 ⟾ Phase 2 abort; (2) Crash after Point 2 ⟾ Phase 2 waits a decision.
Therefore, if anything goes wrong in Phase 1, Phase 2 saves it.
Phase 2
Analysis
After reaching Point 3, the system gets into a stable state including the server and all user nodes. The server would retry until it receives all acknowledgements from all user nodes. When a user node receives a decision, there are several scenarios:
[1] User nodes didn’t vote ⟾ Ack anyway.
[2] User nodes voted ⟾ perform according to the decision, and Ack back.
[3] Duplicate Ack ⟾ Ack anyway.
Summary
The Acks of user nodes contain no information, but the user nodes have the knowledge about what they should do internally. Therefore, just a simple Ack handles everything perfectly. However, no matter what happens, the server would only stop until it receives all responses from user nodes.
Something about Code
The whole project contains 5 modules, which are Server, User Node, Message Module, Recovery Module, LogUtil, and Transaction Module.
The message module does message serialization before sending messages and deserialization after receiving messages.
The transaction module provides the state of each transaction, which is a part of the memory state. Any operation to a transaction is guaranteed to be thread-safe.
The LogUtil provides append methods for all kinds of transaction records. The append operation is guaranteed to be thread-safe. When a crash happens during appending, this record would be ignored.
The recovery module helps construct the exact memory state by using the log when a crash happens. It also provides a function to correctly parse transaction records. This function can identify unsuccessful append operations and ignore them when constructing the memory state. This module also collects garbage files. For example, At Point 3, there are two things that are put into stable storage, which are image files and a commit log record. If a crash happens between these two operations, the image file would be garbage-collected.
Server and User Node do the exact things that I mentioned in the analysis. After they start, they both must recover their memory state before they can do other things. For the server, after it restores its memory state, it would try to finish all uncommitted and committed but incomplete transactions by using multithreading. Each transaction would be handled by one thread. Therefore, it can handle requests in the meantime.
Github Repository for This Project: Two-Phase Commit