JP2000259359A - Raid device and recording medium - Google Patents

Abstract

PROBLEM TO BE SOLVED: To make a data disk calculate a redundant parity and restore data when a disk fault occurs in a data disk. SOLUTION: A RAID device is provided with redundant means which distributedly preserves data in plural data disks 2a-2c and adds redundant parity disks 3a and 3b to the data, a block division means which block-divides data and parity preservation areas into the arbitrary integer number of blocks in a bit unit, and a RAID controller 4 having a parity calculation means calculating the parity of the parity disk added to the data disk at every group unit of the whole disks by using the extended Galois field GE (2n) of '2' and a data restoration means setting data of the disk where a fault occurs as unknown data when the fault occurs in the arbitrary data disk, generating a simultaneous congruence expression in accordance with a rule decided by the extended Galois field GF (2n) and restoring unknown data from the simultaneous congruence expression.

Description

DETAILED DESCRIPTION OF THE INVENTION

[0001]

The present invention relates to a RAID (Redundant) for restoring data lost due to a disk failure.
Arrays of Inexpensive Disks) device and recording medium.

[0002]

2. Description of the Related Art A RAID device is a device that obtains the same performance as a high-performance disk by dispersing and storing various data on a plurality of inexpensive disks.

However, if a large number of small disks are used, the number of disk failures increases and the risk of data loss increases accordingly. Therefore, it is not only necessary to increase the number of disks, but also to prepare extra disks. By providing redundancy, stability and high performance are achieved.

A RAID device is provided with a parity disk for providing redundancy in addition to a data disk. When a failure occurs in a data disk, the RAID device uses the parity data having redundancy to cause a failure. Restoring lost data has been done.

By the way, this type of RAID device is roughly classified into six levels RAID1 to RAID6 from the viewpoint of disk combination or load distribution, and attempts to restore data in the event of a disk failure.

RAID 1 is a mirroring (mirrorin)
g), which is a dual data storage method in which a data disk is divided into two groups and the same data is stored in two group data disks. Data writing is performed simultaneously for both groups, and data reading is performed from any data disk. As a result, when one group data disk fails, the lost data can be easily restored simply by switching to another group.

[0007] In RAID 2, data is distributed and recorded on a plurality of disks in units of bits, while an error correction code (ECC) used in a memory of a computer is added, and data lost due to a failure of a data disk is removed. This is a method for improving reliability by restoring using an error correction code.

RAID 3 is based on the premise that there is a mechanism for detecting a failure for each disk, disperses data to a plurality of disks in bit units without using ECC, adds one parity disk, and Is a method of restoring one failed data disk by exclusive OR in bit units for data lost due to the failure.

RAID 4 is based on the premise that there is a mechanism for detecting a failure for each disk. RAID 3 distributes data in units of bits, whereas RAID 4 distributes data in units of blocks and distributes data to a plurality of data disks. In this method, one disk for failure data is added, and for data lost due to a failure, one disk for failure data is restored by exclusive OR in block units.

RAID5 is based on the premise that there is also a mechanism for detecting a failure for each disk, and parity is distributed and held in all disks in block units, and data lost due to the failure is subjected to exclusive OR operation in block units. Restores one failed data disk.

[0011] RAID6 uses a single parity for failure countermeasures, whereas RAID5 uses a two-dimensional parity and enhances the error correction function using a Reed-Solomon code, so that a plurality of data sets can be used. This is a method for restoring disk failures for use and improving reliability.

[0012]

Accordingly, the above-described RAID apparatuses are classified into RAID1 to RAID6 and data restoration is performed in the event of a data disk failure. Problems have been pointed out.

First, it is necessary to prepare a disk twice as large as the required storage capacity for RAID1.
RAID2, which uses ECC including D1, and RAID6, which expands and sets parity two-dimensionally, have a fixed ratio of the number of data disks and parity disks for each system, and allow free data disks and parity disks. Not only the number of disks cannot be set, but also the parity disk occupies a larger percentage of the data disk, and many parities are changed even when there is a small amount of data change. There are issues that must be addressed.

In RAID3 to RAID5, a data disk may be added in order to increase the data capacity. However, despite the addition of the data disk, a method of calculating parity by exclusive OR is used. Only one parity, which is the capacity of one data disk, can be set.

As a result, when the number of data disks increases, the probability that two or more data disks fail at the same time increases, and when two or more disks fail simultaneously, data can be restored. Gone, RA
There is a problem that the reliability of the ID device is impaired.

Further, as a means for restoring data in the event of data loss by adding a data disk, it is conceivable to group the data into a plurality of units and attach one parity to each group to improve reliability. .

However, even in such a case, when two or more data disks fail at the same time, if one failed disk in the group can be restored, the data can be restored. There is a problem that the lost data cannot be restored when a failure occurs in the storage disk.

The present invention has been made in view of the above circumstances, and can easily calculate a redundant parity for a data disk. Even when a plurality of disks fail simultaneously,
An object of the present invention is to provide a RAID device capable of restoring the contents of the disk.

Another object of the present invention is to provide a RAID capable of easily changing the number of redundant parities in accordance with a use or the like.
It is to provide a device.

Still another object of the present invention is to specify a data erroneous disk and to restore the data from the RA.
An ID device is provided.

Another object of the present invention is to provide a recording medium on which a program capable of calculating parity redundant to a data disk and restoring the contents of the disks even when a failure occurs in a plurality of disks at the same time is provided. Is to do.

[0022]

SUMMARY OF THE INVENTION In order to solve the above-mentioned problems, the present invention provides a redundant means for making a plurality of parity disks redundant with a plurality of data disks, a data storage area and a parity of the data disks. Dividing means for dividing the parity storage area of the disk for use into arbitrary integers in bit units, and an enlarged Galois field GF (2 ⁿ )
(N is an integer) using a parity calculating means for calculating parity of a parity disk to be added to the data disk for each group unit connected by predetermined blocks of all the disks, and at the time of failure of the arbitrary data disk, A RAID control device having data restoration means for creating a simultaneous congruence equation according to the rule defined by the extended Galois field GF (2 ⁿ ) and for restoring the unknown data from the simultaneous congruence expression, Is a RAID device provided with.

In the above configuration, the parity is fixed to a specific disk. However, the configuration may be such that the parity is distributed to an arbitrary disk for each group.

According to the present invention, by taking the above-described means, after data is stored in a plurality of data disks, the parity calculation means uses the expanded Galois field GF (GF) based on the stored data. 2 ⁿ ) (where n is an integer), the parity can be accurately calculated and set on the parity disk.

In the data restoration means, in the event of a data disk failure, normal disk data, parity and data of the failed disk are combined as unknown data in accordance with a rule defined by 2 extended Galois field GF (2 ⁿ ). And recovers unknown data from this simultaneous congruential formula. Therefore, even if a failure occurs in a plurality of data disks, the data on the failed disk can be quickly and reliably restored.

Further, another invention provides a method in which a higher-level device or its own hardware switch transmits a command to a RAID controller.
By determining and inputting an arbitrary number of redundant parity calculations, the number of redundant parities can be easily changed according to the application and purpose, and the reliability can be improved and the flexibility can be flexibly adjusted according to the demands of the user. I can deal with it.

Further, in another invention, a plurality of RAID controllers which respectively manage a plurality of disks are linked, predetermined blocks of all the disks managed by the RAID controllers are grouped, and parity is set for each group. By doing so, the number of parity disks can be reduced, which greatly contributes to the reduction of redundant parity and the cost of the entire RAID device.

Still another invention is that, when calculating a plurality of parities, for the second and subsequent parities, the already calculated parities are regarded as a part of the data and the parities are calculated. The failed disk can be easily identified from the data error and the data can be repaired.

[0029]

Embodiments of the present invention will be described below with reference to the drawings.

FIG. 1 is a block diagram for explaining an embodiment of a RAID apparatus according to the present invention.

Referring to FIG. 1, reference numeral 1 denotes a RAID device provided with, for example, three data disks 2a, 2b, 2c and two parity disks 3a, 3b. Is connected to

The computer 6 downloads, for example, a program required for data processing in the RAID device 1 to the RAID device 1,
It has a function of giving necessary instructions and commands to the AID device 1.

The RAID device 1 includes the data disks 2a, 2b, 2c and the parity disk 3 described above.
In addition to a and 3b, a RAID controller 4 is provided.

Each of the disks 2a to 2c, 3a, 3b
Is divided into blocks in units of 4 bits, and is composed of 6 blocks per disk.

Of the blocks of the disks 2a to 2c, 3a, and 3b, five blocks d11, d12, d13, p14, and p15 of the first (upper) block are the first group, and the second block from the upper one are the first group. The five blocks d21, d22, d23, p24, and p25 are the second group,...

Each of the disks 2a to 2c, 3a, 3b
Is divided into 4-bit units to form one block, so that 16 types of data from 0 to 15 are stored in each block.

The RAID device 4 executes the following means according to a program read directly from the outside or downloaded from the computer 6.

That is, the RAID device 4 uses the two extended Galois fields GF (2 ⁿ ) to
a parity calculating means for calculating parity to be stored in units of blocks of the parity disks 3a and 3b added to a to 2c, and when an arbitrary disk failure occurs, the data of the failed disk is regarded as unknown data (unknown number). By constructing a simultaneous congruence equation according to the rules of the extended Galois field GF (2 ⁿ ), and solving this assembled congruence congruence equation,
It has data restoration means for restoring data of the failed disk.

First, an example of parity calculation by the RAID device 4 will be described.

Since each disk is divided into blocks in units of 4 bits, 16 types of data from 0 to 15 can be stored in each block.

Therefore, the parity is calculated by an extended Galois field GF (extension Galois fi
eld) Calculate using (2 ⁴ ). The extended Galois field can perform addition (subtraction), multiplication, and division within defined types of data. The addition (subtraction) is calculated using exclusive OR, and the multiplication is calculated using the multiplication result diagram of the enlarged Galois field GF (2 ⁴ ) shown in FIG. Note that the division is quoted by reversing the multiplication result diagram of FIG.

FIG. 2 shows the result of multiplication in FIG.
(2) A table in which GF (2 ⁴ ) is calculated using X ⁴ + X + 1, which is the above fourth-order rule polynomial.

Next, a description will be given of a simple enlarged Galois field and a creation example of a diagram showing the multiplication result of FIG.

The Galois field GF (2) is based on two types, 0 and 1, between which addition, subtraction, multiplication, and division can be performed. On the other hand, in GF (2 ^m ), there are 2 ^m elements, and the addition, subtraction, multiplication, and division can be performed freely between them. 2 ^m represents 2 to the power of m.

By the way, the fourth-order multiplication in the extended Galois field is defined.

Under the two kinds of elements 0 and 1 which are the fields of GF (2), considering the root of the fourth order rule polynomial X ⁴ + X + 1 = 0 on GF (2) which is the multiplication result of FIG. No root exists when any element of 0 or 1 is substituted. Therefore, one of the roots of such a rule polynomial is defined as α and the field is expanded.

As a result, since α satisfies α ⁴ + α + 1 = 0, the relational expression of α ⁴ = α + 1 is obtained, and all the relational expressions of the fourth or higher order represented by α can be replaced with the fourth or lower order. .

Therefore, when 16 types of data are considered by the n-th order of α, it can be expressed by the following relational expression.
It does not appear except for the five relational expressions.

[0049] ^{1 α 2 α 2 3 α 3} 4 α 4 = α + 1 5 α 5 = α 2 + α 6 α 6 = α 3 + α 2 7 α 7 = α 4 + α 3 = α 3 + α + 1 8 α 8 = α 4 + α ^{2 + α = α 2 +1 9} α 9 = α 3 + α 10 α 10 = α 4 + α 2 = α 2 + α + 1 11 α 11 = α 3 + α 2 + α 12 α 12 = α 4 + α 3 + α 2 = α 3 + α 2 + α + 1 13 α ¹³ = α ⁴ + α ³ + α ² + α = α ³ + α ² +1 14 α ¹⁴ = α ⁴ + α ³ + α = α ³ +1 15 α ¹⁵ = α ⁴ + α + 1 16 α ¹⁶ = α From the above relational expression, naturally α Multiplying the nth order by
It will fit in any of the 15 types of relational expressions. For example, fits into ^{α 7 + α 14 = α 21} = α 6 = α 3 + α 2 , and the 15 kinds of the formula α6 in. From this relational expression, one cycle is performed for data types “1” to “15”, so α
¹⁶ = α, and returns to “1”.

The multiplication result diagram shown in FIG. 2 can be created by associating the above 15 relational expressions with 1 to 15. In FIG. 2, the exponent of α is converted into a numerical value corresponding to a binary digit.

Incidentally, the n-th multiplication of α in the above example can be handled as the following calculation.

11 × 9 = 12 However, in the text, it is represented by a symbol such as 11 * 9≡12 in order to distinguish it from ordinary calculation. FIG. 2 is a diagram showing the multiplication result of 0 to 15 including 0 in addition to 1 to 15.

Accordingly, FIG. 2 shows the result of multiplication by GF (2 ⁴ ) using the fourth order polynomial X ⁴ + X + 1 on GF (2). Unless otherwise, it is assumed that all calculations are performed using GF (2 ⁴ ).

Therefore, each of the disks d11, d12, d1
For the data to be recorded in the first group of No. 3, the first parity p14 is calculated by multiplying each data by a coefficient of 1 and then adding. The calculation of the parity with a coefficient of 1 is the same as the parity calculation in the conventional RAID. In particular, Becomes In the above equation, the symbol ⊥ means that calculation is performed by exclusive OR, the symbol * means multiplication using the multiplication result in FIG. 2, and the symbol ≡ means congruence.

Next, each of the disks d11, d12, d13
For the data to be recorded in the first group, the second parity p15 is calculated by multiplying each data by an arbitrary different coefficient and adding a value obtained by the multiplication.

2 * d11⊥3 * d12⊥4 * d13≡p15 Now, as a specific example, for example, each data d11, d12, d
Assuming that the value 13 is as follows, the parity is calculated and set in the parity block.

[0057] Hereinafter, the parity is similarly calculated for the second and subsequent groups in the same manner, and set to the parity block.

Next, an example of data restoration processing by the RAID controller will be described.

Now, if all the data disks 2a to 2c have not failed, or if the parity disks 3a,
If 3b is out of order, the recorded data can be known by simply reading the data from the data disk. Further, when only one data disk fails, the data of the failed disk can be easily identified by the same exclusive OR as in the conventional RAID system.

A description will now be given of an example of data restoration when two data disks fail at the same time.

Now, the second and third disks of the five disks fail at the same time, and the data d1 of the first group
2, d13 is lost. In this state, d11, p14, and p15 including the parity of the first group are:
Since the disks 2a, 3a, 3b have not failed, data can be read.

Therefore, the lost data d12 and d13 are placed as unknown data on the left side of the congruence equation, and the readable normal data is placed on the right side.
Two congruences can be created.

[0063] After the normal data d11, p14, and p15 are read from the disk for the two congruent expressions obtained in this way and substituted into the expressions, unknown data d12 and d13 are obtained from these two simultaneous congruent expressions. The procedure for obtaining the unknown data is performed in exactly the same manner as the method for solving a general simultaneous equation.
Therefore, the description will be given with the expression number () added to each expression.

D12⊥ d13≡ 4⊥ 5≡1 (1) 3 * d12⊥4 * d13≡ 15⊥2 * 5≡5 (2) Here, equation 4 * (1) is calculated, The following equation (3) is obtained.

4 * d12⊥4 * d13≡4 * 1 4 * d12⊥4 * d13≡4 (3) Then, the equation (3) is calculated and the unknown data d1 is calculated.
Equation (4) is created by deleting 3.

4 * d12⊥3 * d12⊥4 * d13⊥4 * d13≡4⊥5 (4⊥3) * d12⊥ (4⊥4) * d13≡4⊥5 7 * d12⊥⊥1 ... 4) Here, it can be seen from the multiplication result of FIG. 2 that 7 * 6≡1. Therefore, the expression 6 * (4) is calculated, and the coefficient of the unknown data d12 is set to 1. Ask.

6 * 7 * d12≡6 * 1 d12≡6 (5) Further, the above equation (5) is set to the equation (1) or the equation (2), and the unknown data d13 is similarly obtained. Here, the following equation (6) is created by a method of substituting the equation (5) into the equation (2), and the unknown data d13 is obtained.

3 * d12⊥4 * d13≡5 ... (2) 3 * 6⊥4 * d13≡5 10⊥4 * d13≡54 * d13≡5⊥104 * d13≡15 ... (6) Here, since 4 * 13≡1 is known from the multiplication result shown in FIG. 2, the value of d13 can be obtained by calculating the expression 13 * (6) and setting the coefficient of the unknown data d13 to 1. .

13 * 4 * d13≡13 * 15 d13≡7 (7) By following the above solution procedure, the following equation (5) is obtained.
According to the equation (7), the unknown data d12 = 6 and d13, respectively.
= 7 is obtained, which matches the assumed value set at the beginning.
It can be seen that the unknown data is correctly obtained, and that the data of the failed disk has been restored.

Therefore, the data of the failed disk in all the second and subsequent groups are restored according to the same procedure as described above.

In the specific example described above, the case where the number of redundant parities is 2 has been described as an example. For example, when the number of redundant parities is k, k congruence equations can be assembled. Since up to k pieces of unknown data can be obtained, even if k pieces of data are lost, the data can be restored.

Further, in the above embodiment, since ⁿ of the expanded Galois field GF (2 ⁿ ) is treated as 4, only up to 15 coefficients 1 to 15 can be added to the data of the congruential expression. The maximum number of data in one group was 15 or less. However, by setting n to a larger value, a coefficient having a larger value can be handled, and a very large number of data can be handled.

Further, the RAID control device 4 can be constituted by hardware. That is, a parity calculating means including a logic circuit element (hardware) for calculating parity data to be added to each data disk group using the enlarged Galois field GF (2 ⁿ ) in the manner described above, and an arbitrary disk fault When the data of the failed disk is unknown, the expanded Galois field GF
By constructing a simultaneous congruence equation according to the rule of (2 ⁿ ) and solving the congruent congruence equation, the data can be constituted by data restoring means composed of logic circuit elements (hardware) for restoring data of the failed disk. , Parity calculation and data restoration calculation can be performed at high speed.

(Other Embodiments) (1) In the embodiment shown in FIG. 1, a specific parity disk is provided separately from a data disk for recording data, but as shown in FIG. For example, each of the five disks 7a to 7e is divided into six blocks, and the upper block of each disk 7a to 7e is the first group, the next block is the second group, and the group names are sequentially assigned to the lower blocks. I will attach it. The other configuration is the same as that of FIG. 1 and therefore will not be described below. This embodiment is particularly different from the first embodiment in that each group of five disks 7a to 7e has an arbitrary 2 disks.
One block is set as a parity block.

By the way, in the first group of the disks 7a to 7e shown in FIG. 3, the parity p14 and p15 are set in the blocks of the disks 7d and 7e, and in the second group the parity p24 and p25 are set in the blocks of the disks 7c and 7d.
Set. Parities are set in other groups in the same manner.

As a result, the first group of data d11
Is partially rewritten, the parity p14,
p15 needs to be changed. Hereinafter, even when a part of the data of the second and subsequent groups is changed, the parity is similarly changed.

However, if the configuration is such that the parity is set to a different disk for each group, the following advantages can be obtained. Generally, when a part of data is changed, it is often necessary to change the parity for some groups at once. However, the parity storage position of each group is stored on a different disk as shown in FIG. With this configuration, usually, disk requests concentrate for parity rewriting and wait for disk requests. However, in the present embodiment, disk requests do not concentrate and there is an advantage that disk request waiting can be eliminated. .

(2) Next, the invention of the recording medium according to the present invention will be described.

FIG. 4 is a diagram showing the overall configuration of a RAID device having a recording medium.

The RAID device includes an input device 11 such as a keyboard and a mouse, a display device 12, a recording medium 13 for recording a parity calculation and data restoration program described later, and a parity recorded on the recording medium 13. A data processing unit 14 composed of a CPU that reads out one of a calculation program and a data restoration program to realize a predetermined function, and stores program data, data during processing, data of a processing result, and other data necessary for program processing. It comprises a data buffer 15 for temporary storage and a plurality of disks 16 _{1 to} 16 n connected to a bus line derived from the data processing unit 14.

As a recording medium, a magnetic disk is generally used, but other than that, for example, a magnetic tape, CD-ROM, DVD-ROM, floppy disk, MO, CD-R, memory card, etc. May be used.

The data processing section 14 realizes the following functions when calculating parity and restoring data.

First, in the parity calculation processing, a data read function for sequentially reading data in a group of each data disk, and a predetermined function for each block of data in the group according to the expanded Galois field GF (2 ⁿ ). The parity acquisition function of multiplying the coefficient of the above and adding the multiplied values, the parity setting function of setting the parity acquired by the parity acquisition function to the corresponding block in the group, and the above series of functions for storing the parity And a function to be repeatedly executed for blocks and all groups.

On the other hand, in the data restoration process, a data read function for reading data and parity of a normal data disk and parity disk when a disk failure occurs, and the read data and parity are used in accordance with the number of disk failures. The present invention realizes a data restoration function of creating a simultaneous equation and obtaining unknown data, and a function of repeatedly restoring data for blocks and all groups of a data disk for a series of these functions.

Next, an example of processing of a program recorded on the recording medium 13 will be described with reference to parity calculation processing and data restoration processing.

(A) Example of parity calculation processing (see FIG. 5).

After storing data in each group of the data disk or each block of all groups, the data processing unit 14 reads a parity calculation program from the recording medium 13 when, for example, inputs a parity calculation instruction from the input device 11. The following processing is executed.

That is, after performing initialization processing for erasing unnecessary data in the data buffer 15 and the like, the data processing unit 14 stores data “i = 1” corresponding to the first group of the disk in the counter memory in the data buffer 15. Is set. Thereafter, data of each block belonging to the first group of each data disk is read and stored in the data buffer 15 (S1 to S3, data read function).

Further, the data processing section 14 multiplies each read data in the first group by a predetermined coefficient in accordance with the expanded Galois field GF (2 ⁿ ) to obtain multiplied value data for each data. Then, a parity is obtained by adding these multiplication values (S4, S5, parity acquisition function).

When the parity is obtained as described above, the parity is set to one predetermined block of the parity disk (S6, parity setting function).

Thereafter, it is determined whether the parity setting for all the parity blocks in the first group is completed. If the parity setting is not completed, the process returns to step S3 to execute the same processing. On the other hand, when the parity setting in the first group is completed,
It is determined whether parity setting for all groups is completed (S8),
If it has not been completed yet, +1 is incremented in the counter memory (S9), the process returns to step S3, and the same processing is repeatedly executed.

(B) Example of data restoration processing (FIG. 6
reference).

The data processing unit 14 automatically starts up when a data restoration instruction is issued from the input device 11 or when a disk failure occurs, reads a data restoration program from the recording medium 13, and executes the following processing.

That is, the data processing unit 14 performs initialization processing for erasing unnecessary data in the data buffer 15 and the like, confirms a data disk failure, and stores the data in the counter memory in the data buffer 15 in the first group of the disk. The corresponding data "i = 1" is set. After a while
Data of each block belonging to the first group of each data disk is read and stored in the data buffer 15 (S11 to S14, data read function).

Thereafter, the data processing unit 14 places the unknown data on the left side according to the rules of the extended Galois field GF (2 ⁿ ) using the unknown data and the normal data as the lost data. Is placed on the right side, a simultaneous congruence formula is created according to the number of data disk failures, unknown data is obtained by solving this congruence congruence formula, and stored in the data buffer 15 (S15, data restoration function).

Further, it is determined whether or not all data of the failed data disk in the first group is to be restored (S16). If not all of the failed data of the group is to be restored, the previously obtained unknown data is substituted into the simultaneous congruence equation. Unknown data is obtained (S15, S16).

Further, when it is determined in step S16 that all the in-group failure data has been restored, it is determined whether the restoration of all group data has been completed (S17). If there is any ungrouped data, the counter memory is incremented by +1 (step S17). S18) Returning to step S12, the same processing is repeatedly executed to restore all the lost data.

Therefore, according to the above embodiment, the data processing unit 14 reads and executes the parity calculation program shown in FIG. 5 and the data restoration program shown in FIG. For example, after storing data in each disk, parity can be calculated and set easily and automatically, and data lost when a plurality of data disks fail can be quickly restored.

The program on the recording medium 13 shown in FIG. 4 is considered as application software.
May be used as part of In this case, the program recorded on the recording medium 13 can be read by the data processing unit 14 or the host computer 6.

(3) In the above embodiment, the number of redundant parity calculations is fixed to two blocks for each group. However, the number of redundant parity calculations is determined by software or hardware. You may decide.

FIG. 7 is a block diagram showing such an embodiment.

This RAID system uses the transmission line 20
Controller 21 including computer on top and RAI
The D device 22 is connected.

Controller 21 including this computer
Transmits a program necessary for data processing to the RAID device 22.
The RAID device 22 is provided with a function to download necessary commands and instructions to the RAID device 22.

The RAID device 22 is the same as in FIG. 1 and FIG.
Multiple data storing parity with various data array configurations
Disk 23₁~ 23n, program processing start, program
Keys for inputting instructions necessary for program processing and setting information
-Includes board and other commonly used input devices
Hardware switch 24 and enlarged Galois field GF
(2 ⁿ) And the data disk as described above.
Calculate parity data to be added to each group
Paris composed of software or hardware
Error calculation means and any disk failure,
Expanded Galois field GF with raw disk data as unknown
(2ⁿ), And assemble the simultaneous congruence formula,
By solving the simultaneous congruence equation, the fault occurrence data
Software or hardware to restore disk data
RAID system with hardware-based data restoration means
A control device 25 is provided.

In the above system, an operator operates the controller 21 including a computer.
Enter the number of redundant parity calculations from the
To the device 22 or if the operator
The number of redundant parity calculations is input from the hardware switch 24 of the AID device 22 by operating the switch.

The RAID control device 25 calculates the parity according to the number of parity calculations input for each group or for all groups.

Therefore, according to the above-described embodiment, if the operator inputs the number of redundant parity calculations from the controller 21 or the hardware switch 24, redundancy is freely performed according to the application and purpose. The number of parities can be easily changed, and the reliability and flexibility can be secured.

(4) In the embodiment described above, one R
The AID control devices 6 and 25 use a plurality of disks (2a to 2a).
c, 3a, 3b), ( 7a~7e) or ₍₂₃ 21 to
3n), the parity is calculated and the lost data is restored. For example, as shown in FIG. 8, a plurality of RAID controllers 25a, 25b, and 25c individually manage disks. , For example, RAID
The control device 25a determines that the disks 23a1, 23a2, RAI
The D control device 25b determines that the disks 23b1 to 23b3
There is a configuration in which the ID control device 25c manages the disks 23c1 to 23c3.

In such a RAID device 22,
The plurality of RAID controllers 25a to 25c are linked to each other so that data can be exchanged, and these RAID controllers 25a to 25c
5c managed disks 23a1, 23a2, 23b1
23b3, 23c1 to 23c3 are formed into blocks 26 sequentially from the upper block, and in addition to writing and reading of data d in units of these groups, calculation of redundant parity p and restoration processing of data lost due to disk failure are performed. It is.

The calculation of the parity and the restoration of the data are as described above.

According to such an embodiment, each RAI
1 for each D controller due to redundant parity
This eliminates the restriction of installing more parity disks than the number of parity disks, and reduces redundant parity in the entire RAID device.

(5) In the RAID device shown in FIG. 1, the data of each disk, for example, d11, d12, d13
Are used to calculate the parities p14 and p15 individually, but the parity may be calculated by, for example, the following means to determine the location of the failed disk and restore the data.

More specifically, when calculating the parities p14 and p15, after calculating the parity p14, the calculation of the parity p15 is followed by the calculation of the parity p1 already calculated.
4 is also regarded as a part of the data and is calculated as follows by multiplying each data by a different coefficient.

D11⊥d12⊥d13≡p14 d11⊥d12⊥d13⊥p14≡0 (8) 2 * d11⊥3 * d12⊥4 * d13⊥5 * p14≡p15 (9) where d11 , D12, d13, p14, and p15, if an error e1 occurs, p15
, An error e1 is detected on the right side of the equation (8).

Further, when the parity is calculated in the above equation (9), an error corresponding to the coefficient of each data is detected except for p15. Therefore, by calculating the coefficient of the data, d11, d12, d13 and p14 are calculated. It is possible to specify that there is a possibility that an error has occurred in any of the disks.

Now, for example, each data d11, d12, d1
3, when p14 has the following value, error d1
Let's calculate it assuming that has occurred.

D11≡11 d12≡12 d13≡13 e1≡8 m is a different coefficient value assigned to each data.

The calculation of the parities p14 and p15 is as follows. 11⊥12⊥13≡p14≡10 2 * 11⊥3 * 12⊥4 * 13⊥5 * 10≡p15≡7 Here, the error of e1≡8 is found in d13. Suppose that the value of d13 has changed from 13 to 5.

11⊥12⊥5⊥10≡8≡e1 ... (10) 2 * 11⊥3 * 12⊥4 * 5⊥5 * 10≡1≡m * e1⊥p15 5⊥7⊥7⊥4≡ 1 {m * e1} 7 (11) Both sides of the equation (10) must be 0 as set in the equation (8) if no error occurs in the data, but an error occurs. If it does, it does not become zero. Equation (11) must match the parity p15 set in equation (9) if there is no error in the data.
If an error occurs, m according to the coefficient m of each data *
It comes out with the error of e1 included.

From the above equations (10) and (11),
By calculating and specifying m, it is possible to grasp which data has an error, and to specify a failed disk.

8≡e1 (10 ′) 1≡m * e1⊥7 (11 ′) By substituting this equation (10 ′) into equation (11 ′) and rearranging, 8 * m≡7⊥1 ≡ 6 (12) From the multiplication result diagram of FIG. 2, both sides of the equation (12) are multiplied by a coefficient 15 so that 8 * 15≡1, and the coefficient of m is set to 1 to obtain the value of m.

15 * 8 * m≡15 * 6 m≡4, which indicates that the coefficient is d13. Here, for further checking, using equation 4 * (8) ⊥⊥ (9),
The following equation (13), which excludes the factor of the data d13, is created and verified.

4 * d11 ４ 4 * d12 ４ 4 * d13 ４ 4 * p14≡ 0 2 * d11 ３3 * d12 ４4 * d13 ５ 5 * p14≡p15 6 * d11 ７7 * d12 １1 * p14≡p15 …… (13) 6 * 11 ７ 7 * 12 １ 1 * 10≡715 15 ⊥2⊥10≡7 7≡7 When the values on both sides do not match in the above equation (13), one of the first assumed The error was denied,
It can be determined that there is an error in data at a plurality of locations. For the same reason, it can be seen that an error location can be specified for d11, d12, and p14 other than d13.

When one error occurs in the parity p15, the factor of each data is eliminated by a method excluding the factor of the data d13 created by the above equation (13), and the factor of the data which error is determined. If the error remains constant even after exclusion, it can be determined that there is an error in the parity p15 itself, while if a different error is calculated, it can be determined that there are errors in two or more locations.

If the error location can be identified at one location,
The data at the erroneous part can be easily restored by the procedure described in (1).

As described above, when the number of redundant parities is two, one data can be restored.
Generally, every time the number of redundant parities increases by one, an error factor considered to be added to data can be eliminated one by one, so that it is possible to provide a software RAID device capable of correcting data of redundant number of parities minus one. .

Therefore, according to the above-described embodiment, even if the disk does not have an error detecting function, it can be easily used, and by having such an error detecting function, a more reliable device can be realized.

In addition, the present invention can be variously modified and implemented without departing from the gist thereof.

[0129]

As described above, according to the present invention, parity can be calculated quickly after data is stored in a plurality of disks by using the enlarged Galois field GF (2 ⁿ ), and a plurality of disks can be simultaneously calculated. Even if the disk fails, the contents of the disk can be easily restored.

Further, the number of redundant parities can be arbitrarily changed according to the application and purpose, and a device with improved reliability and flexibility can be realized.

Further, since the entire disks under the management of a plurality of RAID controllers are grouped and redundant parity is set for each group, one or more parity disks are necessarily installed for redundant parity. This eliminates the restriction that must be made, and reduces the parity that is redundant in the entire RAID device.

Further, a failed disk can be easily found from the parity calculation, and the data can be restored.

Further, according to the recording medium of the present invention, it is possible to provide a recording medium in which a program capable of calculating parity and simultaneously restoring the contents of a plurality of disks accurately when a plurality of disks fail is recorded.

[Brief description of the drawings]

FIG. 1 is a configuration diagram showing an embodiment of a RAID device according to the present invention.

FIG. 2 is a diagram illustrating a result of multiplication by an enlarged Galois field GF (2 ⁿ ).

FIG. 3 is a diagram for explaining another embodiment of the RAID device according to the present invention, and is a diagram in which parity is set to an arbitrary block for each group unit.

FIG. 4 is a configuration diagram of a computer system explaining a recording medium according to the present invention.

FIG. 5 is a flowchart for explaining a processing example of a program recorded on the recording medium shown in FIG. 4;

FIG. 6 is a flowchart illustrating another processing example of the program recorded on the recording medium illustrated in FIG. 4;

FIG. 7 is a configuration diagram showing another embodiment of the RAID device according to the present invention.

FIG. 8 is a configuration diagram showing still another embodiment of the RAID device according to the present invention.

[Explanation of symbols]

1, 22 ... RAID devices 2a, 2b, 2c ... data disks 3a, 3b ... parity disks 4, 25a, 25b, 25c ... RAID control devices 6 ... host computers 7a to 7e, 161 to 16n, 23a1, 23a2, 2
3b1 to 23b3, 23c1 to 23c3 ... Disk 13 ... Recording medium 21 ... Controller including computer 22 ... Recording medium 26 ... Group

──────────────────────────────────────────────────続 き Continued on the front page (51) Int.Cl. ⁷ Identification symbol FI Theme coat ゛ (Reference) G11B 19/04 501 G11B 19/04 501G 501D 20/18 570 20/18 570Z

Claims (7)

[Claims] 1. A RAID apparatus for distributing and storing data on a plurality of data disks, a redundancy means for making a plurality of parity disks redundant on the plurality of data disks, a data storage area and a parity of the data disk. Division means for dividing the parity storage area of the disk for use into arbitrary integers in bit units, and an extended Galois field GF (2 ⁿ ) (n is an integer), for each group unit connected by predetermined blocks of all the disks Parity calculating means for calculating the parity of the parity disk to be added to the data disk, and in the event of a failure of the arbitrary data disk, the data of the failed disk is regarded as unknown data, and the expanded Galois field GF (2 ⁿ )
And a RAID control device having a data restoration means for restoring the unknown data from the simultaneous equation according to the rules defined in (1).
ID device. 2. The RAID device according to claim 1, further comprising a parity distribution unit that distributes the parity to an arbitrary disk for each group without fixing the parity to a specific disk. apparatus. 3. A recording medium for recording a parity calculation program for calculating a parity for redundancy of data of a plurality of data disks, wherein the data read function reads data for each data disk group unit. And a parity calculating function of multiplying the data for each group unit by a predetermined coefficient in accordance with the expanded Galois field GF (2 ⁿ ) and adding the multiplied values to calculate a parity; Computer-readable recording in which a parity calculation program is recorded in order to realize a parity setting function of setting a parity to be set to a predetermined block in the corresponding group and a function of repeatedly executing the above series of functions for all groups. Medium. 4. A recording medium for recording a data restoration program for restoring data in the event of a data disk failure, wherein said computer reads out data of a normal data disk and parity of a parity disk when a disk failure occurs. Using the function, the read data and the parity, a simultaneous congruence formula according to the number of disk failures is created based on the rule of the extended Galois field GF (2 ⁿ ), and a data restoration function for finding unknown data. A computer-readable recording medium in which a data restoration program is recorded to realize a function of repeatedly restoring data for all groups. 5. The RA according to claim 1 or 2,
In the ID device, the host device or the hardware switch of the device
A means for determining and inputting an arbitrary number of redundant parity calculations to the AID control device.
AID device. 6. The RAID device according to claim 1, wherein a plurality of RAID controllers for managing a plurality of disks are linked to each other, and the RAID controllers are managed by the RAID controllers. Characterized in that a means for grouping predetermined blocks of all disks of each group and setting parity for each group is provided.
AID device. 7. The RAID device according to claim 1, wherein when calculating a plurality of parities, the second and subsequent parities are already calculated. A RAID apparatus characterized in that the calculated parity is regarded as a part of data, the parity is calculated, a failed disk is specified from a data error in the calculation result, and data is restored.