Peer discovery

In a network, service instances register themselves in a service registry to announce availability.

One machine advertises its presence and sends periodic heartbeats to confirm it is alive.

Another machine continuously queries the registry to stay updated on the current state.

Service registry nodes communicate with each other to replicate data.

This raises two key questions:

• How do service instances of A and B learn about the service registry machines?
• How do service registry machines learn about each other?

Do we need a service registry to manage a service registry?

The answer is no. There is no need for a registry to manage itself.

A simple approach is to list all hostnames and port numbers of registry machines.

This list is manageable because only a small number of machines are typically needed.

Three or five servers are often sufficient.

This list is shared with:

• Every machine in the registry cluster
• Every service instance that needs to connect to the registry

Apache Zookeeper, a widely used open-source coordination service, uses this method.

A client selects a hostname at random from the list and connects to that node.

The list is distributed to clients via:

• Deployment of a file to each client machine
• Upload to a shared database or object storage

A hard-coded list is simple and reliable.

However, it lacks flexibility.

Whenever the list changes, updates must be deployed across many client machines.

DNS allows storing arbitrary text data using TXT records.

We can store the registry host list as a TXT record.

Netflix Eureka uses this method to dynamically add or remove servers.

DNS propagates updates to thousands of clients within minutes.

This approach offers scalability and real-time updates.

Some databases, like Dynamics and Apache Cassandra, use peer discovery.

The idea: I may not know you, but if you share a friend, we can discover each other through that friend.

If one machine knows all others, it can introduce them to each other.

To share information with a group, I don’t need to talk to every individual.

I can share it with one or two people.

Each of those people then shares it with a few others.

Eventually, all members of the group learn the information.

This is how rumors spread.

This principle underlies the GOSEP protocol.

GOSEP is a broadcast protocol for disseminating data.

It is also known as epidemic broadcast.

The protocol draws an analogy to a virus spreading through a population.

Each piece of information acts like a virus.

When a new machine joins the cluster, it can quickly identify all other machines.

When a machine crashes, the rest of the cluster detects the failure rapidly.

GOSEP enables efficient peer discovery without requiring direct communication with every node.

This reduces latency and improves scalability in dynamic environments.

The protocol ensures that information spreads quickly and reliably across the cluster.

It is especially effective in large, distributed systems where nodes frequently join or leave.

GOSEP eliminates the need for centralized coordination to propagate discovery data.

It enables decentralized, self-sustaining peer discovery.

At any given moment, each machine in the cluster knows the state of the cluster—specifically, which machines are currently alive.

The GOSEP protocol enables membership management and failure detection in a cluster.

A single-node cluster has no interesting dynamics. There is no peer to communicate with.

When a second node, B1, joins, it must determine which node to initiate GOSEP with.

This is solved by the concept of a seed node.

A seed node is a node known to all nodes in the cluster.

Seed nodes are used to bootstrap the GOSEP process for every new node joining the cluster.

Node A is the first node in the cluster and serves as the initial seed node.

Node B discovers Node A using established mechanisms.

These mechanisms include:

• A static file containing a list of seed node hostnames
• DNS records storing seed node hostnames

Node B discovers Node A and shares information about itself and Node A.

When Node C joins:

• It initially only knows the seed node, Node A
• After sharing information with Node A, it learns about Node B

Once Node C learns about Node B, Nodes B and C can begin exchanging gossip messages.

In a six-node Cassandra cluster:

• Multiple nodes are designated as seed nodes
• This provides fault tolerance if one seed node fails

Every second, each node initiates a new gossiping round.

Each node independently selects up to three peer pairs to communicate with.

Node A selects Node C to exchange information.

Node A sends a message called CIN.

CIN contains the IP addresses of all nodes known to Node A.

Node C receives the CIN message.

It compares the list of IP addresses in the CIN message with its own known nodes list.

It generates a div message called AC.

The AC message includes:

• IP addresses not known to Node A
• Statuses of those nodes

This represents new information Node A does not have.

Node C also specifies nodes it does not yet know.

Node C requests information about these unknown nodes.

Node C sends the AC message back to Node A.

Node A receives the AC message.

It stores information about previously unknown nodes.

It sends back a message called ACTU.

ACTU contains the information Node C requested.

Node C receives ACTU.

It stores the received information.

The gossip round is complete.

After three messages, both nodes have synchronized their knowledge of the cluster.

When a node is down, the cluster must detect this.

Each node maintains an integer value.

This value increments every time a new gossip round begins.

This occurs every second.

This integer is called the hard-to-read counter.

It is also referred to as a hard-to-read counter or simply a hard-to-read.

Nodes include the hard-to-read value in every gossip message they send.

Each node shares its current hard-to-read values with others.

It also shares hard-to-read values of other nodes it knows about.

This ensures every node maintains a list of hard-to-read values.

Each entry includes a timestamp indicating when the value was last updated.

Every node periodically reviews its list of hard-to-read values.

It checks the timestamps of all PMs (peer messages) in the list.

If a node's hard-to-read value hasn't changed for more than n seconds,

that node is marked as down.

After marking a node as down,

the current node stops regular gossiping with it.

It still attempts periodic reconnection to check if the node is back online.

• Gossip protocol is peer-to-peer communication.

• Machines communicate directly with each other.

• Gossip protocol is decentralized.

• No central coordinator exists.

• Every node operates independently.

• Gossip protocol is fault-tolerant.

• If a machine fails, data still spreads to remaining nodes.

• Gossip protocol is lightweight.

• It has proven to be fast and efficient in practice.

• Databases like React, Cassandra, and Dynamo use gossip for cluster membership.
• Consul, a service discovery system, uses gossip.
• Amazon S3 uses gossip to spread state information quickly.

Gossip protocol can be used to build a distributed rate limiter.

In any distributed system, nodes must quickly share information without relying on a shared data store.

Distributed rate limiter is a good example of such use.

We will discuss it later in the course.