The idea: every downloader also uploads

One server that sends a file to N clients must push N copies through its own uplink. The more clients, the longer it takes. In peer-to-peer (P2P) file sharing, a peer that has part of the file sends it on to others. Each new peer brings its own upload capacity, so the group, the swarm, gets faster as it grows. BitTorrent is the best known protocol of this kind.

A .torrent file with the info_hash and 8 piece hashes. A new peer asks the tracker or the DHT for peers, gets a list, then trades pieces with a seed and three leechers; arrows show pieces flowing in every direction between peers.
The .torrent names the file; the tracker or the DHT names the peers; the pieces then flow between peers, not from one server.

The page has a seed S (it has the whole file) and four leechers P1-P4 with nothing yet. P5 waits outside until it joins. Pieces move in rounds of 10 seconds. In each round an uploader sends one piece to each peer it has unchoked. The boxes that fly between peers are pieces, coloured by piece number.

Pieces and the info_hash

A torrent cuts the file into pieces of equal size, usually 256 KiB to 4 MiB. The page uses 8 pieces, numbered 0 to 7. The .torrent file lists the SHA-1 hash of every piece, so a peer can check each piece on its own and throw away a bad one. The SHA-1 hash of the torrent's info section is the info_hash. It names the torrent everywhere: in the tracker request, in the handshake between peers and in the DHT. A magnet link holds little more than the info_hash.

Peers talk over TCP. After a handshake (protocol name, info_hash, peer_id) each side sends a bitfield, one bit per piece it has, and then a have message for each new piece. The other messages are interested, choke/unchoke, request and piece. The page sums them up per round.

Finding peers: the tracker

A tracker is a server that keeps the list of peers for each info_hash. It never touches the file. A peer sends it an HTTP announce with the info_hash, its peer_id and port, and how much it still needs (left). The tracker answers with a list of peers and an interval: when to announce again, often about 30 minutes. In Demo 1, P5 announces with left=8, gets back S, P1, P2, P3 and P4, and then shakes hands with all five.

No tracker: the Kademlia DHT

A tracker is a single point of failure. The Mainline DHT (BEP 5) replaces it with a distributed hash table built on Kademlia. Every DHT node has a random 160-bit ID; the page uses 6 bits. The peer list for a torrent is kept by the nodes whose IDs are closest to its info_hash. Kademlia measures closeness with XOR: the distance from a to b is a XOR b, read as a number. Two IDs that share a long run of leading bits are close.

Each node keeps a routing table of k-buckets. Bucket i holds up to k contacts (k = 8 in BitTorrent, 2 here) whose distance has its highest bit at position i. So a node knows many nodes near itself and only a few far away, but at least one in every range. To look up a key, a node asks the closest contact it knows with get_peers. A node that holds peers for the key answers with them (values). Any other node answers with the k contacts it knows closest to the key (nodes). Each answer shares at least one more leading bit with the key than the node that sent it, so a lookup in a DHT of n nodes takes about log2 n steps.

A row of six-bit IDs. The key 45 is 101101. P5 (000110) first asks 32 (100000), distance 13, 2 matching leading bits; 32 points to 41 (101001), distance 4, 3 bits; 41 points to 44 (101100), distance 1, 5 bits, which holds the peer list.
Every hop matches more leading bits of the key, so the XOR distance falls fast: 13, then 4, then 1.

In Demo 2, P5 (ID 6) looks up 45 = 101101. It asks 32 (distance 13), which points to 41 and 43. It asks 41 (distance 4), which points to 44 and 46. Node 44 (distance 1) holds the peer list, so 3 queries are enough. P5 then sends announce_peer, with a token it got from the answer, to the closest nodes, so the next newcomer finds it too. In Demo 3 node 44 is down: its query times out, and P5 asks 46, the next closest, which also holds the list. A dead node costs one timeout, not the lookup. Real lookups send α = 3 queries at once, so a slow node hardly matters.

Kademlia is one way to map a key to the nodes that are responsible for it. A Dynamo-style hash ring is another: see Consistent Hashing. A ring needs every node to know the full membership; Kademlia needs only a few contacts per distance range.

Which piece next: rarest first

A downloader can choose any piece the uploader has and it lacks. BitTorrent asks for the rarest one: the piece with the fewest copies among the peers it knows (the "copies of each piece" row on the canvas). Common pieces can be had from anybody later. Rare ones may vanish. The page breaks ties by the lowest piece number; real clients pick at random among the rarest, and pick the very first piece at random so they have something to trade quickly.

The difference shows when the seed leaves. In Demo 6 peers pick at random and S leaves after round 4. In those 4 rounds S sent 8 pieces, but some went to peers that already had a copy, so piece 3 never left the seed. After S leaves, nobody has it, and nobody can ever finish. In Demo 7 the same seed with rarest first sends each of the 8 pieces once, the swarm keeps a full copy, and every peer finishes.

Who gets my upload: choking and tit-for-tat

A peer cannot upload well to everyone at once, so it chokes most peers and unchokes a few. Every 10 seconds it unchokes the peers that uploaded to it fastest over the last 20 seconds (4 regular slots in real clients, 1 on the page). That rule is tit-for-tat: you get the most from the peers you give the most to. On top of that, one optimistic unchoke slot goes to a peer chosen in turn, and it changes every 30 seconds. It lets a new peer with nothing to offer get its first pieces, and it lets a peer find partners that are faster than its current ones. A finished peer (a seed) has nothing to gain, so it serves peers in turn (round robin).

A free rider downloads but never uploads. In Demo 8 P4 is one. After 4 rounds P1, P2 and P3 have 5, 5 and 6 pieces, but P4 has only 3: it never earns a tit-for-tat slot and gets pieces only from the seed and from optimistic unchokes. Run Finish from there and P4 still gets the whole file, because in a swarm this small the peers soon have spare upload. Researchers showed the same in large swarms (the BitThief client); tit-for-tat slows free riders down rather than shutting them out.

How long it takes: client-server vs P2P

Let F be the file size, us the server's (seed's) upload rate, ui the upload rate of peer i and dmin the slowest download rate. With N peers, Kurose and Ross give these lower bounds on the time until everyone has the file:

lower bound on the timewhy
client-servermax(N·F/us, F/dmin)the server sends N copies alone
P2Pmax(F/us, F/dmin, N·F/(us + Σui))the seed sends at least one copy; together they send N copies

On the page F = 8 pieces, us = 2 pieces per round, ui = 2 and download is unlimited. With N = 4 the client-server bound is 4·8/2 = 16 rounds, and Demo 5 takes exactly 16. The P2P bound is max(8/2, 32/10) = 4 rounds. Demo 4 takes 6 rounds: a piece must arrive before it can be sent on, and early on the peers have little to trade. Add P5 (N = 5) and client-server needs 20 rounds, while the P2P bound stays at 4.

Graph of the minimum time in rounds against the number of peers N from 1 to 30. The client-server line rises straight, 4 rounds per peer, to 120. The P2P bound stays at 4 rounds and approaches 4 from below as N grows.
Client-server time grows with every peer; the P2P bound stays flat because each peer adds upload capacity.

Real swarms are limited by the network too: see Network Delay and Throughput for why the slowest link sets the rate. Many peers sit behind home routers that block incoming connections, which is why BitTorrent also uses hole punching and the uTP protocol over UDP; see NAT. For another way a large group spreads information without a central server, see Gossip and SWIM.

What the page leaves out

  • Blocks: a peer requests 16 KiB blocks of a piece, keeps several requests in flight, and checks the piece hash at the end. Endgame mode, which asks every peer for the last blocks, is not shown.
  • Real rates and times: the page moves whole pieces in fixed 10-second rounds and lets downloads be unlimited.
  • The full Kademlia lookup: α = 3 parallel queries, continuing until the k closest nodes have answered, tokens that expire, bucket refresh and node churn. UDP messages are bencoded, and IDs are 160 bits.
  • Peer exchange (PEX), local peer discovery, web seeds, super-seeding, encryption and uTP congestion control.

On the mind map

Open the Distributed Systems mind mapDistributedSystemsReplication: copies of data · what reads seeReplicationPartitioning: split data over nodesPartitioningTime and membership: order events, know who is aliveTime and membershipConsensus: agree on one value or logConsensusTransactions: one change across many servicesTransactionsMessaging: send events between systemsMessagingKafka internals: a replicated append-only logKafka internalsRedis internals: one thread, data in memoryRedis internalsKubernetes: reconcile desired stateKubernetesResilience and speed: stay up and fast under loadResilience and speedPartitioning vs shardingPartitioning vs shardingone server vs many; shard key mattersConsistent hashingConsistent hashingring: adding a node moves few keysBitTorrent and the DHTEvery downloader also uploadsRange vs hash partitioningRange vs hash partitioningrange: fast scans; hash: no hot spotRebalancing partitionsRebalancing partitionsmod N vs fixed vs dynamic: keys movedRedis ClusterRedis Cluster16384 hash slots, MOVED and ASKMapReduceMapReducemap, shuffle by key, reduceSpark RDD lineageSpark RDD lineageLazy recipe; shuffle cuts stagesMapReduce joinsMapReduce joinssort-merge, skew, broadcast and merge joinsS3 object storageS3 object storagedata plus parity shards rebuild a fileRendezvous hashingRendezvous hashinghighest hash score of key+node winsHDFS / GFS file layoutHDFS / GFS file layoutNamenode maps blocks; datanodes pipelineOpen the Distributed Systems mind mapDistributed Systemssplit data over nodesPartitioningPartitioning vs shardingPartitioning vs shardingone server vs many; shard key mattersConsistent hashingConsistent hashingring: adding a node moves few keysBitTorrent and the DHTEvery downloader also uploadsRange vs hash partitioningRange vs hash partitioningrange: fast scans; hash: no hot spotRebalancing partitionsRebalancing partitionsmod N vs fixed vs dynamic: keys movedRedis ClusterRedis Cluster16384 hash slots, MOVED and ASKMapReduceMapReducemap, shuffle by key, reduceSpark RDD lineageSpark RDD lineageLazy recipe; shuffle cuts stagesMapReduce joinsMapReduce joinssort-merge, skew, broadcast and merge joinsS3 object storageS3 object storagedata plus parity shards rebuild a fileRendezvous hashingRendezvous hashinghighest hash score of key+node winsHDFS / GFS file layoutHDFS / GFS file layoutNamenode maps blocks; datanodes pipeline
This page on the Distributed Systems mind map · 88 pages in 10 branches · open it to see the whole map and test yourself in recall mode.