Shulou(Shulou.com)06/02 Report--

This article mainly explains "what is Java distributed consistency protocol and Paxos,Raft algorithm". The content of this article is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn "what is Java distributed consistency protocol and Paxos,Raft algorithm".

2PC

Because BASE theory needs to make a tradeoff between consistency and usability, many algorithms and protocols about consistency have emerged. Among them, the more famous are the second-order commit protocol (2 Phase Commitment Protocol), the third-order commit protocol (3 Phase Commitment Protocol) and the Paxos algorithm.

The 2PC protocol to be introduced in this article is divided into two phases to commit a transaction. And through the cooperation of the coordinator and various participants to achieve distributed consistency.

The two-phase transaction commit protocol is completed jointly by the coordinator and the participants.

Role XA Conceptual function

The coordinator transaction manager coordinates various participants to commit or roll back distributed transactions

Nodes in a distributed cluster of participant resource managers

1. Distributed transaction

Distributed transaction refers to the transaction that involves operating multiple databases, which actually extends the concept of the same database transaction to the transaction of multiple databases. The purpose is to ensure the data consistency in the distributed system.

The key to distributed transaction processing is:

All actions done by the transaction at any node need to be recorded.

All operations performed by the transaction are either committed or rolled back.

2. XA specification

2.1. The composition of the XA specification

The XA specification is a distributed transaction processing model defined by the X/Open organization (now Open Group). The X/Open DTP model (1994) includes:

Application (AP)

Transaction manager (TM): transaction middleware, etc.

Resource Manager (RM): relational databases, etc.

Communication Resource Manager (CRM): message middleware, etc.

2.2. Definition of XA specification

XA specification defines the interface specification (interface function) between transaction middleware and database, which is used by transaction middleware to inform database transaction start, end, commit, rollback and so on. The XA interface function is provided by the database manufacturer.

The second-order commit protocol and the third-order commit protocol are proposed based on the XA specification, and the second-stage commit is the key to realize the XA distributed transaction.

2.3. XA specification programming specification

Configure TM to register RM with TM as the data source. One TM can register multiple RM.

AP initiates a global transaction to TM. At this point, TM sends a XID (Global transaction ID) to notify each RM.

AP gets the agent of the resource manager from TM (for example, using the JTA interface, get the JDBC connection or JMS connection of the RM managed by this TM from the context managed by TM).

AP indirectly operates the RM for business operations through the connection obtained from the TM. It is through this XID association that TM passes the XID to RM,RM during each AP operation to manipulate the relationship with the transaction.

When AP ends a global transaction, TM notifies RM that the global transaction ends. Start the second-stage commit, that is, the prepare-commit process.

The flow of the XA specification is roughly shown in the figure:

3. Two-phase commit (2PC)

3.1. Definition of two-phase submission

The algorithm idea of two-stage submission can be summarized as follows: each participant will notify the coordinator of the success or failure of the operation, and then the coordinator will decide whether each participant should submit the operation or abort the operation according to the feedback information of all participants.

The so-called two stages are:

The first stage: preparatory stage (voting stage)

Phase 2: submission phase (execution phase)

3.1.1. Preparation stage

The preparation phase is divided into three steps:

a. Transaction inquiry

The coordinator asks all participants if they are ready to execute the transaction and starts waiting for a response from each participant.

b. Execute a transaction

Each participant node performs transaction operations. If the local transaction succeeds, the Undo and Redo information is logged in the transaction log, but not committed; otherwise, a failure is returned and execution is exited.

c. Each participant feedback the response of the transaction inquiry to the coordinator

If the participant successfully executes the transaction operation, then feedback to the coordinator Yes response, indicating that the transaction can perform the commit; if the participant does not successfully execute the transaction, it returns No to the coordinator, indicating that the transaction cannot perform the commit.

3.1.2. Submission stage

During the commit phase, two actions are performed based on the voting results of the preparatory phase: performing the transaction commit and interrupting the transaction.

The process to commit a transaction is as follows:

a. Send a submission request

The coordinator sends a commit request to all participants.

b. Transaction commit

After receiving the commit request, the participant will formally perform the transaction commit operation, and after completing the commit, release the transaction resources occupied during the execution of the transaction.

c. Feedback on transaction commit results

After completing the transaction commit, the participant sends Ack information to the coordinator.

d. Transaction commit confirmation

After receiving the Ack information from all participants, the coordinator completes the transaction.

The interrupt transaction process is as follows:

a. Send a rollback request

The coordinator sends a Rollback request to all participants.

b. Transaction rollback

After receiving the Rollback request, the participant uses the Undo information recorded during the commit phase to perform the transaction rollback operation. After the rollback is complete, the resources consumed during the entire transaction execution are released.

c. Feedback the result of transaction rollback

After completing the transaction rollback, the participant wants the coordinator to send the Ack message.

d. Transaction interrupt acknowledgement

After receiving the Ack information from all participants, the coordinator completes the transaction interruption.

3.1. Advantages and disadvantages of two-phase submission

Advantages: the principle is simple and the realization is convenient.

Disadvantages: synchronous blocking, single point problem, inconsistent data, poor fault tolerance.

Synchronous blocking

During the two-phase commit process, all nodes are waiting for a response from other nodes and cannot do anything else. This kind of synchronous blocking greatly limits the performance of distributed systems.

Single point problem

The coordinator is important throughout the two-phase submission process, and if the coordinator has problems during the submission phase, the whole process will not work. More importantly, other participants will be in a state where the transaction resource is locked all the time and will not be able to continue to complete the transaction operation.

Data inconsistency

Suppose that after the coordinator sends commit requests to all participants, a local network exception occurs, or the coordinator itself crashes before sending all commit requests, resulting in only some participants receiving commit requests. This will lead to serious data inconsistencies.

Fault tolerance is not good

If there is a failure of the participants in the submission query phase of the two-stage submission, so that the coordinator can never get the confirmation information of all the participants, the coordinator can only rely on its own timeout mechanism to determine whether the transaction needs to be interrupted. Obviously, this strategy is too conservative. In other words, the two-phase commit protocol does not have a well-designed fault-tolerant mechanism, and the failure of any node will lead to the failure of the whole transaction.

Summary

For the synchronous blocking and single point problem of 2PC protocol, a solution will be introduced into 3PC protocol in the next article.

3PC

Due to the defects of two-stage submission, such as synchronous blocking, single point problem, brain fissure and so on. Therefore, the researchers made improvements on the basis of two-stage submission and proposed three-stage submission.

Unlike two-phase commit, three-phase commit has two change points.

Introduce a timeout mechanism-introduce a timeout mechanism in both coordinators and participants.

Inserting a preparatory phase into the first and second phases ensures that the status of the participating nodes is consistent before the final commit phase.

1. Definition of three-phase submission

Three-phase commit (Three-phase commit), also known as three-phase commit protocol (Three-phase commit protocol), is an improved version of two-phase commit (2PC).

The so-called three stages are: ask, then lock the resource, and finally actually submit.

The first stage: CanCommit

The second stage: PreCommit

The third stage: Do Commit

two。 The process of three-stage submission

2.1. Stage 1: CanCommit

The CanCommit phase of 3PC is actually very similar to the preparatory phase of 2PC. The coordinator sends a commit request to the participant, and the participant returns the Yes response if it can be submitted, otherwise the No response is returned.

a. Transaction inquiry

The coordinator sends a CanCommit request to the participant. Ask if a transaction commit operation can be performed. Then start waiting for a response from the participant.

b. Response feedback

After the participant receives the CanCommit request, normally, if he / she thinks the transaction can be executed smoothly, he / she will return the Yes response and enter the ready state; otherwise, he / she will report back to the No.

2.2. Stage 2: PreCommit

After receiving a response from all participants, the coordinator performs two actions based on the results: perform transaction pre-commit, or interrupt the transaction.

2.2.1. Perform transaction pre-commit

a. Send a pre-submission request

The coordinator sends a request for preCommit to all participant nodes and enters the prepared state.

b. Transaction pre-commit

After the participant is requested by the preCommit, the transaction operation is performed, and the Undo and Redo information is also recorded in the transaction log corresponding to the "execute transaction" in the 2PC preparation phase.

c. Each participant responded to feedback.

If the participant successfully executes the transaction, feedback the ACK response while waiting for instructions: commit (commit) or terminate (abort).

2.2.2. Interrupt a transaction

a. Send interrupt request

The coordinator issues an abort request to all participant nodes.

b. Interrupt a transaction

If a participant receives an abort request or times out, the transaction will be interrupted.

2.3. Stage 3: Do Commit

The real transaction commit at this stage can also be divided into the following two situations.

2.3.1. Execute submission

a. Send a submission request

If the coordinator receives the ACK response from each participant, he will move from the pre-submitted state to the submitted state. And send a doCommit request to all participants.

b. Transaction commit

After the participant receives the doCommit request, the formal transaction commit is performed. And release all transaction resources after the transaction commit is completed.

c. Response feedback

After the transaction is committed, an ACK response is sent to the coordinator.

d. Complete the transaction

After receiving the ACK response from all participants, the coordinator completes the transaction.

2.3.2. Interrupt a transaction

If the coordinator does not receive an ACK response from the participant (either the recipient sends a non-ACK response or the response times out), the interrupt transaction is executed.

a. Send interrupt request

The coordinator sends an abort request to all participants.

b. Transaction rollback

After receiving the abort request, the participant uses the undo information recorded in phase 2 to perform the rollback operation of the transaction, and releases all transaction resources after the rollback is completed.

c. Feedback result

After the participant completes the transaction rollback, an ACK message is sent to the coordinator.

d. Interrupt a transaction

After receiving the ACK message from the participant, the coordinator completes the interruption of the transaction.

3. Summary

3.1. Advantages of three-phase submission

Compared with the two-phase commit, the three-phase commit mainly solves the problem of single point of failure and reduces the blocking time.

Because once the participant cannot receive the message from the coordinator in time, he will execute commit by default. Instead of holding transaction resources all the time and being in a blocking state.

3.2. Disadvantages of three-phase submission

Three-phase commit can also lead to data consistency problems. Due to network reasons, the abort response sent by the coordinator is not received by the participant in time, so the participant performs the commit operation after waiting for the timeout.

This results in data inconsistencies with other participants who received the abort command and performed the rollback.

IV. Paxos

Used to achieve consensus problems, that is, for the values generated by multiple nodes, the algorithm can ensure that only one value is selected.

There are three main types of nodes:

Proponent (Proposer): propose a value

Recipient (Acceptor): vote on each proposal

Learner: be informed of the result of the vote and do not participate in the voting process.

Execution process

Specifies that a proposal contains two fields: [n, v], where n is the sequence number (unique) and v is the suggestion value.

The following figure illustrates the initial process of running the algorithm in a system with two Proposer and three Acceptor, with each Proposer sending a proposal request to all Acceptor.

When Acceptor receives a proposal request containing a proposal [N1, v1] and has not received a proposal request before, send a proposal response, set the currently received proposal to [N1, v1], and guarantee that no proposal with a sequence number less than N1 will be accepted in the future.

As shown in the figure below, Acceptor X sends a [no previous] proposal response when it receives a proposal request from [no previous 2, vroom8] because it has not received a proposal before, setting the currently received proposal to [nasty 2, vroom8], and guarantees that it will not accept any proposal with a sequence number less than 2 in the future. Other Acceptor is similar.

If Acceptor receives a proposal request, the included proposal is [N2, v2] and has previously received an offer [N1, v1]. If N1 > N2, the offer request is discarded; otherwise, the proposal response is sent, which contains the previously received proposal [N1, v1], sets the currently received proposal to [N2, v2], and ensures that no proposal with a sequence number less than N2 will be accepted in the future.

As shown in the figure below, Acceptor Z received a request for proposal from Proposer A, and abandoned the request because it had previously received a proposal from Proposer B, and Acceptor X received a request from Proposer B because the proposal was previously received, and 2 SN1, then ignore the request and end the approval process directly.

b)。 Otherwise, check the last approved accept request and reply; if no approval has been made before, simply reply

Accept approval phase:

(1a). After a period of time, some Acceptor responses have been received, which can be divided into the following categories:

a)。 If the number of replies satisfies the majority, and all responses are yes, Porposer sends out an accept request with a motion.

b)。 The number of responses met the majority, but some replied:,. Then Porposer finds more than half of all responses, and if so, issues an accept request with a motion

c)。 The number of replies does not meet the majority. Proposer tried to increase the serial number to SN1+, to continue execution.

(1b). After a period of time, some Acceptor responses have been received, which can be divided into the following categories:

a)。 If the number of responses meets the majority, it is confirmed that V1 is accepted.

b)。 The number of replies does not meet the majority, V1 is not accepted, Proposer increases the serial number to SN1+, to 1 to continue execution

(2)。 Without breaking its promise to other proposer, acceptor will accept and reply to the accept request upon receipt of the request.

1.3 algorithm optimization (fast paxos)

In the case of competition, the convergence speed of Paxos algorithm is very slow, and there may even be livelock. For example, when three or more proposer send prepare requests, it is difficult for one proposer to receive more than half of the responses and continue to implement the first phase of the protocol. Therefore, in order to avoid competition and accelerate the speed of convergence, the role of Leader is introduced into the algorithm. under normal circumstances, at most one participant can play the role of Leader, while other participants play the role of Acceptor, while all people play the role of Learner.

In this optimization algorithm, only Leader can propose a motion, which avoids competition so that the algorithm can converge quickly and tend to be consistent. In this case, the paxos algorithm is essentially reduced to a two-phase commit protocol. However, in abnormal cases, the system may have multi-Leader, but this will not destroy the consistency of the algorithm. At this time, multiple Leader can put forward their own proposals, and the optimized algorithm will degenerate into the original paxos algorithm.

The workflow of a Leader can be divided into three stages:

(1)。 In the learning stage, learn data that you don't know from other participants (resolution)

(2)。 The synchronization phase allows the vast majority of participants to maintain data (resolution) consistency.

(3)。 The service phase is the client service, and the proposal is proposed.

1.3.1 Learning stage

When a participant becomes a Leader, it should need to know the vast majority of paxos instances, so it immediately starts an active learning process. Assuming that the current new Leader already knows the paxos instances of 1-134,138 and 139, it will perform the first phase of the paxos instances of 135137and greater than 139s. If it detects only 135and 140s of paxos instances with certain values, it will eventually know about 1135s and 138140s of paxos instances.

1.3.2 synchronization phase

At this point, Leader already knows the paxos instances of 1-135,138-140, so it will re-execute the paxos instances of 1-135to ensure that the vast majority of participants are consistent on the paxos instances of 1-135s. As for the paxos instance, it does not execute the paxos instance immediately, but waits until the 136,137 paxos instance is populated during the service phase. The reason for filling the intervals here is to avoid future Leader always having to learn the paxos instances in these intervals, and these paxos instances do not have a corresponding definite value.

1.3.4 Service Pha

Leader converts a user's request into a corresponding paxos instance. Of course, it can execute multiple paxos instances concurrently. When an exception occurs in the Leader, it is likely to cause interruption of the paxos instance.

1.3.5 question

(1) the electoral principles of Leader

(2) how does .Acceptor perceive the failure of the current Leader and how does the customer know the current Leader?

(3)。 When multiple Leader occurs, how to kill the excess Leader

(4)。 How to extend Acceptor dynamically

5. Raft

Raft is similar to Paxos, but easier to understand and easier to implement.

Raft is mainly used to run for the main node.

A single Candidate campaign.

There are three kinds of nodes: Follower, Candidate and Leader. Leader periodically sends heartbeats to Follower. Each Follower sets a random campaign timeout, usually 150ms~300ms. If you do not receive Leader's heartbeat within this time, it will become Candidate and enter the campaign stage.

The following figure shows the initial phase of a distributed system with only Follower and no Leader. After waiting for a random campaign timeout, Follower A did not receive a heartbeat from Leader, so he entered the campaign phase.

At this point A sends a voting request to all other nodes.

Other nodes will reply to the request, and if more than half of the nodes reply, the Candidate will become Leader.

After that, Leader will periodically send heartbeats to Follower,Follower to receive heartbeats and restart the timing.

Multiple Candidate campaigns

If more than one Follower becomes Candidate and gets the same number of votes, you need to restart voting, for example, Candidate B and Candidate D both get two votes in the following figure, so you need to restart voting.

When voting starts again, because the random election timeout set by each node is different, the probability of reappearing multiple Candidate and getting the same number of votes next time is very low.

Log replication

Changes from the client are passed into Leader. Note that the change has not been committed, it is just written to the log.

Leader copies the changes to all Follower.

Leader waits for most of the Follower to be modified before committing the changes.

At this point, all Follower notified by Leader have them also submit changes, and the values of all nodes are agreed.

Thank you for your reading, the above is the content of "what is Java distributed consistency protocol and Paxos,Raft algorithm". After the study of this article, I believe you have a deeper understanding of what Java distributed consistency protocol and Paxos,Raft algorithm are, and the specific use needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.