Systems and methods for improving redundant storage fault tolerance

• US 8,386,841 B1
• Filed: 07/21/2010
• Issued: 02/26/2013
• Est. Priority Date: 07/21/2010
• Status: Active Grant

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Inventors: Renade, Dilip
• Primary Examiner(s): Lottich, Joshua P
• Application Number:
  US12/840,772
• Time in Patent Office: 951 Days
• Field of Search: 714/4.1, 714/6.11, 714/6.2, 714/6.22, 714/6.23, 714/6.24, 714/6.3, 714/52
• US Class Current: 714/6.22
• CPC Class Codes: G06F 11/1088 Reconstruction on already foreseen single or plurality of spare disks
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity

Abstract

A computer-implemented method for improving redundant storage fault tolerance may include 1) identifying a plurality of storage devices storing an encoded set of data, with the encoded set of data including a redundant form of an underlying set of data, 2) determining that a subset of the plurality of storage devices have failed, 3) reconstructing encoded data lost due to the failure of the subset of the plurality of storage devices, and then 4) redundantly storing the reconstructed encoded data on the plurality of storage devices. Various other methods, systems, and computer-readable media are also disclosed.

Claims

1. A computer-implemented method for improving redundant storage fault tolerance, at least a portion of the method being performed by a computing device comprising at least one processor, the method comprising:

identifying a plurality of storage devices storing an encoded set of data, the encoded set of data comprising a redundant form of an underlying set of data;

determining that a subset of the plurality of storage devices have failed;

reconstructing encoded data lost due to the failure of the subset of the plurality of storage devices;

redundantly storing the reconstructed encoded data on the plurality of storage devices by;

identifying a level of fault tolerance for the reconstructed encoded data;

encoding the reconstructed encoded data to match the level of fault tolerance.

2. The computer-implemented method of claim 1, wherein the plurality of storage devices comprises at least one of:

at least a portion of an archival storage system;

at least a portion of a distributed storage system.

3. The computer-implemented method of claim 1, wherein reconstructing the encoded data comprises:

decoding a corresponding portion of the underlying set of data using portions of the encoded set of data that survived the failure;

re-encoding the corresponding portion of the underlying set of data.

4. The computer-implemented method of claim 1, wherein reconstructing the encoded data comprises generating the lost encoded data without fully decoding and re-encoding a corresponding portion of the underlying set of data.

5. The computer-implemented method of claim 1, wherein redundantly storing the reconstructed encoded data on the plurality of storage devices comprises storing the reconstructed encoded data in a stripe across the plurality of storage devices.

6. The computer-implemented method of claim 1, wherein the level of fault tolerance for the reconstructed encoded data comprises a level of fault tolerance for the underlying set of data.

7. The computer-implemented method of claim 1, wherein redundantly storing the reconstructed encoded data on the plurality of storage devices comprises storing metadata relating to the redundantly stored reconstructed encoded data on the plurality of storage devices.

8. The computer-implemented method of claim 7, wherein the metadata comprises at least one of:

a location of the redundantly stored reconstructed encoded data on the plurality of storage devices;

decoding information for the redundantly stored reconstructed encoded data;

information indicating that the redundantly stored reconstructed encoded data corresponds with the encoded data lost due to the failure.

9. The computer-implemented method of claim 7, wherein storing the metadata on the plurality of storage devices comprises redundantly storing the metadata on the plurality of storage devices with a higher level of fault tolerance than the redundantly stored reconstructed encoded data.

10. A system for improving redundant storage fault tolerance, the system comprising:

an identification module programmed to identify a plurality of storage devices storing an encoded set of data, the encoded set of data comprising a redundant form of an underlying set of data;

a determination module programmed to determine that a subset of the plurality of storage devices have failed;

a reconstruction module programmed to reconstruct encoded data lost due to the failure of the subset of the plurality of storage devices;

a redundancy module programmed to redundantly store the reconstructed encoded data on the plurality of storage devices by;

identifying a level of fault tolerance for the reconstructed encoded data;

encoding the reconstructed encoded data to match the level of fault tolerance;

at least one processor configured to execute the identification module, the determination module, the reconstruction module, and the redundancy module.

11. The system of claim 10, wherein the plurality of storage devices comprises at least one of:

at least a portion of an archival storage system;

at least a portion of a distributed storage system.

12. The system of claim 10, wherein the reconstruction module is programmed to reconstruct the encoded data by:

decoding a corresponding portion of the underlying set of data using portions of the encoded set of data that survived the failure;

re-encoding the corresponding portion of the underlying set of data.

13. The system of claim 10, wherein the reconstruction module is programmed to reconstruct the encoded data by generating the lost encoded data without fully decoding and re-encoding a corresponding portion of the underlying set of data.

14. The system of claim 10, wherein the redundancy module is programmed to redundantly store the reconstructed encoded data on the plurality of storage devices by storing the reconstructed encoded data in a stripe across the plurality of storage devices.

15. The system of claim 10, wherein the level of fault tolerance for the reconstructed encoded data comprises a level of fault tolerance for the underlying set of data.

16. The system of claim 10, wherein the redundancy module is programmed to redundantly store the reconstructed encoded data on the plurality of storage devices by storing metadata relating to the redundantly stored reconstructed encoded data on the plurality of storage devices.

17. The system of claim 16, wherein the metadata comprises at least one of:

a location of the redundantly stored reconstructed encoded data on the plurality of storage devices;

decoding information for the redundantly stored reconstructed encoded data;

information indicating that the redundantly stored reconstructed encoded data corresponds with the encoded data lost due to the failure.

18. A non-transitory computer-readable-storage medium comprising one or more computer-executable instructions that, when executed by at least one processor of a computing device, cause the computing device to:

identify a plurality of storage devices storing an encoded set of data, the encoded set of data comprising a redundant form of an underlying set of data;

determine that a subset of the plurality of storage devices have failed;

reconstruct encoded data lost due to the failure of the subset of the plurality of storage devices;

redundantly store the reconstructed encoded data on the plurality of storage devices by;

identifying a level of fault tolerance for the reconstructed encoded data;

encoding the reconstructed encoded data to match the level of fault tolerance.