How BitTorrent's Rarest First Algorithm Ensures Fault Tolerance

[00:00:00]so the performance of the BitTorrent Network relies heavily on the order in which the pieces are requested by the peers in this fifth video of the BitTorrent internal series we take a look at the peace selection algorithm that BitTorrent uses and learn how it makes the network fault tolerant while ensuring a very fast download rate across the network but before we move forward I'd like to talk to you about a portion system design that I have been running for over a year now the course is a cohort based course which means I won't be rambling a solution and it will not be a monologue instead a small focus group of 50 60 Engineers every cohort will be brainstorming systems and designing it together this way we build a solid system and learn from each other's experiences the course to date is Android by 600 plus Engineers spanning 9 cohorts and 10 countries Engineers from companies like Google Microsoft GitHub slack Facebook Tesla Yelp Flipkart drip 11 and many many many more have taken this course and have some wonderful things to say the coolest part about the course is the depth we go into and the breadth we cover we cover topics ready from real-time text communication for slack to designing our own toy load balancer to Quick buses live text commentary to doing impressions counting at scale for any advertisement business in all we would cover roughly 28 questions and the detailed curriculum uh split week by week can be found on the course page which is linked in the description down below so if you are looking to learn system design from the first principles you will love this course I have two offerings for you the first one is the live cohort viscose which you see on the left side and the second one is the recorded course which you can see on the right side the Live code base course happens every two months and it will go on for eight weeks while the recorded course contains the recordings from one of the past cohorts as is if you are in a hurry and want to bench learn system design I would highly recommend you going for the recorded one otherwise the Live code is where you can participate and discuss things live with me and the entire cohort and amplify your learnings the decision is totally up to you the course details prerequisites testimonials can be found on the course pagemary dot me slash masterclass and I would highly recommend you to check that out I put the link of the course in the description down below so if you are interested to learn system design go for it check out the link in the description down below and I hope to see you in my next cohort so the original file that is shared in the network is split into pieces the length of each piece depends on the torrent that you have but it would be constant for a particular torrent let's say it's 256 KB to 1 MB right so every piece let's say every piece in our torrent is 1 MB big right so what would happen is if if a file has if a file has length of 3 MB and we take a piece size of 1 MB what would happen we would have three pieces overall each of this piece is passed to the hash function which computes a sharp one hash of it and this hash is placed in the dot torrent file through this we when we are trying to download a particular file we know that these are the pieces this is what we want and this is how we can get it right so as part of First Step you would want to download a torrent file you've got you'll go to the tracker to say hi I have this torrent file and I want uh to download this particular file so what torrent what the tracker would do is it would give you the list of peers in the network once you have the list of peers in the network you'll directly talk to the peers and request for the pieces that you need and the peer would send you those pieces and then you would concaten it and create the file locally right the performance of this entire protocol depends on the order in which pieces are requested but why let me give you a simple example let's say I have a file which is 5 MB big and I'm making a piece of length 1 MB right so I'll total have five pieces for my entire file right so now what would happen is let's say if everyone starts from P0 everyone starts from P0 that everyone request the P0 then Piece One Piece two piece three and so on and so forth so what would happen is there might come a state where we know that there would be a cedar in the network who has the entire file and there would be leeches in the network who does not who are who are right now downloading the file and let's say if everyone downloads 0 then 1 then 2 then 3 then 4 and so on and so forth so for example after three pieces where everyone in the network has three pieces your Cedar left the network no one has the fourth and the fifth piece this is where the problem is you don't want Into You don't want to be in a situation where every peer in the network has the same set of pieces and the cedar left the network so now your download cannot proceed so which is where the order in which the pieces are requested by the peers matters a lot right so that we don't have an over dependence on the cedar always right so this is why the order in which we are requesting the pieces matters and which is why we need a piece selection algorithm with us okay so the how like if you want to devise an algorithm what would be the core criteria of it so we would want a piece selection algorithm to fulfill two needs first we should be maximizing the download speed of the network second we should be minimizing the dependency on the cedar we saw the example on why we would want to minimize the dependency on the C diff because what if the cedar leaves and no one in the network has the piece to down to complete the download right and to maximize the download speed obviously your peace selection algorithm cannot make the overall download slower because that's what the aim of a P2P network is to distribute the file as quickly as possible right so that is where we talk about an algorithm called rarest first piece selection algorithm by the name it's it is uh self-explanatory that what we are doing is we are trying to go for the rarest piece first so which means that the piece is the piece which is the rarest in the network you would try to prioritize downloading that and the piece which are common we can delay the downloading of that piece this way we would be reducing the dependency on the Cedar and we would ensure that everyone in the network has almost all the pieces that are required to complete the fight so that even if Cedar leaves the network you would have enough nodes in the network that would have those pieces so that you can complete the download like every node would complete the download right so the core idea of this algorithm is prioritizing downloading of a piece that is rare so say we have three peers in the network pra prb and PRC pra wants to download a file so it would start downloading the pieces from its peer set B and C and who gave this peer set to a the tracker so when a joined the network 8 up to the tracker and said hey I need PS2 download file from so the tracker would send in B and C right so this is how Aspire set has B and C in it and it can only download files from BSC because it does not know the existence of other peers in the network so what would happen is a would send a request to B and C checking if they have pieces with them and BNC would respond and a would keep track of the pieces available with the peers so that it would Fetch and request the rarest piece that is there in the network right it's it's like a greedy approach to fetch to to ensure that the file is distributed uniformly right so let's talk about advantages of error first and then we'll go into the implementation part of it so advantages just from the core objective perspective we can see the advantages of redist first being spreading the seed so we are trying to what would happen is because we are prioritizing the rarest piece first to be downloaded by a peer what would happen is we are reducing the dependency on the Cedar and we would only go to the cedar when someone is requesting the piece that is not existing in the network so the load on the cedar is reduced whoever wants a piece that is not yet fetched by anyone in the network then only would go to the cedar right otherwise your network can internally distribute among themselves and can solve the problem right second we would get an increased download speed because the better the distribution of pieces in the network the faster will be the download speed because now it can go to multiple peers and basically download the the pieces that it wants right so you'd get a very fast download fit because there is a very nice uniform distribution of the pieces within the network third is enabling upload we know that the reciprocation is a very important part of BitTorrent through which it ensures that no one abuses or there are no Free Riders in the platform or in the network so what this would mean is if you as a peer hold a rare piece everyone in the network would want it from you because they want it from you they would be unchoking you giving you a better download speed reciprocation right and this is what makes this uh strategy very special because now if you hold a rare piece everyone wants it from you so you'll in turn get a better download speed so reciprocation this is the core idea of Choke algorithms anyway we talked about stroke algorithms in the previous video interest if you have not dived if you have not seen that video please watch it because it's a very superb algorithm that ensures there are no Free Riders and it's all such beautifully the entire problem right so with reciprocation we'll get faster download so this is a good strategy of or being rarest first is pretty solid here and fourth and final and the most important one is preventing rarer piece missing which means that we would never have we would never have a a situation where a rare piece goes missing because we are prioritizing downloading of the rare piece first right when which is really important right so reducing the dependency on the cedar while ensuring that even if someone leaves the network we would still have the pieces floating around in the network that people can complete their corresponding downloads right now we're going to the implementation part of it so now how does a PR compute rarest piece okay so this is where you would see how the overall flow happens so every peer like for example pra went first went to the tracker to seek who all are peers that it can talk to and let's say the tracker sent prb and PRC so now what would happen is every peer has a peer set that it got from the tracker right now there are two ways by which peer can tell about the pieces they have because now what you need to know is let's say I know the pieces oh sorry I know the peers but how would I know what pieces they have someone has to tell me but you cannot go to tracker otherwise it would overburden the tracker so it's the peers who would tell you the pieces they have and there are two ways to do it first is the have messages so what happens is whenever a peer downloads a particular piece or it has a particular piece it would broadcast a half message that I have this piece right so a series of have messages are sent by peers B and see for each piece that it has so now a would be getting have messages from PSB and C this way a can keep track of the pieces that B and C has on its own machine and this is one way through which a would know the pieces that B and C has right the second way to do it is called bit field message so when a connection is set up between two peers right let's say pra and prb after the initial handshake what can happen is prb can send a bit field message a bit filled message basically very simple approach what it holds it it holds for each piece it has a bit in the bit field that is set to zero and one one implies that the peer has this piece and zero implies that it doesn't so peer B when the handshake is complete P or B would have this bit filled handy it would know which pieces it holds it would send this bit filled to a once a gets the bit filled a would know the pieces that B has and then now with this one of these two approaches a knows the pieces that the peer set of its has what it can do is it can compute the rarest first because it would know across its unlock here I'm talking about a very small scale of three nodes but in reality it is 50 nodes 50 50 notes and then uh and at Max it goes to 50 but through this it would know the rarest piece because it would know which all pieces does each of the peer in the network holds and now what it can prioritize is it can prioritize downloading of the relay space because it would know that hey this piece is the least that anyone has so let me download that so everyone tries to prioritize downloading of the rarest piece first right and the redist piece is computed every time you receive a have message from a priority receiver bit field message from appear because you need to recompute it every time right so your product is downloading of the redisps and it would be recomputed every time you receive a half message from appear that something changed then do you do a very quick recompute of it right okay so you would have foreseen that only rare rest first is not enough to solve this problem because there are lots of edge cases let's talk about those edge cases first when a peer has just joined the network right it would need to have downloaded the first piece as soon as possible why because P2P network works on reciprocation if you have peace to give you'll get a piece in return right so otherwise they are choked right this is what we've seen in the choke algorithm so because of this when a peer joins a network it would not have any peace with it because if it does not have any peace what would happen is it would need to prioritize downloading of first piece as soon as possible so that it has something to share now if you go for an arrest first approach in this case what happens is you would have to wait for a very long time for it also this would slow down the overall download uh capacity or sorry it would slow down the overall download rate of a particular Peer who has just joined a network giving it a poor experience so what would you do you would want to have a separate strategy for a peer that has just recently joined so that is where random first policy comes in So Random pieces because you are not applying any explicit logic over here you are just downloading any piece that you can get at random from the network so that you have at least something to start with so that is where if you have less than four pieces exactly if you have less than four pieces of a particular file that you are trying to download then instead of going for rare s first you would go for random uh you would go for basically random piece strategy through this what you would ensure is you would ensure a very fast uh way to get at least some peace with you so that you can then you will have something to share and then you will get other pieces in return right so this is what you do when you have less than four pieces in total but as soon as you hit four pieces you would switch your strategy from random piece first to rarest first right so this is what you would use to ensure that you are like when you are just doing a cold start when you are just starting up you would not go for Radice first but instead you'd go for random first to have something to share with the network right so first Port piece uh so for the first four pieces you would do random first and then you would move switch to rarest first right okay then comes a second policy which is strict priority policy now here but I have been talking about is you have a file in the network it is broken into pieces but PC is 1 mbbit for example right but the a piece is also broken into blocks and block is the unit of transmission as in when you are transmitting in one call you will get one block in return you are not getting a piece in return you'll get a block in return once you have all the blocks of the pieces then you complete the piece and you say hey now I have this piece right because piece can be big block would definitely be small which can be exchanged in one TCP call right so file is split into pieces and pieces are split into Block in each transfer a block of a piece is transferred and now things become interesting so given that a peer cannot contribute back to the network until it has a complete piece because peace is a unit that we are operating at or a peer can say I have this piece but to download a piece it has to download multiple blocks so what if appear downloads three blocks from three different pieces it would take a long time for it to complete to one piece right so that is where what a strict what a strict piece policy or strict download policy says is that you would want to prioritize so if you have downloaded a block of a particular piece you should be prioritizing downloading of all the blocks of the piece so that you would have a completion of a piece much quicker so that you can contribute back uh to the network as soon as possible right so you so this way or this policy would ensure that that you are you are focused and you are downloading all the blocks of a piece completing a piece so that you can then broadcast a have message in the network and say hey I have this piece now right very important so this is how you would ensure that your focused on downloading the piece on priority and as soon as possible and the final policy is the end game mode right so what it says is the end game mode is when you are about to finish the download what would happen is let's say You are downloading blocks right because when you are downloading pieces slash blocks what might happen is at the later stage of your download at the final stage of your download what would happen is you might be you might be needing let's say five blocks and you have made requests to all five of them yeah so you have made requests for all five of them and now you are waiting for the response to come in now that you are waiting for the response to come in typically towards the lag end of the download Things become slower because the pieces are hard to find or because everyone else is anyway busy so you would want to complete the download as soon as possible so in order to do this what happens is when your download is about to finish which means when you have made the request for all the blogs that you need and now you are waiting for all of them to respond what you do is instead of that you would make requests to all the peers that you have instead of saying that hey I'll only talk to One peer to get my particular piece you'll broadcast this to every PR in your PR set and say hey I need this block give me all of them right so with this what happens with this what happens is you are prioritizing completion of your download and when this happens you would say array but now if I need a particular piece let's say P1 and I am sending it to all the peers that I need PSP one what if all of them sends me that it's okay all of them would send you that you would discard the reader net piece that you got right the piece that you got you would you would basically create a file out of it but then when all of them is about to send you that message what you do is as soon as you receive a block in this indie game mode when you receive a block you would send a Cancel message to everyone that hey I received this block please don't send me again to just try to minimize the network overhead that comes in but you would say but requesting for all the pieces every time basically it will be very taxing on the network that it is taxing but it is an end game mode which means it would happen only at the end of the download not in the middle of it given that what we are doing is we are trading a little heavy on the network uh consumption versus faster download you're always prioritizing faster download right and this is what is important to give a best download experience to appear in the network right so just to iterate on the end game mode endgame mode is triggered when you wanted the last n blocks and you have made requests for all of them you would be broadcasting a message that hey I want all of these blocks so that anyone who has it can prioritize sending it to you rather than you waiting for the response and once you receive a block you send a Cancel message to everyone that hey I received this block please don't send me if you receive in the middle if you received a redundant block you would discard it right this would make your overall download at the end much faster right you should not be doing it in the middle you should only be doing in the end game which means during the final stages of your download you should be doing it to complete your download as soon as possible and this is the piece selection algorithm that BitTorrent uses in order to ensure fault tolerance in the network while a very fast download speed or very fast distribution speed within the network this is such a beautiful piece of other it is such a beautiful piece of algorithm it's very intuitive and it's very simple to even write and build and code and this is how uh your overall P2P network is built with chokes algorithm to ensure you select the right peer and you don't uh and and you basically penalize the Free Riders and with arrest piece for strategy you ensure that you do not have any large dependency on Cedar and even if a node leaves even if a cedar leaves the network you would still have your network functional and the download would proceed as usual so yeah that's it for this video this was the video on peace selection algorithm that BitTorrent uses if you guys like this video give this video a thumbs up if you guys like the channel give this channel a sub this was the fifth video in the BitTorrent internal series and I'll see in the next one thanks [Music]