Shulou(Shulou.com)05/31 Report--

In this article Xiaobian introduces in detail "what is the Q-check algorithm of raid6 disk array", the content is detailed, the steps are clear, and the details are handled properly. I hope that this article "what is the Q-check algorithm of raid6 disk array" can help you solve your doubts.

[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 0, 1, 01, 10, 5, 6, and so on. The specific implementation of the principle of data storage, please refer to the relevant articles. This chapter provides an overview of RAID 6-level storage principles in Linux environments. 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 0 and the different 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]

It is 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 + CQ = 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.

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).

After reading this, the article "what is the Q-check algorithm of raid6 disk array" has been introduced. If you want to master the knowledge of this article, you still need to practice and use it to understand it. If you want to know more about related articles, 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.