Flexible redundant array of independent disks (RAID) computation device

Patent metadata

Field	Value
Publication number	US-10102072-B2
Application number	US-201615282254-A
Country	US
Kind code	B2
Filing date	Sep 30, 2016
Priority date	Dec 2, 2013
Publication date	Oct 16, 2018
Grant date	Oct 16, 2018

Abstract

A method for calculating a plurality (M) of redundancy blocks for multiple (N) data blocks of a plurality (D) of words each, the method comprises: receiving the number (M) of redundancy blocks by a calculator that comprises multiple (R) calculation units; configuring the calculator according to M and R; concurrently calculating, if M equals R, by the multiple (R) calculation units of the calculator, R sets of parity vectors, each set includes a plurality (D) of parity vectors; and calculating the plurality (M) of the redundancy blocks based on the R sets of parity vectors.

First claim

We claim:

1. A system comprising:
a calculator that comprises R number of calculation units and a buffer having a buffer size; and
a controller for configuring the calculator in at least one of a redundancy calculation mode to calculate M number of one or more redundancy blocks for data blocks of D number of words each, or a reconstruction mode to reconstruct N number of one or more information blocks of D number of words each,
wherein in the redundancy calculation mode:
the controller is arranged to configure the calculator according to M and R by determining a size of each data block based on a ratio between the buffer size and a number of activated calculation units in the redundancy calculation mode; and
the calculator is arranged to:
calculate one or more sets of parity vectors by at least a subset of the R number of calculation units of the calculator, wherein each set of parity vectors includes D number of parity vectors; and
calculate M number of one or more redundancy blocks based on the one or more sets of parity vectors, and

wherein in the reconstruction mode:
the controller is arranged to configure the calculator according to N and R by determining a size of each reconstructed data block in response to a ratio between the buffer size and a number of activated calculation units in the reconstruction mode, wherein the N number of one or more information blocks are selected from a group of (N+M) information blocks, the group of (N+M) information blocks comprising N data blocks and M parity blocks; and
the calculator is arranged to:
calculate one or more sets of reconstructed data vectors by at least a subset of the R number of calculation units of the calculator, wherein each set of reconstructed data vectors includes D number of reconstructed data vectors; and
generate N number of reconstructed data blocks based on the one or more sets of reconstructed data vectors.

2. The system according to claim 1 , wherein in the redundancy calculation mode, different calculation units calculate different sets of parity vectors by multiplying different rows of a Vandermonde matrix by intermediate vectors.

3. The system according to claim 1 , wherein in the reconstruction mode, different calculation units calculate different sets of reconstructed data vectors by multiplying different rows of an inverted matrix by intermediate vectors.

4. The system according to claim 1 , wherein different values of M represent different redundant array of independent disks (RAID) levels.

5. The system according to claim 1 , wherein R is not smaller than four.

6. A method for calculating M number of one or more redundancy blocks for data blocks of D number of words each, the method comprising:
receiving the data blocks by a calculator that comprises R number of calculation units and a buffer having a buffer size;
configuring the calculator according to M and R by determining a size of each data block based on a ratio between the buffer size and a number of activated calculation units;
calculating one or more sets of parity vectors by at least a subset of the R number of calculation units of the calculator, wherein each set of parity vectors includes D number of parity vectors; and
calculating M number of one or more redundancy blocks based on the one or more sets of parity vectors.

7. The method according to claim 6 , wherein if M equals R, the one or more sets of parity vectors includes R sets of parity vectors calculated by the R number of calculation units, and the M number of one or more redundancy blocks are calculated based on the R sets of parity vectors.

8. The method according to claim 6 , wherein if M is smaller than R, the one or more sets of parity vectors includes M sets of parity vectors calculated by the M number of calculation units, and the M number of one or more redundancy blocks are calculated based on the M sets of parity vectors.

9. The method according to claim 6 , wherein if M equals one, the one or more sets of parity vectors includes a single set of parity vectors calculated by a single calculation unit, and one redundancy block is calculated based on the single set of parity vectors.

10. The method according to claim 6 , wherein if M exceeds R, and M modulo R equals a difference X, the step of calculating the one or more sets of parity vectors includes:
selecting a certain set of R rows of a Vandermonde matrix;
calculating R sets of parity vectors by the R number of calculation units by processing the certain set of R rows of the Vandermonde matrix;
if there are more than R rows of the Vandermonde matrix that were not processed, then selecting a new certain set of R rows of the Vandermonde matrix and calculating additional R sets of parity vectors by the R number of calculation units by processing the new certain set of R rows of the Vandermonde matrix; and
if there are X rows of the Vandermonde matrix that were not processed, then selecting a further certain set of X rows of the Vandermonde matrix and calculating X sets of parity vectors by X number of the calculation units of the calculator by processing the further certain set of X rows of the Vandermonde matrix.

11. The method according to claim 10 , wherein different calculation units calculate different sets of parity vectors by multiplying different rows of the Vandermonde matrix by intermediate vectors.

12. The method according to claim 6 , wherein different values of M represent different redundant array of independent disks (RAID) levels.

13. The method according to claim 6 , wherein R is not smaller than four.

14. The method according to claim 6 , further comprising receiving multiple coefficients of a Vandermonde matrix in descriptors of the data blocks.

15. A method for reconstructing N number of one or more information blocks of D number of words each, the method comprising:
receiving a value of N by a calculator that comprises R number of calculation units and a buffer having a buffer size, wherein the N number of one or more information blocks are selected from a group of (N+M) information blocks, the group of (N+M) information blocks comprising N data blocks and M parity blocks;
configuring the calculator according to N and R by determining a size of each reconstructed data block in response to a ratio between the buffer size and a number of activated calculation units;
calculating one or more sets of reconstructed data vectors by at least a subset of the R number of calculation units of the calculator, wherein each set of reconstructed data vectors includes D number of reconstructed data vectors; and
generating N number of reconstructed data blocks based on the one or more sets of reconstructed data vectors.

16. The method according to claim 15 , wherein if N equals R, the one or more sets of reconstructed data vectors includes R sets of reconstructed data vectors calculated by the R number of calculation units, and the N number of reconstructed data blocks are calculated based on the R sets of reconstructed data vectors.

17. The method according to claim 15 , wherein if N is smaller than R, the one or more sets of reconstructed data vectors includes N sets of reconstructed data vectors calculated by the N number of calculation units, and the N number of reconstructed data blocks are calculated based on the N sets of reconstructed data vectors.

18. The method according to claim 15 , wherein if N equals one, the one or more sets of reconstructed data vectors includes a single set of reconstructed data vectors calculated by a single calculation unit, and one re

Assignees

• Amazon Tech Inc

Inventors

• Diamant Ron
• Bshara Nafea
• Shapira Yaniv
• Nakibly Guy

Classifications

• G06F2211/1057

  Parity-multiple bits-RAID6, i.e. RAID 6 implementations · CPC title

• G06F11/1092 Primary

  Rebuilding, e.g. when physically replacing a failing disk · CPC title

• G06F11/1096

  Parity calculation or recalculation after configuration or reconfiguration of the system · CPC title

• G06F11/2094

  Redundant storage or storage space (G06F11/2056 takes precedence) · CPC title

• G06F11/1076 Primary

  Parity data used in redundant arrays of independent storages, e.g. in RAID systems · CPC title