Publish/Subscribe

Publish/Subscribe is a system where peers congregate around topics they are interested in. Peers interested in a topic are said to be subscribed to that topic:

Diagram showing a shaded area with curved outline representing a topic.Scattered within the shaded area are twelve dots representing peers. A labelpoints to the dots which reads “Peers subscribed to topic”.

Peers can send messages to topics. Each message gets delivered to all peers subscribed to the topic:

Diagram with two panels showing progression from left to right. In the firstpanel are scattered dots within a shaded area representing peers subscribed to atopic. From one of the dots comes a speech bubble labeled with “Message”. In thesecond panel all dots now have a copy of the speech bubble above themrepresenting that the message has been transmitted to all peers subscribed tothe topic.

Example uses of pub/sub:

  • Chat rooms. Each room is a pub/sub topic and clients post chat messages to which are received by all other clients in the room.
  • File sharing. Each pub/sub topic represents a file that can be downloaded. Uploaders and downloaders advertise which pieces of the file they have in the pub/sub topic and coordinate downloads that will happen outside the pub/sub system.

Design goals

In a peer-to-peer pub/sub system all peers participate in delivering messages throughout the network. There are several different designs for peer-to-peer pub/sub systems which offer different trade-offs. Desirable properties include:

  • Reliability: All messages get delivered to all peers subscribed to the topic.
  • Speed: Messages are delivered quickly.
  • Efficiency: The network is not flooded with excess copies of messages.
  • Resilience: Peers can join and leave the network without disrupting it. There is no central point of failure.
  • Scale: Topics can have enormous numbers of subscribers and handle a large throughput of messages.
  • Simplicity: The system is simple to understand and implement. Each peer only needs to remember a small amount of state.

libp2p currently uses a design called gossipsub. It is named after the fact that peers gossip to each other about which messages they have seen and use this information to maintain a message delivery network.

Discovery

Before a peer can subscribe to a topic it must find other peers and establish network connections with them. The pub/sub system doesn’t have any way to discover peers by itself. Instead, it relies upon the application to find new peers on its behalf, a process called ambient peer discovery.

Potential methods for discovering peers include:

  • Distributed hash tables
  • Local network broadcasts
  • Exchanging peer lists with existing peers
  • Centralized trackers or rendezvous points
  • Lists of bootstrap peers

For example, in a BitTorrent application, most of the above methods would already be used in the process of downloading files. By reusing peers found while the BitTorrent application goes about its regular business, the application could build up a robust pub/sub network too.

Discovered peers are asked if they support the pub/sub protocol, and if so, are added to the pub/sub network.

Types of peering

In gossipsub, peers connect to each other via either full-message peerings or metadata-only peerings. The overall network structure is made up of these two networks:

Diagram showing a large shaded area with many interconnected dots insiderepresenting connected peers all subscribed to the same topic. Thick, dark lineslabelled “Full-message peering” connect all the dots in a loose mesh, formingmany triangles and polygons. Between these lines runs a dense mesh of thinner,lighter lines labelled “Metadata-only peering”. These lines run from each dot toalmost every other dot around it, criss-crossing over each otherfrequently.

Full-message

Full-message peerings are used to transmit the full contents of messages throughout the network. This network is sparsely-connected with each peer only being connected to a few other peers. (In the gossipsub specification this sparsely-connected network is called a mesh and peers within it are called mesh members.)

Limiting the number of full-message peerings is useful because it keeps the amount of network traffic under control; each peer only forwards messages to a few other peers, rather than all of them. Each peer has a target number of peers it wants to be connected to. In this example each peer would ideally like to be connected to 3 other peers, but would settle for 24 connections:

Diagram showing a large shaded area with scattered dots inside connected bythick, dark lines representing full-message peerings between peers. Most of thedots have three dark lines running from them to other dots. One of the dots hasfour lines running from it and is labelled as “Peer reached upper bound”. Adifferent dot has only two lines running from it and is labelled “Peer reachedlower bound”.  Beneath the diagram is a legend reading “Network peering degree = 3;Upper bound = 4; Lower bound = 2“ accompanied with small symbols showing dotswith three, four and two lines running from themrespectively.

The peering degree (also called the network degree or D) controls the trade-off between speed, reliability, resilience and efficiency of the network. A higher peering degree helps messages get delivered faster, with a better chance of reaching all subscribers and with less chance of any peer disrupting the network by leaving. However, a high peering degree also causes additional redundant copies of each message to be sent throughout the network, increasing the bandwidth required to participate in the network.

In libp2p’s default implementation the ideal network peering degree is 6 with anywhere from 412 being acceptable.

Metadata-only

In addition to the sparsely-connected network of full-message peerings, there is also a densely-connected network of metadata-only peerings. This network is made up of all the network connections between peers that aren’t full-message peerings.

The metadata-only network shares gossip about which messages are available and performs functions to help maintain the network of full-message peerings.

Diagram showing a large shaded area with scattered dots inside connected bymany thin, light lines representing metadata-only peerings between peers. Thelines between the dots are labelled “Each peering is a network connectionbetween two peers”.

Grafting and pruning

Peerings are bidirectional, meaning that for any two connected peers, both peers consider their connection to be full-message or both peers consider their connection to be metadata-only.

Either peer can change the connection type by notifying the other. Grafting is the process of converting a metadata-only connection to full-message. Pruning is the opposite process; converting a full-message peering to metadata-only:

Diagram showing two side-by-side, two-step processes. In the first process isa thin, light line connecting two dots representing two peers connected by ametadata-only connection. From the left dot emanates a speech bubble reading“I’m grafting our connection into a full-message peering” below the speechbubble is an arrow showing the bubble travelling along the connection to the doton the right. In the following step, the line becomes thick, dark and is nowlabelled “Full-message peering”. The second process is the reverse of the firstprocess; two dots are connected by a thick, dark line which becomes a thin,light line labelled “Metadata-only peering”. The speech bubble reads “I’mpruning our connection back to a metadata-only peering.”

When a peer has too few full-message peerings it will randomly graft some of its metadata-only peerings to become full-message peerings:

Diagram with three panels showing a progression from top to bottom. In thefirst panel is a dot with many lines radiating out from it representing a peerwith many connections. Two of the lines are dark representing full-messageconnections. Next to this are a series of circles, the first two of which areshaded dark, labelled “Start with 2 full-content peerings”. The first threecircles in the series are labelled “Too few”. The next nine circles are labelled“Acceptable amount”. The circles after that are labelled “Too many”. The sixthcircle in the series is singled out with a label “Ideal”. In the second panel,four of the previously light lines radiating out from the dot have beenhighlighted green. A dice symbol is present indicating random selection of thenow highlighted lines. Four circles in the series are also highlighted green, upto the circle labelled “Ideal”. The panel is titled “Select more peers to graftto get to the ideal number”. In the final panel the highlighted green lines anddots have become dark to indicate they have become full-content peerings. Thetitle reads “Grafting complete”.

Conversely, when a peer has too many full-message peerings it will randomly prune some of them back to metadata-only:

Diagram with three panels showing a progression from top to bottom, similar tothe previous diagram. In the first panel is a dot with many lines radiating outfrom it representing a peer with many connections. Fourteen of the lines aredark representing full-message connections. There are also a few light lines inthe mix representing metadata-only peerings. Next to this are a series ofcircles, the first fourteen of which are shaded dark, labelled “Start with 14full-content peerings”. The first three circles in the series are labelled “Toofew”. The next nine circles are labelled “Acceptable amount”. The circles afterthat are labelled “Too many”. The sixth circle in the series is singled out witha label “Ideal”. In the second panel, eight of the previously dark linesradiating out from the dot have been highlighted pink. A dice symbol is presentindicating random selection of the now highlighted lines. Eight circles in theseries are also highlighted pink, from the end down to the circle labelled“Ideal”. The panel is titled “Select peers to prune to get the ideal number”. Inthe final panel the highlighted pink lines and dots have become light toindicate they have become metadata-only peerings. The title reads “Pruningcomplete”.

In libp2p’s implementation, each peer performs a series of checks every 1 second. These checks are called the heartbeat. Grafting and pruning happens during this time.

Subscribing and unsubscribing

Peers keep track of which topics their directly-connected peers are subscribed to. Using this information each peer is able to build up a picture of the topics around them and which peers are subscribed to each topic:

Diagram showing a large dot in the center surrounded by smaller dots which areconnected by thin, light lines to the large dot. The large dot is identified as“Viewing from this peer’s perspective” and the smaller dots are identified as“Directly-connected peer”. Behind the dots are five differently-colored shadedareas, some overlapping and some disjoint. Each area is labelled as a topic,from “Topic 1” to “Topic 5”. The shaded areas fade out with distance from thelarge, central dot indicating that the peer’s perspective has limited range.One of the smaller dots that does not share a shaded area with the large dot islabelled “Peers keep track of other’s subscriptions even if not subscribed tothe same topics as them”.

Keeping track of subscriptions happens by sending subscribe and unsubscribe messages. When a new connection is established between two peers they start by sending each other the list of topics they are subscribed to:

Diagram showing two dots connected by a thin, light line. Each dot has aspeech bubble emanating from it with an arrow showing it moving along theconnecting line towards the other dot. The left dot’s speech bubble says “I amsubscribed to: Topic 1, Topic 2, Topic 3”. The right dot’s speech bubble says “Iam subscribed to: Topic 1, Topic 5”.

Then over time, whenever a peer subscribes or unsubscribes from a topic, it will send each of its peers a subscribe or unsubscribe message. These messages are sent to all connected peers regardless of whether the receiving peer is subscribed to the topic in question:

Diagram showing two dots connected by a thin, light line. The left dot has aspeech bubble emanating from it with an arrow showing it moving along theconnecting line towards the right dot. The speech bubble says “I amsubscribed to: Topic 5. I am unsubscribed from: Topic 2, Topic 3.”

Subscribe and unsubscribe messages go hand-in-hand with graft and prune messages. When a peer subscribes to a topic it will pick some peers that will become its full-message peers for that topic and send them graft messages at the same time as their subscribe messages:

Diagram with two panels showing a downward progression. The first panel showsa central dot connected to two other dots, one to its left and one to its rightby thin, light lines. The right dot is inside a shaded area labelled “Topic 3”.Two speech bubbles emanate from the central dot, one pointing left towards theleft dot and the other pointing right towards the right dot. The left speechbubble says “I am subscribed to Topic 3”. The right speech bubble says “I amsubscribed to Topic 3. Also, I’m grafting our connection into a full-messagepeering.” The next panel shows the same three dots, however the central dot isnow inside the shaded area labelled “Topic 3” and the line connecting thecentral and right dots has become thick and dark indicating a full-messagepeering.

When a peer unsubscribes from a topic it will notify its full-message peers that their connection has been pruned at the same time as sending their unsubscribe messages:

Diagram with two panels showing a downward progression. It’s similar to theprevious diagram but reversed order. The first panel shows a central dotconnected to two other dots, one to its left and one to its right. The lineconnecting the central and left dots is thin and light while the line connectingthe central and right dots is thick and dark. The central and right dots areinside a shaded area labelled “Topic 3”. Two speech bubbles emanate from thecentral dot, one pointing left towards the left dot and the other pointing righttowards the right dot. The left speech bubble says “I am unsubscribed from Topic3”. The right speech bubble says “I am unsubscribed from Topic 3. Also, I’mpruning our connection back to a metadata-only peering.” The next panel showsthe same three dots, however the central dot is no longer inside the arealabelled “Topic 3” and the line connecting the central and right dots has becomethin and light like the left line to indicate a metadata-onlypeering.

Sending messages

When a peer wants to publish a message it sends a copy to all full-message peers it is connected to:

Diagram with two panels showing progression from left to right. The firstpanel is titled “Peer creates new message of its own”. A small, unlabelledspeech bubble emanates from a dot. The dot has four thick, dark lines radiatingoutward from it. The second panel is titled “Message sent to all otherfull-message peers”. It shows four copies of the speech bubble now moving awayfrom the dot along each of the four lines.

Similarly, when a peer receives a new message from another peer, it stores the message and forwards a copy to all other full-message peers it is connected to:

Diagram with three panels showing progression from left to right. The firstpanel is titled “Incoming message”. A small speech bubble travels alonga thick, dark line towards a dot indicating a peer. There are also three otherthick, dark lines radiating outward from the dot. The second panel is titled“Peer stores a copy of the message”. It shows the same dot with lines radiatingoutward. The speech bubble is now centred above the dot. The final panel istitled “Message forwarded to all other full-message peers”. It shows threecopies of the speech bubble now moving away from the dot along the three linesthat the speech bubble has not appeared on yet.

In the gossipsub specification, peers are also known as routers because of this function they have in routing messages through the network.

Peers remember a list of recently seen messages. This lets peers act upon a message only the first time they see it and ignore retransmissions of already seen messages.

Peers might also choose to validate the contents of each message received. What counts as valid and invalid depends on the application. For example, a chat application might enforce that all messages must be shorter than 100 characters. If the application tells libp2p that a message is invalid then that message will be dropped and not replicated further through the network.

Gossip

Peers gossip about messages they have recently seen. Every 1 second each peer randomly selects 6 metadata-only peers and sends them a list of recently seen messages.

Diagram with three panels showing progression from left to right. The firstpanel is titled “Every 1 second…”. It shows a dot with many thin, light linesradiating outwards representing metadata-only connections. A stopwatch symbol ispresent indicating passage of time. The second panel is titled “Select 6metadata-only peerings at random”. Six of the lines radiating outwards have beenhighlighted yellow and a dice symbol is present indicating random selection. Thefinal panel is titled “Send them a list of recently seen messages”. Each of thenow-highlighted lines has a speech bubble travelling along it moving outwardsfrom the central dot. The six speech bubbles are identical and read “I haveseen:” followed by three small speech bubble symbols inside the larger speechbubble, in different shades of purple to indicate three different messages.One of the small purple speech bubbles is labelled “Seen messages specify thesender and sequence number, but not the full message contents”.

Gossiping gives peers a chance to notice in case they missed a message on the full-message network. If a peer notices it is repeatedly missing messages then it can set up new full-message peerings with peers that do have the messages.

Here is an example of how a specific message can be requested across a metadata-only peering:

Diagram with six panels showing a downward progression. Each panel showstwo dots connected by a thin, light line representing two peers connectedby a metadata-only connection. Each of the dots also has several other linesradiating outwards, some thin and light, some thick and dark. These linesrepresent a mix of metadata-only and full-message peerings to other peers notpictured. The first panel is titled “Peer receives a message from theirfull-message peers”. On the left of the diagram there are three purple speechbubbles travelling along three thick, dark lines towards the dot on the left.The second panel is titled “Peer waits until heartbeat and selects randommetadata-only peers”. Above the left dot are stopwatch and dice symbolsrepresenting the passage of time and random selection. Three of the linesconnected to the left dot that were previously thin and light have now beenhighlighted yellow, including the line connecting the left and right dots. Thehighlighted lines represent the connections that were randomly selected. Thethird panel is titled “Newly received message is gossiped to metadata-onlypeers”. This panel still shows the yellow highlighted connections. Emanatingfrom the left dot and travelling along the line connecting it to the right dotis a speech bubble that reads “I have seen:” followed by a small purple speechbubble to represent the message that the left dot just received. The fourthpanel is titled “Peer notices that it does not have the gossiped message andrequests it”. The previously highlighted lines have gone back to being thin andlight. The right dot has a speech bubble emanating from it, travelling to theleft peer that reads “Please send:” followed by the same small purple speechbubble. The fifth panel is titled “Requested message is transferred”. There isnow a purple speech bubble travelling along the line connecting the two dotsfrom left to right. The final panel is titled “Newly received message isbroadcast to full-content peers”. There are now three copies of the purplespeech bubble travelling outwards from the right dot along the three thick, darklines connected to it.

In the gossipsub specification, gossip announcing recently seen messages are called IHAVE messages and requests for specific messages are called IWANT messages.

Fan-out

Peers are allowed to publish messages to topics they are not subscribed to. There are some special rules about how to do this to help ensure these messages are delivered reliably.

The first time a peer wants to publish a message to a topic it is not subscribed to, it randomly picks 6 peers (3 shown below) that are subscribed to that topic and remembers them as fan-out peers for that topic:

Diagram with two panels showing progression from left to right. The firstpanel is titled “Peer wants to publish a message to a topic it is not subscribedto”. It shows a small cluster of dots within a shaded area representing peerssubscribed to a topic. The dots are connected by a mix of thin, light and thick,dark lines representing metadata-only and full-message peerings. Outside theshaded area is a single dot representing a peer not subscribed to the topic.This dot is connected to several of the dots inside the shaded area by thin,light lines. The second panel is titled “Randomly select 3 peers subscribed tothe topic and remember them as fan-out peers”. In this panel, three of the linesconnecting the outside dot to dots inside the shaded area have become blue andnow have arrowheads at the end pointing towards the peer inside the shaded areathey are connected to. These lines represent fan-out peerings. A dice symbol ispresent indicating random selection of which metadata-only peerings becamefan-out peerings.

Unlike the other types of peering, fan-out peerings are unidirectional; they always point from the peer outside the topic to a peer subscribed to the topic. Peers subscribed to the topic are not told that they have been selected and still treat the connection as any other metadata-only peering.

Each time the sender wants to send a message, it sends the message to its fan-out peers, who then distribute the message within the topic:

Diagram with two panels showing progression from left to right. Each panelshows the same cluster of peers subscribed to a topic with a single peer outsideas shown in the previous diagram. The first panel is titled “New message sent tofan-out peers”. It shows three purple speech bubbles travelling along three bluearrows from the single towards peers inside the shaded area. This representsthree application messages being sent along three fan-out connections to threepeers subscribed to the topic. The second panel is titled “Once inside thetopic, the message is forwarded to all other subscribers as usual”. The purplespeech bubbles have moved from outside the shaded area to inside out. Now thereis a copy of the speech bubble above every dot in the shadedarea.

If the sender goes to send a message but notices some of their fan-out peers went away since last time, they will randomly select additional fan-out peers to top them back up to 6.

When a peer subscribes to a topic, if it already has some fan-out peers it will prefer them to become the full-message peers:

Diagram with two panels showing progression from left to right. Each panelshows the same cluster of peers subscribed to a topic with a single peer outsideas shown in the previous diagrams. The first panel is titled “Peer has existingfan-out peerings”. Of the lines that connect the dot outside the shaded areawith dots inside the shaded area, three of them are blue and have arrowheadspointing towards dots inside the shaded area, while the rest are thin, light andhave no arrowheads. This represents the peer not subscribed to the topic havingthree fan-out peerings with peers subscribed to the topic and the rest of itspeerings are metadata-only. The second panel is titled “Upon subscribing to thetopic, fan-out peerings preferentially become full-message peerings”. The singlepeer that was previously outside the shaded area is now inside it, representingthat it is now subscribed to the topic. The three previously-blue arrows havebecome thick, dark lines representing former fan-out peerings becomingfull-message peerings. The other lines from the dot are still thin and light asbefore.

After 2 minutes of not sending any messages to a topic, all the fan-out peers for that topic are forgotten:

Diagram with two panels showing progression from left to right. Each panelshows the same cluster of peers subscribed to a topic with a single peeroutside, including three blue, arrowed fan-out peerings as shown in the previousdiagrams. The first panel is titled “After not publishing any message for 2minutes…” There is a stopwatch above the single dot indicating the passage oftime. The second panel is titled “All fan-out peerings revert to metadata-onlypeerings”. In this panel the three previously blue, arrowed lines connectingthe single dot to dots inside the shaded area have become thin and light,representing the peer’s fan-out peerings becoming metadata-only peerings.

Network packets

The packets that peers actually send each other over the network are a combination of all the different message types seen in this guide (application messages, have/want, subscribe/unsubscribe, graft/prune). This structure allows several different requests to be batched up and sent in a single network packet.

Here is a graphical representation of the overall network packet structure:

Diagram showing a large speech bubble titled “Network packet”. The bubble isdivided into four main sections titled “Application messages”, “I have seenthese messages”, “Please send me these messages”, “Subscription changes” and“Grafting and pruning”. Inside the section titled “Application messages” is asmaller, purple speech bubble labelled “Application message”. The purple speechbubble contains several filled-in fields in the style of a paper form. Thesender field says “Peer A”. The sequence number field says 5. The recipients(topic ID’s) field had three lines, which read “Topic 1”, “Topic 2”, and “Topic3”. The message body field says “The heaviest domestic cat on record is 21.297kilograms.” The final two fields are for the sender public key and sendersignature. Each of these contains a series of random-looking numbers between 0and 255, representing a series of bytes. Below the purple speech bubble isanother also labelled “Application message”, however this bubble fades out andno fields are visible, representing the presence of additional applicationmessages that have been elided for presentation in this diagram. In the sectiontitled “I have seen these messages” (subtitle: “IHAVE”), there is a table withthree columns. The columns are titled “Recipient (Topic ID)”, “Sender” and“Sequence number”. There are three rows in the table, each row populated with atopic name, sender and sequence number. The data is illustrative and theparticular values are not significant. In the section titled “Please send methese messages” (subtitle: “IWANT”), there is a table similar to the previousone but with only sender and sequence number columns; the recipient column isnot present. Again, there are three rows in the table, populated withillustrative senders and sequence numbers. In the section titled “Subscriptionchanges” is a table with two columns. The first column is titled “For thistopic…” and the second column is titled “I want to…”, with the choice ofsubscribe or unsubscribe. The table has three rows populated with data. Twoof the topics are being subscribed to and one is being unsubscribed from. In thefinal section, which is titled “Grafting and pruning” is another table with twocolumns, similar to the previous table. The first column is titled “For thistopic…”, however the second column is titled “You have been…” with the choice ofgrafted or pruned. There are three rows in this table. Two of the topicshave been grafted and one has been pruned (no particular connection to theprevious table).

See the specification for the exact Protocol Buffers schema used to encode network packets.

State

Here is a summary of the state each peer must remember to participate in the pub/sub network:

  • Subscriptions: List of topics subscribed to.
  • Fan-out topics: These are the topics messaged recently but not subscribed to. For each topic the time of the last sent message to that topic is remembered.
  • List of peers currently connected to: For each peer connected to, the state includes all the topics they are subscribed to and whether the peering for each topic is full-content, metadata-only or fan-out.
  • Recently seen messages: This is a cache of recently seen messages. It is used to detect and ignore retransmitted messages. For each message the state includes who sent it and the sequence number, which is enough to uniquely identify any message. For very recent messages, the full message contents is kept so that it can be sent to any peers that request the message.

Diagram titled “Peer state”. There are four sections titled “Topics Isubscribe to”, “Topics I recently sent a message to”, “Peers currently connectedto” and “Recently seen messages”. In the section titled “Topics I subscribe to”is a list of three arbitrary topic names, “Topic 1”, “Topic 4” and “Topic 5”. Inthe section titled “Topics I recently sent a message to” (subtitle: “but don’tsubscribe to”), is a table listing topic IDs and the time of last sent messagefor each topic ID. There are two topics listed, Topic 6 and Topic 7, with lastmessages sent 10 seconds ago and 35 seconds ago respectively. The sectiontitled “Peers currently connected to” contains a large table. The columnsare titled “Peer ID”, “Topics they subscribe to”, and “Type of peering“which has the choice of full-message, metadata-only or fan-out. The table ispopulated with six different peers, some of which are subscribed to severaltopics, so have multiple rows in the “Topics they subscribe to” and “Type ofpeering” columns. For each topic that each peer subscribes to one of theboxes is ticked for full-message, metadata-only or fan-out. The topics forwhich full-message is ticked are all topics listed above in the “Topics Isubscribe to” section. Likewise, for the topics which fan-out is ticked, thetopics all appear above in the “Topics I recently sent a message to”section. In the final section, which is titled “Recently seen messages”, isanother large table. The columns are “Sender (Peer ID)”, “Sequence number”,“Time first seen” and “Full message”. The first four table rows arebracketed with a label “Last few seconds”. Rows within this bracket all havethe full message column populated with a purple speech bubble representingthat the full message contents are remembered as part of the state formessages seen in the last few seconds. All eight of the table rows arebracketed with the label “Last 2 minutes”, however for the last four rowsthe full message column is empty. These rows only have the sender (Peer ID),sequence number and time first seen columns populated. The table rows arelisted in order of time first seen, from 1 second ago in the top row to 90seconds ago in the bottom row. Some of the sequence numbers are shared betweenmessages, but only where the sender is different.

More information

For more detail and a discussion of other pub/sub designs that influenced the design of gossipsub, see the gossipsub specification.

For implementation details, see the gossipsub.go file in the source code of go-libp2p-pubsub, which is the canonical implementation of gossipsub in libp2p.