Following article explains a simplified version of Erasure Coding:
here is the recipe:
- Take a file of size M.
- Split the file into k chunks, each of the same size M/k.
- Now, apply the (n, k) code on these k chunks to get n chunks, each of the same size M/k.
- Now the effective size is nM/k. Thus the file is expanded n/k times. We need n to be greater than or equal to k, so n/k is at least 1. If n equals k, you have just split the file and there is no coding performed.
- Any k chunks out of the n chunks can be used to get back the file.
So this also means that the code can tolerate upto (n - k) erasures. The following figure shows this recipe being followed for a (4, 2) code.
Without really wondering how do actually add files, the following example illustrates one particular case of designing a (4, 2) code.
Lets say you have four computers (aka nodes) that you can use to store files. Instead of putting all the eggs in the same basket, you will want to spread it out and in this case, store the file twice by doing something like this:
where X1 is the first block of file A and X2 the second. Another way is to store the coded blocks:
Now if you lose nodes 1 and 3, in the case when you store uncoded blocks, X1 is lost permanently, so the file A gets corrupted. Whereas in the case when you store coded blocks, even when those two nodes fail, it is possible to recover X1 and X2 and thus A from A2 and A4. This is because
A2 = X2and
A4 = X1 + 2*X2. So one can solve these equations and get back X1 and X2! Neat, isn’t it?
And my question is related to the last sentence:
How to solve these equations and get back X1 and X2 ?
We have two equations:
(1) A2 = X2 (2) A4 = X1 + 2*X2
AFAIK: We are able to solve an equation, if the number of equations is equal or more than the number of unknown variables.
Based on this:
- Which ones are know and which ones are unknown in two above equations? A2 and A4 are unknown? Or X1 and X2 are unknown ?
- If X1 and X2 are known, then we are able to find A4 and A2 even by a single equation.so, we do not need two!
- If X1 and X2 are unknown, then they will be found based on A2 and A4. In this case, how is it feasible to recover the original file by two coded values A2 and A4 ?
How to solve this system of linear equations ?
It is NOT clear to me which one is known and which one is unknown:
A2 and A4 are unknown?
X1 and X2 are unknown?