Systems and methods for data repair

• US 9,201,733 B2
• Filed: 03/13/2013
• Issued: 12/01/2015
• Est. Priority Date: 03/13/2013
• Status: Active Grant

• Current Assignee: Futurewei Technologies Incorporated (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Futurewei Technologies Incorporated (Huawei Investment & Holding Co., Ltd.)
• Inventors: Verma, Ajit, Hughes, James, Liu, Xian
• Primary Examiner(s): LAMARRE, GUY J
• Application Number:
  US13/800,213
• Publication Number:
  US 20140281784A1
• Time in Patent Office: 993 Days
• Field of Search: 714/752, 714/770, 714/769, 711/114
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1084 Degraded mode, e.g. caused by single or multiple storage removals or disk failures
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity

Abstract

An embodiment method for data repair in a storage system includes determining, by a processor, a minimum number of missing data blocks needed to repair a corrupted object in a first portion of the storage system, wherein the missing data blocks are not available in the first portion of the storage system, retrieving only the minimum number of missing data blocks needed to repair the corrupted object from a second portion of the storage system, and repairing the corrupted object in the first portion of the storage system using erasure codes and the retrieved minimum number of missing data blocks.

Claims

1. A method for data repair in a storage system comprising:

determining, by a processor, a minimum number of missing data blocks needed to repair a corrupted object in a first portion of the storage system using erasure codes, wherein the missing data blocks are not available in the first portion of the storage system;

retrieving only the minimum number of missing data blocks needed to repair the corrupted object from an uncorrupted copy of the corrupted object stored in a second portion of the storage system; and

repairing the corrupted object in the first portion of the storage system using erasure codes and the retrieved minimum number of missing data blocks.

2. The method of claim 1, further comprising, after repairing the corrupted object:

determining a number of missing parity information blocks associated with the repaired corrupted object; and

generating the number of missing parity information blocks associated with the repaired corrupted object.

3. The method of claim 1, wherein the first portion of the storage system is a first datacenter and the second portion of the storage system is a second datacenter.

4. The method of claim 1, wherein retrieving the minimum number of missing data blocks comprises pulling the minimum number of missing data blocks from the second portion of the storage system over a network.

5. The method of claim 1, further comprising:

storing objects in the storage system as a plurality of groups of identically-sized data blocks, wherein the corrupted object is one of the stored objects in the storage system; and

generating a number of parity information blocks associated with each group of identically-sized data blocks.

6. The method of claim 5, wherein determining the minimum number of missing data blocks needed to repair the corrupted object further comprises:

determining a number of available data blocks in a group of data blocks needing repair, wherein the group of data blocks is one of the plurality of groups of identically sized data blocks of the corrupted object;

determining a number of available parity information blocks associated with the group of data blocks; and

determining the minimum number of missing data blocks, wherein the minimum number of missing data blocks is a difference between a minimum number of data blocks required to repair the group of data blocks and the number of available data blocks plus the number of available parity information blocks.

7. The method of claim 6, wherein the minimum number of data blocks required to repair the group of data blocks corresponds to the number of parity information blocks associated with each group of data blocks.

8. The method of claim 5, wherein storing the objects comprises storing the objects as a plurality of groups of twelve one-megabyte data blocks, and wherein generating the number of parity information blocks comprises generating three parity information blocks associated with each group of twelve one-megabyte data blocks.

9. The method of claim 5, wherein storing the objects further comprises storing the objects in a distributed hash table (DHT) implementation.

10. A method for data repair in a storage system comprising:

determining, by a processor, a number of available data blocks in a group of data blocks needing repair in a first portion of the storage system, wherein the number of available data blocks is greater than zero;

determining a number of available parity information blocks associated with the group of data blocks in the first portion of the storage system;

comparing the number of available data blocks plus the number of available parity information blocks with a minimum number of blocks needed to repair the group of data blocks using erasure codes;

determining a total number of missing data blocks needed to repair the group of data blocks, wherein the total number of missing data blocks is a difference between the minimum number of blocks and the number of available data blocks plus the number of available parity information blocks;

retrieving the total number of missing data blocks from a copy of the group of data blocks stored in a remote portion of the storage system, wherein the remote portion of the storage system is separate from the first portion of the storage system; and

repairing the group of data blocks in the first portion of the storage system using the retrieved total number of missing data blocks, the available data blocks in the first portion of the storage system, and the available parity information blocks in the first portion of the storage system.

11. The method of claim 10, further comprising, after repairing the group of data blocks, generating a number of missing parity information blocks when the number of available parity information blocks is less than a number of parity information blocks generated by the storage system, for each group of data blocks, wherein the number of missing parity information blocks is a difference between the number of parity information blocks generated by the storage system, and the number of available parity information blocks.

12. The method of claim 11, wherein the minimum number of blocks needed to repair the group of data blocks corresponds with the number of parity information blocks generated, by the storage system, for each group of data blocks.

13. The method of claim 10, wherein the remote portion of the storage system is a combination of multiple remote portions of the storage system.

14. The method of claim 13, wherein retrieving the total number of missing data blocks comprises:

retrieving a first number of missing data blocks from a first remote portion of the storage system;

comparing the first number of missing data blocks with the total number of missing data blocks; and

retrieving a second number of missing data blocks from a second remote portion of the storage system when the first number of missing data blocks is less than the total number of missing data blocks, wherein the second number of missing data blocks is equal to a difference between the total number of missing data blocks and the first number of missing data blocks.

15. The method of claim 14, wherein the first portion of the storage system and the first and the second remote portions of the storage system are a first, second, and third datacenter respectively.

16. A storage system comprising:

a processor; and

a computer readable storage medium storing programming for execution by the processor, the programming including instructions to repair an object needing repairs in a first portion of the storage system, wherein the instructions to repair the object include further instructions to;

determine a number of missing data blocks required to repair the object needing repairs using erasure codes;

retrieve only the number of missing data blocks from a copy of the object stored on a remote portion of the storage system, wherein the remote portion of the storage system is separate from the first portion of the storage system; and

repair the object using erasure codes and the retrieved number of missing data blocks.

17. The storage system of claim 16, wherein the programming includes further instructions to:

store the object as a plurality of identically sized groups of data blocks in the first portion of the storage system;

generate a number of parity information blocks for each of the plurality of identically sized groups of data blocks; and

store the number of parity information blocks in the first portion of the storage system.

18. The storage system of claim 16, wherein the instructions to repair the object needing repairs include further instructions to, after the instructions to repair the object, generate a number of missing parity information blocks associated with the object.

19. The storage system of claim 16, wherein the first portion of the storage system is a first datacenter, wherein the remote portion of the storage system includes a plurality of other datacenters different than the first datacenter.

20. The storage system of claim 16, wherein the instructions to retrieve the number of missing data blocks include further instructions to pull the number of missing data blocks from the remote portion of the storage system over a network.