Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userXORing Elephants: Novel Erasure Codes for Big Data
141
0
0.0
(
0
)
Added by
Maheswaran Sathiamoorthy
Publication date
2013
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Distributed storage systems for large clusters typically use replication to provide reliability. Recently, erasure codes have been used to reduce the large storage overhead of three-replicated systems. Reed-Solomon codes are the standard design choice and their high repair cost is often considered an unavoidable price to pay for high storage efficiency and high reliability. This paper shows how to overcome this limitation. We present a novel family of erasure codes that are efficiently repairable and offer higher reliability compared to Reed-Solomon codes. We show analytically that our codes are optimal on a recently identified tradeoff between locality and minimum distance. We implement our new codes in Hadoop HDFS and compare to a currently deployed HDFS module that uses Reed-Solomon codes. Our modified HDFS implementation shows a reduction of approximately 2x on the repair disk I/O and repair network traffic. The disadvantage of the new coding scheme is that it requires 14% more storage compared to Reed-Solomon codes, an overhead shown to be information theoretically optimal to obtain locality. Because the new codes repair failures faster, this provides higher reliability, which is orders of magnitude higher compared to replication.
rate research
Read More
In this paper, we study the problem of storing an archive of versioned data in a reliable and efficient manner in distributed storage systems. We propose a new storage technique called differential erasure coding (DEC) where the differences (deltas) between subseque
Product codes (PCs) and staircase codes (SCCs) are conventionally decoded based on bounded distance decoding (BDD) of the component codes and iterating between row and column decoders. The performance of iterative BDD (iBDD) can be improved using soft-aided (hybrid) algorithms. Among these, iBDD with combined reliability (iBDD-CR) has been recently proposed for PCs, yielding sizeable performance gains at the expense of a minor increase in complexity compared to iBDD. In this paper, we first extend iBDD-CR to SCCs. We then propose two novel decoding algorithms for PCs and SCCs which improve upon iBDD-CR. The new algorithms use an extra decoding attempt based on error and erasure decoding of the component codes. The proposed algorithms require only the exchange of hard messages between component decoders, making them an attractive solution for ultra high-throughput fiber-optic systems. Simulation results show that our algorithms based on two decoding attempts achieve gains of up to $0.88$ dB for both PCs and SCCs. This corresponds to a $33%$ optical reach enhancement over iBDD with bit-interleaved coded modulation using $256$ quadrature amplitude modulation.
Streaming codes are a class of packet-level erasure codes that are designed with the goal of ensuring recovery in low-latency fashion, of erased packets over a communication network. It is well-known in the streaming code literature, that diagonally embedding codewords of a $[tau+1,tau+1-a]$ Maximum Distance Separable (MDS) code within the packet stream, leads to rate-optimal streaming codes capable of recovering from $a$ arbitrary packet erasures, under a strict decoding delay constraint $tau$. Thus MDS codes are geared towards the efficient handling of the worst-case scenario corresponding to the occurrence of $a$ erasures. In the present paper, we have an increased focus on the efficient handling of the most-frequent erasure patterns. We study streaming codes which in addition to recovering from $a>1$ arbitrary packet erasures under a decoding delay $tau$, have the ability to handle the more common occurrence of a single-packet erasure, while incurring smaller delay $r<tau$. We term these codes as $(a,tau,r)$ locally recoverable streaming codes (LRSCs), since our single-erasure recovery requirement is similar to the requirement of locality in a coded distributed storage system. We characterize the maximum possible rate of an LRSC by presenting rate-optimal constructions for all possible parameters ${a,tau,r}$. Although the rate-optimal LRSC construction provided in this paper requires large field size, the construction is explicit. It is also shown that our $(a,tau=a(r+1)-1,r)$ LRSC construction provides the additional guarantee of recovery from the erasure of $h, 1 leq h leq a$, packets, with delay $h(r+1)-1$. The construction thus offers graceful degradation in decoding delay with increasing number of erasures.
Based on the erasure channel FEC model as defined in multimedia wireless broadcast standards, we illustrate how doping mechanisms included in the design of erasure coding and decoding may improve the scalability of the packet throughput, decrease overall latency and potentially differentiate among classes of multimedia subscribers regardless of their signal quality. We describe decoding mechanisms that allow for linear complexity and give complexity bounds when feedback is available. We show that elaborate coding schemes which include pre-coding stages are inferior to simple Ideal Soliton based rateless codes, combined with the proposed two-phase decoder. The simplicity of this scheme and the availability of tight bounds on latency given pre-allocated radio resources makes it a practical and efficient design solution.
This paper studies low-latency streaming codes for the multi-hop network. The source is transmitting a sequence of messages (streaming messages) to a destination through a chain of relays where each hop is subject to packet erasures. Every source message has to be recovered perfectly at the destination within a delay constraint of $T$ time slots. In any sliding window of $T+1$ time slots, we assume no more than $N_j$ erasures introduced by the $j$th hop channel. The capacity in case of a single relay (a three-node network) was derived by Fong [1], et al. While the converse derived for the three-node case can be extended to any number of nodes using a similar technique (analyzing the case where erasures on other links are consecutive), we demonstrate next that the achievable scheme, which suggested a clever symbol-wise decode and forward strategy, can not be straightforwardly extended without a loss in performance. The coding scheme for the three-node network, which was shown to achieve the upper bound, was ``state-independent (i.e., it does not depend on specific erasure pattern). While this is a very desirable property, in this paper, we suggest a ``state-dependent (i.e., a scheme which depends on specific erasure pattern) and show that it achieves the upper bound up to the size of an additional header. Since, as we show, the size of the header does not depend on the field size, the gap between the achievable rate and the upper bound decreases as the field size increases.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
