CN1959648B - Method for establishing error encoding scheme and equipment for reducing data loss - Google Patents

Abstract

One embodiment disclosed is method for protecting data stored on at least one storage unit against uncorrectable media errors. The method includes associating a given redundancy set of at least one redundancy information sector (R) with a given data set of at least two data information sectors (D). The information content of the redundancy set is computed dependent on the information content of the data set. A storing operation stores the information content of the redundancy set consecutively with the information content of the data set forming a segment such that the redundancy set is placed logically in between a first part and a second part of the data set, and accessing at least one data information sector (D) in the data set by reading and/or writing the information content of the at least one data information sector (D) and at least one redundancy information sector (R) in the redundancy set with a single request.

Description

Method for creating an error-correcting coding scheme and apparatus for reducing data loss

technical field

The present invention relates to a method of creating an error correction coding scheme to reduce data loss. It also relates to methods, apparatus, computer program products and computer programs for reducing data loss. It also relates to a system for protecting data stored at at least one storage unit against uncorrectable media errors.

Background technique

The storage unit is eg based on at least one magnetic or optical disk or solid state memory as storage medium. As the storage capacity of a single storage unit increases, the probability of encountering at least one medium-dependent error when reading data stored on at least one storage medium of the storage unit also increases. Data is lost when errors cannot be corrected by re-reading certain portions of the medium. By storing redundant data distributed to two or more storage units, the reliability of a system comprising the two or more storage units can be increased. Such a system is known as a Redundant Array of Independent Disks (RAID). A RAID-configured system primarily reduces data loss due to a complete failure of a storage unit.

US 2005/0108594 A1 discloses a method of protecting data on a disk drive against uncorrectable media errors. A RAID configured storage system is provided with protection against uncorrectable media errors by a technique in which redundant information sectors are associated with data information sectors. The data information sector and the redundant information sector are written as a single segment into a single storage unit. The redundant information is based on a Reed-Solomon code (an XOR-based code) or an even-odd parity check.

Therefore, there is a need to provide a simpler method of creating encoding schemes to reduce data loss than previously proposed techniques. Also, there is a need to provide a method, apparatus, computer program and computer program product for reducing data loss that is simpler than previously proposed techniques. There is also a need to provide a system for protecting data stored on at least one storage unit from uncorrectable media errors that is simpler and more reliable than previously proposed techniques.

Contents of the invention

According to an embodiment of the first aspect of the present invention there is provided a method for creating an error correction coding scheme to reduce loss of data comprising at least two data information entities associated with a given data set having at least two data information entities Given a redundant set of two redundant information entities, the information content of said redundant set is calculated from the information content of said data set, said method comprising the following steps: a basic selection step for selecting represented by a basic matrix A basic coding scheme of wherein each redundant information entity is represented by a row and each information entity is represented by a column; and a matrix setting step for setting a target matrix having a subset of the columns of the basic matrix and for The base matrix changes the order of columns until the target matrix satisfies a given pattern of nonzero elements to at least a given degree. This functionality allows building a computation engine for computing the information content of the redundancy set that is simpler than the computation engines used in previously proposed techniques. The given pattern of the non-zero elements affects the complexity of the error correction coding scheme and thus its implementation in the computation engine. The information entity may be a bit or a byte or a sector on a storage unit or any other suitable entity for storing or transmitting or receiving information.

According to a preferred embodiment of the first aspect of the present invention, said given pattern of nonzero elements is chosen to comprise the main diagonal of a square pattern submatrix of said target matrix, said main diagonal having mainly nonzero elements zero elements, the target matrix has a number of rows and columns equal to the number of redundant information entities in the redundancy set. The given pattern of said non-zero elements is thus simpler and regular and allows simpler construction of calculation engines.

In this respect, it is advantageous that said given pattern of non-zero elements is chosen to also comprise adjacent diagonals arranged adjacent to said main diagonal of said square pattern sub-matrix of said target matrix, so The elements adjacent to the diagonal are chosen to be predominantly nonzero. This allows the calculation engine to be built so that elements of the adjacent diagonal can be processed by utilizing intermediate results calculated from elements of the main diagonal. The calculation engine can thus be more efficient.

According to a further preferred embodiment of the first aspect of the present invention, said fundamental matrix is selected to have a minimum number of non-zero elements, a minimum number of data information entities in said data set for a given Hamming distance of said basic coding scheme number and the minimum number of redundant information entities in the redundancy set. This allows reducing the number of operations for computing the information content of said redundancy set.

According to other preferred embodiments of the first aspect of the present invention, in the matrix setting step, the order of the columns is changed until each of the target matrix whose number of columns is equal to the number of redundant information entities in the redundancy set The rank of the square lattice matrix is equal to the number of redundant information entities in the redundant set. This allows recovery of consecutive unreadable data information entities at most equal to the number of redundant information entities in said redundancy set, also called "erasures". Thereby, data can be more reliably protected against data loss and the possibility of data loss can be reduced.

According to a further preferred embodiment of the first aspect of the present invention, said created error correction scheme is based on calculating the exclusive OR of the information content of all data information entities represented by non-zero elements in each row of said target matrix, respectively. This allows for simpler and higher-performing error-correcting coding schemes, while reducing the overhead of computing the redundancy set, and is easier to implement than previously proposed techniques.

In this respect it is advantageous if the basic coding scheme is based on one of Hamming codes or extended Hamming codes. This makes the error correction coding scheme more reliable.

According to an embodiment of the second aspect of the present invention, there is provided a method for reducing the loss of data comprising at least two redundant information entities associated with a given data set having at least two data information entities Given a redundancy set of , the information content of the redundancy set is calculated from the information content of the data set by applying an error correction coding scheme represented by a parity check matrix, where each redundancy information entities are represented by rows, and each information entity of said data is represented by a column, and at least two square sub-matrices of said parity-check matrix have diagonals with predominantly non-zero elements and have the same redundancy as said The number of redundant information entities in the set is equal to the number of rows and columns and represents consecutively placed data information entities of said data set, said method comprising: a first calculation step for processing said at least two primary pairs calculating an intermediate result of the redundant information entity based on the data information entity on the diagonal line; and a second calculation step for calculating the information content of the redundant information entity according to the intermediate result. Computing the information content of the redundancy set is simpler since the main diagonals of the at least two square sub-matrices of the parity-check matrix have predominantly non-zero elements.

According to a preferred embodiment of the second aspect of the present invention, at least one square sub-matrix of said parity-check matrix whose elements on said main diagonal are predominantly non-zero also has adjacent diagonals whose elements are predominantly non-zero, And said second calculating step comprises using said intermediate result to process data information entities on the corresponding adjacent diagonal. This allows more efficient computation of the information content of the redundant set.

According to other preferred embodiments of the second aspect of the present invention, the corresponding information content of each redundant information entity in said redundancy set is calculated as all Exclusive OR of the corresponding information content of all data information entities in the above data set. This allows to reduce overhead when computing the information content of the redundancy set, resulting in higher performance. The method is also easier to implement.

According to an embodiment of the third aspect of the present invention, an apparatus for reducing data loss is provided. The device corresponds to an embodiment of the second aspect of the invention and its advantages.

According to an embodiment of the fourth aspect of the present invention there is provided a system for protecting data stored on at least one storage unit against uncorrectable media errors. The system comprises an apparatus comprising the third aspect of the invention and at least one storage unit. Each information entity represents a sector on said at least one storage unit. The system corresponds to the device and its advantages.

According to a preferred embodiment of the fourth aspect of the present invention, the system is configured as a redundant array of independent storage units. This configuration is also known as Redundant Array of Independent Disks (RAID). This allows for greater reliability, especially in the event of a complete failure of a storage unit. Data loss is thus reduced by inter-disk redundancy provided by redundant arrays of independent storage units and by intra-disk redundancy provided by redundant sets. Advantageous embodiments of the third aspect of the invention are not limited to disks, but may also include any other kind of storage unit.

According to an embodiment of the fifth aspect of the present invention there is provided a computer program product for reducing data loss, the computer program product comprising a computer readable medium containing program instructions executable by a computer. Said program instructions correspond to embodiments of the second aspect of the invention and its advantages.

According to an embodiment of the sixth aspect of the invention there is provided a computer program comprising program instructions for reducing data loss. Said program instructions correspond to embodiments of the second aspect of the invention and its advantages.

Description of drawings

Referring now by way of example to the accompanying drawings, these drawings are:

Figure 1 schematically shows a system;

Figure 2 is a block diagram of the system shown in Figure 1;

3 is a schematic diagram of data organization in a system configured with RAID level 5 including five storage units;

Figure 4 is a schematic diagram of the data organization of a segment in a system comprising eight storage units configured with RAID level 5;

Figure 5 shows a parity check matrix representing an interleaved parity check code;

Figure 6A shows a parity check matrix representing a known extended Hamming code;

Figure 6B shows a parity check matrix of a sparse extended Hamming code;

Figure 6C shows a parity check matrix of a sparse Hamming code;

Figure 7 shows a flowchart of a method for automatically creating an error correction coding scheme;

Figure 8 shows a parity check matrix representing an automatically created error correction coding scheme based on the parity check matrix shown in Figure 6C;

Figure 9 shows a flowchart of a method for reducing data loss; and

Fig. 10 shows a table showing properties of error correction coding schemes based on the parity check matrices shown in Figs. 5, 6B, 6C and 8, respectively.

Detailed ways

Figure 1 illustrates a system for gaining an understanding of an embodiment of the invention. The system comprises at least one storage unit 100 represented in this embodiment by a hard disk drive comprising at least one magnetic disk 101 as storage medium and a read/write head 102 . A read/write head 102 may be placed on a selected track of the at least one magnetic disk 101 . Binary data is stored on the magnetic disk 101 by selectively orienting the magnetism in selected data areas on the magnetic disk 101 using the read/write head 102 . The system also includes means 103 for reducing data loss. The at least one storage unit 100 is connected to a device 103 .

FIG. 2 shows a block diagram of the system shown in FIG. 1 . The device 103 comprises a host interface 104 for connecting to a host (e.g. a computer system), a controller 105 for controlling the at least one storage unit 100, a computing engine 106 comprising an internal memory 107 and an external memory connected to the computing engine 106 108. The host interface 104, the controller 105 and the computing engine 106 are connected so that data can be requested through the at least one storage unit 100 to the host interface 104 or vice versa and between the host interface 104 and the computing engine 106 or between the controller 105 and the computing engine 106 to send.

Figure 3 shows an overview of data organization in a system configured with RAID level 5 comprising an array 200 of five storage units 100 labeled as first storage unit HDD1, second Storage unit HDD2, third storage unit HDD3, fourth storage unit HDD4, and fifth storage unit HDD5. The five storage units 100 are respectively connected to the device 103 . Data is organized in stripes 202 . Stripe 202 spans all five storage units 100 . For each stripe 202 , each individual storage unit 100 of the system includes a stripe 203 . Each stripe 203 includes four segments 204, and each segment 204 includes sixteen data blocks, each data block including eight sectors. Each segment 204 therefore includes 128 sectors.

In a system configured with RAID level 5, each stripe 203 carries user data E or RAID parity data P. The RAID parity data P is calculated as the modulo-2 sum (also called exclusive OR or XOR) of all user data E in the same stripe 202 . The location of the RAID parity data P is rotated from one storage unit 100 to some other storage unit 100 in the array 200 in successive stripes, respectively. If a certain storage unit 100 fails, then from other user data E and RAID parity data P stored in the same stripe 202 on other storage units 100 that are still working, the data stored on the failed storage unit 100 can be recovered. Corresponding user data E and RAID parity data P. A system configured with RAID level 5 allows rebuilding the information content of a failed storage unit 100 by recovering damaged data and writing it to a spare storage unit 100 included in the system.

If the second storage unit 100 fails or a media error occurs on some other storage unit 100 before the rebuild is complete, data loss can occur in a system configured with RAID level 5. As the storage capacity of a single storage unit 100 increases, the total number of bytes read during the reconstruction operation becomes larger. This increases the possibility of encountering uncorrectable media errors (usually causing one or more sectors to become unreadable). This is especially problematic when uncorrectable media errors coincide with the failure of one storage unit 100 in the system. For example, if one storage unit 100 fails in a system configured with RAID level 5, the reconstruction process will read all the data on the remaining storage units 100 to rebuild the damaged data on the spare storage unit 100 . At this stage, an uncorrectable media error on any surviving memory unit 100 in the array 200 would result in data loss because there is no way to reconstruct the information content of the uncorrectable sector. During this problematic phase, the risk of data loss becomes greater as disk capacity continues to grow rapidly while disk bandwidth and disk reliability increase much more slowly. Theoretical and practical results indicate that the major source of data loss in systems configured with RAID level 5 is media-related failures during rebuilds.

By providing in-disk redundancy, also known as sector protection through in-disk redundancy (SPIDRE), the risk of data loss due to one or more media errors can be reduced. 4 is an overview diagram of the data organization of a segment 204 of another system configured with RAID level 5, said system including eight storage units 100, respectively labeled as the first storage unit HDD1, the second storage unit HDD2, the third storage unit unit HDD3, fourth storage unit HDD4, fifth storage unit HDD5, sixth storage unit HDD6, seventh storage unit HDD7, and eighth storage unit HDD8. Segment 204 includes sixteen data blocks on each storage unit 100 with user data E, RAID parity data P or on-disk redundancy data S. Each segment 204 on each storage unit 100 has a data block with on-disk redundant data S. The on-disk redundant data S is respectively associated with the user data E or the RAID parity data P of the segment 204 on the same storage unit 100 . When user data E and RAID parity data P are respectively written into segment 204 or updated in segment 204, calculation engine 106 in device 103 can be used to calculate and provide user data E and RAID parity from segment 204 Data P calculates the information content of redundant data S on the disk. The computing engine 106 can also be used to restore the user data of unreadable sectors respectively from the information content of other user data E and RAID parity data P and the on-disk redundant data S stored in the same segment 204 of the same storage unit 100 E and the information content of the RAID parity data P.

The concept of intra-disk redundancy can be applied to any existing RAID architecture or level, for example, RAID level 5, level 51, level 6 or level N+3. The RAID redundancy provided by the RAID redundancy data S mainly reduces the loss of data stored on the array 200 caused by the failure of a certain complete storage unit 100 . On-disk redundancy reduces the loss of data stored on each individual storage unit 100 due to uncorrectable media errors. It can be understood that the concept of intra-disk redundancy can also be applied to a system including only a single storage unit 100 .

Each modification to user data E in a segment 204 (for example, the fourth block of segment 204 on the second storage unit HDD2) should be accompanied by an update to the on-disk data associated with the modified user data E in the same segment 204. Update of redundant data S (for example, the ninth data block of segment 204 on the second storage unit HDD2). Furthermore, the RAID parity data P corresponding to the modified user data E should also be updated (for example, the fourth data block of the segment 204 on the eighth storage unit HDD8). Due to the update of the RAID parity data P, the redundant data S on the disk associated with the updated RAID parity data P should also be updated (for example, the ninth data block of the segment 204 on the eighth storage unit HDD8 ). Writing these four data blocks individually results in four requests. By sequentially storing the on-disk redundant data S and the user data E in the same segment 204, only the first request 205 and the second request 206 are used to update the block of the user data E, the block of the RAID parity data P and the on-disk The corresponding block of redundant data S.

In normal operation (ie, no failure of any storage unit 100 ), user data E can be read from at least one storage unit 100 without simultaneously reading the corresponding RAID parity data P. Correspondingly, the user data E can be read from at least one storage unit 100 without simultaneously reading the on-disk redundant data S, as long as no medium error occurs during the reading of the user data E. Reading several blocks of contiguous user data E is advantageously done using a single request. This request may also include the reading of on-disk redundant data S if it is located between the blocks of user data E included by the request. It can be understood that in this case, the information content of the redundant data S on the disc can be ignored.

Each request to update user data E uses reading and writing at least two data blocks on at least two storage units 100: respectively modified user data E and RAID parity data P, and corresponding on-disk redundancy The remaining data S. Using separate requests to read and write each of the four data blocks would use four read requests plus four write requests for each update of user data E. By applying the first request 205 and the second request 206, updating of the user data E can be achieved using only two read requests plus two write requests. One or more other data blocks ( In particular user data E or RAID parity data P). The number of data blocks requested per request thus depends on the distance between the modified block of user data E or RAID parity data P and the corresponding block of on-disk redundant data S. By placing the on-disk redundant data S approximately in the middle of the segment 204, the average data for all read and/or write requests can be reduced compared to placing the on-disk redundant data S at the beginning and end of the segment 204 number of blocks. In this embodiment, the average number of data blocks read and/or written per request is approximately 5.27. A typical ratio of seek time per request to time to read a block of data, say 4KB, is about 50 to 1. Using each request to read and/or Or the impact of writing multiple data blocks on overall read/write performance (especially when updating user data E) is therefore smaller.

As an example, each data block is 4KB in size. Segment 204 has 128 sectors. Each data block is divided into eight sectors. A data block with on-disk redundant data S is regarded as a redundant set of redundant information sectors R. The number r of redundant information sectors R is eight. Each block of user data E has eight data information sectors D. There are fifteen blocks of user data E in section 204 . Therefore, the number n of data information sectors D with user data E is 120. All 120 data information sectors D of all blocks of user data E of segment 204 are regarded as one data set. The redundancy set is associated with the data set in segment 204 . The information content of the redundant set is calculated from the information content of the data set. Specifically, each sector of redundant information R in the redundant set is considered as a parity calculated from a corresponding associated subset of the data set, i.e. as a parity check that is a subset of the data set Each redundant information sector R is calculated from the parity of the corresponding associated set of data information sectors D.

When a block of user data E cannot be correctly read from the storage unit 100, the block of user data E is marked as a so-called "deleted portion". In some cases, the information content of the deleted part can be restored by using other blocks of user data E of the same segment 204 on the same storage unit 100 and information content of on-disk redundant data S. The error correction capability (or more precisely, the erasure recovery capability) achieved by providing the redundancy set associated with the data set in the segment 204 depends on the data information sector D used to calculate the corresponding redundant information sector R Select accordingly. It is desirable to compute the information content of the redundant set using as few computational operations as possible in order to reduce the need to use complex computation engines 106 .

Fig. 5 shows a parity check matrix H, which represents a so-called interleaved parity-check code (IPC code), specifically an IPC-8 (128, 120) code, which is used in one embodiment of the present invention and hereinafter It is called the first type of parity check matrix. The parity check matrix H has 8 rows, and each row corresponds to each redundant information sector R in the redundancy set. The parity check matrix H also has 128 columns, and each column corresponds to each sector of the segment 204 . The non-zero elements in the parity check matrix H are shown as dots. For each data block, the interleaved parity code has eight non-zero elements. Non-zero elements are placed on the diagonal of each distinct 8×8 sub-matrix representing a block of data. All non-zero elements in each row of the parity-check matrix H mark all sectors that form the corresponding associated subset of the data set used to compute the corresponding sector R of redundancy information. The corresponding redundant information sector R is calculated by calculating the exclusive-or of all data information sectors D marked in the corresponding row of the parity-check matrix H. Applying the interleaved parity code, there are 128 non-zero elements in the number nz, ie 128 XOR operations should be performed to calculate the information content of the redundancy set, ie the on-disk redundant data S of the segment 204 . The minimum Hamming distance dmin of the interleaved parity code is 2. IPC-8 (128, 120) encoding has the property of correcting at most r number of redundant information sectors R, ie at most 8 consecutive sectors with media errors in segment 204 and any single sector media error.

6A to 6C respectively show the second, third and fourth types of parity check matrix H used in one embodiment of the present invention. The second type of parity check matrix H shown in FIG. 6A is a known extended Hamming code whose minimum Hamming distance dmin is 4. The number nz of nonzero elements in this parity check matrix H is 576. The third type of parity check matrix H shown in FIG. 6B is an extended Hamming code, and the parity check matrix H is sparse, that is, the number of non-zero elements nz is reduced to 512. The minimum Hamming distance dmin is 4. In the fourth type of parity check matrix H shown in FIG. 6C , the number nz of nonzero elements is further reduced. FIG. 6C shows a Hamming code in which the parity check matrix H is sparse and the minimum Hamming distance dmin is 3. FIG. The number nz of non-zero elements is 376.

For a given minimum Hamming distance dmin of 4 or 3, the number r of redundant information sectors R being 8, and the number n of data information sectors D being 120, the third and fourth types of parity check matrices H have the smallest number of non-zero elements nz.

When the minimum Hamming distance dmin is 3, it can ensure that the parity check matrix H has the least number of non-zero elements nz, because the columns of the parity check matrix H representing the Hamming code are formed from the set of binary tuples, and the redundant information fan The number r of elements of the region R represents all non-zero numbers up to 2 minus 1 to the r power of the number of redundant information sectors R. The columns of the parity-check matrix H may be sorted such that the number of nonzero elements nz of the columns increases from left to right. If all sectors of the segment 204 are represented by columns less than 2 to the power r of the number of redundant information sectors R minus 1, the minimum number nz of non-zero elements can be guaranteed by selecting the leftmost column. The minimum number of non-zero elements cannot be guaranteed in the same way when the minimum Hamming distance dmin is greater than 3.

The third and fourth types of parity-check matrices H are also modified so that, in terms of error correction capabilities for correcting at most r redundant information sectors R (i.e., at most 8 consecutive sectors with medium errors), They exhibit the same properties as interleaved parity codes. Compared with interleaved parity-check codes, extended Hamming codes have better error correction capability because the minimum Hamming distance dmin is 4 or 3, respectively. This additionally allows any three and two sector media errors in segment 204 to be corrected, respectively. Typically, a single media error of the minimum Hamming distance dmin minus 1 can be corrected in section 204 . The use of extended Hamming codes thus results in improved protection of the storage unit 100, and thus increases the reliability of the storage unit 100, but also increases the computing power of the computing engine 106 to perform a greater number of XOR operations, because with Compared with the interleaved parity-check code, the number nz of non-zero elements in the parity-check matrix H is larger. The error correction capability of the interleaved parity code is applicable to most high-end storage units 100, especially most high-end hard disk drives (eg, incorporating Small Computer System Interface, SCSI). One of the extended Hamming codes, which have higher error correction capabilities than interleaved parity codes, can be considered for low-end storage units 100, especially low-end hard drives (e.g., in combination with Advanced Technology Attachment System, ATA or Serial Advanced Technology Attachment System, SATA).

In order to reduce the need to use a complex calculation engine 106 and to ensure certain characteristics of data protection, for example, the error correction capability of at most r consecutive unreadable sectors that corrects the number of redundant information sectors R caused by media errors can be improved Parity check matrix H. Two metrics are introduced to better compare different error correction coding schemes based on different parity-check matrices H.

The first metric is XORO, or XOR overhead. XORO is a measure of the computational cost of programming an XOR engine to complete all the XOR operations for a given task (eg, computing the information content of a redundant set). The XOR engine is represented by calculation engine 106 . For a single XOR operation with k operands, XORO is defined as XORO(k)=k+1. XORO does not state the size of the operands.

A given task consumes memory bandwidth due to subtasks such as moving data or parity between the storage unit 100 and the external memory 108, sending user data E from the external memory 108 to the host through the host interface 104 ( e.g., computer system), or move data or parity into and out of an XOR engine (ie, compute engine 106). Memory bandwidth consumption is quantified by a second metric named MBWC. For example, if a given task is to compute the XOR of a given number of data blocks (e.g., user data E or RAID parity data P) received from the host and combine these blocks with the calculation result (e.g., on-disk redundancy If the remaining data S) are written together in at least one memory cell 100, then the memory bandwidth consumption MBWC to complete this given task consists of several parts. In the first part, a given number of data blocks received from the host are written to the external memory 108 . In the second part, the given number of data blocks are read from the external memory 108 into the computing engine 106 . In the third part, the calculation result is written back to the external memory 108 . In the fourth part, a given number of blocks and calculation results are written to at least one storage unit 100 . Therefore, the total number of data blocks transferred to and from the external memory is three times the given number of data blocks plus twice the calculated result. In this example, all data blocks have the same size, eg, 4KB.

The calculation of XORO is further illustrated using IPC-8 (128, 120) encoding. Each redundant information sector R is the result of an exclusive OR operation of fifteen different data information sectors D out of a total of 120 data information sectors D of segment 204 . The interleaved correlation of redundant information sectors R to data information sectors D is captured in an 8×128 parity-check matrix H with a regular pattern comprising sixteen different 8 A sub-matrix of the x8 pattern, the sub-matrix having non-zero elements on the corresponding main diagonal. All other elements of each 8x8 pattern sub-matrix are zero. If all 120 data information sectors D of the segment 204 are stored in the external memory 108, then it is possible to use sector R) to calculate each redundant information sector R in the eight redundant information sectors R. Therefore, the calculated XORO value of each redundant information sector R is equal to sixteen, while the calculated XORO value of all eight redundant information sectors R is 128. In this case, each redundant information sector R can be calculated sector by sector.

Considering that 120 data information sectors D are stored consecutively in consecutive locations of the external memory 108, the complexity of the calculation engine can be reduced. All eight redundant information sectors R can then be calculated using a single XOR operation with fifteen source operands and one destination operand. However, in this case, each operand spans eight consecutive sectors. The calculated redundancy information sector R is also stored in the external memory 108 consecutively. Therefore, the XORO value of all eight redundant information sectors R is calculated to be 16. The value of MBWC remains the same due to the different calculation of the redundant information sector R and is equal to 47 data blocks. Contrary to the above case, in the present case the calculation of each redundant information sector R is done block by block.

Fig. 7 shows a flowchart of a method for automatically creating an error correction coding scheme in order to reduce data loss. The error correction coding scheme created provides a balance between reducing the complexity of the computation engine 106 and memory bandwidth consumption (ie, XORO value and MBWC value). In the basic selection step, a parity check matrix H (for example, a parity check matrix H of the fourth type) is selected as a basic matrix. In the matrix setup step, the selected base matrix is modified so that it exhibits a given pattern of non-zero elements (eg, a regular pattern similar to a pattern sub-matrix according to IPC-8 (128, 120)). However, the given mode can be different according to requirements.

The method starts with step S1 as entry point. In step S2, said basic selection step is performed. In addition, the number r of redundant information sectors R and the number L of sectors in the section 204 are set. For example, the number r of redundant information sectors R is 8, and the number L of sectors in section 204 is 128, including eight redundant information sectors R and 120 data information sectors D. In step S3, the target matrix H' is set. In this instance, the target matrix H' is set as a square identity matrix having the number of rows and columns equal to the number r of redundant information sectors R. The identity matrix represents a sector R of redundant information. Furthermore, the randomized basic matrix H1 is set by randomly changing the order of the columns of the selected basic matrix (i.e., the selected parity check matrix H), and the first r (the number of redundant information sectors R) columns are removed , if the columns already represent the identity matrix (this is the case when the parity check matrix H of the fourth type is chosen as the fundamental matrix). In addition, a vector I including one element for each sector in the section 204 is set, ie, the number of elements of the vector I is equal to the number L of sectors. Set the first r elements of the vector I (the number of redundant information sectors R) to 1, and set the other elements to 0. In the vector I, all columns of the randomized basic matrix H1 that also appear in the target matrix H' are marked with 1.

In step S4, the value of the first variable i is set to the number r of redundant information sectors R plus 1. Correspondingly, in step S5, the value of the second variable j is set as the number r of redundant information sectors R plus 1. The first variable i represents the index of the current column in the target matrix H'. The second variable j represents the index of the current column in the randomized fundamental matrix H1. In step S6, it is checked whether the element of the vector I pointed to by the second variable j is equal to zero. If yes, i.e., the corresponding column of the randomized fundamental matrix H1 is not yet present in the target matrix H', then in step S7 the column of the randomized fundamental matrix H1 pointed to by the second variable j is appended to the target matrix H' The position pointed to by the first variable i in .

In step S8, it is checked whether the target matrix H' satisfies a given set of predetermined conditions. The predetermined conditions depend on the requirements for the resulting error correction coding scheme. This given set of predetermined conditions may eg comprise a target matrix H' exhibiting a given pattern of non-zero elements, eg elements on the main diagonal of the corresponding pattern sub-matrix are predominantly non-zero. This can be easily checked by eg masking the corresponding element and counting the number of non-zero elements covered by the mask. If the counted number of non-zero elements of each pattern sub-matrix exceeds a given threshold, the pattern may be considered to be present in the corresponding pattern sub-matrix of the target matrix H'.

Said set of predetermined conditions may also comprise a target matrix H' showing a given characteristic with respect to the error correction capability of the resulting error correction coding scheme. For example, to realize the ability to correct at most r (the number of redundant information sectors R) consecutive unreadable sectors in the segment 204, each column of the target matrix H' with the number of columns equal to the number r of redundant information sectors R The square sub-matrices should have a rank equal to the number r of redundant information sectors R.

If the target matrix H' satisfies all predetermined conditions in a given set of said predetermined conditions to a given extent, then in step S9, keep the column appended to the target matrix H' and set the current element of the vector I to 1 . Satisfying the predetermined condition to a given extent means, for example, that not all the different square sub-matrices of the target matrix H' should exhibit the given pattern, but at least a given number or percentage of the sub-matrices should exhibit the given pattern. In step S10, the value of the first variable i is incremented by 1. In step S11, it is checked whether the value of the first variable i is equal to the number L of sectors in the segment 204 or not. If yes, the method ends at step S12. Otherwise, the method continues in step S5.

If in step S8 the target matrix H' does not satisfy all predetermined conditions in the given set of said predetermined conditions to a given extent, the columns appended to the target matrix H' are deleted in step S13. Then in step S14 the value of the second variable j is increased to try to randomize the next column of the basic matrix H1. In step S15, it is checked whether the value of the second variable j is equal to the number L of sectors in the segment 204 or not. If not, the method continues at step S6. Otherwise, there are no more columns to try. In this case, the method continues at step S3, i.e. the target matrix H' and the vector I are reset and a new randomized fundamental matrix H1 is created from the fundamental matrix by randomly reordering the columns of the selected fundamental matrix . If the current element of vector I is not equal to 0 in step S6, the method also continues with step S14.

FIG. 8 shows a fifth type of parity check matrix H obtained as a resultant target matrix H' according to the method shown in FIG. 7 . This parity-check matrix H is such that the elements on the main diagonal of each square pattern sub-matrix are predominantly non-zero and has the ability to correct up to eight consecutive unreadable sectors in segment 204 when applied as an error-correcting coding scheme conditions of. In addition, other predetermined conditions are such that (if possible) the elements of the corresponding adjacent diagonal in each pattern sub-matrix are predominantly non-zero. The twelve pattern sub-matrices of the fifth type of parity check matrix H satisfy this predetermined condition.

By enabling the calculation engine 106 to perform operations on intermediate results stored in the internal memory 107 and overwriting the source operands with the calculation or intermediate results T, and by utilizing the non-zero elements of a given pattern (including the predominantly non-zero elements of the pattern sub-matrix) The main diagonal and adjacent diagonals), can further reduce the XORO value and MBWC value. Operations performed only on data stored in the internal memory 107 do not affect the MBWC value, since no data movement is used between the calculation engine 106 and the external memory 108 . These operations contribute 2 to the XORO value. Therefore, it is advantageous to calculate the redundant information sector R by using the intermediate result T stored in the internal memory 107 of the calculation engine 106 .

For the example shown in Figure 8, the following calculations can be performed. processing the corresponding information content of the data information sector D corresponding to the elements of the main diagonal of the corresponding pattern sub-matrix to obtain the first, second, third, fourth, fifth, sixth, seventh and eighth The intermediate results T1 , T2 , T3 , T4 , T5 , T6 , T7 , T8 together form the intermediate result T stored in the internal memory 107 . These results can be computed using a single XOR operation with an operand size of eight sectors as described above. This can be written as T = [T1, T2, T3, T4, T5, T6, T7, T8] = XOR(C9, C17, ... C97) where each operand has size 8, or as

T1=C9*C17*...*C97

T2＝C10＊C18＊...＊C98

T3=C11*C19*...*C99

T4=C12*C20*...*C100

T5＝C13*C21*...*C101

T6=C14*C22*...*C102

T7=C15*C23*...*C103

T8＝C16*C24*...*C104

For the second to thirteenth main diagonals, Cx represents the information content of the data information sector D in the xth sector of the segment 204, and "*" represents an exclusive OR operation. For this XOR operation, the XORO value is 12 and the MBWC value is 12x8 sectors (ie, 96 sectors). The intermediate result T can now be used to process elements on the corresponding adjacent diagonal:

T1 = XOR(T1, T2)

T2 = XOR(T2, T3)

T3 = XOR(T3, T4)

T4=XOR(T4, T5)

T5 = XOR(T5, T6)

T6=XOR(T6, T7)

T7 = XOR(T7, T8)

where each operand has size 1, or written as

T1＝T1＊T2＝C9＊C10＊C17＊C18＊...＊C97＊C98

T2＝T2＊T3＝C10＊C11＊C18＊C19＊...＊C98＊C99

T3＝T3＊T4＝C11＊C12＊C19＊C20＊...＊C99＊C100

T4＝T4＊T5＝C12＊C13＊C20＊C21＊...＊C100＊C101

T5＝T5＊T6＝C13＊C14＊C21＊C22＊...＊C101＊C102

T6＝T6＊T7＝C14＊C15＊C22＊C23＊...＊C102＊C103

T7=T7*T8=C15*C16*C23*C24*...*C103*C104.

For this step, an XORO value of 7x2 (ie, 14) is obtained, and a MBWC value of 0. like

The following deals with the fourteenth, fifteenth and sixteenth main diagonals:

T=[T1, T2, T3, T4, T5, T6, T7, T8]=XOR(T1, C105, C113, C121)

where each operand has size 8, or written as

T1=T1*C105*C113*C121

T2=T2*C106*C114*C122

T3=T3*C107*C115*C123

T4=T4*C108*C116*C124

T5=T5*C109*C117*C125

T6=T6*C110*C118*C126

T7=T7*C111*C119*C127

T8=T8*C112*C120*C128.

For this step, the XORO value is 3 and the MBWC value is 3x8 (ie, 24). The total XORO value after this step is 30 and the total MBWC value is 128 sectors or sixteen data blocks.

The remaining non-zero elements of the parity-check matrix H can then be processed individually on a sector-by-sector basis. There are 164 non-zero elements in the parity check matrix H that are not on one of the main diagonals or one of the adjacent diagonals.

Also, there are eight elements that are zero on the main or adjacent diagonals. In total they require another 172 XOR's with operands the size of one sector. This results in an additional XORO value of 172 and an MBWC value of 172 sectors. Therefore, for computing the information content of the redundancy set, the total XORO value is 202 and the MBWC value is 300 sectors or 37.5 data blocks. Since the fifteen blocks of user data E are moved from the host to the external memory 108 and the fifteen blocks of user data E and the resulting calculated on-disk redundancy data S are moved to at least one storage unit 100, additional Fifteen plus sixteen data blocks contributed to the MBWC value. The total MBWC value is thus approximately 69 data blocks.

To place redundant information sector R approximately in the middle of segment 204 as described above, the columns of parity check matrix H may be cyclically shifted. For example, the original columns C1 through C64 of an embodiment of the parity check matrix H become columns C65 through C128, and the original columns C65 through C128 become columns C1 through C64.

In this way, the redundant information sector R is moved from columns C1 to C8 to columns C65 to C72.

For the parity-check matrix H embodiment described, it can be verified that cyclic shifting of this column does not change the ability to correct up to eight consecutive unreadable sectors in segment 204 .

FIG. 9 shows a flowchart of a method for reducing data loss that may be implemented within hardware in device 103 . The method can also be implemented as a computer program including program instructions executable by a computer. The device 103 may comprise a computer for executing program instructions of said computer program. Alternatively, the computer program may be part of the computer system's operating system or basic input/output system. A computer-readable medium containing program instructions executable by the device 103 or a computer system may be provided. The computer readable medium may be, for example, a CD-ROM, a flash memory card, a hard disk, or any other suitable computer readable medium.

The method shown in FIG. 9 utilizes the error correction coding scheme created by the method shown in FIG. 7 and performs the calculations described above for FIG. 8 . The method starts at step S20. In step S21, a first calculation step is performed by processing the information content of the data information sector D on the main diagonal of the pattern sub-matrix as described above to calculate the intermediate result T of the redundant information sector R. In step S22, as described above, the information content of the data information sector D on the adjacent diagonal of the pattern sub-matrix is processed by using the intermediate result T to overwrite the previously calculated intermediate result T. In step S23, the information content of the redundant information sector R is calculated from the intermediate result T (eg, by processing the remaining non-zero elements of the parity check matrix H as described above). The method ends at step S24.

Fig. 10 shows a graph with minimum Hamming distance dmin, burst erasure recovery (i.e., error correction capability to correct consecutive unreadable sectors), number of non-zero elements nz in parity check matrix H, parity check matrix H Table of corresponding XORO values and MBWC values for third, fourth, fifth and first types. In the table, the third type of parity-check matrix H is labeled "Extended Hamming code", the fourth type is labeled "SD3" (most sparse distance 3), and the fifth type is labeled "OSD3" (optimized minimum distance 3). Sparse distance 3), and the first type is labeled "IPC-8".

The embodiments explained above are based on sectors as information entities. Alternatively, an information entity may also represent bits, bytes or any other suitable information entity. Said redundant information sector R and data information sector D represent specific embodiments and can be seen more generally as redundant information entity R and data information entity D respectively. Furthermore, reducing data loss due to media errors on storage unit 100 is only one application among many. Losses of data transmitted or received over a radio channel or cable may likewise be reduced, for example, by applying the error correction coding scheme provided above.

It will be understood that the present invention has been described by way of example only and that modifications of detail may be made within the scope of the invention.

Each feature disclosed in the description and (where appropriate) claims and drawings may be provided independently or in any appropriate combination.

label

100 storage units

101 disk

102 read/write heads

103 equipment

104 host interface

105 controller

106 computing engine

107 internal memory

108 external memory

200 array

202 strips

203 articles

204 paragraphs

205 first request

206 second request

D data information sector/entity

dmin minimum Hamming distance

User data

H parity check matrix

H' target matrix

Fundamental matrix for H1 randomization

HDD hard disk drive

I vector

i first variable

j second variable

The number of sectors in the L segment

n data information sector number

nzNumber of non-zero elements

PRAID parity data

r Number of redundant information sectors

R redundant information sector/entity

Redundant data in S disk

Sx steps

T intermediate result

Tx intermediate results

Claims (13)

1. A method for creating an error correction coding scheme to reduce data loss in data storage, said data comprising at least two redundancies associated with a given data set having at least two data information entities (D) Given a redundant set of information entities (R), the information content of said redundant set is calculated from the information content of said data set, said method comprising the steps of: a basic selection step (S2) for selecting a basic coding scheme represented by a basic matrix, wherein each redundant information entity (R) is represented by a row, and each information entity is represented by a column; and a matrix setting step (S3) for setting a target matrix (H') having a subset of the columns of the basic matrix and for changing the order of columns according to the basic matrix until the target matrix (H') The given number or given percentage of submatrices satisfy the given pattern of nonzero elements. 2. A method as claimed in claim 1, wherein said given pattern of non-zero elements is chosen to comprise the main diagonal of a square pattern sub-matrix of said target matrix (H'), said main diagonal Lines have predominantly non-zero elements, said target matrix (H') has a number of rows and columns equal to the number (r) of redundant information entities (R) in said redundancy set. 3. A method as claimed in claim 2, wherein said given pattern of non-zero elements is selected to also include said main diagonal with said square pattern submatrix of said target matrix (H') adjacently arranged adjacent diagonals, the elements of which are chosen to be predominantly non-zero. 4. A method as claimed in any preceding claim, wherein the fundamental matrix is selected as the number of data information entities (D) in the data set for a given Hamming distance (dmin) of the basic coding scheme (n) and the number (r) of redundant information entities (R) in said redundant set, having the least number of non-zero elements (nz). 5. The method according to any one of claims 1-3, wherein, in the matrix setting step (S3), the order of the columns is changed until the number of columns matches the redundant information entity in the redundant set (R) each row number of the said target matrix (H ') that number (r) is equal is the rank of the square submatrix of the redundant information entity number (r) in said redundant set and said redundant set The number (r) of redundant information entities (R) is equal. 6. The method according to any one of claims 1-3, wherein the error correction coding scheme created is based on calculating respectively all data information represented by non-zero elements in each row of the target matrix (H') XOR of the information content of entity (D). 7. A method as claimed in claim 6, wherein the basic encoding scheme is based on one of: Hamming codes or extended Hamming codes. 8. A method for reducing data loss in data storage comprising at least two redundant information entities (R) associated with a given data set having at least two data information entities (D) Given a redundant set, the information content of the redundant set is computed from the information content of the data set by applying an error correction coding scheme represented by a parity check matrix (H), where each A redundant information entity (R) is represented by a row, and each information entity of said data is represented by a column, and at least two square sub-matrices of said parity-check matrix (H) have diagonal elements with predominantly non-zero elements line and have the number of rows and columns equal to the number (r) of redundant information entities (R) in said redundancy set, and represent consecutively placed data information entities (D) of said data set, said method comprising : a first calculation step for calculating an intermediate result (T) of said redundant information entities (R) by processing said data information entities (D) on said at least two main diagonals; and A second calculation step for calculating the information content of said redundant information entity (R) based on said intermediate result (T). 9. A method as claimed in claim 8, wherein at least one square sub-matrix of said parity-check matrix (H) whose elements on said main diagonal are predominantly non-zero also has adjacent elements whose elements are predominantly non-zero diagonal, and said second computing step includes processing data information entities (D) on corresponding adjacent diagonals with said intermediate result (T). 10. The method according to any one of claims 8 or 9, wherein the information content of each redundant information entity (R) in the redundancy set is calculated as defined by the parity check matrix (H ), the non-zero elements in the row corresponding to the redundant information entity represent the exclusive OR of the information content of all data information entities (D) in the data set. 11. An apparatus for reducing data loss in data storage comprising at least two redundant information entities (R) associated with a given data set having at least two data information entities (D) Given a redundant set, the information content of the redundant set is computed from the information content of the data set by applying an error correction coding scheme represented by a parity check matrix (H), where each A redundant information entity (R) is represented by a row, and each information entity of said data is represented by a column, and at least two square sub-matrices of said parity-check matrix (H) have diagonal elements with predominantly non-zero elements line and have the number of rows and columns equal to the number (r) of redundant information entities (R) in the redundancy set, and represent the continuously placed data information entities (D) of the data set, the device executes Do the following: computing intermediate results (T) of said redundant information entities (R) by processing said data information entities (D) on said at least two main diagonals; and The information content of said redundant information entity (R) is calculated from said intermediate result (T). 12. A system for protecting data stored on at least one storage unit (100) against uncorrectable media errors, said system comprising: A device (103) as claimed in claim 11; at least one storage unit (100); and Each information entity represents a sector on said at least one storage unit (100). 13. The system as claimed in claim 12, said system configured as a redundant array of independent storage units (100).

Images