Principle of distribution: understanding the gossip protocol

gossip What is it?

gossip agreement （gossip protocol） also called epidemic agreement （epidemic protocol）, It's a protocol for information exchange between nodes or processes based on epidemic transmission , It is widely used in distributed systems , For example, we can use gossip Protocol to ensure that all nodes in the network have the same data .gossip protocol Originally by Xerox's Palo Alto Research Center （Palo Alto Research Center） Researcher Alan · Demers （Alan Demers） On 1987 Created in .

from gossip You can see the words , It means eight trigrams in Chinese 、 Rumors, etc , We can imagine the spread of gossip （ Or the spread of an epidemic ）;gossip The protocol works like this .gossip The protocol uses a random way to spread information across the network , And make the data of all nodes in the system consistent in a certain period of time .Gossip It's actually a decentralized distributed protocol , We solve two problems: the propagation of state in cluster and the guarantee of state consistency .

If you want to know in time Spark、Hadoop perhaps Hbase Related articles , Welcome to wechat public account ：iteblog_hadoop

gossip advantage

Extensibility （Scalable）

gossip The protocol is extensible , Generally need O(logN) The wheel can spread information to all nodes , among N Represents the number of nodes . Each node sends only a fixed number of messages , And the number of nodes in the network cannot . During data transmission , Nodes do not wait for messages ack, So it doesn't matter if the message fails , Because the message can be delivered to the node that failed to deliver it before through other nodes . The system can easily scale to millions of processes .

Fault tolerance （Fault-tolerance）

The restart or downtime of any node in the network will not affect gossip The operation of the protocol .

Robustness, （Robust）

gossip The agreement is a decentralized agreement , Therefore, all nodes in the cluster are peer-to-peer , No special nodes , Therefore, the problem of any node will not prevent other nodes from sending messages . Any node can join or leave at any time , Without affecting the overall service quality of the system （QOS）

Final consistency （Convergent consistency）

Gossip The protocol realizes the exponential rapid dissemination of information , So when there is new information to spread , Messages can be quickly sent to global nodes , In a limited time, all nodes can have the latest data .

gossip The type of agreement

As mentioned earlier, nodes will spread information to the whole network , Under what circumstances does a node initiate information exchange ？ This involves gossip The type of agreement . At present, there are mainly two methods ：

• Anti-Entropy（ Anti entropy ）： Propagate all data with a fixed probability
• Rumor-Mongering（ Rumors spread ）： Propagate only newly arrived data

Anti-Entropy

Anti-Entropy The main way of working is ： Each node periodically selects other nodes randomly , Then by exchanging their own all Data to eliminate the difference between the two .Anti-Entropy This method is very reliable , But every time the nodes exchange all their data in pairs, it will bring a very large communication burden , This will not be used frequently .

Anti-Entropy Use “simple epidemics” The way , So it contains two states ：susceptible  and  infective, This model is also called  SI model. be in  infective  The status node represents that it has data updates , This data will be shared with other nodes ; be in  susceptible  A node in state represents that it has not received updates from other nodes .

Rumor-Mongering

Rumor-Mongering The main way of working is ： When a node has new information , This node becomes active , And periodically contact other nodes to send new information . Until all nodes know the new information . Because nodes only exchange new information , All greatly reduce the burden of communication .

Rumor-Mongering Use “complex epidemics” Method , comparison Anti-Entropy One more state ：removed, This model is also called  SIR model. be in  removed  A node with status indicates that it has received updates from other nodes , But it will not share this update with other nodes .

because Rumor The message will be marked as... At some time  removed, Then it will not be sent to other nodes , therefore Rumor-Mongering Type of gossip The protocol has a minimal probability that the update will not reach all nodes .

Generally speaking , To achieve a compromise between communication cost and reliability , These two methods need to be used together .

gossip Protocol communication

Whether it's Anti-Entropy still Rumor-Mongering Both involve the data interaction between nodes , There are three main modes of interaction between nodes ：Push、Pull as well as Push&Pull.

• Push： The node that initiates the information exchange A Select the contact node randomly B, And send them their own messages , node B Update the data newer than yourself after receiving the information , Generally, the node with new information will be the initiating node .
• Pull： The node that initiates the information exchange A Select the contact node randomly B, And get information from the other side . Generally, the node without new information will be the initiating node .
• Push&Pull： The node that initiates the information exchange A To the selected node B Send a message , At the same time, get data from the other party , Used to update your own local data .

gossip Algorithm implementation

Gossip The agreement is realized according to the idea of rumor spread or epidemic spread , therefore ,Gossip The implementation algorithm of the protocol is also very simple , Here are Anti-Entropy and Rumor-Mongering Implementation pseudo code .

If you want to know in time Spark、Hadoop perhaps Hbase Related articles , Welcome to wechat public account ：iteblog_hadoop