Shulou(Shulou.com)05/31 Report--

This article introduces you how to carry out paxos algorithm analysis, the content is very detailed, interested friends can refer to it, I hope it can help you.

Basic paxos

Can I just have one acceptor? You can't. All proposers send messages to one acceptor, and if this acceptor crashes, then the whole system crashes. Solution: Use quorum. Multiple acceptors, only need most acceptors to select a certain value, in case a certain acceptor crashes, does not affect the system.

Each acceptor chooses only the first value. Is that okay? You can't. Because there may be as many acceptors of proposal1 as there are acceptors of proposal2, it is impossible to select which proposal is chosenproposal. For example, server1 selects proposal1, server2 selects proposal1 and proposal2, and server3 selects proposal2. Solution: Each proposer must confirm whether there is currently a proposal selected before initiating a proposal, and if so, abandon his proposal.

Conflict will occur in the process of choosing, and conclusions will be drawn according to different conflicts: once a proposal is selected, other campaign proposals must choose the same value; proposals are sorted according to proposal number, rejecting the old proposal;

From the above description, we can design the proposal number structure as follows: It consists of two parts:

round number: The number of rounds executed by paxos, each server must keep the latest maxRound [ensure that there are as few conflicts as possible, all compete for the largest number]

Server ID: Each server has a unique ID (ensure that the proposal number is not the same)

maxRound must be stored on a permanent storage medium. A section of server crash can be reused to initiate a proposal.

Paxos objectives for each phase:

the prepare phase

accept phase

Make all acceptors accept the proposal.

Find any selected proposal. After discovery, change your value to the Value of discovery

Block an unfinished proposal. When a proposal with a higher proposal number enters the prepare phase, the old proposal is rejected in the accept phase.

Main logic:

proposeracceptor1. Select proposal number n

2. Broadcast to acceptor prepare(n)

3. response prepare(n): if (n > minProposal) then minProposal =n; Return(acceptedProposal,acceptedValue)4. Get most acceptors Reply: If there is a return, select the value corresponding to the largest proposal number in the return as the value of this proposal; if there is no return, you can continue to use the previous value.

5. Broadcast accept(n,value) to all acceptors

6. Response accept(n,value): if(n >= minProposal) then acceptedProposal = minProposal = n; acceptedValue = value; Return minProposal 7. Get most acceptors Return: If result>n exists, it means that the proposal is rejected, repeat 1~6, and the next set n is greater than result, otherwise choose proposal

All competing proposals must have a common acceptor, so that new and old proposals can be discovered and terminated in time.

paxos livelock: results in no proposal chosen. proposal A passes early in prepare phase, another proposal B enters prepare, acceptor's minProposal increases, causing A to be rejected in accept phase, A to retry immediately and enter prepare phase, causing acceptor's minProposal to increase, B to be rejected after entering accept phase. And so on. There is no command that works properly.

Solution: Each retry must occur after a random delay.

How do multi-paxos select log entries?

Implementation steps:

Find the first log entry Entry slot that doesn't know if it was chosen (not necessarily the first empty slot)

Run basic paxos with value as client command

Does the prepare return contain an acceptedvalue?

There is: chosen acceptedvalue, and repeat step 1

No:chosen client request, the slot is the slot sought

Examples:

1234567server 1movaddcmp

ret

server 2movadd

sub

ret

server 3movaddcmp

cmpret

As shown in the table above, when the client requests jmp, suppose server3 crashes. At this time, to slot3, since server1 and server2 are different, it is unknown whether to choose Proposal, so the value of client command is value; run paxos, enter prepare (n), server1 slot3 already has acceptedvalue, so the value of Proposal will be changed to the value of server1 slot 3, and then proceed to the accept phase, server2 slot3 receives value. Change server2 slot3 to cmp.

1234567server 1movaddcmp

ret

server 2movaddcmpsub

ret

server 3movaddcmp

cmpret

Similarly, server1 slot4 is changed to sub:

1234567server 1movaddcmpsub

ret

server 2movaddcmpsub

ret

server 3movaddcmp

cmpret

Then slot5, acceptedValue=null; the value of the next Proposal is the value defined by the meta, i.e. the command of the client.

1234567server 1movaddcmpsubjmpret

server 2movaddcmpsubjmpret

server 3movaddcmp

cmpret

Log entry slot.

Note: Server3 crashed!

In the above processing process: the server can receive multiple client requests at the same time, as long as it can ensure that the log entries of the client requests are different; but when the command enters the server state machine, it must be executed sequentially.

How to improve multi-paxos performance?

Multi-paxos problem:

When multiple proposers are in progress, conflicts and retries will occur, which will reduce the efficiency of system selection.

Two RPC calls are required for each selected value;

Solution:

Select the learner. There is only one leader at a time, so there will be no conflict between multiple proposers.

Clear most prepare RPC calls

Make a preparation

Most log entries can be completed in an RPC call

How to choose a leader? 1. Let serverid be the largest as leader; 2. Every Tms, each server sends a heartbeat packet to other servers. 3. If the server does not receive a server heartbeat larger than it within 2Tms, then it can act as a leader and accept client requests. It has the role of proposer. 4. A server that is not a leader rejects client requests and redirects requests to the role of leader, acceptor.

How to handle the prepare phase

Associate Proposal with logEntry slot, each Proposal number represents a slot

the maximum acceptedProposal values;

In the current log entry slot, the current slot of each server has no acceptedvalue, and noMoreAccepted is returned.

If the acceptor returns noMoreAccepted, skip all prepare RPC after the current server of the same slot (until accept rejects Proposal, reject Proposal indicates that the acceptro layer has accepted Proposal, there is acceptedvalue).

If the leader knows noMoreAccepted, there is no need to use prepare and go directly to the accept phase. Because the slot of all servers is empty, notify the acceptor accept Proposal directly. Only one round of accept RPC is required.

Block old Proposal:

Find the value of possible chosens:

Why do we need the prepare phase?

After improvement:

How do you back it up? Goal: The backup on each server is a full backup.

Target breakdown:

log entry without full replication: full replication

Only the proposer knows which entry was chosen: all servers know which entry was chosen.

Solution steps:

The proposer accepts RPC requests in the background until all servers respond. Most servers are full replication (why only most?) Because there may be a server crash before, some log entries are empty, even if the response is once, all slots cannot be filled completely, the operation Boone enters the state machine execution, and cannot achieve full replication)

track chosen entries

such that entries can be known whether or not they have been chosen: acceptedEntry[i] = infinity indicates that the i-th entry was chosen.

Each server maintains a firstUnchosenIndex, which is the index of entries, indicating that entries before the index are chosen.

The proposer (i.e. leader) tells the acceptor to choose the entry:

Proposer sends firstUnchosenIndex when accepting RPC. Then the acceptor knows that all entries with index less than firstUnchosenIndex are chosen.

Acceptor label entry is chosen if it satisfies both of the following conditions: i np np = n reply prepare_ok(n, na, va) else reply prepare_rejectacceptor's accept(n, v) handler: if n >= np np = n na = n va = v reply accept_ok(n) else reply accept_reject About how to carry out paxos algorithm analysis to share here, I hope the above content can be of some help to everyone, you can learn more knowledge. If you think the article is good, you can share it so that more people can see it.

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.