The Piece Selection algorithm that makes BitTorrent fault tolerant



421 views BitTorrent Internals



In a BitTorrent network, the file is split into pieces and then distributed across the network. A piece is a unit of transmission and when a peer has all the pieces it concatenates them and re-creates the entire file.

Importance of Piece Selection strategy

Having a piece selection strategy is important because what if every single peer starts with the first piece first, this would increase the load on the peers/seeders that have them; thus reducing the speed of distribution.

What if before anyone could download the last few pieces, the seeder (having all the pieces) leave the network? none of the lechers would be able to complete their download.

Rarest-first Piece Selection

Core idea: prioritize the download of the piece that is the rarest in the network.

Advantages

Spreading the seed

Rarest-first piece selection strategy ensures only “new” pieces (that are with no other leechers) are downloaded from the seeder. We get a quick distribution of pieces in the network and a reduced load on the seeder.

Increases download speed

Since more peers have a variety of pieces, they can quickly trade among themselves and complete downloads faster.

Enabling upload

When a peer has a rare piece, every other peer would be interested in downloading it. Because of reciprocation, it would be frequently unchoked from others, getting a better download speed.

Preventing rarer missing piece

By prioritizing the download of the rarest pieces, we ensure that rare pieces do not go missing from the network even when the seeder leaves.

How to compute the rarest piece?

There are two ways to know which pieces the peers have

  1. Have messages: a peer in the network broadcasts the pieces it has
  2. Bitfield message: during the initial handshake, a peer sends a Bitfield message that contains the pieces that it holds.

Every peer maintains the piece availability across its peer set and uses it to compute the rarest piece.

Random First Policy

When a peer joins a network, to proactively participate, it would need to get the first piece as soon as possible, and hence instead of picking the rarest first, it goes for random pieces.

Strict Priority Policy

A file is split into pieces and a piece is split into blocks. Blocks are what get transferred. Hence, when a block of a piece is fetched, we prioritize downloading all the blocks of the same piece before moving on to the new one.

End Game Mode

Downloading the last few pieces may take time and hence a peer. In the end game mode, a peer sends a request to all the peers for every block that is remaining.

The peers respond with the block and this completes the download faster.


Arpit Bhayani

Arpit's Newsletter

CS newsletter for the curious engineers

❤️ by 17000+ readers

If you like what you read subscribe you can always subscribe to my newsletter and get the post delivered straight to your inbox. I write essays on various engineering topics and share it through my weekly newsletter.




Other essays that you might like


Exploiting and stealing from the BitTorrent network

406 views 17 likes 2022-08-19

Stealing is bad, but in a P2P network, it is a cakewalk. In this 7th video of the BitTorrent Internals series, we take ...

Kademlia - a Distributed Hash Table implementation to power the overlay network of BitTorrent

667 views 36 likes 2022-08-17

Kademlia is a Distributed Hash Table implementation and it is used as an overlay network for BitTorrent. Instead of talk...

The Piece Selection algorithm that makes BitTorrent fault tolerant

421 views 22 likes 2022-08-15

Performance of the BitTorrent network relies heavily on the order in which the pieces are requested by the peers. In th...

The Choke Algorithm that powers BitTorrent

517 views 23 likes 2022-08-12

One of the most important algorithm that powers BitTorrent is The Choke Algorithm In this 4th video of the BitTorrent I...


Be a better engineer

A set of courses designed to make you a better engineer and excel at your career; no-fluff, pure engineering.


System Design Masterclass

A masterclass that helps you become great at designing scalable, fault-tolerant, and highly available systems.

800+ learners

Details →

Designing Microservices

A free playlist to help you understand Microservices and their high-level patterns in depth.

17+ learners

Details →

GitHub Outage Dissections

A free playlist to help you learn core engineering from outages that happened at GitHub.

67+ learners

Details →

Hash Table Internals

A free playlist to help you understand the internal workings and construction of Hash Tables.

25+ learners

Details →

BitTorrent Internals

A free playlist to help you understand the algorithms and strategies that power P2P networks and BitTorrent.

42+ learners

Details →

Topics I talk about

Being a passionate engineer, I love to talk about a wide range of topics, but these are my personal favourites.




Arpit's Newsletter read by 17000+ engineers

🔥 Thrice a week, in your inbox, an essay about system design, distributed systems, microservices, programming languages internals, or a deep dive on some super-clever algorithm, or just a few tips on building highly scalable distributed systems.



  • v12.7.8
  • © Arpit Bhayani, 2022

Powered by this tech stack.