Distributed data rebuilding

• US 10,579,450 B2
• Filed: 11/13/2018
• Issued: 03/03/2020
• Est. Priority Date: 01/30/2015
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Pure Storage, Inc.
• Inventors: Khadiwala, Ravi V., Wozniak, Ethan S., Resch, Jason K.
• Primary Examiner(s): Alphonse, Fritz
• Application Number:
  US16/189,203
• Publication Number:
  US 20190079822A1
• Time in Patent Office: 476 Days
• Field of Search: 714763, 714766, 714767
• CPC Class Codes: G06F 11/0709 in a distributed system consisting of a plurality of standalone computer nodes, e.g. clusters, client-server systems
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: H03M 13/09 Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/3761 using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

A distributed storage network (DSN) stores sets of encoded data slices in sets of storage units. A first storage unit assigned to store an encoded data slice included in a set of encoded data slices transmits a rebuild request associated with the storage error to a second storage unit. The second storage unit generates the rebuilt encoded data slice in response to the rebuild request, and transmits the rebuilt encoded data slice back to the first storage unit, which stores the rebuilt encoded data slice.

Claims

1. A method for use in a distributed storage network (DSN) storing sets of encoded data slices in sets of storage units, the method comprising:

transmitting, from a first storage unit to a second storage unit, a rebuild request associated with an encoded data slice to be rebuilt, the encoded data slice to be rebuilt being one encoded data slice of a set of encoded data slices;

generating, by the second storage unit, a rebuilt encoded data slice in response to the rebuild request;

transmitting the rebuilt encoded data slice from the second storage unit to the first storage unit; and

storing the rebuilt encoded data slice in the first storage unit.

2. The method of claim 1, further comprising:

the first storage unit selecting the second storage unit to receive the rebuild request.

3. The method of claim 1, wherein generating the rebuilt encoded data slice includes:

obtaining a decode threshold number of encoded data slices included in the set of encoded data slices from storage units other than the first storage unit.

4. The method of claim 3, wherein generating the rebuilt encoded data slice further includes:

dispersed storage error decoding the decode threshold number of encoded data slices to produce a recovered data segment; and

dispersed storage error encoding the recovered data segment to produce the rebuilt encoded data slice.

5. The method of claim 1, wherein transmitting the rebuilt encoded data slice from the second storage unit to the first storage unit includes:

generating a write slice request at the second storage unit, the write slice request including the rebuilt encoded data slice; and

transmitting the write slice request to the first storage unit.

6. The method of claim 1, further comprising:

transmitting a plurality of rebuild slice requests from the first storage unit to a plurality of different storage units, wherein each of the different storage units rebuilds a different encoded data slice in response to the plurality of rebuild slice requests.

7. The method of claim 1, further comprising:

transmitting rebuilding information from the first storage unit to the second storage unit, the rebuilding information including one or more of an encoding matrix, a decoding matrix, or identities of storage units to be utilized for rebuilding.

8. A distributed storage network (DSN) comprising:

a set of storage units configured to store sets of encoded data slices, each storage unit included in the set of storage units including a processor and associated memory, and coupled to each other via a communications network;

a first storage unit included in the set of storage units, the first storage unit configured to;

transmit, to a second storage unit, a rebuild request associated with an encoded data slice to be rebuilt, the encoded data slice to be rebuilt being one encoded data slice of a set of encoded data slices;

the second storage unit configured to;

generate a rebuilt encoded data slice in response to the rebuild request;

transmit the rebuilt encoded data slice from the second storage unit to the first storage unit; and

the first storage unit further configured to store the rebuilt encoded data slice.

9. The distributed storage network (DSN) of claim 8, wherein the first storage unit is further configured to:

select the second storage unit to receive the rebuild request.

10. The distributed storage network (DSN) of claim 8, wherein the second storage unit is further configured to:

obtain a decode threshold number of encoded data slices included in the set of encoded data slices from storage units other than the first storage unit.

11. The distributed storage network (DSN) of claim 10, wherein the first storage unit is further configured to:

dispersed storage error decode the decode threshold number of encoded data slices to produce a recovered data segment; and

dispersed storage error encode the recovered data segment to produce the rebuilt encoded data slice.

12. The distributed storage network (DSN) of claim 8, wherein the second storage unit is further configured to:

generate a write slice request at the second storage unit, the write slice request including the rebuilt encoded data slice; and

transmit the write slice request to the first storage unit.

13. The distributed storage network (DSN) of claim 8, wherein the second storage unit is further configured to generate the rebuilt encoded data slice by:

transmit a plurality of rebuild slice requests from the first storage unit to a plurality of different storage units, wherein each of the different storage units rebuilds a different encoded data slice in response to the plurality of rebuild slice requests.

14. The distributed storage network (DSN) of claim 8, wherein the first storage unit is further configured to:

transmit rebuilding information to the second storage unit, the rebuilding information including one or more of an encoding matrix, a decoding matrix, or identities of storage units to be utilized for rebuilding.

15. A storage unit included in a set of storage units used by a distributed storage network (DSN) to store sets of encoded data slices, the storage unit comprising:

a processor and associated memory;

a plurality of distributed storage (DS) memories coupled to the processor and associated memory, the plurality of DS memories used by the processor and associated memory for storage of encoded data slices;

a network interface coupled to the processor and associated memory, the network interface configured to couple the storage unit to other storage units included in the set of storage units via a communications network;

the processor and associated memory configured to;

transmit, to another storage unit, a rebuild request associated with an encoded data slice to be rebuilt, the encoded data slice to be rebuilt being one encoded data slice of a set of encoded data slices;

receive, via the network interface, a rebuilt encoded data slice generated by the another storage unit in response to the rebuild request; and

store the rebuilt encoded data slice in the plurality of DS memories.

16. The storage unit of claim 15, wherein the processor and associated memory are further configured to:

select the another storage unit to receive the rebuild request from among the other storage units included in the set of storage units.

17. The storage unit of claim 16, wherein the processor and associated memory are further configured to:

select the another storage unit based on a rebuilding performance capability level of each candidate storage unit.

18. The storage unit of claim 15, wherein the processor and associated memory are further configured to:

transmit a plurality of rebuild slice requests to a plurality of different storage units, wherein each of the different storage units rebuilds a different encoded data slice in response to the plurality of rebuild slice requests.

19. The storage unit of claim 15, wherein the processor and associated memory are further configured to:

receive, via the network interface, a write slice request generated by the another storage unit, the write slice request including the rebuilt encoded data slice.

20. The storage unit of claim 15, wherein the processor and associated memory are further configured to:

transmit rebuilding information to the another storage unit, the rebuilding information including one or more of an encoding matrix, a decoding matrix, or identities of storage units to be utilized for rebuilding.