Parallel partial repair of storage

• US 10,740,198 B2
• Filed: 12/22/2016
• Issued: 08/11/2020
• Est. Priority Date: 12/22/2016
• Status: Active Grant

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.), Purdue Research Foundation (The Trustees of Purdue University (d/b/a Purdue University))
• Original Assignee: Purdue Research Foundation (The Trustees of Purdue University (d/b/a Purdue University))
• Inventors: Panta, Rajesh, Ra, Moo-Ryong, Bagchi, Saurabh, Mitra, Subrata
• Primary Examiner(s): Leibovich, Yair
• Application Number:
  US15/387,770
• Publication Number:
  US 20180181471A1
• Time in Patent Office: 1,328 Days
• Field of Search: 714 63
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/1662 the resynchronized component or unit being a persistent storage device re-synchronization of failed mirror storage G06F11/2082; rebuild or reconstruction of parity RAID storage G06F11/1008

Abstract

A reconstruction may be divided into a set of partial operations and scheduled in parallel using a distributed protocol which overlays a reduction tree to aggregate the results. In addition, a scheduling algorithm called multiple partial parallel repair is introduced for handling concurrent failures. Multiple reconstructions may be coordinated in parallel while working to minimize the conflict for shared resources.

Claims

1. A computer-implemented method for repair of storage, the computer-implemented method comprising:

detecting, by a processor of a first server, an indication of data loss in storage of the first server;

responsive to receiving the indication of data loss,

determining, by the processor, a destination server to host a completed repair of the lost data; and

determining, by the processor, a set of servers to do partial repairs of the lost data wherein the determining of the set of servers for partial repairs is based on an availability in cache of data chunks required for partial repair of the lost data; and

coordinating, by the processor, instructions to do the completed repair of the lost data on the destination server based on a combination of the partial repairs.

2. The method of claim 1, wherein the partial repairs of the lost data occurs at approximately the same time.

3. The method of claim 1, wherein the determining of the set of servers for partial repairs is further based on availability of data chunks required for partial repair of the lost data.

4. The method of claim 1, wherein the determining, by the processor, of the set of servers for partial repairs is further based on load of a candidate server.

5. The method of claim 1, wherein the determining, by the processor, of the destination server is further based on a candidate destination server belonging to a failure domain.

6. The method of claim 1, wherein the determining, by the processor, of the destination server is further based on load on a candidate destination server.

7. The method of claim 1, wherein the partial repairs of the lost data is based on a scalar multiplication of local chunk data by a decoding coefficient.

8. The method of claim 1, wherein the completed repair of the lost data on the destination server comprises an aggregate XOR operation between results of partial repairs of the lost data.

9. The method of claim 1, wherein the indication of data loss is based on a degraded read.

10. The method of claim 1, further comprising scheduling, by the processor, the completed repair of the lost data based on input output (IO) read time of the destination server.

11. A computer readable storage medium associated with repair of storage, the computer readable storage medium comprising computer executable instructions that when executed by a computing device cause said computing device to effectuate operations comprising:

detecting by a first server a data loss in storage of a second server;

responsive to receiving the indication of data loss,

determining a destination server to host a completed repair of the lost data; and

determining a set of servers to do partial repairs of the lost data, wherein the partial repairs of the lost data is based on a scalar multiplication of local chunk data by a decoding coefficient; and

coordinating, instructions to do the completed repair of the lost data on the destination server based on a combination of the partial repairs.

12. The computer readable storage medium of claim 11, wherein the partial repairs of the lost data occurs at approximately the same time.

13. The computer readable storage medium of claim 11, wherein the determining of the set of servers for partial repairs is further based on availability of data chunks required for partial repair of the lost data.

14. The computer readable storage medium of claim 11, wherein the determining of the set of servers for partial repairs is further based on load of a candidate server.

15. The computer readable storage medium of claim 11, wherein the determining of the destination server is further based on a candidate destination server belonging to a failure domain.

16. The computer readable storage medium of claim 11, wherein the determining of the destination server is further based on load on a candidate destination server.

17. The computer readable storage medium of claim 11, wherein the completed repair of the lost data on the destination server comprises an aggregate XOR operation between results of partial repairs of the lost data.

18. An apparatus associated with repair of storage, the apparatus comprising:

a processor; and

a memory coupled with the processor, the memory comprising executable instructions that when executed by the processor cause the processor to effectuate operations comprising;

detecting an indication of data loss in storage of a first server;

responsive to receiving the indication of data loss,

determining a destination server to host a completed repair of the lost data; and

determining a set of servers to do partial repairs of the lost data, wherein the partial repairs of the lost data is based on a scalar multiplication of local chunk data by a decoding coefficient; and

coordinating, instructions to do the completed repair of the lost data on the destination server based on a combination of the partial repairs.

19. The apparatus of claim 18, wherein the partial repairs of the lost data is based on a scalar multiplication of local chunk data by a decoding coefficient.

20. The apparatus of claim 18, wherein the completed repair of the lost data on the destination server comprises an aggregate XOR operation between results of partial repairs of the lost data.