Two-phase commit
Two-phase Commit (2PC) : Ensure that a transaction maintains ACID properties when spanning multiple nodes; There are two types of nodes: Coordinator and Participants. There is only one Coordinator and several Participants.
Process:
1. Preparation phase: The coordinator asks the participant whether the transaction has been successfully executed;
2. Commit phase: If the transaction is successfully executed on each participant, the coordinator sends a notification for the participant to commit the transaction; Otherwise, the coordinator sends a notification to the participant to roll back the transaction.
It is important to note that in the preparation phase, the participant executes the transaction but has not committed it yet. Commit or rollback occurs only after notification from the coordinator is received during commit phase.
Existing problems
1. The participant is faulty. Solution: You can set a timeout period for the transaction, and if one of the participants never responds, the transaction is considered to have failed.
2. The coordinator is faulty. Solution: Synchronize the operation logs to the standby coordinator and let the standby coordinator take over.
Paxos
There are two models for node communication in distributed system: Shared memory and message passing.
In distributed systems based on the messaging communication model, the following errors are inevitable: processes may slow, be killed, or restart, messages may be delayed, lost, or repeated, leaving aside the possibility of message tampering, or Byzantine errors, in the basic Paxos scenario.
The Paxos algorithm solves the problem of how to reach agreement on a value in a distributed system where the above exceptions may occur, ensuring that no matter what happens, the consistency of the resolution will not be broken.
There are three main types of nodes:
1. Proposer (Proposer) : proposes a value;
2. Acceptors: vote on each proposal;
3. A Learner is told the result of a vote and does not participate in the voting process.
Process:
Specify that a proposal contains two fields: [n, v], where n is the ordinal number (unique) and v is the proposal value.
The following diagram illustrates the initial process of running this algorithm on a system with two proposers and three acceptors, each of which sends a proposal request to all acceptors.
When an Acceptor receives an Acceptor request for an offer numbered [N1,v1] and has not previously received an offer, it sends an offer response with the received offer set to [n1,v1] and guarantees that it will not accept any proposal numbered less than N1.
An Acceptor X sends a [no previous] offer response to an Acceptor X request for a previous offer, and sets the current received offer to [n=2, v=8]. And promised not to accept any proposal with a serial number less than 2 again. Other acceptors are similar.
If an Acceptor accepts a proposal for [n2, v2] that has previously received an offer for [N1, v1]. If n1 >n2, the proposal request is discarded; Otherwise, send the proposal response containing the previously received proposal [N1, v1]. Set the received proposal to [n2,v2], and ensure that the proposal whose serial number is less than N2 will not be accepted in the future.
(A) An Acceptor Z receives A proposal (n=2, v=8) from A Proposer (n=4, v=5) with n > 2. Acceptor X receives a Proposer request (n=4, v=5) from a Proposer (n=2, v=8). If an Acceptor X receives a proposal (n=2, v=8) from a Proposer (n=2, v= 4), it sends a proposal (n=2, v=8). Set the current received proposal to [n=4,v=5] and ensure that the proposal whose sequence number is less than 4 will not be accepted in the future. Acceptor Y is similar.
A Proposer sends an accept request when it receives more than half of the proposals received from acceptors. A Proposer A receives two proposals and sends [n=2, v=8] to accept the request. This acceptance request is discarded by all acceptors because all acceptors at this point promise not to accept proposals with a serial number less than 4.
Proposer B then receives two proposals and starts sending acceptance requests as well. Note that the v that accepts the request needs to take the maximum value of V it receives, which is 8. So it sends the accept request [n=4, v=8].
An Acceptor sends a notification to all users if the Acceptor receives an acceptance request with a sequence number greater than or equal to the minimum promised sequence number. When Learner detects that a majority of acceptors have accepted a proposal, the proposal value is selected by Paxos.
Raft
Simplified, easier to understand and easier to implement.
Introduce the master node and pass the election. Node types: Follower, Candidate, and Leader The Leader periodically sends heartbeat packets to the followers. Each Follower sets a random campaign timeout period, usually 150ms to 300ms. If the Follower does not receive a heartbeat packet from the Leader within this period, it becomes a Candidate and enters the campaign phase.
Process:
① The following figure shows the initial stage of a distributed system, where there are only followers but no Leader. Follower A waits for A random campaign timeout and does not receive the heartbeat packet from the Leader, so Follower A enters the campaign.
② At this point, A sends the voting request to all other nodes.
③ The other nodes respond to the request, and if more than half of them respond, the Candidate becomes the Leader.
(4) The Leader then periodically sends heartbeat packets to the followers. After receiving the heartbeat packets, the followers start the timer again.
Multiple candidates
(1) If multiple followers become candidates and get the same number of votes, a new poll is needed. For example, Candidate B and Candidate D both get two votes, so a new poll is needed.
② When the voting starts again, the random election timeout time set by each node is different, so the probability of multiple candidates appearing again and getting the same votes is very low.
Log copy
① All changes from the client are passed to the Leader. Note that the change has not yet been committed, but is just written to the log.
② The Leader copies the changes to all followers.
③ The Leader waits for most followers to make changes before committing the changes.
(4) At this point, the Leader will notify all followers to submit the modification, and the values of all nodes are consistent.
The last
I have arranged a: Java core knowledge points, Java systematic information, interview topics and 20 years of the latest Internet real questions, e-books, etc.) need friends can pay attention to the public number [Process xu Yuan xiao Wan] can obtain.