Home > Erasure Coding > Erasure Coding for Big Data

Erasure Coding for Big Data

Thus this leads to an LRC with $r=2$. This construction can be generalized to any $r$ and the resultant codes turn out to be optimal.

4.2 Hierarchical Codes

One disadvantage of an LRC is that the idea of an LRC is not scalable. Consider an $[24,14]$ linear code which is made up of the union of $6$ disjoint $[4,3]$ ‘local’ codes (see Figure 22 on the left). These local codes are single parity check codes and ensure that the code has locality $3$. However, if there are $2$ or more erasures within a single local code, then recovery is not possible. Codes with hierarchical locality [32] (see Figure 22 (right)) seek to overcome this by building a hierarchy of local codes to ensure that in the event that a codeword in the lowest level fails, then the local code at the next level can take over. The local codes at higher levels have a minimum distance that permits recovery from more than one erasure.

5 Recovery from Multiple Erasures

Hierarchical codes present one method of designing a code with locality that can recover from more than one erasures. There are other approaches as well. Availability codes [33], [34] cater to the situation when a node containing a code symbol that it is desired to access is unavailable as the particular node is busy serving other requests. To handle such situations, an availability code is designed so that the same code symbol can be recovered in multiple ways, as a linear combination of a small subset of the remaining code symbols. The binary product code shown in Figure 23 is one example of an availability code. The symbols $P$ shown in the figure represent respectively either a row or column parity. Here each code symbol can be recovered in $3$ distinct ways: directly from the node storing the code symbol or else by computing the sum of the remaining entries in either the row or the column containing the desired symbol.

Figure 23
Figure 23: The binary product code as an example of an availability code. In this example, the code symbol ‘5’ can be recovered either directly from the node storing the code symbol, or else by computing either the row sum: ‘$4$’+‘$6$’+‘$P$’ or else, the column sum ‘$2$’+‘$8$’+‘$P$’.

The most general approach, and the one that imposes the least constraint in terms of how recovery is to be accomplished is sequential recovery [35], [36]. An example of a code with sequential recovery is shown in Figure 24. In the figure, the numbers correspond to the indices of the $8$ message symbols. The $4$ vertices correspond to the $4$ parity symbols. It can be seen that if message symbols $1$ and $5$ are erased, and one chooses to decode using locality, then one must first decode $5$ before decoding symbol $1$.

6 Codes with Local Regeneration

There is a class of codes known as codes with local regeneration that provide the benefits of both reduced degree and reduced repair bandwidth (see Figure 25). For details the reader is referred to [37, 38, 39].

Figure 24
Figure 24: An example code with forced sequential recovery from $2$ erasures for certain erasure patterns.
Figure 25
Figure 25: Codes with local regeneration combine desirable features of both RGC and LRC.

7 Conclusion

Erasure coding for distributed storage enables the reliable storage of very large amounts of data with far less overhead in comparison to replication, while efficiently handling node repairs. Over the past decade, this area has seen extensive research and many exciting codes have been developed as a result. The adoption of LRCs into the Microsoft Azure storage which resulted in significant cost savings, is one of the big success stories along this line of research. Although there are practical implementations of regenerating codes in the literature, regenerating codes are yet to make their way into a production cluster. The planned incorporation of the Clay code into the Nautilus release of Ceph, is an important step in this direction. There remain some open theoretical problems that are also of interest to industry. An example of this is the problem of constructing (vector) MDS codes which are repair bandwidth-efficient, yet offer a low sub-packetization level so as to mitigate the problem of fragmented read.

8 Acknowledgement

The authors would like to acknowledge support from the J. C. Bose National Fellowship, the US National Science Foundation under Grant No. 1421848 as well as from the NetApp University Research Fund, a corporate advised fund of the Silicon Valley Community Foundation.PIC


Pages ( 5 of 6 ): « Previous1 ... 34 5 6Next »

Leave a Comment:

Your email address will not be published. Required fields are marked *