pieces, rarest-first, choking
Bram Cohen designed BitTorrent around splitting files into pieces, fetching the rarest first and choking to reward uploaders, so that popular files get faster, not slower, as more people download.
Architecture Patterns · lesson 5 of 7 · about 28 min
Peer-to-peer systems
Systems with no central server: why capacity grows with the number of users, how a swarm keeps a file alive after the seed leaves, how a distributed hash table finds data in a handful of hops, how to store data on unreliable peers, why people upload at all, and how one attacker with many identities can break a DHT. Tap any for a plain-language card.
0 / 9 sections done
Every downloader is also a server
A thousand people want the same 4 GB file from a server with a 1 Gbps link. Whose bandwidth should carry it?
The classic textbook model (Kurose and Ross) gives the minimum time as the largest of three limits: the server sending one copy, the slowest client downloading one copy, and the total bytes everyone must receive divided by the total upload capacity of server plus peers. Real swarms do not reach that ideal, but the shape is right: client-server time rises roughly linearly with N, peer-to-peer time levels off. Move the sliders.
1,000 clients, a 4 GB file and a 1 Gbps server: client-server needs about 8.9 hours; with peers each uploading 20 Mbps the same job takes about 25 minutes.
Speed-up from peers21.0×
Server must upload (client-server)4,000 GB
Server must upload (peer-to-peer)190 GB
1,000 clients, 4 GB, a 1,000 Mbps server: client-server takes 8.9 h, peer-to-peer takes 25 min at best, because 1,000 peers add 20.0 Gbps of upload to the server's 1.0 Gbps.
Idealised minimum times: client-server = max(N·F ÷ server upload, F ÷ slowest download); peer-to-peer = max(F ÷ server upload, F ÷ slowest download, N·F ÷ (server upload + N × peer upload)). Peers download at 100 Mbps.
Pieces and swarms
The original seed will leave after a while. Will the crowd still be able to finish the file without it?
This is a small round-based simulation: 60 pieces, each node uploads one piece a round (the seed two), each peer asks a random neighbour for one piece a round, and finished peers keep seeding. The seed leaves at the round you choose. Switch the policy and watch how many copies of the rarest piece exist: when that hits zero, the file is dead.
With the seed staying 40 rounds, rarest-first lets all 40 peers finish (about 67 rounds on average); random choice leaves 10 pieces that no one has and nobody finishes.
Peers finished40 of 40
Pieces nobody has0
Mean time to finish67 rounds
With rarest-first choice every one of the 40 peers finished, on average after 67 rounds, even though the seed left at round 40.
Round-based toy model with 60 pieces and 8 neighbours per peer. The top chart is the minimum number of copies of any piece (shaded: after the seed leaves); the bottom is peers finished.
Finding things with no index server
Who has the piece, or the file, or the key? No node knows everyone. How does a question find its answer in a few hops?
That is the Chord design (2001); Kademlia (2002), used by BitTorrent's Mainline DHT and Ethereum's node discovery, reaches the same logarithmic bound using XOR distance. This page runs real Chord lookups over a random ring. Grow the network from a thousand to a few thousand nodes and watch the hops barely move.
1,000 nodes need about 5.8 hops on average (about half of log₂ 1000 ≈ 10). Walking the ring one node at a time would take about 500.
Average hops (400 lookups)5.83
Worst lookup11 hops
Typical lookup time466 ms
Pointers per node~10
Ring walk instead~500 hops
In a ring of 1,000 nodes the average lookup took 5.8 hops (the worst 11), about 466 ms at 80 ms per hop. Every node knew only about 10 others.
Real Chord lookups over random 24-bit node ids, 400 random keys, using finger tables; no failures here (see the next scene for churn).
Nobody promises to stay
Your data lives on laptops that sleep, phones that lose signal and users who uninstall. How many copies is enough?
Availability is only half of it. Whenever a peer leaves for good, the fragments it held are gone and must be rebuilt elsewhere, or the redundancy slowly drains away; this repair traffic is a continuous cost of peer-to-peer storage. Set how reliable peers are, and compare. Same overhead, very different results.
Peers online half the time, 3× storage: 3 replicas give 87.5% availability; 10-of-30 erasure coding gives 97.9%. Peers online only 30% need 20 replicas for 99.9%.
Replicas needed for 99.9% (full copies)10
Repair traffic per peer1.85 Mbps
Storage overhead3×
With peers online 50% of the time and 3× storage, 3 replicas are available 87.5% of the time and 10-of-30 erasure coding 97.9%. To reach 99.9% with full copies you would need 10. Keeping redundancy up costs each peer about 1.85 Mbps of repair traffic.
Replication: 1 − (1 − a)^r. Erasure coding: P(at least k of n peers up), exact binomial. Repair = data per peer ÷ average lifetime. Peers are assumed independent, which real failures (a shared ISP, a shared timezone) are not.
Why would anyone upload?
Uploading costs you bandwidth and gives you nothing directly. Why not download and disappear?
The effect is that contributors trade with each other at full speed while free-riders live on the leftover optimistic slots. The numbers here are an idealised model (each peer splits its upload u into 4 slots; free-riders upload nothing), not a measurement of any real client, and real BitTorrent can still be gamed, but the incentive direction is clear. Raise the free-rider share and compare.
With 20% free-riders and 10 Mbps uploads: contributors average 9.5 Mbps and free-riders 2 Mbps under tit-for-tat, while in an altruistic network everyone gets 8 Mbps.
Contributor downloads in56 min
Free-rider downloads in4.4 h
Free-rider penalty4.8× slower
With 20% free-riders, tit-for-tat gives contributors 9.5 Mbps and free-riders 2.0 Mbps, so a 4 GB file takes 56 min versus 4.4 h. In an altruistic network everyone, including the free-riders, would get 8.0 Mbps.
Idealised choking model: contributors receive 3 reciprocated slots (3u/4) plus the optimistic share; free-riders only the optimistic share, c·u/4, where c is the contributor fraction.
Which design?
Six jobs, four designs.
Peer-to-peer is not better or worse than client-server; it is a different trade. Pick the design that fits each job. Each answer is worth 20 XP.
Ask: do you need a trusted authority, mass distribution of the same bytes, lookup with no index, or a mix?
Question 1 / 6
Bank balances and transfers must be correct, auditable and controlled by one company.
Tip: press 1 to 4 to answer, Enter for the next one.
Who lives by this
From BitTorrent to Windows Update.
Published examples of peer-to-peer ideas in production, and one where they were retired.
XOR-metric DHT
Kademlia, by Petar Maymounkov and David Mazieres, finds a key in a logarithmic number of hops using XOR distance; it underlies BitTorrent's Mainline DHT, and similar designs are used for node discovery in systems such as Ethereum and IPFS.
supernodes and a peer cache
Skype once relied on well-connected user machines as supernodes and Spotify's desktop client once fetched music partly from other users; both later moved the work to company-run infrastructure as bandwidth got cheaper and control, reliability and privacy mattered more.
update sharing
Windows can download update pieces from other PCs on the same network or from other machines as well as from Microsoft's servers, reducing the bytes each device pulls from the internet; it is a hybrid, with servers as the reliable fallback.
Interview angle
What interviewers actually ask.
Six questions, each worth 20 XP. Peer-to-peer answers are judged on whether you know both the strengths and the costs.
Name the benefit (capacity, no single point) and the cost (churn, trust, incentives).
Question 1 / 6
Why does a peer-to-peer network's capacity grow with its number of users?
Tip: press 1 to 3 to answer, Enter for the next one.
Break it
Anyone can join a DHT, and joining is free. What happens when one person joins with a thousand fake nodes?
Defences all work by making identities costly or constrained: tie the id to something scarce (an IP address, a proof-of-work puzzle, a stake), restrict how many ids can come from one network, store each key on nodes found by several independent routes, and verify data by hash or signature so a wrong answer is detected. Raise the puzzle difficulty below and watch the attack price climb, while an honest node still pays it only once.
1,000,000 nodes, no puzzle, a laptop doing 100 million hashes/s: eclipsing a key takes about 0.01 s. With a 24-bit puzzle the same attack takes about 1.9 days, while a new honest node pays 0.17 s once.
Time to eclipse one chosen key10 ms
Honest node's one-off join costunder a millisecond
Fake share of the network0.10%
Random keys with 11+ fake replicas≈ 0
Spreading 1,000 fake nodes at random barely matters (0.10% of the network, almost no keys affected). Choosing ids to surround one key is the real attack: about 1.0e+6 hashes, 10 ms at 100 MH/s, while a joining honest node pays under a millisecond once.
Model: each node id costs 2^bits hashes; to put k ids among the k closest to a chosen key an attacker must try about N candidate ids. Random placement: a key is lost if a majority of its k replicas are fake (exact binomial).