US 9,152,499 B1Granted

Method and system for calculating parity values for multi-dimensional RAID

AssigneeDSSD, Inc.

InventorsTodor Ivanov Mollov, Jeffrey S. Bonwick

Life of this patent

Estimating the term…

Loading patent…

Abstract

A method for calculating parity values including calculating a first set of parity values using datum stored in RAID Grid locations in a first PCB, where datum associated with the RAID Grid locations in the first PCB is obtained in a first order that is based on a Hilbert curve. The method further includes calculating a second set of parity values using datum stored in RAID Grid locations in a second PCB, where datum associated with the RAID Grid locations in the second PCB is obtained in a second order that is based on the Hilbert curve. The method further includes storing at least a portion of the first set of parity values and a second set of parity values in a cache, memory, or persistent storage, where each of the first parity values and second parity values is associated with a separate RAID Grid location in the RAID Grid.

Claims20

Dependent claims

A system comprising:

a memory, a cache, and a persistent storage;
and
a processor that:
performs, using a first datum, a first plurality of parity value calculations to obtain a first plurality of parity values, wherein the first datum is associated with a first Redundant Array of Independent Disks (RAID) Grid location in a first parity calculation block (PCB) in a RAID Grid, wherein the RAID Grid comprises a first dimension and a second dimension, wherein at least one of the first plurality of parity values is associated with the first parity RAID Grid location in the first dimension and at least one of the first plurality of parity values is associated with a second parity RAID Grid location in the second dimension;
performs, using a second datum, a second plurality of parity value calculations to obtain a second plurality of parity values, wherein the second datum is associated with a second RAID Grid location in the first PCB;
performs, using a third datum and at least one selected from a group consisting of at least one of the first plurality of parity values and at least one of the second plurality of parity values, a third plurality of parity value calculations to obtain a third plurality of parity values, wherein the third datum is associated with a third RAID Grid location in the first PCB;
performs, using a fourth datum and at least one selected from a group consisting of at least one of the first plurality of parity values and at least one of the second plurality of parity values, a fourth plurality of parity value calculations to obtain a fourth plurality of parity values, wherein the fourth datum is associated with a fourth RAID Grid location in the first PCB;
and
stores each of the fourth plurality of parity values in at least one selected from a group consisting of the cache, the memory, and the persistent storage, wherein each of the fourth plurality of parity values is associated with a separate RAID Grid location in the RAID Grid,
wherein the processor is operatively connected to the memory, the cache, and the persistent storage.

7 more elements

A system, comprising:

a memory, a cache, and a persistent storage;
and
a processor that:
calculates a first set of parity values for a RAID Grid using datum stored in each of a plurality of RAID Grid locations in a first parity calculation block (PCB), wherein the datum associated with each of the plurality of RAID Grid locations in the first PCB is obtained in a first order and wherein the first order is based on a Hilbert curve wherein, based on the first order, a first parity value is calculated using a first datum in a first RAID Grid location in the first PCB, and a second parity value is calculated using a second datum in a last RAID Grid location in the first PCB, wherein the last RAID Grid location is adjacent to the first RAID Grid location, wherein the first PCB comprises N RAID Grid locations, wherein N≧4;
calculates a second set of parity values for the RAID Grid using datum stored in each of a plurality of RAID Grid locations in a second PCB, wherein the datum associated with each of the plurality of RAID Grid locations in the second PCB is obtained in a second order and wherein the second order is based on the Hilbert curve;
and
stores at least a portion of the first set of parity values and at least a portion of the second set of parity values in at least one selected from a group consisting of the cache, the memory, and the persistent storage, wherein each of the first set of parity values and the second set of parity values is associated with a separate RAID Grid location in the RAID Grid,
wherein the processor is operatively connected to the memory, the cache, and the persistent storage.

5 more elements

Dependencies are inferred from the claim text.

Facts

Application: 14/510,795Filed 9 Oct 2014 · continuation
Priority: 4 Dec 2013
Granted: 6 Oct 2015
Term ends: Not estimatedThe source records don’t support an estimate.

Classification6 codes

G06F 11/1076
Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's: parity data used in redundant arrays of…
G06F 3/0619
Improving the reliability of storage systems: in relation to data integrity, e.g. data losses, bit errors
G06F 3/0647
Horizontal data movement in storage systems, i.e. moving data in between storage devices or systems: migration mechanisms
G06F 3/0689
Plurality of storage devices: disk arrays, e.g. RAID, JBOD