Method and system for checkerboard RAID

• US 10,127,113 B1
• Filed: 03/31/2016
• Issued: 11/13/2018
• Est. Priority Date: 03/31/2016
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Inventors: Bonwick, Jeffrey S., Tabrizi, Haleh
• Primary Examiner(s): Iqbal, Nadeem
• Application Number:
  US15/086,429
• Time in Patent Office: 957 Days
• CPC Class Codes: G06F 11/108 Parity data distribution in semiconductor storages, e.g. in SSD
• CPC Class Codes: G06F 11/1096 Parity calculation or recalculation after configuration or reconfiguration of the system
• CPC Class Codes: G06F 2201/845 Systems in which the redundancy can be transformed in increased performance

Abstract

A system and method for storing data including receiving a request to write data and in response to the request selecting a set of free physical locations in persistent storage. The system and method further include determining an aggregate failure rate of the set of free physical locations, making a first determination that the aggregate failure rate is less than a failure rate threshold for the persistent storage and based on the first determination calculating a parity value using at least a portion of the data, and writing the data and the parity value to the set of free physical locations.

Claims

1. A method for storing data comprising:

receiving a request to write data;

in response to the request;

selecting a first set of free physical locations across a plurality of storage devices to form a first new redundant array of independent disks (RAID) stripe, wherein each free physical location is distributed across an independent fault domain (IFD);

determining a first aggregate failure rate of the first new RAID stripe;

making a first determination that the first aggregate failure rate exceeds a failure rate threshold for the plurality of storage devices;

selecting, based on the first determination, a second set of free physical locations across the plurality of storage devices to form a second new RAID stripe, comprising;

replacing a first free physical location of the first set of free physical locations with a second free physical location across the plurality of storage devices, wherein the first and second free physical locations reside on the same storage device;

determining a second aggregate failure rate of the second new RAID stripe;

making a second determination that the second aggregate failure rate is less than the failure rate threshold for the plurality of storage devices;

based on the second determination;

calculating a parity value using at least a portion of the data; and

writing the data and the parity value to the second set of free physical locations forming the second new RAID stripe.

2. The method of claim 1, further comprising:

prior to making the first determination;

obtaining a plurality of individual failure rates associated with the plurality of storage devices; and

determining the failure rate threshold using at least a portion of the plurality of individual failure rates.

3. The method of claim 1, further comprising:

after writing the data and the parity value to the second set of physical free physical locations forming the second new RAID stripe;

obtaining a second plurality of individual failure rates for the plurality of storage devices; and

determining a second failure rate threshold using at least a portion of the second plurality of individual failure rates, wherein the second failure rate threshold is different than the failure rate threshold.

4. The method of claim 1, further comprising:

after writing the data and the parity value to the second set of physical free physical locations forming the second new RAID stripe and after at least a portion of the plurality of storage devices is replaced to obtain a second plurality of storage devices;

obtaining a second plurality of individual failure rates for the second plurality of storage devices; and

determining a second failure rate threshold using at least a portion of the second plurality of individual failure rates, wherein the second failure rate threshold is different than the failure rate threshold.

5. The method of claim 1, further comprising:

receiving a second request to write second data;

in response to the second request;

selecting a third set of free physical locations across the plurality of storage devices to form a third new RAID stripe;

determining a third aggregate failure rate of the third new RAID stripe;

making a third determination that the third aggregate failure rate exceeds the failure rate threshold for the plurality of storage devices;

based on the third determination;

making a fourth determination that there are no additional combinations of free physical locations to select; and

based on the fourth determination;

issuing an error notification to a client that issued the second request.

6. The method of claim 5, further comprising:

after making the fourth determination, initiating an updating of the failure rate threshold.

7. The method of claim 1, wherein the plurality of storage devices comprises solid state storage.

8. The method of claim 1, wherein writing the data and the parity value to the second set of free physical locations forming the new second RAID stripe, comprises:

determining a first physical location in the second set of free physical locations that has a highest individual failure rate; and

writing the parity value to the first physical location.

18. The method of claim 1, wherein the first free physical location exhibits a highest individual failure rate across the first set of free physical locations.

9. A system, comprising:

a storage array comprising a plurality of storage devices (SDs); and

a controller operatively connected to the storage array and configured to;

receive a request to write data;

in response to the request;

select a first set of free physical locations in the plurality of SDs to form a first new redundant array of independent disks (RAID) stripe, wherein each free physical location is distributed across an independent fault domain (IFD);

determine a first aggregate failure rate of the first new RAID stripe;

make a first determination that the first aggregate failure rate exceeds a failure rate threshold for the storage array;

select, based on the first determination, a second set of free physical locations in the plurality of SDs to form a second new RAID stripe, comprising;

replacing a first free physical location of the first set of free physical locations with a second free physical location in the plurality of SDs, wherein the first and second free physical locations reside in the same SD;

determine a second aggregate failure rate of the second new RAID stripe;

make a second determination that the second aggregate failure rate is less than the failure rate threshold for the storage array;

based on the second determination;

calculate a parity value using at least a portion of the data; and

write the data and the parity value to the second set of free physical locations forming the second new RAID stripe.

10. The system of claim 9, wherein the controller is further configured to:

prior to making the first determination;

obtain a plurality of individual failure rates associated with the plurality of SDs; and

determine the failure rate threshold using at least a portion of the plurality of individual failure rates.

11. The system of claim 9, wherein the controller is further configured to:

after writing the data and the parity value to the second set of physical free physical locations forming the second new RAID stripe;

obtain a second plurality of individual failure rates for the plurality of SDs; and

determine a second failure rate threshold using at least a portion of the second plurality of individual failure rates, wherein the second failure rate threshold is different than the failure rate threshold.

12. The system of claim 9, wherein the controller is further configured to:

after writing the data and the parity value to the second set of physical free physical locations forming the second new RAID stripe and after a least a portion of the plurality of SDs is replaced to obtain a second plurality of SDs;

obtain a second plurality of individual failure rates for the second plurality of SDs; and

determine a second failure rate threshold using at least a portion of the second plurality of individual failure rates, wherein the second failure rate threshold is different than the failure rate threshold.

13. The system of claim 9, wherein the controller is further configured to:

receive a second request to write second data;

in response to the second request;

select a third set of free physical locations in the persistent storage to form a third new RAID stripe;

determine a third aggregate failure rate of the third new RAID stripe;

make a third determination that the third aggregate failure rate exceeds the failure rate threshold for the storage array;

based on the third determination;

make a fourth determination that there are no additional combinations of free physical locations to select;

based on the fourth determination;

issue an error notification to a client that issued the second request.

14. The system of claim 13, wherein the controller is further configured to:

after making the fourth determination, initiate an updating of the failure rate threshold.

15. The system of claim 9, wherein at least one of the plurality of SDs comprises NAND flash.

19. The system of claim 9, wherein the first free physical location exhibits a highest individual failure rate across the first set of free physical locations.

16. A non-transitory computer readable medium comprising instructions, which when executed by at least one processor perform a method, the method comprising:

receiving a request to write data;

in response to the request;

selecting a first set of free physical locations across a plurality of storage devices to form a first new redundant array of independent disks (RAID) stripe, wherein each free physical location is distributed across an independent fault domain (IFD);

determining a first aggregate failure rate of the first new RAID stripe;

making a first determination that the first aggregate failure rate exceeds a failure rate threshold for the plurality of storage devices;

selecting, based on the first determination, a second set of free physical locations across the plurality of storage devices to form a second new RAID stripe, comprising;

replacing a first free physical location of the first set of free physical locations with a second free physical location across the plurality of storage devices, wherein the first and second physical locations reside in the same storage device;

determining a second aggregate failure rate of the second new RAID stripe;

making a second determination that the second aggregate failure rate is less than the failure rate threshold for the plurality of storage devices;

based on the second determination;

calculating a parity value using at least a portion of the data; and

writing the data and the parity value to the second set of free physical locations forming the second new RAID stripe.

17. The non-transitory computer readable medium of claim 16, the method further comprising:

prior to making the first determination;

obtaining a plurality of individual failure rates associated with the plurality of storage devices; and

determining the failure rate threshold using at least a portion of the plurality of individual failure rates.

20. The non-transitory computer readable medium of claim 16, wherein the first free physical location exhibits a highest individual failure rate across the first set of free physical locations.