Gossip networks

Geert Vos —  April 26, 2013 — 4 Comments

In this article we would like to present a Java implementation of a Gossip clustering framework. The library is being developed as a personal project of the author. The framework is based on a protocol that is inspired by gossiping. The framework provides a scalable solution to discover other members in the cluster and provides a way to determine a stable state of the cluster (i.e., everyone in the cluster has the same view).

Gossiping is a very old and powerful way of communicating. According to evolutionary biologists it helps bonding in large groups and it helps monitoring reputations1. Since these concepts are closely related to clustering, gossiping provides a good basis for a clustering protocol.

In the gossiping protocol that we implement in our framework, the gossipers are the members of the cluster. On start up, nodes are seeded with at least one of the other cluster member’s details. When the cluster algorithm starts, each node randomly picks a node from the seed lists and tries to contact it. Once contact is established, they gossip and exchange information about what they know about other members. Any new information is merged with the information already known. Using this technique the node quickly gains knowledge about the other members in the cluster. The nodes will keep randomly talking to their peers to stay up to date.

The following example demonstrates the protocol:

Node 1 is seeded with information of node 2.
Node 2 is seeded with information of node 3.
Node 3 has no seed.

Node 1 gossips with node 2:

Node 1 sends: { from: "node1", to: "node2", nodes: ["node1", "node2"] }
Node 2 now knows: ["node1", "node2", "node3"]
Node 2 reply: { from: "node2", to: "node1", nodes: ["node1", "node2", "node3"] }
Node 1 now knows: ["node1","node2", "node3"]

Node 2 gossips with node 3:

Node 2 sends: { from: "node2", to: "node3", nodes: ["node1", "node2", "node3"] }
Node 3 now knows: ["node1", "node2", "node3"]
Node 3 reply: { from: "node3", to: "node2", nodes: ["node1", "node2", "node3"] }
Node 2 now knows: ["node1", "node2", "node3"]

Within 2 steps, every node in the cluster knows about all the other nodes.

The process of gossiping repeats continuously. Each gossip message contains the information about the known members and a timestamp per member of the last update. This timestamp serves two purposes. The information is used to merge information after a gossip. The latest information will be kept. Second, we can use this information to detect dead nodes. If we didn’t get an update about a node within a certain interval, we mark it as dead and remove from the list of active participants.

Besides keeping track of the last time we saw a node, we can also keep track of their view of the cluster. This is done by generating a hash of all the members a node knows. By comparing hashes, nodes can detect whether or not they have the same view of the cluster. If all members in the cluster have the same view, we mark the cluster as stable.

A gossip protocol like the one we present here has a number of advantages over a more traditional method like a shared message bus or a master node. First of all, a gossip based cluster is more fault tolerant, there is not a single component that can fail and disrupt communication. The network itself is also resilient for node failure. It is also scalable, it automatically scales with the number of nodes that are part of the cluster and information spreads very fast. The downsides of using a gossip like protocol is that information is often transmitted multiple times (the feature that makes it fault tolerant) and the protocol does only provide a probabilistic guarantee that the information will arrive.

In our Java library we implemented both the clustering and the stability detection described above. We randomly connect to a peer and exchange a JSON message with the information about our node and our peers. Using the Java library is extremely simple, here we setup a basic node in a cluster:

long time = System.currentTimeMillis();
 
GossipClusterMember member2 = 
    new GossipClusterMember("Member-2", "host", 1, time);
GossipCluster cluster = 
    new GossipCluster("ClusterName",
                      "Member-1",
                      "host",
                      9000,
                      member2);
 
GossipServer server = new GossipServer(cluster);
server.start();

The code above creates a new cluster for member1 and passes in member2 as a seed. After the setup a server for the cluster is created and started. The cluster also has a name configured. This is used to track which cluster a member belongs to. Members of other clusters will not be added to the member list. This might occur in case of misconfiguration.

When you run two different nodes of the cluster, they will start exchanging messages. The gossip messages in the current implementation have the following structure:

{
   "memberInfo":[
      {
         "id":"Member-1",
         "host":"localhost",
         "port":8003,
         "lastSeenOnline":1366232245732,
         "hash":"uiiFopYD5IC3ObQCUgxniA==",
         "metaData":{
            "partitionServer.port":"5000"
         }
      },
      {
         "id":"Member-2",
         "host":"localhost",
         "port":8009,
         "lastSeenOnline":1366232246197,
         "hash":"uiiFopYD5IC3ObQCUgxniA==",
         "metaData":{
            "partitionServer.port":"5001"
         }
      }
 
   ],
   "from":"Member-1",
   "to":"Member-2",
   "cluster":"demoCluster"
}

The cluster provides a very simple listener interface to notify the application about state changes in the cluster. The following events are available:

public interface ClusterEventListener {
 
	void onNewActiveMember(ClusterMember member);
	void onNewInactiveMember(ClusterMember member);
	void onMemberActivated(ClusterMember member);
	void onMemberDeactivated(ClusterMember member);
	void onClusterStabilized(List<ClusterMember> members);
	void onClusterDestabilized();
	
}

The library presented here is a prototype and under development. Still, feel free to give it a try. The library is available on GitHub: https://github.com/geertvos/gossip

In a follow up we will discuss how to use this library in your clustered applications.

1. McAndrew, Frank T. (October 2008). “The Science of Gossip: Why we can’t stop ourselves”. Scientific American.

4 responses to Gossip networks

  1. 

    Very nice approach, Geert! Have you tried to see how it scales?

    I’d be very interested to hear your opinions about the following questions:
    - How fast such a gossip solution converges for a setup with a few thousands cluster members?
    - Does it scale at all for a few thousands members?
    - Wouldn’t it exchange too much information inside gossip messages if the number of nodes is very big?
    - How would it behave if you have a lot of nodes and many nodes join or leave a cluster on a regular basis? Would it spend too much time on stabilization using gossip or would it converge quickly?

    I guess you can easily answer these questions simply by writing a unit test or an example app that would model the mentioned scenarios. It would be useful as an example, as a test and a performance investigation tool for gossip networks.

    • 

      This library is not yet tested it with thousands of nodes. My current aim is to support hundreds of nodes. In general, most distributed computing platforms will have enough on hundreds of nodes.

      The tests I did so far (running 101 instances inside a single VM) were quite amazing. It behaves much better then I expected, but it was not a very realistic scenario either. To really test the scalability I will have to setup a test that takes network latency etc, into consideration.

      I will keep your questions in mind for a potential next post.

  2. 
    Hymie Hapstead April 27, 2013 at 2:51 am

    I think you will experience gossip echoes because I can see you have a leakage back to the source (albeit indirect). This will cause an echo some time removed from the time that the original message was passed.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s