Erasure Coding Tutorial: The Key to Efficient File Storage

I would like to welcome you to this short tutorial on eraser coding and we're going to be talking about three things what Erasure coding is how it is useful for a file storage system such as swarm and finally how it actually does its magic under the hood so let's get going in a file storage system such as swarm it is a very common problem that we cannot retrieve all the data for example let's say we have a file and it consists of three chunks that are stored in different places physically but one of the nodes that stores our data is down for whatever reason and we cannot retrieve all three chunks only two of them in that case the data are corrupted we cannot do anything with it how can we solve this problem the most obvious solution is simply to duplicate to have duplicate versions of the chunks so that if one Noe is done we can still retrieve it from another one and that is a good option but there are two problems with it first of all it's quite wasteful because one has to duplicate all the data and second of all it's still not as secure as it could be because if for example two chunks are missing at the same time and both of them happen to be chunk number three then the data are still irrecoverable because chunk three is simply missing so because of these problems we have to look for a better solution than simple straightforward duplication enter eraser codes the idea behind eraser codes is as follows we have some original file an original message as it's called and it consists of three chunks we're going to add to that some number of extra chunks for example let us add two extra chunks to these original Three chunks four and five those are so-called parity chunks those are extra chunks and now we take the original data we encode them with some clever algorithm and we do so in such a way that any three out of these five chunks are sufficient to recover the original data so this is much more efficient and much more secure than straightforward duplication in this case for example we only need to add in two extra chunks and we can lose any two out of these five and still be able to recover the data how does this actually work in practice let me show you through a very simple example that it's not so hard to achieve as it might look at first glance so as a very simple example let us take this simple message that consists of the characters 1 2 three and four that is going to be our message that we're going to be encoding let us say that we want to store it in three different pieces in such a way that any two of them should be able to recover the original message so in other words we're going to have three chunks one of them is considered a parity chunk and in such a way that any two out of these three will be able to recover the data and one way to do this would be as follows we could chop up the numbers in such a way that the first chunk would just contain the first half of the original data one and two and we have our encoding rule there in the middle which is just that we keep the values Unchained then we have the encoding rule for the second chunk which is again the same keep the values unchanged we just store the numbers three and four as they are but what do we do with the third chunk that's where the trick is and one possibility out of infinitely many others is simply to add the corresponding values that is if we have the number four down here that means that that is interpreted as the sum of the first numbers in the first two chunks and similarly the number six down here is interpreted as the sum is obtained rather as the sum of the corresponding values in the corresponding positions in the other two chunks and if you think about it this is now sufficient to be able to recover the original message from any two of the chunks for example if we have chunks one and three only then we know that the first number is one we know the second number is two but what is the third number well we know that we obtained the number four by adding one and some value so we simply subtract off one from four to backtrack what that number was and we get the answer three and analogously that is the same way we would obtain the number for here and that really is all there is to this kind of encoding we just have to formulate these rules in such a way that we can easily backtrack after formulating them and for example this particular encoding satisfies this Criterion and you can see how in three chunks we manage to encode the information in such a way that any two out of the three is sufficient for decoding the original message so that's it for today thank you very much for your attention and I will see you next time