Zookeeper: PaxOS algorithm learning

Post big guy’s blog: Big guy collates paxOS analysis

Distributed can’t escape the problem

The principle of CAP

Also known as the CAP theorem, it states that in A distributed system, there are three very important properties: consistency C, availability A, and partition fault tolerance P

• Consistency

  Check whether all hosts in a distributed system can have the same data backup at the same time. If yes, the distributed system is consistent

• Availability

  Does the failure of some nodes in the cluster affect the response to client read and write requests? Note that if it does affect the response for a short period of time, it does not have the “availability” described here.

• Partition tolerance

  A host in a distributed system is called a partition. Hosts in a distributed system cannot ensure data consistency, that is, inconsistency is an error.

  A distributed system that cannot respond to client requests in a timely manner, i.e., is not available, is also an error;

  For distributed systems, there must be “tolerance” to these errors, that is, fault tolerance, which must be ！！！！！！！！！！

A trade-off between

As explained above, partition fault tolerance is a must for distributed systems

To ensure availability, nodes must be added, and availability does improve. However, the problem with increasing the number of nodes is that data synchronization between so many nodes is a lot of consumption, and it is extremely easy to cause data inconsistency.

When we emphasize consistency, fewer nodes means less data synchronization costs, but fewer nodes result in poor service availability.

So consistency and availability are not the same thing, they are opposites!

combination

So if we get the basic idea, we know that the possible combinations are 3

CA: A single point of application option because there is no partitioning

The following two choices are the combination of distributed systems. Neither CP nor AP represents the complete abandonment of the other, but weak support

CP: Emphasize consistency, give up some usability, such as Zookeeper, election process will temporarily make the system unavailable, such as the banking system must require data consistency

AP: Emphasize usability, give up some consistency, such as some refund services, within 2 hours of the account, meet the requirements within the user’s acceptable range

The protagonist Paxos

In order to introduce PaxOS, ZooKeeper follows CP principles and emphasizes consistency

So the question is, how do you make distributed systems consistent?

Paxos algorithm! At present, one of the most effective algorithms to solve distributed consistency problem is how to reach agreement on a certain value (resolution) in distributed system.

The underlying principle of ZooKeeper, ZAB, is based on PaxOS

So you have to understand the PaxOS algorithm

Question of the Byzantine general

The introduction copied from the Internet:

The Byzantine generals had to decide unanimously whether or not to attack an enemy force. The problem was that the generals were geographically separated and relied on their correspondents to deliver orders, but there were traitors among the correspondents who could tamper with messages, traitors who could trick certain generals into taking offensive action; To precipitate a decision with which not all generals agree, such as to precipitate an attack when the generals do not wish to; Or confuse some generals so they can’t make a decision.

In a word: your in-cluster network is secure and there is no tampering of communication messages

The big premise of paxOS is that your distributed system doesn’t have the Byzantine general problem

Most systems are deployed on a local area network, so message tampering is rare. On the other hand, incomplete messages caused by hardware and network problems only need a set of simple verification algorithms.

role

It is interesting to note that the Paxos algorithm can be described by a simple story with three characters:

-Chuck: No, no, no, no.

An Acceptor or a member of parliament

Learner: Only accept the final result opinion (civilian)

The story of the PaxOS algorithm also unfolds among these characters

The story background

• There is a small island called Paxos where a group of people live, and everything on the island is decided by a special group of people called senators.
• The total number of MPS is fixed and cannot be changed. (This is a key point)
• Each change in environmental affairs on the island requires the adoption of a proposal, and each proposal has a number, which is always increasing and cannot be reversed.
• Each proposal needs the approval of a majority of lawmakers to take effect. (Very important)
• 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.

More than half the principle

There is a special note in the background of the previous story: each proposal needs the approval of more than half of the senators to take effect

This is known as the rule of half

Paxos is based on the principle of half mathematics: we call the set composed by most (half) processes a legal set, and two legal (half) sets must have non-empty intersection, that is, at least one common process, which is called the nature of legal set. For example, the set of processes A,B,C,D, and F, the legal set Q1 includes processes A,B,C, and Q2 includes processes B,C, and D, so the intersection of Q1 and Q2 must not be empty, and C is the common process of Q1 and Q2. If there is one fundamental principle to Paxos, it is this simple property. That is to say: there must be intersection between two sets of half, that is, they must be equal, that is, they must reach agreement.

For example: three people, a proposal, as long as two people agree to it; Four people. One motion. Three people need to approve it

The proposed process

There are generally two levels:

1. Stage 1 (Prepare Stage)

   1. Proposer selects a proposal number N and sends a Prepare request numbered N to more than half of the acceptors. Pareper (N)
   2. If an Acceptor receives a Prepare request with number N:
      1. If it is smaller than the request it has already responded to, it rejects, does not respond, or returns error.
      2. If N is greater than the number of all Prepare requests this Acceptor has responded to (maxN), it returns {pok, null, if any, for the proposal with the highest number that it has accepted (after phase 2). Null}) as a response back to the Proposer
      3. The Acceptor also promises not to accept any proposal numbered less than N. ！！！！！！！ Important to explode ！！！！！！！！！！

2. Stage 2 (Accept Stage) :

   1. If a ProposerReceived more than halfAn Acceptor responds to a Prepare request numbered N by sending an Accept request to more than half of all acceptors for the [N,V] proposal.
      1. If the response does not contain any proposals, then V is determined by the Proposer itself.
   2. If an Acceptor receives an Accept request for a proposal numbered N
      1. As long as the Acceptor does not respond to a Prepare request with a number greater than N, it accepts the proposal.
      2. If N is less than an Acceptor and the prepare request it responded to, it rejects, does not respond, or responds with an ERROR.

Live lock

Paxos looks fine at first glance, but live locks can occur in extreme cases

Solve the live lock problem

Choose The Lord, only the Lord can Propose, the others can only ask the Lord and let the Lord Propose