How Gnutella Scaled to Handle Query Traffic

Senior software engineer blogging about software systems, computing history, and practical engineering.

How Gnutella Scaled to Handle Query Traffic

By the year 2007, Limewire was installed on a third of desktop computers and estimates from the year prior showed a concurrent node count in the millions. Routing that much traffic in a peer-to-peer system gets complicated.

This is part two of my Gnutella exploration series. Please read the Gnutella Explanation article first if you are not already familiar with Gnutella.

In the previous article, I explained that Gnutella queries permeated the network by being passed through a mesh of peers. Each peer would inspect a query and then pass it to its neighbors. When one of those peers found a matching file, it would send a Query Hit message back in the direction from which the query arrived.

This is true for the earliest versions of the protocol, but I was not being entirely honest.

That method of searching was known as flood routing . A query was sent outward without knowing which peers might actually have something relevant.

Later Gnutella clients still forwarded queries through the network, but they became much better at deciding which parts of the network were worth bothering. The new system was called the Query Routing Protocol , or QRP.

QRP allowed a connection to advertise which search terms might be reachable without the need for central file indexes.

Many Gnutella explainer articles (and Gnutella skeptics) still describe the network as though every query was sprayed toward every peer. I used to believe them, too.

Flood routing is a convenient half-truth we tell for the sake of moving an explanation along, like the time I told my son that semicolons in JavaScript are optional.

The lie is useful because flood routing is extremely easy to explain. It is not useful if you want to understand how Gnutella grew beyond its early experimental phase. Blindly sending every search to every reachable machine was not going to work at the scale of peak Gnutella in the mid-2000s.

The Old Routing System

You can't really call it a network protocol if there is only one working implementation. That's just network software, not a protocol. A good protocol should be simple enough that independent developers can implement it, and flood routing met this goal despite efficiency issues.

You can fit the entire query model in your head:

Send a query to every connected peer.

Decrease its TTL.

Have those peers repeat the process until the TTL reaches zero.

Suppress duplicate queries using the query's unique identifier.

Return any results along remembered reverse routes.

This simplicity gave early Gnutella an ecosystem of diverse clients and, importantly, people actually using the network. Flood routing was not free, though.

Suppose every peer has four connections. The first peer might forward a query to four neighbors. Each of those peers normally excludes the connection from which the query arrived, so a tree-like expansion would start at 4, then expand to 12, 36, 108, and so on.

A real mesh contains cycles, duplicate suppression, and peers with different connection counts, so the actual numbers vary. The important part is that the amount of traffic still grows very quickly.

Most of those peers will not have anything relevant to the search, but they must receive the message, parse it, inspect it, remember its identifier, and decide whether to forward it again.

The network therefore spends most of its query bandwidth proving that peers do not have the requested file.

This is tolerable when the network contains a few thousand machines. It becomes expensive when the network contains millions of machines and every user is typing searches at the same time.

The scalability problems were eventually demonstrated with sciencey PDFs that clearly did the math.

Leaves and Ultrapeers

Early Gnutella was an undifferentiated mesh of peers. Later versions that used QRP divided nodes into two roles:

A leaf sat at the edge of the network.

An ultrapeer participated in a highly connected upper tier.

This may sound like client-server architecture, but there was no permanent server and no central authority deciding who could become an ultrapeer.

An ultrapeer was still an ordinary Gnutella user running an ordinary Gnutella client. The difference was that an ultrapeer, unlike a leaf node, had enough bandwidth, uptime, memory, and network reach to perform additional routing work. Ultrapeers were usually those super lucky power users with a DSL connection and a high-end Windows 2000 box with 2 GBs of RAM.

Some clients will automatically promote a node based on things such as uptime, firewall status, available memory, file descriptors, and bandwidth.

A more plebeian peer on a dial-up connection behind a firewall, or with low uptime would operate as a leaf.

Leaves maintained connections to several ultrapeers for redundancy. Ultrapeers...