CN106293526B - A kind of expandable method and system of three disks fault-tolerant array - Google Patents
A kind of expandable method and system of three disks fault-tolerant array Download PDFInfo
- Publication number
- CN106293526B CN106293526B CN201610637554.1A CN201610637554A CN106293526B CN 106293526 B CN106293526 B CN 106293526B CN 201610637554 A CN201610637554 A CN 201610637554A CN 106293526 B CN106293526 B CN 106293526B
- Authority
- CN
- China
- Prior art keywords
- band
- block
- disk
- data block
- check
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
- 238000000034 method Methods 0.000 title claims abstract description 60
- 238000013508 migration Methods 0.000 claims abstract description 37
- 230000005012 migration Effects 0.000 claims abstract description 37
- 238000003491 array Methods 0.000 claims abstract description 36
- 230000008569 process Effects 0.000 claims abstract description 20
- 238000012795 verification Methods 0.000 claims description 58
- 230000004048 modification Effects 0.000 claims description 19
- 238000012986 modification Methods 0.000 claims description 19
- 239000012141 concentrate Substances 0.000 claims description 10
- 230000008859 change Effects 0.000 claims description 6
- 230000007704 transition Effects 0.000 claims description 4
- 238000004458 analytical method Methods 0.000 claims 1
- 230000009467 reduction Effects 0.000 description 4
- 238000012360 testing method Methods 0.000 description 4
- 230000000694 effects Effects 0.000 description 3
- 238000013507 mapping Methods 0.000 description 3
- 238000010276 construction Methods 0.000 description 2
- 238000010586 diagram Methods 0.000 description 2
- 229910003460 diamond Inorganic materials 0.000 description 2
- 239000010432 diamond Substances 0.000 description 2
- 241001269238 Data Species 0.000 description 1
- 230000008901 benefit Effects 0.000 description 1
- 238000013500 data storage Methods 0.000 description 1
- 230000007812 deficiency Effects 0.000 description 1
- 238000011161 development Methods 0.000 description 1
- 238000005516 engineering process Methods 0.000 description 1
- 239000000203 mixture Substances 0.000 description 1
- 230000008439 repair process Effects 0.000 description 1
Classifications
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
- G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
- G06F3/0601—Interfaces specially adapted for storage systems
- G06F3/0602—Interfaces specially adapted for storage systems specifically adapted to achieve a particular effect
- G06F3/061—Improving I/O performance
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
- G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
- G06F3/0601—Interfaces specially adapted for storage systems
- G06F3/0628—Interfaces specially adapted for storage systems making use of a particular technique
- G06F3/0638—Organizing or formatting or addressing of data
- G06F3/064—Management of blocks
-
- G—PHYSICS
- G06—COMPUTING; CALCULATING OR COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F3/00—Input arrangements for transferring data to be processed into a form capable of being handled by the computer; Output arrangements for transferring data from processing unit to output unit, e.g. interface arrangements
- G06F3/06—Digital input from, or digital output to, record carriers, e.g. RAID, emulated record carriers or networked record carriers
- G06F3/0601—Interfaces specially adapted for storage systems
- G06F3/0668—Interfaces specially adapted for storage systems adopting a particular infrastructure
- G06F3/0671—In-line storage system
- G06F3/0683—Plurality of storage devices
- G06F3/0689—Disk arrays, e.g. RAID, JBOD
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- Human Computer Interaction (AREA)
- Physics & Mathematics (AREA)
- General Engineering & Computer Science (AREA)
- General Physics & Mathematics (AREA)
- Techniques For Improving Reliability Of Storages (AREA)
- Detection And Correction Of Errors (AREA)
Abstract
The invention discloses the expandable methods and system of a kind of three disk fault-tolerant arrays, and this method comprises the following steps: the preparation stage, and relevant parameter is collected from storage system, calculate necessary parameter for next two stages；Migration phase selects a part of band as band collection, and according to parameter calculated in the preparation stage, some data lines are selected in each band, for migrating into the disk newly added；Empty band polymerize by merging phase, by the invention it is possible to ensure that data distribution is balanced after extension, the I/O expense in expansion process is smaller.
Description
Technical field
The present invention relates to big datas and cloud storage field, more particularly to a kind of three disk fault-tolerant arrays based on xor operation
Expandable method and system.
Background technique
In large-scale data center, for mass data storage in bulk redundancy disk, user can be with concurrent access number therein
According to.These redundancy magnetic disks are referred to as redundant array of independent disks (RAID).Recently, three disk fault-tolerant arrays (3DFTs) are in large-scale number
According to popular in center, because they can provide high reliability and inexpensive expense.
In past 20 years, scientist proposes many correcting and eleting codes to achieve the effect that three disks are fault-tolerant, including maximum distance
Separable code (MDS) and non-MDS coding.MDS is encoded in the case where giving a certain number of redundancies, can be provided maximum data and be protected
Shield.Some codings, if STAR encode, Triple-Star coding, TIP-Code coding and EH-Code coding coding mode by
Three kinds of different verification (row verification, tiltedly verification, reversed tiltedly verification) compositions, to provide high reliability.Non-MDS coding due to
Part storage efficiency is sacrificed, higher performance or reliability can be gone all out with.
Recently, with the development of cloud computing, the scalability of disk array is by extensive discussions.This is because:
1, increasing additional disk in the three disk fault-tolerant arrays encoded based on MDS can be improved storage efficiency, reduce at
This cost.
2, there is new plus disk disk array that can provide higher I/O handling capacity and bigger capacity.More numbers
According to that can concurrently access, reduce I/O expense, improves the performance of whole system.
3, three disk fault-tolerant arrays are widely used in large-scale data center, are because it has high reliability.Reliability exists
Play important role in large-scale data center.
Unfortunately, existing extended method is poorly suited for use in the three disk fault-tolerant arrays based on xor operation.One
A little method (such as Round-Robin (RR) and Semi-RR) has been proved to, in expansion process, they are in Data Migration and school
Running repair produces a large amount of I/O expense on changing.Semi-RR also suffers from unbalanced problem of data distribution after extension simultaneously.Its
His method in order under the layout of this complexity of correcting and eleting codes equilibrium data distribution take a large amount of I/O, such as SDM and RS6.SDM
A part of band is sacrificed, so that concentrating in a band, data distribution is balanced.It can handle by two kinds of different checks
Coding made of coding (but there are three types of different verifications in the three disk fault-tolerant encodings based on xor operation), this will lead to verification
Modification and I/O expense are very high.RS6 is a kind of RAID-6 extended method for RDP coding, it will lead to additional Data Migration
Expense.Under some codings, after RS6 is to coding extension, so that data distribution is unbalanced, as STAR coding and TIP-Code are compiled
Code.Some other methods, such as FastScale, GSR and CRAID, they are for RAID-0 or RAID-5 array, Bu Nengyun
Use three disk fault-tolerant arrays.
As it can be seen that therefore the extension that existing extended method is not suitable for the three disk fault-tolerant arrays based on xor operation has in fact
Necessity proposes a kind of technological means, to solve the above problems.
Summary of the invention
In order to overcome the deficiencies of the above existing technologies, purpose of the present invention is to provide a kind of three disk fault-tolerant arrays can
Extended method and system can apply on the three disk fault-tolerant arrays based on xor operation, so that the data distribution after extension
It is balanced.
In view of the above and other objects, the present invention proposes a kind of expandable method of three disk fault-tolerant arrays, including walk as follows
It is rapid:
Preparation stage collects relevant parameter from storage system, calculates necessary parameter for next two stages；
Migration phase selects a part of band as band collection, and according to parameter calculated in the preparation stage, every
Some data lines are selected in a band, for migrating into the disk newly added；
Merging phase, by the tape merge with null or empty data block.
Further, in the preparation stage, according to the layout encoded of MDS in three disk fault-tolerant arrays and its configuration parameter, meter
Calculate ns, neAnd L, it is supplied to two later stages, wherein nsIndicate the band number that a band is concentrated, neIt indicates at this
Band concentrates the total quantity for being arranged to null, and L is indicated in a band, the minimum number of null.
Further, migration phase includes the following steps:
Band collection is read in and is cached；
According to the minimal modifications amount of check block, suitable data block is migrated；
Update and recalculate check block.
Further, the data block of entire band collection and check block are disposably read in the caching X positioned at memory, band collection
In be selected null be placed into caching Y in.
Further, the minimal modifications amount according to check block, the step of migrating to suitable data block, is to row
After verification, tiltedly verification, the relationship reversely tiltedly verified are analyzed, change the position of some data blocks, so that these blocks still exist
In their original verification chains.
Further, it the update and recalculates in check block step, by calculating raw line check block and Xin Jia
The exclusive or and Lai Geng newline check block of data block.
Further, described to update and recalculate in check block step, it updates tiltedly verification and needs to calculate original oblique verification
Block, the exclusive or of data block and corresponding updated row check block in related null and.
Further, described to update and recalculate in check block step, it is recalculated according to the coding formula of correcting and eleting codes
Reversed oblique check block.
Further, the merging phase includes the following steps:
Determine which band needs is merged or is split, so that overall computing cost is minimum；
Merge band between band concentration or band collection.
In order to achieve the above objectives, the present invention also provides a kind of expansible systems of three disk fault-tolerant arrays, comprising:
Preparatory unit collects relevant parameter from storage system, provides for migration units and combining unit necessary
Parameter；
Migration units select a part of band as band collection, and according to parameter calculated in the stage one, each
Some data lines are selected in band, for migrating into the disk newly added, in transition process, the movement of data block is by difference
What the association between verification was determined；
Combining unit, for that will have the tape merge of null or empty data block.
Compared with prior art, a kind of expandable method of three disk fault-tolerant arrays of the present invention and system are according to different check
Relevance selects suitable data block to be migrated, thus reach the quantity of the smallest Data Migration and verification modification, meanwhile,
To there is the present invention band of empty data block to merge, so that the I/O cost reduction of verification modification, therefore the present invention can be true
Data distribution is balanced after conservation exhibition, and the I/O expense in expansion process is smaller.
Detailed description of the invention
Fig. 1 is a kind of step flow chart of the expandable method of three disk fault-tolerant arrays of the present invention；
Fig. 2 is the overall construction drawing of this method；
The example of Fig. 3 this method indicates to extend the band 0 that front/rear band is concentrated；
The example of Fig. 4 this method indicates to extend the band 1 that front/rear band is concentrated；
The example of Fig. 5 this method indicates to extend the band 2 that front/rear band is concentrated；
The example of Fig. 6 this method indicates the merging process for the band 0 and 1 that band is concentrated；
Fig. 7 is a kind of system architecture diagram of the expansible system of three disk fault-tolerant arrays of the present invention.
Specific embodiment
Below by way of specific specific example and embodiments of the present invention are described with reference to the drawings, those skilled in the art can
Understand further advantage and effect of the invention easily by content disclosed in the present specification.The present invention can also pass through other differences
Specific example implemented or applied, details in this specification can also be based on different perspectives and applications, without departing substantially from
Various modifications and change are carried out under spirit of the invention.
Fig. 1 is a kind of step flow chart of the expandable method of three disk fault-tolerant arrays of the present invention.As shown in Figure 1, of the invention
A kind of expandable method of three disks fault-tolerant array, includes the following steps:
Step 101, stage one, i.e. preparation stage: collecting relevant parameter from storage system, is next two ranks
Section calculates necessary parameter.
Step 102, stage two, i.e. migration phase: selecting a part of band as band collection, and is fallen into a trap according to the stage one
The parameter of calculating selects some data lines in each band, for migrating into the disk newly added.In transition process, number
Movement according to block is determined by the association between different check, this can guarantee balanced data distribution.
Step 103, stage three, i.e. merging phase: by the tape merge with null or empty data block, verification modification is reduced
Quantity and I/O expense.
Fig. 2 is a kind of overall construction drawing of the preferred embodiment of the expandable method of three disk fault-tolerant arrays of the present invention, above
Three stages respectively corresponded left, center, right part in Fig. 2, and Fig. 3 is the example of this method, indicated to extend the band that front/rear band is concentrated
0；Fig. 4 is the example of this method, indicates to extend the band 1 that front/rear band is concentrated；Fig. 5 is the example of this method, indicates extension
The band 2 that front/rear band is concentrated；Fig. 6 is the example of this method, indicates the merging process for the band 0 and 1 that band is concentrated.Below
Cooperation Fig. 2-Fig. 6 is further illustrated into the present invention by specific example:
One, the preparation stage
In this stage, necessary parameter is calculated for next two step.
According to the layout encoded of MDS in three disk fault-tolerant arrays and its configuration parameter, n can be calculated with following formulas,
neAnd L, wherein nsIndicate the band number that a band is concentrated, neIt indicates to be arranged to the sum of null in band concentration
It measures, L is indicated in a band, the minimum number of null.According to Fig.2, a band collection contains many bands.Each
In band, part row is set as " null ", and in order to reach data balancing, they can be used to move to other disks.
By taking the three disk fault-tolerant arrays that are encoded based on Triple-Star extend to 9 pieces of disks from 7 pieces of disks as an example.nd=4, nr
=4 and m=2, wherein ndIndicate the quantity of data disks in extension front disk array, nrIt indicates to extend the line number in previous band
Amount, m indicate the quantity of extension disk.According to above-mentioned formula, n can be calculateds=3, ne=4, L=1.This indicates a band
Collection includes three bands, and one, which shares 4 row data, is set as null, and being used to equilibrium data load, (data block in null is moved
Move to other disks).Each band contains at least one null.Therefore, after expansion, band concentrates the corresponding sky of three bands
Capable quantity be be not 1,1,2 (1+1+2=4=ne)。
Two, migration phase
After obtaining relevant parameter on last stage, this stage concentrates suitable data block to migrate band.It can divide
It is operated for following three step:
(1) band collection is read in and is cached.
In order to reduce the quantity for reading I/O operation in expansion process, the present invention is by the data block and check block of entire band collection
It is disposable to read in the caching X for being located at memory.Band concentrates selected null to be placed into caching Y.It concentrates, reads in a band
Data on one piece of disk are that primary sequence is read, corresponding once to read I/O.
(2) migrating data block
The present invention migrates suitable data block according to the minimal modifications amount of check block.To three kinds of different schools
Test block (row verification, tiltedly verification, reversed tiltedly verification) relationship analyzed after, the present invention changes the position of some data blocks,
So that these blocks are still in their original verification chains.This way may insure to modify check block as few as possible.This hair
The bright migration algorithm for giving STAR coding and Triple-Star coding and verifying about row verification and tiltedly, which can be by number
According to the quantity of migration and the computational minimization of verification modification.TheRow is seen as basic row, this
Row does not need to move any data block in the horizontal direction.Next, changing the data block in same disk overhead and being located at
The mapping relations between data block in null, this will not cause Data Migration expense.The remaining data block positioned at null with
Polling sequence is written into empty data block.
Wherein, the migration algorithm that STAR coding and Triple-Star coding are verified about row verification and tiltedly is as follows:
Obtain and calculate the value of following parameter, n, m, nr ndAnd L, new plus disk label fromIt arrives
If
IfAndAnd i is not
The ID of null, i, j respectively indicate line number and disk number of the data block in band,
Then
If i < rb
Then i'=i, j'=j-m
Else if i > rb
Then i'=i, j'=j+m
For example, as in Figure 3-5,This is indicated at each
In band, the 1st capable does not move any data block.Newly plus disk be numberedIt arrivesAfter new addition disk, 2 (C of block0,2) use C0,4It indicates.2 (C of block0,4, i=0, j=4) and full
The condition of the above-mentioned algorithm of foot, therefore this method is migrated to C0,2(i'=0, j=4-2=2).Similar, this method will be round
The data block (such as block 9,18 and 25 etc.) of label is migrated to different disks, but they still verify chain and oblique school in original row
Test chain.
Next, the present invention changes reflecting between the data block in same disk overhead and the data block in null
Penetrate relationship.The data block (such as block 14,13 and 30 etc.) that diamond indicia is selected from caching Y, is written the empty data block of same disk
In.Therefore, this can be by Data Migration minimizing overhead.Finally cache remaining data block (such as block 12,15,18 and 31 in Y
Deng) empty data block is written into polling sequence.In rare cases, the data block cached in Y is not enough to fill up same magnetic
The empty data block of disk, this will increase a part of Data Migration quantity.
(3) update and recalculate check block
Three kinds of check block needs are updated or recalculate.Row check block can be another by one-time write check disk
Outer two kinds of check blocks needs are temporarily stored in caching X.
More newline check block
Here pass through the exclusive or and Lai Geng newline check block for calculating the data block of raw line check block and Xin Jia.Next,
We are by its disposable writing line check disk, because row verification will not be changed in merging phase.For example,V12And V14Indicate the value of data block 12 and 14.
Update oblique check block
It updates tiltedly verification and needs to calculate original oblique check block, the data block in related null and corresponding updated row verification
The exclusive or of block and.The data that the oblique verification that oblique part newly increases can be used in caching X are calculated.For example,Next, oblique check block is put into caching X.
Recalculate reversed oblique check block
According to the coding formula of correcting and eleting codes, reversed oblique check block is recalculated used here as the data block in caching X, and will
It is put into caching X.
Up to the present, it has been completed in the expansion process that a band is concentrated.If certain data are in expansion process
It is lost, they can be resumed out by caching X and Y.
Three, merging phase
It is because it can reduce the I/O quantity of verification modification that the present invention, which needs merging phase,.Because having null (or empty
Data block) band there is still a need for check blocks to carry out data protection, the school needed in the quantity of check block and a complete band
It is the same for testing number of blocks.Therefore a tape merge so that all check blocks are fully utilized, and are reduced verification and repaired by us
Change the expense with I/O.
Merging phase needs following steps:
1) determine which band needs is merged or is split, so that overall computing cost is minimum.
After previous stage, band concentrates the line number of each band to know.The present invention selects some lucky
The band matched merges, and forms a complete band.If split without suitable band to band.Due to I/O
The reduction of expense, splitting brought computing cost can undertake, and will not have an impact to expansion process.
By taking the three disk fault-tolerant arrays that are encoded based on Triple-Star extend to 9 pieces of disks from 7 pieces of disks as an example.Such as Fig. 3-4
It is shown, it is assumed that there are three band collection I, II and III, each band collection includes band 0,1 and 2.Band 0 and 1 in band collection I can
To be merged into a complete band, as shown in Figure 6.Band 2 in band collection I can be with the band 2 in band collection II and II
It merges.Therefore, it after the completion of merging, extends the preceding 3 × 3=9 band with 7 pieces of disks and becomes 1 × 3+1=4
Band with 9 pieces of disks.
2) merge band between band concentration or band collection
The step can be divided into two parts:
Merging data block and row check block；
Merge tiltedly verification and reversed tiltedly verification, and by its one-time write check disk.
In the first portion, the operation of merging data block and row check block only changes the rower of data block and row check block
Number, additional I/O expense will not be generated.Block Ci,j(band a) is mapped to block Ci+x,j(band b), x are the numbers of the row in band b
Amount (does not include null).As in Figure 3-5, block C1,2(band 1) is mapped to C4,2The position of (band 0), x=3.
In the second portion, merge tiltedly verification and reversed tiltedly verification, and by its one-time write check disk.We can letter
Above two verification singly is calculated by XOR operation.Row check block Ci,p+1(band a) and(the value of band b)
Addition obtains a new Ci,p+1, x is the quantity (not including null) of the row in band a.I.e.As in Figure 3-5,R'0C in band 0 can be used0,8It indicates.?
In band 1,R'10C in band 0 can be used4,8It indicates.Data and row check block in band 1
After being mapped to band 0,Therefore the C in band 0 is updated4,8It is to calculate item
With original C in 00,8With the C in band 14,8Exclusive or andReversed oblique check block
Calculating it is similar with the calculating of oblique check block.Next, check disk is written in they and discharges spatial cache.Aforesaid operations can be with
It is parallel to carry out, accelerate entire extension process.
Fig. 7 is a kind of system architecture diagram of the expansible system of three disk fault-tolerant arrays of the present invention.As shown in fig. 7, of the invention
A kind of expansible system of three disks fault-tolerant array, including preparatory unit 701, migration units 702 and combining unit 703.
Wherein, preparatory unit 701 collects relevant parameter from storage system, is migration units 702 and combining unit
703 provide necessary parameter；Migration units 702 select a part of band as band collection, and calculate according in the stage one
Parameter, some data lines are selected in each band, for migrate to newly plus disk in, in transition process, data block
Movement be to be determined by the association between different check, this can guarantee balanced data distribution；Combining unit 703 is used
In the tape merge that will have null or empty data block, to reduce the quantity and I/O expense of verification modification.
Preparatory unit 701 can use following public affairs according to the layout encoded of MDS in three disk fault-tolerant arrays and its configuration parameter
Formula calculates ns, neAnd L.According to Fig.2, a band collection contains many bands.In each band, part row is set as
" null ", in order to reach data balancing, they can be used to move to other disks.
Migration units 702 concentrate suitable data block to migrate band, can be divided into following three step and be operated:
(1) band collection is read in and is cached.
In order to reduce the quantity for reading I/O operation in expansion process, migration units 702 are by the data block of entire band collection and school
It tests block and disposably reads in the caching X for being located at memory.Band concentrates selected null to be placed into caching Y.In a band collection
In, reading the data on one piece of disk is that primary sequence is read, corresponding once to read I/O.
(2) migrating data block
Migration units 702 migrate suitable data block according to the minimal modifications amount of check block.To three kinds of differences
Check block (row verification, tiltedly verification, reversed tiltedly verification) relationship analyzed after, change the position of some data blocks, make
These blocks are obtained still in their original verification chains.This way may insure to modify check block as few as possible.Migration is single
Member 702 gives STAR coding and Triple-Star coding about the row verification and tiltedly migration algorithm that verifies, which can will
The quantity of Data Migration and the computational minimization of verification modification.TheRow is seen as basic row, this
A line does not need to move any data block in the horizontal direction.Next, changing data block and the position in same disk overhead
Mapping relations between the data block in null, this will not cause Data Migration expense.The remaining data block positioned at null
It is written into polling sequence in empty data block.
Wherein, the migration algorithm that STAR coding and Triple-Star coding are verified about row verification and tiltedly is as follows:
Obtain and calculate the value of following parameter, n, m, nr ndAnd L, new plus disk label fromIt arrives
If
IfAndAnd i is not
The ID of null
Then
If i < rb
Then i'=i, j'=j-m
Else if i > rb
Then i'=i, j'=j+m
For example, as in Figure 3-5,This is indicated at each
In band, the 1st capable does not move any data block.Newly plus disk be numberedIt arrivesAfter new addition disk, 2 (C of block0,2) use C0,4It indicates.2 (C of block0,4, i=0, j=4) and full
The condition of the above-mentioned algorithm of foot, therefore migration units 702 are migrated to C0,2(i'=0, j=4-2=2).Similar, migration is single
Member 702 migrates the data block (such as block 9,18 and 25 etc.) of circular mark to different disks, but they are still in original row
Verify chain and tiltedly verification chain.
Next, migration units 702 change the data block in same disk overhead and data block in null it
Between mapping relations.The data block (such as block 14,13 and 30 etc.) that diamond indicia is selected from caching Y, is written the sky of same disk
In data block.Therefore, this can be by Data Migration minimizing overhead.Finally cache remaining data block (such as block 12,15,18 in Y
With 31 etc.) empty data block is written into polling sequence.In rare cases, the data block cached in Y is not enough to fill up together
The empty data block of one disk, this will increase a part of Data Migration quantity.
(3) update and recalculate check block
Three kinds of check block needs are updated or recalculate.Row check block can be another by one-time write check disk
Outer two kinds of check blocks needs are temporarily stored in caching X.
More newline check block
Here pass through the exclusive or and Lai Geng newline check block for calculating the data block of raw line check block and Xin Jia.Next,
We are by its disposable writing line check disk, because row verification will not be changed in merging phase.For example,V12And V14Indicate the value of data block 12 and 14.
Update oblique check block
It updates tiltedly verification and needs to calculate original oblique check block, the data block in related null and corresponding updated row verification
The exclusive or of block and.The data that the oblique verification that oblique part newly increases can be used in caching X are calculated.For example,Next, oblique check block is put into caching X.
Recalculate reversed oblique check block
According to the coding formula of correcting and eleting codes, reversed oblique check block is recalculated used here as the data block in caching X, and will
It is put into caching X.
Up to the present, it has been completed in the expansion process that a band is concentrated.If certain data are in expansion process
It is lost, they can be resumed out by caching X and Y.
Combining unit 703 is by a tape merge, so that all check blocks are fully utilized, and reduces verification modification and I/
The expense of O.
Combining unit needs following steps:
1) determine which band needs is merged or is split, so that overall computing cost is minimum.
After previous stage, band concentrates the line number of each band to know.The present invention selects some lucky
The band matched merges, and forms a complete band.If split without suitable band to band.Due to I/O
The reduction of expense, splitting brought computing cost can undertake, and will not have an impact to expansion process.
By taking the three disk fault-tolerant arrays that are encoded based on Triple-Star extend to 9 pieces of disks from 7 pieces of disks as an example.Such as Fig. 3-4
It is shown, it is assumed that there are three band collection I, II and III, each band collection includes band 0,1 and 2.Band 0 and 1 in band collection I can
To be merged into a complete band, as shown in Figure 6.Band 2 in band collection I can be with the band 2 in band collection II and II
It merges.Therefore, it after the completion of merging, extends the preceding 3 × 3=9 band with 7 pieces of disks and becomes 1 × 3+1=4
Band with 9 pieces of disks.
2) merge band between band concentration or band collection
The step can be divided into two parts:
Merging data block and row check block；
Merge tiltedly verification and reversed tiltedly verification, and by its one-time write check disk.
In the first portion, the operation of merging data block and row check block only changes the rower of data block and row check block
Number, additional I/O expense will not be generated.Block Ci,j(band a) is mapped to block Ci+x,j(band b), x are the numbers of the row in band b
Amount (does not include null).As in Figure 3-5, block C1,2(band 1) is mapped to C4,2The position of (band 0), x=3.
In the second portion, merge tiltedly verification and reversed tiltedly verification, and by its one-time write check disk.We can letter
Above two verification singly is calculated by XOR operation.Row check block Ci,p+1(band a) and(the value of band b)
Addition obtains a new Ci,p+1, x is the quantity (not including null) of the row in band a.I.e.As in Figure 3-5,R'0C in band 0 can be used0,8It indicates.?
In band 1,R'10C in band 0 can be used4,8It indicates.Data and row check block quilt in band 1
After being mapped to band 0,Therefore the C in band 0 is updated4,8It is to calculate band 0
In original C0,8With the C in band 14,8Exclusive or andThe meter of reversed tiltedly check block
It calculates similar with the calculating of oblique check block.Next, check disk is written in they and discharges spatial cache.Aforesaid operations can be parallel
It carries out, accelerates entire extension process.
In conclusion the expandable method and system of the present invention three disk fault-tolerant arrays of one kind are according to the association of different check
Property, select suitable data block to be migrated, thus reach the quantity of the smallest Data Migration and verification modification, meanwhile, this hair
It is bright that will there is the band of empty data block to merge, so that the I/O cost reduction of verification modification, therefore present invention can assure that expand
Data distribution is balanced after exhibition, and the I/O expense in expansion process is smaller.
The above-described embodiments merely illustrate the principles and effects of the present invention, and is not intended to limit the present invention.Any
Without departing from the spirit and scope of the present invention, modifications and changes are made to the above embodiments by field technical staff.Therefore,
The scope of the present invention, should be as listed in the claims.
Claims (10)
1. a kind of expandable method of three disk fault-tolerant arrays, includes the following steps:
Preparation stage collects relevant parameter from storage system, calculates necessary parameter for next two stages；
Migration phase selects a part of band as band collection, and according to parameter calculated in the preparation stage, at each
Some data lines are selected in band, for migrating into the disk newly added；
Merging phase, by the tape merge with null or empty data block.
2. the expandable method of three disk fault-tolerant arrays of one kind as described in claim 1, it is characterised in that: in the preparation stage, root
According to the layout encoded of MDS in three disk fault-tolerant arrays and its configuration parameter, n is calculateds, neAnd L, it is supplied to two later ranks
Section, wherein nsIndicate the band number that a band is concentrated, neIt indicates to be arranged to the total quantity of null, L in band concentration
It indicates in a band, the minimum number of null.
3. the expandable method of three disk fault-tolerant arrays of one kind as claimed in claim 2, which is characterized in that migration phase includes such as
Lower step:
Band collection is read in and is cached；
According to the minimal modifications amount of check block, suitable data block is migrated；
Update and recalculate check block.
4. the expandable method of three disk fault-tolerant arrays of one kind as claimed in claim 3, it is characterised in that: by entire band collection
Data block and check block disposably read in the caching X positioned at memory, and band concentrates selected null to be placed into caching Y.
5. the expandable method of three disk fault-tolerant arrays of one kind as claimed in claim 4, it is characterised in that: described according to check block
Minimal modifications amount, the step of migrating to suitable data block, is to row verification, tiltedly verification, the relationship reversely tiltedly verified carry out
After analysis, change the position of some data blocks, so that these blocks are still in their original verification chains.
6. the expandable method of three disk fault-tolerant arrays of one kind as claimed in claim 5, it is characterised in that: the update and again
It calculates in check block step, the exclusive or and Lai Geng newline check block of the data block by calculating raw line check block and Xin Jia.
7. the expandable method of three disk fault-tolerant arrays of one kind as claimed in claim 6, it is characterised in that: the update and again
Calculate in check block step, update tiltedly verification and needs to calculate original oblique check block, the data block in related null and it is corresponding more
The exclusive or of new row check block and.
8. the expandable method of three disk fault-tolerant arrays of one kind as claimed in claim 7, it is characterised in that: the update and again
It calculates in check block step, reversed oblique check block is recalculated according to the coding formula of correcting and eleting codes.
9. the expandable method of three disk fault-tolerant arrays of one kind as claimed in claim 8, which is characterized in that the merging phase packet
Include following steps:
Determine which band needs is merged or is split, so that overall computing cost is minimum；
Merge band between band concentration or band collection.
10. a kind of expansible system of three disk fault-tolerant arrays, comprising:
Preparatory unit collects relevant parameter from storage system, provides necessary parameter for migration units and combining unit；
Migration units select a part of band as band collection, and according to parameter calculated in the stage one, in each band
In select some data lines, for migrate to newly plus disk in, in transition process, the movement of data block is by different check
Between association determined；
Combining unit, for that will have the tape merge of null or empty data block.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201610637554.1A CN106293526B (en) | 2016-08-05 | 2016-08-05 | A kind of expandable method and system of three disks fault-tolerant array |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201610637554.1A CN106293526B (en) | 2016-08-05 | 2016-08-05 | A kind of expandable method and system of three disks fault-tolerant array |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN106293526A CN106293526A (en) | 2017-01-04 |
| CN106293526B true CN106293526B (en) | 2019-04-12 |
Family
ID=57665961
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201610637554.1A Active CN106293526B (en) | 2016-08-05 | 2016-08-05 | A kind of expandable method and system of three disks fault-tolerant array |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN106293526B (en) |
Families Citing this family (5)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN107094186B (en) * | 2017-06-15 | 2019-10-01 | 深圳市云舒网络技术有限公司 | A kind of correcting and eleting codes optimization method of distributed memory system |
| CN111880963B (en) * | 2020-07-29 | 2022-06-10 | 北京浪潮数据技术有限公司 | Data reconstruction method, device, equipment and storage medium |
| CN112835533B (en) * | 2021-02-25 | 2023-02-17 | 上海交通大学 | A rack-level cloud storage array expansion method and device |
| CN114816278B (en) * | 2022-06-30 | 2022-11-11 | 苏州浪潮智能科技有限公司 | Data migration method, system, equipment and storage medium of storage server |
| US11804854B1 (en) * | 2022-07-26 | 2023-10-31 | Hewlett Packard Enterprise Development Lp | Changing error-correction configurations |
Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN102200892A (en) * | 2011-04-29 | 2011-09-28 | 华中科技大学 | Capacity expansion method based on dynamic redundant array of independent disks (RAID) system |
| CN104881365A (en) * | 2015-05-31 | 2015-09-02 | 上海交通大学 | RAID-6 extensible method based on erasure code similarity |
| CN104881372A (en) * | 2015-05-31 | 2015-09-02 | 上海交通大学 | Data migration method capable of improving RAID-6 (redundant array of independent disks-6) expandability |
| CN105630423A (en) * | 2015-12-25 | 2016-06-01 | 华中科技大学 | Erasure code cluster storage expansion method based on data caching |
Family Cites Families (2)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6996689B2 (en) * | 2003-04-16 | 2006-02-07 | Lsi Logic Corporation | Systems and methods for striped storage migration |
| TWI334564B (en) * | 2007-02-14 | 2010-12-11 | Via Tech Inc | Data migration systems and methods for independent storage device expansion and adaptation |
-
2016
- 2016-08-05 CN CN201610637554.1A patent/CN106293526B/en active Active
Patent Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN102200892A (en) * | 2011-04-29 | 2011-09-28 | 华中科技大学 | Capacity expansion method based on dynamic redundant array of independent disks (RAID) system |
| CN104881365A (en) * | 2015-05-31 | 2015-09-02 | 上海交通大学 | RAID-6 extensible method based on erasure code similarity |
| CN104881372A (en) * | 2015-05-31 | 2015-09-02 | 上海交通大学 | Data migration method capable of improving RAID-6 (redundant array of independent disks-6) expandability |
| CN105630423A (en) * | 2015-12-25 | 2016-06-01 | 华中科技大学 | Erasure code cluster storage expansion method based on data caching |
Also Published As
| Publication number | Publication date |
|---|---|
| CN106293526A (en) | 2017-01-04 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN106293526B (en) | A kind of expandable method and system of three disks fault-tolerant array | |
| JP6771018B2 (en) | Improved performance of 2D array processor | |
| EP3399419B1 (en) | Method and system for multi-dimensional raid | |
| US11494265B2 (en) | Securing against errors in an error correcting code (ECC) implemented in an automotive system | |
| CN105786408B (en) | Logic sector mapping in flash array | |
| CN101652752B (en) | File server for redundant array of independent disks (RAID) system | |
| US5613085A (en) | System for parallel striping of multiple ordered data strings onto a multi-unit DASD array for improved read and write parallelism | |
| US8037391B1 (en) | Raid-6 computation system and method | |
| CN104965768B (en) | The method and system placed for the service-aware data in storage system | |
| CN109643258A (en) | The multinode reparation of erasing code is regenerated using high-speed minimum memory | |
| CN109582484B (en) | Protection against errors in Error Correcting Code (ECC) implemented in automotive systems | |
| US20050114727A1 (en) | Uniform and symmetric double failure correcting technique for protecting against two disk failures in a disk array | |
| CN101620518B (en) | Method and apparatus for creating redundancy array in disc RAID | |
| CN112799604A (en) | A RAID6 disk array expansion method and data filling method based on N-Code | |
| US5896493A (en) | Raid algorithm using a multimedia functional unit | |
| CN104932835A (en) | Erasure code based distributed storage system capacity expansion and reduction method | |
| US12321230B2 (en) | Alias-free tagged error correcting codes for machine memory operations | |
| Fu et al. | A stack-based single disk failure recovery scheme for erasure coded storage systems | |
| Zhang et al. | Fast 3D visualization of massive geological data based on clustering index fusion | |
| JP2002278707A (en) | Disk controller | |
| CN104137082B (en) | Method and device for writing data of first block size | |
| CN106227463B (en) | RAID, reading and writing data and its method for reconstructing | |
| CN104035825B (en) | Redirect source list processing method, device and compiler | |
| KR100861859B1 (en) | Multi-path data retrieval from redundant array | |
| CN109426503A (en) | The method and device of simulation excitation is provided |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| GR01 | Patent grant | ||
| GR01 | Patent grant |