CN111782439B - Double-disk circulation verification method based on horizontal coding - Google Patents

Abstract

The invention discloses a double-disk circulation checking method based on horizontal coding, which comprises the following steps that the layout of the horizontal coding consists of N disks, wherein N-2 data disks and 2 checking disks are arranged; all the magnetic disks are striped, the data blocks and the check blocks which are positioned in the same row form one stripe, and m stripes are formed in a conformal mode. Constructing a mapping table in the storage system, wherein corresponding values in the mapping table represent positions of check values in strips with the same offset; setting the same initial value for all marks in the mapping table, wherein the initial value represents the current check value and is stored in a second check disk; when a write request arrives, dividing write request data into a plurality of parts according to the size of a data block, performing data write operation by taking a stripe as a unit, generating a check value and storing the check value into a corresponding check disk; after each new check value is stored, the mark corresponding to the current strip in the mapping table is inverted, and the mark is updated; after all the stripes are written, all the final check values are merged.

Description

A Double Disk Cyclic Verification Method Based on Horizontal Coding

technical field

The invention belongs to the field of data storage, in particular to a horizontal encoding-based double-disk cyclic verification method.

Background technique

With the rapid development of the Internet and the advent of the era of big data, network data information is showing an explosive growth trend. The efficient storage, management and use of data has become an urgent problem to be solved by the Internet and related industries. The network storage system performance poses a huge challenge. Nowadays, network storage systems have been greatly improved in terms of storage capacity, data availability, and I/O performance, and network storage has been more and more widely used in various industries. Currently, there are mainly three mainstream network storage technologies: Directed Attached Storage, Network Attached Storage, and Storage Area Network, each of which has its own applicable fields.

The rapid development of storage requirements has made the industry put forward higher requirements for disk capacity and energy saving. For this reason, Chen P M, Lee E K, Gibson GA and others proposed the RAID technology "RAID: high-performance, reliable secondary storage [J ]. Acm Computing Surveys, 1994, 26(2): 145-185". However, with the development of big data, the traditional RAID technology has only one parity disk, which has inherent shortcomings in frequent disk read and write, and is not suitable for the storage environment where specific data is frequently accessed. When the data is frequently read and written to the data disk, the verification disk needs to be verified at all times, and the read and write speed of the verification disk will become the bottleneck of data storage, especially in interactive applications, online games, etc. system, this problem is particularly serious.

Contents of the invention

Aiming at the deficiencies of the prior art, the technical problem to be solved by the present invention is to provide a double disk cyclic verification method based on horizontal coding.

The technical solution of the present invention to solve the technical problem is to provide a double-disk cyclic verification method based on horizontal encoding, which is characterized in that the method includes the following steps:

(1) The layout of horizontal coding consists of N disks, including N-2 data disks and 2 check disks; N>2; each data disk is divided into m data blocks of equal size; each check disk The check disk is divided into m check blocks of the same size as the data block; all disks are striped, and the data blocks and check blocks in the same row form a stripe, forming a total of m stripes; between data disks Work in parallel, work sequentially between stripes; m≥1;

(2) Construct a mapping table in the storage system based on the layout, and the corresponding value in the mapping table indicates the location of the check value in the strip with the same offset; set the same initial value for all the marks in the mapping table, the The initial value represents the current calibration value stored in the second calibration disk;

When the write request comes, the write request data is divided into several parts according to the size of the data block, and the data write operation is performed in units of stripes, and the check value is generated and stored in the corresponding check disk; each time a new check is stored value, the flag corresponding to the current stripe in the mapping table must be reversed, and the flag should be updated; until all stripes are filled;

(3) After all stripes are full, merge all final check values.

Compared with the prior art, the present invention has the beneficial effects of:

1. Improve the data read and write rate. Since the traditional RAID architecture only includes a single check disk, when writing new data, it is necessary to read the old check value and old data, and then write the generated new data into the check disk, which will greatly increase the The delay caused by checking the disk. This method adds a verification disk on the basis of traditional RAID, adopts double verification disk operation, one verification disk is used for reading verification data, and the other verification disk is used for writing verification data, and the work is divided into tasks, effectively Solved the read and write bottleneck of the verification disk.

2. The double check disk operation with division of labor for reading and writing is used, which greatly improves the performance of the storage system.

3. The mapping table takes up less space on the disk, which effectively reduces the impact of disk merging for verification.

4. When a certain disk fails, XOR is performed according to other data blocks and parity blocks in the same stripe in the entire RAID disk group to ensure the reliability of the storage system.

Description of drawings

FIG. 1 is a schematic diagram of a dual-disk cyclic verification process in Embodiment 1 of the present invention.

FIG. 2 is a schematic diagram of the initial value of the mapping table flag in Embodiment 1 of the present invention.

Fig. 3 is a schematic diagram of generation of a local check value in a check block P ₀ according to Embodiment 1 of the present invention.

Fig. 4 is a schematic diagram of generating a local check value in a check block P ₀ ′ according to Embodiment 1 of the present invention.

Fig. 5 is a schematic diagram of generating a final check value in the check block P ₀ according to Embodiment 1 of the present invention.

Fig. 6 is a schematic diagram of generation of the final check value in the check block _P1 and the partial check value in _P2 according to Embodiment 1 of the present invention.

FIG. 7 is a schematic diagram of markings of the mapping table generated after four write requests according to Embodiment 1 of the present invention.

Detailed ways

Specific examples of the present invention are given below. The specific embodiments are only used to further describe the present invention in detail, and do not limit the protection scope of the claims of the present application.

The invention provides a kind of double-disk cyclic verification method (abbreviation method) based on horizontal coding, it is characterized in that the method comprises the following steps:

(1) The layout of the horizontal encoding is composed of N disks, including N-2 data disks and 2 check disks; each data disk is divided into m data blocks of equal size for storing user data; A parity disk is divided into m parity blocks of the same size as the data block, which are used to store parity data; all disks are striped, and the data blocks and parity blocks in the same row form a strip, forming a total of m stripes; data disks work in parallel, and stripes work sequentially; N>2; m≥1;

(2) Construct a mapping table in the storage system based on this layout, and the corresponding value in the mapping table indicates the position of the check value in the strip with the same offset; set the same initial value for all the marks in the mapping table, the initial The value is set to 0 or 1, and the initial value represents that the current calibration value is stored in the second calibration disk;

When the write request comes, the write request data is divided into several parts according to the size of the data block, and the data write operation is performed in units of stripes, and the check value is generated and stored in the corresponding check disk; each time a new check is stored value, the flag corresponding to the current stripe in the mapping table must be reversed, and the flag should be updated; until all stripes are filled;

(3) After all stripes are full, merge all final check values.

Preferably, step 2) is specifically: constructing a mapping table in the storage system based on the layout, the corresponding value in the mapping table represents the location of the check value in the strip of the same offset; The same initial value, the initial value is set to 0 or 1, the initial value represents the current calibration value stored in the second calibration disk;

When the first write request arrives, the write request data is divided into several parts according to the size of the data block, and the divided write request data is written in parallel from the first data block of the first stripe, and the newly written data Perform XOR with the initial value of the storage system to generate a check value, store it in the first check disk, and reverse the mark corresponding to the current stripe in the mapping table;

When the second write request arrives, judge whether the current stripe is full; if it is not full, divide the write request data into several parts according to the size of the data block, and write the divided write request data corresponding to the previous write request data. In adjacent free data blocks, the newly written data and the check value already stored in the first check disk are XORed with each other to generate a new check value, which is stored in the second check disk, and mapped Invert the mark corresponding to the current stripe in the table; if it is full, start writing from the first data block of the next stripe, and XOR the newly written data with the initial value of the storage system to generate the stripe check value, and store it in the first check disk, and reverse the mark corresponding to the current stripe in the mapping table;

When the third write request arrives, judge whether the current stripe is full; if it is not full, divide the write request data into several parts according to the size of the data block, and write the divided write request data corresponding to the previous write request data. In adjacent free data blocks, the newly written data and the check value stored in the second check disk are XORed with each other to generate a new check value, and the first check value in the first write request The check value in the disk is replaced with a new check value, and at the same time, the mark corresponding to the current stripe in the mapping table is reversed; if it is full, write from the first data block of the next stripe, and the new The written data is XORed with the initial value of the storage system to generate the verification value of the stripe, and stored in the first verification disk, and at the same time, the flag corresponding to the current stripe in the mapping table is reversed;

Repeat the above steps until all stripes are filled.

Preferably, step 3) is specifically: according to the tag updated in the mapping table, determine the storage location of the final check value of each stripe; finally, merge all the final check values of all the stripes into the same check disk , and then remove another check disk.

Preferably, in step 3), all the mapping table marks are summed, and if the summation result is greater than 1/2 of the number m of marks, the final check value is merged into the second check disk, otherwise merged to the first check disk.

Preferably, when the disk is damaged, the original data in the damaged disk is lost. At this time, it is necessary to replace the damaged disk with a new disk and perform data recovery. The specific method of data recovery is: read the data of the undamaged data disk and neutralize the undamaged The check value of the check disk, the data in the same stripe and the check value are XORed with each other, and the result obtained is recovery data, and the recovery data is stored in a new replacement disk.

Example 1

(1) As shown in Figure 1, there are 6 disks for horizontal encoding, including 4 data disks (D ₀ ~ D ₃ ) and 2 parity disks (P and P'), and each data disk is divided into m equal-sized Each check disk is divided into m check blocks of the same size as the data block. For ease of understanding, the block size is set to 64KB. The data block and check block in the same row form a stripe, a total of m stripes (Stripe ₀ ~Stripe _m-1 );

The initial value of the storage system in this embodiment is 0, and the initial value of all marks in the mapping table is set to 0 (as shown in Figure 2), 0 represents that the current check value is in P', and 1 represents that the current check value is in P ;

此时，将映射表中条带Stripe₀对应的标记取反，更新为1；(2) The first write request arrives, as shown in Figure 3, the data size is 128KB, and the data size is larger than the block size. Therefore, the data is divided into two parts and written into data blocks B _0,0 and B _1,0 , write the verification value generated by the exclusive OR of the data in B _0,0 and B _1,0 and the initial value of the storage system to the verification block P ₀ of the verification disk P

At this point, invert the flag corresponding to Stripe ₀ in the mapping table and update it to 1;

此时，将映射表中条带Stripe₀对应的标记取反，更新为0；The second write request comes, as shown in Figure 4, the data size is 54KB, the data size is smaller than the block size, the data is written to the data block B _2,0 , and the data in B _2,0 and P ₀ are mutually XORed to generate Write the verification value of the verification block P ₀ ' of the verification disk P'

At this point, invert the flag corresponding to Stripe ₀ in the mapping table and update it to 0;

原校验值删除，替换成新校验值；此时，将映射表中条带Stripe₀对应的标记取反，更新为1；The third write request comes, as shown in Figure 5, the data block size is 24KB, the data size is smaller than the block size, the data is written into the data block B _3,0 , and the data in B _3,0 and P ₀ ' are mutually exclusive Or write the generated verification value into the verification block P of the verification disk P ₀

Delete the original check value and replace it with the new check value; at this time, invert the mark corresponding to Stripe ₀ in the mapping table and update it to 1;

再把B_0,2、B_1,2与存储系统的初始值相互异或生成的校验值写入校验盘P的校验块P₂/>

此时，将映射表中条带Stripe₁对应的标记取反，更新为1；将映射表中条带Stripe₂对应的标记取反，更新为1；The fourth write request comes, as shown in Figure 6, the data block size is 380KB, and the data size is larger than the block size. Therefore, the data is divided into 6 parts and written to data blocks B _0,1 , B _1,1 , and B respectively. _2,1 , B _3,1 , B _0,2 and B _1,2 , B _0,1 , B _1,1 , B _2,1 , B _3,1 and the initial value of the storage system are mutually exclusive or generated Write the verification value of the verification block P ₁ of the verification disk P

Then write the verification value generated by XOR of B _0,2 , B _1,2 and the initial value of the storage system into the verification block P ₂ /> of the verification disk P

At this point, invert the flag corresponding to Stripe ₁ in the mapping table and update it to 1; invert the flag corresponding to Stripe ₂ in the mapping table and update it to 1;

Repeat the above steps for other strips;

(3) After all stripes are filled, the final check value is merged; according to the tag updated in the mapping table, determine the storage location of the final check value of each stripe, wherein according to Fig. 7, the stripe Stripe ₀ , Stripe The marks corresponding to ₁ and Stripe ₂ are both 1, therefore, the final check values are stored in P ₀ , P ₁ and P ₂ ; finally, all the final check values of all stripes are merged into the same check disk , and then remove another check disk.

并将计算得到的B_2,0数据写入数据盘D₂'的数据块B_2,0中。数据块B_2,1～B_2,n-1的数据恢复方法相同。Assuming that the data disk _D2 fails or is damaged during the storage process, and the original data in _D2 is lost, at this time, replace the damaged disk _D2 with a new disk _D2 ' and perform data recovery. The specific method of data recovery is: read The data in B _0,0 , B _1,0 , B _3,0 and the local check value in the check block P ₀ ', the data in B _2,0 is composed of the data _in B 0,0 and the data in B _1,0 The data in B _3,0 and the local check value in the check block P ₀ ' are XORed to obtain

And write the calculated _B2,0 data into the data block _B2,0 of the data disk _D2 '. The data restoration method of data blocks B _2,1 to B _2,n-1 is the same.

What is not mentioned in the present invention is applicable to the prior art.

Claims (5)

1. A double-disk cyclic verification method based on horizontal encoding, characterized in that the method may further comprise the steps: (1) The layout of horizontal coding consists of N disks, including N-2 data disks and 2 check disks; N>2; each data disk is divided into m data blocks of equal size; each check disk The check disk is divided into m check blocks of the same size as the data block; all disks are striped, and the data blocks and check blocks in the same row form a stripe, forming a total of m stripes; between data disks Work in parallel, work sequentially between stripes; m≥1; (2) Construct a mapping table in the storage system based on the layout, and the corresponding value in the mapping table indicates the location of the check value in the strip with the same offset; set the same initial value for all the marks in the mapping table, the The initial value represents the current calibration value stored in the second calibration disk; When the write request comes, the write request data is divided into several parts according to the size of the data block, and the data write operation is performed in units of stripes, and the check value is generated and stored in the corresponding check disk; each time a new check is stored value, the flag corresponding to the current stripe in the mapping table must be reversed, and the flag should be updated; until all stripes are filled; (3) After all stripes are full, merge all final check values. 2. the double-disk cyclic verification method based on horizontal coding according to claim 1, is characterized in that step 2) is specifically: build a mapping table in the storage system based on this layout, corresponding value in the mapping table represents the same The position of the check value in the offset strip; set the same initial value for all the marks in the mapping table, the initial value is set to 0 or 1, and the initial value represents the current check value stored in the second check disk ; When the first write request arrives, the write request data is divided into several parts according to the size of the data block, and the divided write request data is written in parallel from the first data block of the first stripe, and the newly written data Perform XOR with the initial value of the storage system to generate a check value, store it in the first check disk, and reverse the mark corresponding to the current stripe in the mapping table; When the second write request arrives, judge whether the current stripe is full; if it is not full, divide the write request data into several parts according to the size of the data block, and write the divided write request data corresponding to the previous write request data. In adjacent free data blocks, the newly written data and the check value already stored in the first check disk are XORed with each other to generate a new check value, which is stored in the second check disk, and mapped Invert the mark corresponding to the current stripe in the table; if it is full, start writing from the first data block of the next stripe, and XOR the newly written data with the initial value of the storage system to generate the stripe check value, and store it in the first check disk, and reverse the mark corresponding to the current stripe in the mapping table; When the third write request arrives, judge whether the current stripe is full; if it is not full, divide the write request data into several parts according to the size of the data block, and write the divided write request data corresponding to the previous write request data. In adjacent free data blocks, the newly written data and the check value stored in the second check disk are XORed with each other to generate a new check value, and the first check value in the first write request The check value in the disk is replaced with a new check value, and at the same time, the mark corresponding to the current stripe in the mapping table is reversed; if it is full, write from the first data block of the next stripe, and the new The written data is XORed with the initial value of the storage system to generate the verification value of the stripe, and stored in the first verification disk, and at the same time, the flag corresponding to the current stripe in the mapping table is reversed; Repeat the above steps until all stripes are filled. 3. the double-disc cyclic verification method based on horizontal coding according to claim 1, is characterized in that step 3) is specifically: according to the mark that mapping table updates, determine the storage location of the final verification value of each strip; Finally, merge all final check values of all stripes into the same check disk, and then remove another check disk. 4. the double-disk cyclic verification method based on horizontal encoding according to claim 1, is characterized in that in step 3), all mapping table marks are summed, if the summation result is greater than 1/ of the number of marks m 2, merge the final check value into the second check disk, otherwise merge it into the first check disk. 5. The double-disk cyclic verification method based on horizontal encoding according to claim 1, characterized in that when the disk is damaged, the original data in the damaged disk is lost, and now it is necessary to replace the damaged disk with a new disk and perform data recovery , the specific method of data recovery is: read the data in the undamaged data disk and the check value of the undamaged check disk, the data and the check value in the same stripe are XORed with each other, and the result obtained is the restored data, and the The recovery data is stored to a new replacement disk.

Images