Shulou(Shulou.com)06/01 Report--

This article shows you how to analyze the Q-check algorithm of RAID 6 in Linux environment, the content is concise and easy to understand, it can definitely brighten your eyes. I hope you can get something through the detailed introduction of this article.

[preface]

RAID is a redundant array of cheap disks (Redundant Array of Inexpensive Disks). RAID technology forms a logical hard disk by combining individual disks in different ways, thus improving the performance of disk reading and the security of data. Different combinations are identified by RAID levels, and the common RAID levels are, 1, 01, 10, 5, 6, and so on. The specific implementation of the principle of data storage, please refer to the relevant articles. This article mainly summarizes the storage principle of RAID 6 level in Linux environment. The command to configure RAID in the Linux environment is "mdadm".

[Overview of RAID 6]

RAID 6 is a stand-alone hard disk structure with two kinds of parity codes (P and Q) with distributed storage. Compared with RAID 5, RAID 6 adds a second independent parity code (Q) information block. Two independent parity systems use different algorithms, and the reliability of data is very high. Even if two hard drives fail at the same time, it will not affect the use of data. It is mainly used in situations where absolute data security is required. As shown below:

Q in the figure above is the second check information block of RAID 6, using a very complex "Jia Luo Huayu" algorithm, which will be discussed later.

[Overview of P check of RAID 6]

In fact, the P check of RAID 6 is the same as that of RAID 5, and both use XOR operation. The principle of the XOR operator is that the same is the same and the difference is 1. Only one hard disk can be lost in RAID 5, but RAID 6 adds a Q check to RAID 5, so RAID 6 supports dropping two disks at the same time. The XOR operation is as follows:

P = A + B + C = A xor B xor C

A = P-B-C = P xor B xor C

Note: the above addition and subtraction are XOR operations.

[Overview of Q-check for RAID 6]

When it comes to Q-check, it is a bit complicated, which adopts the "Jia Luo Huayu" algorithm mentioned above. "Jia Luo Huayu" is actually a finite field GF (2 ^ 8) of "0255". In GF (2 ^ 8), no matter it is addition, subtraction, multiplication or division, it will not exceed this range. Moreover, addition and subtraction are reversible, multiplication and division are reversible, and the calculated value is unique in GF (2 ^ 8). Note: the addition, subtraction, multiplication and division mentioned here are not daily addition, subtraction, multiplication and division, but operations in "Jia Luo Hua domain". In GF (2 ^ 8), if the n-th power of 2 is greater than a certain value (primitive polynomial), the value (primitive polynomial) will be taken off, and the result will be returned to GF (2 ^ 8). Therefore, the result values from 2 ^ 0 to 2 ^ 255 are guaranteed to be unique within GF (2 ^ 8).

There are 16 primitive polynomials in GF (2 ^ 8), which are as follows:

1 x8+x7+x6+x5+x4+x2+1 1 1111 0101 = 0x1F5

2 x8+x7+x6+x5+x2+x+1 1 1110 0111 = 0x1E7

3 x8+x7+x6+x3+x2+x+1 1 1100 1111 = 0x1CF

4 x8+x7+x6+x+1 1 1100 0011 = 0x1C3

5 x8+x7+x5+x3+1 1 1010 1001 = 0x1A9

6 x8+x7+x3+x2+1 1 1000 1101 = 0x18D

7 x8+x7+x2+x+1 1 1000 0111 = 0x187

8 x8+x6+x5+x4+1 1 0111 0001 = 0x171

9 x8+x6+x5+x3+1 1 0110 1001 = 0x169

10 x8+x6+x5+x2+1 1 0110 0101 = 0x165

11 x8+x6+x5+x+1 1 0110 0011 = 0x163

12 x8+x6+x4+x3+x2+x+1 1 0101 1111 = 0x15F

13 x8+x6+x3+x2+1 1 0100 1101 = 0x14D

14 x8+x5+x3+x2+1 1 0010 1101 = 0x12D

15 x8+x5+x3+x+1 1 0010 1011 = 0x12B

16 x8+x4+x3+x2+1 1 0001 1101 = 0x11D

The primitive polynomial commonly used in RAID 6 is 0X11D, which is the last one in the above column. The same is true of RAID 6 in a Linux environment.

OK, back to Q-check, Q-check and P-check combine to form a binary first-order equation. K1, K2, K3 are the values of polynomials in GF (2 ^ 8).

P = A + B + C

Q = A*K1 + B*K2 + C*K3

[Jia Luo Huayu's multiplication and division]

Jia Luo's addition and subtraction in Hua domain is also an XOR operation, so I won't explain it in detail, but focus on multiplication and division. Through the above Q-check, we know that the generation of Q-check requires the multiplication operation in Jia Luo Hua domain. Calculating the multiplication operation is a very complicated thing. The best solution is to generate a table of all the values of the polynomials in GF (2 ^ 8), and to find out the multiplication value by looking up the table.

1. Generate positive table GFILOG

The positive table GFILOG is generated by the method of the following table. Note that the primitive polynomial of this table is 0X11D.

As follows: it is positive table GFILOG

2. Generate anti-table GFLOG

With the forward transformation table, it is very simple to get the reverse table. Take the transformation value of the table in the forward direction as the index and OK the index in the forward table as the value. The table is as follows:

3. Calculation of multiplication and division (look-up table method)

Multiplication: a * K1 = GFILOG [(GFLOG [A] + GFLOG [K1]) mod 255]

Division: a / K1 = GFILOG [(GFLOG [A]-GFLOG [K1] + 255) mod 255]

Now that we know Jia Luo's multiplication and division, it is much more convenient for us to calculate the Q-check.

[generate missing data based on Q check]

When two disks are broken in RAID 6, how do you generate the lost data? Use a stripe of RAID 6 as an example.

1. If the two pieces of data lost in a stripe are P and Q, then it happens that the data is not lost and can be extracted normally.

2. If the two pieces of data lost in a stripe are P and A, then the data of A can be calculated according to the Q check.

P = A*K1 + B*K2 + C*K3

A*K1 = P + B*K2 + C*K3

A = (P + B*K2 + C*K3) / K1 / / Note: K1 can be obtained by looking up the table.

3. If the two pieces of data lost in a stripe are Q and A, then the data of A can be calculated according to the check P.

P = A + B + C

A = P + B + C

4. If the two pieces of data lost in a stripe are An and B, then the data of An and B can be calculated according to check P and Q.

P = A + B + C

Q = A*K1 + B*K2 + C*K3

A = P + B + C

Q = (P + B + C) * K1 + B*K2 + C*K3

Q = P*K1 + B*K1 + C*K1 + B*K2 + C*K3

Q = P*K1 + C*K1 + C*K3 + B*K1 + B*K2

Q + P*K1 + C*K1 + C*K3 = (K1+K2) * B

B = (Q + P*K1 + C*K1 + C*K3) / (K1+K2)

After calculating the value of B, it is much easier to calculate the value of An according to the P checksum.

A = P + B + C

[RAID 6 in Linux]

According to the previous content, we already know the general principle of RAID 6. Because there are 16 primitive polynomials in Jia Luo Huayu, there are many kinds of RAID 6, plus the value of K is not fixed. Therefore, calculating the Q-check value of a RAID 6 becomes very complicated. However, the K value of RAID 6 in Linux environment has been tested. According to the number of disks enough to form a RAID 6 array, the value of K is taken as the value of K from the beginning of the original polynomial 0X11D (total disk number of RAID 6-2).

The above content is how to analyze the Q-check algorithm of RAID 6 in Linux environment. Have you learned the knowledge or skills? If you want to learn more skills or enrich your knowledge reserve, you are welcome to follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.