Easy to understand Paxos algorithm (fart people)

First, Paxos is a consistency algorithm based on messaging. Proposed by Leslie Lamport in 1990, Paxos has been widely used in distributed computing in recent years. Google’s Chubby and Apache’s Zookeeper are all implemented based on its theory. Paxos is also considered to be the only distributed consistency algorithm so far, and the other algorithms are improvements or simplifications of Paxos. One problem to mention is that Paxos has a premise: there is no Byzantine general problem. This means that Paxos only works in a trusted computing environment that can’t be corrupted by an intrusion.

A detailed description of Paxos can be found in the Wiki: zh.wikipedia.org/zh-cn/Paxos… Mapping between servers.

Paxos describes a situation where there is an Island called Paxos where there is a group of people, and everything on the Island is decided by a special group of people, senators. The Senator Count is fixed and cannot be changed. Each change in environmental affairs on the island requires the adoption of a Proposal, and each Proposal has a PID number, which is always increasing and cannot be reversed. A majority of Senators (Senator Count /2 +1) is required for each proposal to take effect. Each member will only agree to proposals greater than their current number, both those in force and those not in force. If an MP receives a proposal of less than or equal to the current number, he will reject it and tell the other party: your proposal has already been made. The current number here is the number that each senator keeps in his notebook, and he keeps updating it. There is no guarantee that the number on all members’ notebooks will always be the same throughout parliament. Now parliament has one goal: to make sure that all members agree on the proposals.

All right, now that parliament is in operation, all members start their notebooks with the number zero on them. One lawmaker sent a proposal to set the electricity rate at 1 yuan per kilowatt hour. First he looked in his notebook and said, well, the current motion number is 0, so my motion number is 1, so he sent a message to all the senators: Motion number 1, set the electricity rate at 1 yuan per kilowatt hour. The other member received the message and checked his notepad, oh, the current motion number is 0, the motion is acceptable, so he wrote down the motion and replied: I accept your motion number 1, and he wrote down in his notepad: the current motion number is 1. The member who initiated the motion received more than half of the responses and immediately sent a notice to everyone: Motion 1 is effective! The Congressman who received the bill would modify his notepad, changing a good proposal from a record to a formal law. When someone asked him how much the electricity bill was, he would check the law and tell the other party: 1 yuan/KWH.

Now look at the resolution of the conflict: suppose there are three MPS s1-S3, and BOTH S1 and S2 propose a motion at the same time: Motion 1, setting electricity charges. S1 wants to be 1 yuan per degree, S2 wants to be 2 yuan per degree. S3 receives S1’s proposal first, so he does the same thing as before. He then receives an offer from S2, and when he looks in his notebook, he says, gee, this offer is less than or equal to my current number 1, so he rejects the offer: Sorry, that offer was made earlier. S2’s offer was rejected, and S1 issued a formal offer: Proposition 1 is valid. S2 asks S1 or S3 and updates the contents of Decree 1, and then he can choose to proceed with proposition 2.

Okay, I think that’s the best part of Paxos. Now let’s see how Paxos is implemented in ZK Server.

Mapping between ZK Server and ZK Server:

  1. Island — ZK Server Cluster

  2. Mp (Senator) – ZK Server

  3. Proposal (Proposal) – ZNode Change (Create/Delete/SetData…).

  4. Offer Id (PID) — Zxid(ZooKeeper Transaction Id)

  5. Official decree – All ZNodes and their data

It seems that all the key concepts correspond to each other, but wait a minute, the lawmakers of Paxos island are supposed to be equal, and it seems that ZK Server has a concept of Leader. Yes, in fact, the concept of Leader should also belong to the Paxos category. If parliamentarians are all equal, at some point there will be a “live lock” due to the proposed conflict. Lamport, The author of Paxos, elaborated on this problem and proposed a solution in his article “The Part-time Parliament” — set up a president among all members of Parliament, and only The president has The right to make proposals. If members of Parliament have their own proposals, they must be sent to The president and put forward by The president. Ok, we have one more character: president.

President – ZK Server Leader

Another question arises, how is the president chosen? oh, my god! It’s a long story. In taobao core system team Blog above there is an article is to introduce how to elect the president, interested can go to see: rdc.taobao.com/blog/cs/?p=…

Now let’s assume that the president has been chosen. Let’s see how ZK Server is implemented.

Case 1:

When Client goes to a ZK Server to ask about a certain law (ZNode data), the legislator takes out his notebook (Local storage) without hesitation, looks up the law and tells him the result, while stating: my data may not be the latest. You want the latest figures? No problem. Hold on. I’ll get back to you when I Sync with the president.

Situation 2:

Fart minb (Client) to a member (ZK Server) there to ask the government to return the ten thousand yuan owed to him, the Congressman asked him to wait in the office, he will reflect the problem to the president, the president asked all the members of the opinion, most of the members said that the money owed to the fart people must be returned, so the president issued a statement, from the state Treasury to take out ten thousand yuan to repay, The Treasury’s total assets went from $1 million to $990,000. Fart b gets the money back (Client function returns).

Case 3:

The president suddenly died, lawmakers one after another found that the president could not be contacted, so they issued a statement, elected a new president, the presidential election during the government shutdown, refused to fart people’s request.

There are many other cases, but these cases can always be prototyped and solved in Paxos’s algorithm. That’s why we think of Paxos as the soul of Zookeeper. Of course, ZK Server has a lot of its own features: Session, Watcher, Version and so on, we need to spend more time to study and learn.

Reprint articles the Zookeeper full resolution – Paxos as soul link: www.douban.com/note/208430…

Is everyone still ok? If you like, move your hands to show 💗, point a concern!! Thanks for your support!

Welcome to pay attention to the public number [Ccww technology blog], original technical articles launched at the first time