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

This article introduces the knowledge of "what is web election, majority and lease". In the operation of practical cases, many people will encounter such a dilemma. Next, let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Election (electioin)

Consistency problem (consistency) is the problem of how to reach a decision between independent nodes, and the selection of leader that everyone agrees with is also a consistency issue in nature, so how to deal with outage recovery and network differentiation also needs to be considered in the leader election.

Bully algorithm [1] is the most common election algorithm, which requires that each node corresponds to a sequence number, and the node with the highest sequence number is leader. After the leader outage, the node with the next high sequence number is reselected as leader, and the process is as follows:

(a). Node 4 finds that the leader is unreachable, initiates a re-election to the node with a higher sequence number than itself, and puts its own serial number in the re-election message.

(B) (c) After receiving the reselection information, nodes 5 and 6 compare the sequence numbers, find that their sequence numbers are larger, return an OK message to node 4 and initiate re-election to the nodes with higher sequence numbers.

(d). Node 5 receives an OK message from node 6, while node 6 does not receive an OK message from a node with a higher sequence number after a timeout, so it thinks it is leader.

(e). Node 6 broadcasts the information that it becomes a leader to all nodes.

Reviewing the theoretical basis of distributed system-consistency, 2PC and 3PC, we can see that there is 2PC in Bully algorithm, which has the process of propose and vote.

In the consistency algorithms Paxos, ZAB [2] and Raft [3], nodes play the role of leader in order to improve the efficiency of resolution. The specific implementation of leader election is described in ZAB and Raft. Similar to the Bully algorithm, zxid is used to identify nodes in ZAB, and the node with the largest zxid indicates the latest transaction it has and is selected as leader.

Majority (quorum)

In the scenario of network differentiation, the above Bully algorithm will encounter a problem. The separated nodes think that they have the largest sequence number and will generate multiple leader, so it is necessary to introduce quorum [4]. Majority thinking is common in distributed systems, which ensures that decisions are unique in the case of network differentiation.

The principle of the majority is simple: if the total number of nodes is 2f+1, then a resolution is passed if it is approved by more than f nodes. In the leader election, only the part with a majority of nodes can elect leader in the network differentiation scenario, which avoids the generation of multi-leader.

The majority idea is also applied to replica management, adjusting the number of Vw and Vr according to the actual read-write ratio of the business, in order to achieve a balance between reliability and performance [5].

Lease (lease)

A very important question in the election, which has not been mentioned above: how to determine that leader is not available and when to launch a re-election? It is possible to first think of judging whether the leader state is normal by the heartbeat (heart beat), but in the case of network congestion or instant outage, this can easily lead to dual hosts.

Lease is a common method to solve this problem. It was originally proposed to solve the distributed cache consistency problem [6], and then it has been applied in many aspects, such as distributed lock [7].

The principle of lease is also not complicated. The central idea is that only one node gets the lease within the duration of each lease, and the lease must be reissued when it expires. Suppose we have lease issuance node Z, nodes 0, 1, and 2 run for leader, and the lease process is as follows:

(a). Nodes 0, 1, and 2 register themselves on Z, and Z issues a lease to the node according to certain rules (for example, first-come-first-served). The lease also corresponds to a valid duration; it is assumed that node 0 gets the lease and becomes leader.

(B). When leader goes down, the re-election will be held only after the lease expires (timeout), where Node 1 gets the lease and becomes leader.

The lease mechanism ensures that there is at most one leader at a time, avoiding the two-master problem caused by using only the heartbeat mechanism. In practice, zookeeper and ectd can be used to issue leases.

That's all for "what are web elections, majorities and leases?" Thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

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.