Жоғалған деректерді қалпына келтіру коды

Code added to allow recovery of lost data
In coding theory, an erasure code is a forward error correction (FEC) code under the assumption of bit erasures (rather than bit errors), which transforms a message of k symbols into a longer message (code word) with n symbols such that the original message can be recovered from a subset of the n symbols. The fraction r = k/n is called the code rate. The fraction k’/k, where k’ denotes the number of symbols required for recovery, is called reception efficiency. The recovery algorithm expects that it is known which of the n symbols are lost — unlike forward error correction codes.

Optimal erasure codes have the property that any k out of the n code word symbols are sufficient to recover the original message (i. e., they have optimal reception efficiency). Optimal erasure codes are maximum distance separable codes (MDS codes).

The linear construction above can be generalized to polynomial interpolation. Additionally, points are now computed over a finite field. First we choose a finite field F with order of at least n, but usually a power of 2. The sender numbers the data symbols from 0 to k − 1 and sends them. He then constructs a (Lagrange) polynomial p(x) of order k such that p(i) is equal to data symbol i. He then sends p(k), , p(n − 1). The receiver can now also use polynomial interpolation to recover the lost packets, provided he receives k symbols successfully. If the order of F is less than 2b, where b is the number of bits in a symbol, then multiple polynomials can be used. The sender can construct symbols k to n − 1 'on the fly', i. e., distribute the workload evenly between transmission of the symbols. If the receiver wants to do his calculations 'on the fly', he can construct a new polynomial q, such that q(i) = p(i) if symbol i < k was received successfully and q(i) = 0 when symbol i < k was not received. Now let r(i) = p(i) − q(i). Firstly we know that r(i) = 0 if symbol i < k has been received successfully. Secondly, if symbol i ≥ k has been received successfully, then r(i) = p(i) − q(i) can be calculated. So we have enough data points to construct r and evaluate it to find the lost packets. So both the sender and the receiver require O(n (n − k)) operations and only O(n − k) space for operating 'on the fly'.

This process is implemented by Reed–Solomon codes, with code words constructed over a finite field using a Vandermonde matrix. Most practical erasure codes are systematic codes each one of the original k symbols can be found copied, unencoded, as one of the n message symbols. In particular, various implementations of Reed Solomon erasure coding are used by Apache Hadoop, the RAID 6 built into Linux, Microsoft Azure, Facebook cold storage, and Backblaze Vaults. The classical way to recover from failures in storage systems was to use replication. However, replication incurs significant overhead in terms of wasted bytes. Therefore, increasingly large storage systems, such as those used in data centers use erasure coded storage. The most common form of erasure coding used in storage systems is Reed Solomon (RS) code, an advanced mathematics formula used to enable regeneration of missing data from pieces of known data, called parity blocks. In a (k, m) RS code, a given set of k data blocks, called "chunks", are encoded into (k + m) chunks. The total set of chunks comprises a stripe. The coding is done such that as long as at least k out of (k + m) chunks are available, one can recover the entire data. This means a (k, m) RS encoded storage can tolerate up to m failures. Example: In RS (10, 4) code, which is used in Facebook for their HDFS, 10 MB of user data is divided into ten 1MB blocks. Then, four additional 1 MB parity blocks are created to provide redundancy. This can tolerate up to 4 concurrent failures. The storage overhead here is 14/10 = 1.4X. In the case of a fully replicated system, the 10 MB of user data will have to be replicated 4 times to tolerate up to 4 concurrent failures. The storage overhead in that case will be 50/10 = 5 times. This gives an idea of the lower storage overhead of erasure coded storage compared to full replication and thus the attraction in today's storage systems. Initially, erasure codes were used to reduce the cost of storing "cold" (rarely accessed) data efficiently; but erasure codes can also be used to improve performance serving "hot" (more frequently accessed) data.