Explain this algorithm in distributed systems to help you stand out from the candidates you are interviewing for!

Author: Fishing table guy, senior architect

(1) What is the Paxos algorithm?

Paxos algorithm is a very classical algorithm, which is widely used in distributed systems. For example, it has a very core use in the famous ZooKeeper.

It is getting more and more difficult to go out for an interview, especially at some well-known Internet companies. Because these Internet companies use a variety of technologies in their systems, such as ZooKeeper.

A few years ago, when a candidate was interviewing for a Java position in a large company, he might have asked you to explain how ZooKeeper works and how to use it.

But now the competition is more and more fierce, go out to interview may directly ask you to tell a technology underlying core algorithm implementation, such as Paxos algorithm is now more and more big factories will ask a question.

However, algorithms like Paxos are really boring and difficult to understand. Many articles talk about it with a lot of professional terms and a lot of mathematical formulas, and many concepts are not clearly explained.

And for the engineering direction of the technical people, Paxos algorithm as long as from a high-level point of view, to his core idea understanding is already ok.

So in this article we use a relatively easy to understand way, from an interesting point of view to describe the core idea of Paxos algorithm, to help you stand out in the interview of large factories!

(2) The election process of the League Chairman

If there are 25 people in a company team, one of them needs to serve as the chairman of the team, which is responsible for the organization related to the team building, such as organizing people to travel, eat and drink out.

The scene of the group building and the role of the group chairman should be familiar to you.

In fact, this scene extends to the technology, is a very typical distributed system election scene. If there are 25 machines, one of these machines should be elected as a Leader node, responsible for the overall control of the cluster, is it the same as a team electing a team construction chairman?

Sure at this time, it is said, that is not easy, find a man as head to vote, let became chairman of the party building of interested people who voluntarily to nominate themselves, then everybody respectively for these people to vote, vote vote for anyone tell the head, the man by the statistics of each candidate’s votes, see which one of the vote in the last they choose who to be chairman of party building.

This works, but Paxos doesn’t accept it.

From the perspective of the Paxos algorithm, it would say that if everyone is relying on a poll leader to vote, what if the poll leader suddenly loses contact?

For example, if someone in your family gets sick and goes to the hospital, or if you suddenly get food poisoning and go to the hospital, then you can’t elect a league chairman.

Prompt:

To extend to the technology, that is, 25 machines choose one machine as the head of the voting election, specialized collection of votes, and then the number of votes, finally choose a machine, what if that machine suddenly broke down? Will it lead to electoral defeat? So Paxos doesn’t accept this.

As shown below:

So now, instead of voting by a poll leader, these 25 people are going to send each other text messages, and they’re going to send each other text messages to elect a president.

The advantage is that even if 12 of the 25 people are busy at work, in meetings, or with sick kids, and can’t vote by text message, the remaining 13 people still have more than half of them here, and they can vote.

So the voting process doesn’t have to depend on one person, even though nearly half of the people are out of contact, you can still elect a president.

Prompt:

In technology, 25 machines instead of looking for a poll leader, they send messages to each other to try to elect a caucus president.

In this way, even if 12 machines fail and go down, the remaining 13 machines can still elect a team construction chairman, which greatly improves the fault tolerance of the system.

So how do 25 people text each other to elect a league president?

First of all, out of those 25 people, you need to find 5 of them to be the team leader, and those 5 people are responsible for sending and receiving text messages with everyone to decide who is going to be the team president, and then let’s say that there are 3 candidates who are going to be nominated as the team president.

The following figure shows the process:

(3) Paxos Stage 1: Application stage

First of all, except for the five captains, all of them need to try to communicate with the voting captains in the first stage.

At this stage, each team member would send a text message to each team leader, and the message was “I apply to communicate with you”.

And each team leader will constantly receive messages from each member. For the team leader, judging by the time stamp when he gets the message, if the message sent by a person is the latest, he will reply that I agree to communicate with you.

If a member receives a letter from more than half of the captains (three in this case) saying they agree to communicate, they can tell those captains who agree to communicate whom they want to vote for.

However, it should be noted that the captain will constantly receive messages from others, so it is very likely that he just promised to communicate with you, but immediately received messages from others, found that others’ messages were updated, so he agreed to communicate with others, and your right to communicate will be cancelled.

So if a member of your team is on a texting binge and suddenly finds that more than half of your team members have agreed to communicate, don’t worry.

This member needs to quickly move on to the next stage and tell the captains that they want to vote. If they post late, the captains may be talking to someone else and will not talk to you!

(4) Paxos Stage 2: a relatively smooth voting stage

At this point, a member who has obtained the qualification to communicate with more than half of the captains can then send a text message saying that the person they want to vote for is one of the three candidates, which may be decided by the member’s own head, a random candidate.

At this time, consider for a moment, if the three captains have not received the updated application message from other members, and are keeping communication with this member, then the three captains have received the vote sent by him, for example, to elect “Zhang SAN” as the chairman of the group construction, it will be directly approved!

At this time, the members found that the three captains replied that they would use the “Zhang SAN” as the chairman of the group construction, that was decided, and the chairman of the group construction was this “Zhang SAN”.

Later, when other members sent an application text message to the captain, if they got the right to communicate with the three captains, the three captains would reply by text message that it was “Zhang SAN” and had been elected.

At this time, the other members will directly abide by the election result, it is considered “Zhang SAN”.

Another case, if some other members as a captain, “zhang SAN” the voting results however it with two other know “zhang SAN” vote on the captain didn’t establish communication, but with the rest of the two is not know the captain of the communication, “zhang SAN” the voting results because the members perceive one captain has chosen “zhang”, At this point he will try to say, I will vote for “John”, and inform the other two team leaders who are still in a daze that it is “John”.

At this point, the other two confused captains will also choose to accept the voting result of “Zhang SAN”, and the last five captains will receive the voting result of “Zhang SAN”, and then all members will also receive the voting result of “Zhang SAN” in the process of communicating with the captain.

In the end, all members will find that the final election result is: Zhang SAN. It was a very smooth voting period.

(5) Paxos Stage 2: What if the vote doesn’t go well?

So let’s go over the top, in case the vote doesn’t go well?

For example, a member of the team has successfully obtained the qualification to communicate with three team leaders, and when the vote request is sent, one of the team leaders has already established communication with others, and at this point, your vote will not be ignored.

There may be only two captains who receive your “threes” vote, but you can’t be sure to choose “threes” until you reach three captains.

What about this time? Maybe in this chaotic situation, for example, among the 5 captains, 2 of them received the vote of “Zhang SAN”, 1 of them received the vote of “Li Si”, and 2 of them received the vote of “Wang Wu”, so the election result could not be determined.

Then all the members continue to repeat the above steps, communicate with the leader, and then try to vote again.

If a member to communicate with 3 captain was established, in which two captain told him that he had received “zhang SAN” vote, a captain told him he has received the “bill” vote, then the members vote will see which is the latest, such as “bill” the voting is the latest, then he will say, I just “bill”.

The two captains who received “Three” votes will change their votes to “four”, and it will appear that all three captains have accepted “four” votes.

If another member establishes communication with a captain who receives a “Li4” vote and two captains who receive a “King 5” vote, he will find that “Li4” is newly elected, and then he will say, I will vote for “Li4”.

Then the two captains who received the votes of “King Five” also received the votes of “Lee Four”. And so on, let’s use our imaginations a little bit, and this process could go on for a long time, until finally, all the captains have accepted the “Thursday” vote, and all the members have accepted the “Thursday” vote.

(6) Extension: Paxos algorithm terminology explanation

In fact, the above process has been simplified with a simple example of voting for the chairman of the group to simplify very popular, although it is still a bit brain-burning, but I suggest you watch it several times, certainly according to the train of thought can roughly figure out a Paxos algorithm.

He has two main points: one is to use more than half, and one is to use only the latest votes.

A Paxos algorithm calls an Acceptor to a machine whose roles are numbered with a leader and a “Proposer” to a common member, and sends a text message to each other with a timestamp known as the epoch.

If you replace the above process with communication between machines and voting, you can understand the process.