This is how redundancy looks

Redundancy codes* are widely used in computer systems to enhance the reliability of data storage. They are employed in many projects at Yandex. For instance, using redundancy codes instead of replication in our internal object storage saves millions without compromising reliability. However, despite their broad application, a clear explanation of how redundancy codes work is quite rare. Those wishing to understand face something like the following (from Wikipedia):

My name is Vadim, and at Yandex, I work on the development of the internal object storage MDS. In this article, I will describe the theoretical foundations of redundancy codes (Reed-Solomon codes and LRC) in simple terms. I will explain how it works without complicated mathematics and obscure terminology. At the end, I will provide examples of the use of redundancy codes at Yandex.

I won't delve deeply into a number of mathematical details, but I will provide links for those who want to explore further. I should also note that some mathematical definitions may not be strict, as the article is aimed not at mathematicians, but at engineers who wish to grasp the essence of the issue.

* In English literature, redundancy codes are often referred to as erasure codes.

1. The Essence of Redundancy Codes

The essence of all redundancy codes is extremely simple: to store (or transmit) data in such a way that it does not get lost in the event of errors (disk failures, data transmission errors, etc.).

In most* redundancy codes, data is divided into n data blocks, for which m redundancy code blocks are calculated, resulting in a total of n + m blocks. Redundancy codes are constructed in such a way that it is possible to recover n data blocks using only a portion of the n + m blocks. Next, we will focus only on block redundancy codes, meaning those in which data is divided into blocks.

To recover all n data blocks, at least n out of n + m blocks are required, as you cannot obtain n blocks with only n-1 block (in this case, one block would have to be taken "out of thin air"). Are n arbitrary blocks from n + m blocks sufficient for recovering all data? It depends on the type of redundancy codes; for instance, Reed-Solomon codes allow recovery of all data using any arbitrary n blocks, while LRC redundancy codes do not always provide that capability.

Data Storage

In data storage systems, each of the data blocks and redundancy code blocks is typically recorded on a separate disk. Thus, when any disk fails, the original data can still be recovered and read. Data can be recovered even if multiple disks fail simultaneously.

Data transfer

Redundancy codes can be used for reliable data transmission over an unreliable network. The transmitted data is divided into blocks, and redundancy codes are calculated for them. Both data blocks and redundancy code blocks are sent over the network. In the event of errors in arbitrary blocks (up to a certain number of blocks), the data can still be transmitted without errors over the network. Reed-Solomon codes, for example, are used for data transmission over optical communication lines and in satellite communications.

* There are also redundancy codes where the data is not divided into blocks, such as Hamming codes and CRC codes, which are widely used for data transmission in Ethernet networks. These are codes for error-resistant encoding, designed for error detection rather than correction (Hamming code also allows for partial error correction).

2. Reed-Solomon Codes

Reed-Solomon codes are among the most widely used redundancy codes, invented in the 1960s and first gaining widespread application in the 1980s for the mass production of compact discs.

There are two key questions for understanding Reed-Solomon codes: 1) how to create redundancy code blocks; 2) how to recover data using redundancy code blocks. Let's find the answers to these.
For simplification, we will assume that n=6 and m=4. Other schemes can be considered analogously.

How to create redundancy code blocks

Each code redundancy block is considered independently of the others. To calculate each block, all n data blocks are used. In the diagram below, X1-X6 are data blocks, P1–P4 are redundancy code blocks.

All data blocks must be of the same size; to align them, zero bits can be used. The resulting redundancy code blocks will be the same size as the data blocks. All data blocks are divided into words (for instance, 16 bits each). Suppose we divide the data blocks into k words. Then all redundancy code blocks will also be divided into k words.

To calculate the i-th word of each redundancy block, the i-th words of all data blocks will be used. They will be calculated using the following formula:

Here, the values of x are the words of the data blocks, p are the words of the redundancy code blocks, and all alpha, beta, gamma, and delta are specially chosen numbers, the same for all i. It should be noted that all these values are not ordinary numbers but elements of a Galois field; the operations +, -, *, / are not the familiar operations, but special operations introduced over the elements of a Galois field.

The Purpose of Galois Fields

It may seem simple: divide data into blocks, blocks into words, using the words of the data blocks to calculate the words of the redundancy code blocks — we obtain redundancy code blocks. In general, this is indeed how it works, but the devil is in the details:

As mentioned above, the word size is fixed, in our example 16 bits. The formulas above for Reed-Solomon codes are such that when using ordinary integers, the result of the calculation p may be impossible to represent with a word of the allowable size.
When recovering data, the formulas above will be viewed as a system of equations that need to be solved in order to recover the data. During the solving process, there may be a need to divide integers by each other, resulting in a real number that cannot be accurately represented in computer memory.

These issues prevent the use of integers for Reed-Solomon codes. The original solution can be described as follows: let’s create special numbers that can be represented using words of a required length (for example, 16 bits), and the result of all operations (addition, subtraction, multiplication, division) on them will also be represented in memory as words of the required length.

Such 'special' numbers have long been studied in mathematics and are called fields. A field is a set of elements with operations of addition, subtraction, multiplication, and division defined for them.

Galois fields* are fields for which there exists a unique result for each operation (+, -, *, /) for any two elements of the field. Galois fields can be constructed for numbers that are powers of 2: 2, 4, 8, 16, etc. (in fact, for any prime number p, but practically we are only interested in powers of 2). For example, for words of size 16 bits, this field contains 65,536 elements, for each pair of which a result can be found for any operation (+, -, *, /). The values x, p, alpha, beta, gamma, delta from the above equations will be considered elements of the Galois field for calculations.

Thus, we have a system of equations that can be used to construct redundancy code blocks by writing the corresponding computer program. This same system of equations can be used to restore data.

* This is not a strict definition, rather a description.

How to Restore Data

Restoration is necessary when, out of n + m blocks, some blocks are missing. These can be either data blocks or redundancy code blocks. The absence of data blocks and/or redundancy code blocks means that the corresponding variables x and/or p are unknown in the above equations.

The equations for Reed-Solomon codes can be viewed as a system of equations in which all values alpha, beta, gamma, delta are constants, all x and p corresponding to available blocks are known variables, and the other x and p are unknown.

For example, let’s say data blocks 1, 2, 3 and redundancy code block 2 are unavailable, then for the i-th group of words there will be the following system of equations (the unknowns are marked in red):

We have a system of 4 equations with 4 unknowns, meaning we can solve it and recover the data!

From this system of equations, several conclusions about data recovery for Reed-Solomon codes (n data blocks, m redundancy code blocks) follow:

Data can be recovered when losing any m blocks or fewer. When losing m+1 or more blocks, the data cannot be recovered: one cannot solve a system of m equations with m + 1 unknowns.
To recover even a single data block, you need to use any n of the remaining blocks, while any of the redundancy codes can be used.

What else you need to know

In the description above, I skip over several important questions that require a deeper dive into mathematics. In particular, I don't mention the following:

The equation system for Reed-Solomon codes must have a (unique) solution for any combination of unknowns (no more than m unknowns). Based on this requirement, the values of alpha, beta, gamma, and delta are chosen.
The equation system needs to be constructed automatically (depending on which blocks are unavailable) and solved.
You need to construct a Galois field: for a given word size, be able to find the result of any operation (+, -, *, /) for any two elements.

At the end of the article, there are references to literature on these important questions.

Choosing n and m

How to practically choose n and m? In practice, in data storage systems, redundancy codes are used for space saving, so m is always chosen to be less than n. Their specific values depend on several factors, including:

Data storage reliability. The larger m is, the more disk failures can be tolerated, meaning higher reliability.
Redundancy of storage. The higher the ratio of m / n, the greater the redundancy of storage, and the more expensive the system will be.
Query processing time. The greater the sum of n + m, the longer the response time for queries will be. Since reading data (during recovery) requires reading n blocks stored on n different disks, the reading time will be determined by the slowest disk.

Moreover, storing data in multiple data centers imposes additional constraints on the choice of n and m: when one data center fails, the data must still be readable. For example, when storing data in 3 data centers, the condition must hold: m >= n/2; otherwise, it may occur that the data is unavailable for reading when one data center is down.

3. LRC — Local Reconstruction Codes

To recover data using Reed-Solomon codes, it is necessary to use n arbitrary data blocks. This is a significant drawback for distributed data storage systems, as recovering data from one failed disk requires reading data from most of the remaining disks, creating a substantial additional load on the disks and the network.

The most common errors are the unavailability of a single data block due to the failure or overload of one disk. Is there any way to reduce the excessive load for data recovery in such (the most common) cases? It turns out that there is: local redundancy codes (LRC) are specifically designed for this purpose.

LRC (Local Reconstruction Codes) are redundancy codes developed by Microsoft for use in Windows Azure Storage. The idea behind LRC is quite simple: to split all data blocks into two (or more) groups and calculate part of the redundancy codes for each group separately. This way, part of the redundancy codes will be calculated using all data blocks (in LRC, they are called global redundancy codes), while another part will be calculated using one of the two groups of data blocks (these are called local redundancy codes).

LRC is denoted by three numbers: n-r-l, where n is the number of data blocks, r is the number of global redundancy code blocks, and l is the number of local redundancy code blocks. To read data when one data block is unavailable, only n/l blocks need to be read — this is l times fewer than with Reed-Solomon codes.

For example, consider the LRC schema 6-2-2. X1–X6 are 6 data blocks, P1, P2 are 2 global redundancy blocks, P3, P4 are 2 local redundancy blocks.

The redundancy code blocks P1, P2 are calculated using all data blocks. The redundancy code block P3 is calculated using data blocks X1–X3, and the redundancy code block P4 is calculated using data blocks X4–X6.

The rest is done in LRC similarly to Reed-Solomon codes. The equations for calculating the word counts of the redundancy code blocks will be as follows:

To select the alpha, beta, gamma, and delta numbers, a series of conditions must be met to ensure data recovery is possible (i.e., solving the system of equations). More details can be read in article.
Also, in practice, to calculate local redundancy codes P3, P4, the XOR operation is applied.

From the system of equations for LRC, several conclusions follow:

To recover any single data block, it is sufficient to read n/l blocks (n/2 in our example).
If r + l blocks are unavailable, and all blocks belong to one group, then the data cannot be recovered. This can be easily explained with an example. Let blocks X1–X3 and P3 be unavailable: this is r + l blocks from one group, 4 in our case. Thus, we have a system of 3 equations with 4 unknowns, which cannot be solved.
In all other cases of r + l blocks being unavailable (when at least one block from each group is available), the data can be recovered in LRC.

Thus, LRC outperforms Reed-Solomon codes in data recovery after single errors. In Reed-Solomon codes, to recover even one data block requires using n blocks, while in LRC, to recover one data block, it is enough to use n/l blocks (n/2 in our example). On the other hand, LRC falls short compared to Reed-Solomon in the maximum number of allowable errors. In the examples above, Reed-Solomon codes can recover data with any 4 errors, while for LRC, there are 2 combinations of 4 errors where data cannot be recovered.

What is more important depends on the specific situation, but often the reduced redundant load provided by LRC outweighs the slightly lower reliability of storage.

4. Other redundancy codes

In addition to Reed-Solomon and LRC codes, there are many other redundancy codes. Different redundancy codes use different mathematics. Here are some other redundancy codes:

Redundancy code using the XOR operator. The XOR operation is performed on n data blocks, resulting in 1 redundancy code block, i.e., an n+1 scheme (n data blocks, 1 redundancy code). Used in RAID 5, where data blocks and redundancy codes are cyclically written across all disks in the array.
The even-odd algorithm, based on the XOR operation, allows for the construction of 2 redundancy code blocks, i.e., the n+2 scheme.
The STAR algorithm, based on the XOR operation, allows for the construction of 3 redundancy code blocks, i.e., the n+3 scheme.
Pyramide codes are another type of redundancy codes from Microsoft.

5. Use in Yandex

A number of Yandex's infrastructure projects use redundancy codes for reliable data storage. Here are a few examples:

The internal object storage MDS, which I mentioned at the beginning of the article.
YT — Yandex's MapReduce system.
YDB (Yandex DataBase) is a distributed newSQL database.

MDS uses LRC redundancy codes, following the 8-2-2 scheme. Data with redundancy codes is written to 12 different disks across various servers in 3 different data centers: 4 servers in each data center. For more details, read about it in article.

YT utilizes both Reed-Solomon codes (the 6-3 scheme), which were implemented first, and LRC redundancy codes (the 12-2-2 scheme), with LRC being the preferred storage method.

YDB uses redundancy codes based on even-odd (the 4-2 scheme). The redundancy codes in YDB have already been discussed at Highload.

The use of different redundancy code schemes is dictated by varying requirements imposed on systems. For example, in MDS, data stored using LRC is immediately distributed across 3 data centers. It is crucial for us that the data remains readable in the event of any one data center going offline, thus the blocks must be distributed across data centers so that when one data center is unavailable, the number of inaccessible blocks does not exceed the allowable limit. In the 8-2-2 scheme, 4 blocks can be placed in each data center; therefore, if any data center goes offline, 4 blocks will be inaccessible, and data can still be read. Whichever scheme we choose for distribution across 3 data centers, it must be the case that (r + l) / n >= 0.5, meaning the storage redundancy will be at least 50%.

In YT, the situation is different: each YT cluster is entirely located in one data center (different clusters in different data centers), so there is no such limitation. The 12-2-2 scheme offers 33% redundancy, which means storage becomes cheaper while also being able to withstand up to 4 simultaneous disk outages, just like the scheme in MDS.

There are many more intricacies involved in using redundancy codes in data storage and processing systems: nuances of data recovery, the impact of recovery on query execution time, data writing features, etc. I plan to discuss these and other practical aspects of using redundancy codes separately if the topic is of interest.