Distributed data rebuilding

• US 10,169,123 B2
• Filed: 11/17/2017
• Issued: 01/01/2019
• Est. Priority Date: 01/30/2015
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Khadiwala, Ravi V., Wozniak, Ethan S., Resch, Jason K.
• Primary Examiner(s): Alphonse, Fritz
• Application Number:
  US15/816,721
• Publication Number:
  US 20180074879A1
• Time in Patent Office: 410 Days
• Field of Search: 714764, 714766, 714770
• 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 identifies a storage error associated with that encoded data slice. The first storage unit selects a second storage unit to generate a rebuilt encoded data slice to replace the encoded data slice with the error, and transmits a rebuild request associated with the storage error to the 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:

identifying, by a first storage unit included in a set of storage units, a storage error associated with an encoded data slice of a set of encoded data slices, the encoded data slice assigned to be stored in the first storage unit;

selecting a second storage unit to generate a rebuilt encoded data slice to replace the encoded data slice assigned to be stored in the first storage unit;

transmitting, from the first storage unit to the second storage unit, a rebuild request associated with the storage error;

generating, by the second storage unit, the 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:

identifying the storage error based on a slice storage pattern of the set of storage units.

3. The method of claim 1, wherein identifying the storage error includes:

comparing a calculated integrity value to a stored integrity value associated with the encoded data slice; and

identifying a corrupted encoded data slice in response to an unfavorable comparison.

4. The method of claim 1, further comprising:

selecting the second storage unit from a plurality of candidate storage units, the selecting based on a rebuilding performance capability level of each candidate storage unit.

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, wherein generating the rebuilt encoded data slice includes:

obtaining a decode threshold number of representations of encoded data slices of the set of encoded data slices;

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

encoding the recovered data segment to produce the rebuilt encoded data slice.

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;

identify a storage error associated with an encoded data slice of a set of encoded data slices, the encoded data slice assigned to be stored in the first storage unit;

select a second storage unit to generate a rebuilt encoded data slice to replace the encoded data slice assigned to be stored in the first storage unit;

transmit, from the first storage unit to the second storage unit, a rebuild request associated with the storage error;

the second storage unit configured to;

generate the 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

a 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:

identify the storage error based on a slice storage pattern of the set of storage units.

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

compare a calculated integrity value to a stored integrity value associated with the encoded data slice; and

identify a corrupted encoded data slice in response to an unfavorable comparison.

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

select the second storage unit from a plurality of candidate storage units, wherein selection is based on a rebuilding performance capability level of each candidate storage unit.

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:

obtaining a decode threshold number of representations of encoded data slices of the set of encoded data slices;

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

encoding the recovered data segment to produce the rebuilt encoded data slice.

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;

identify a storage error associated with an encoded data slice of a set of encoded data slices, the encoded data slice assigned to the storage unit for storage;

select another storage unit to generate a rebuilt encoded data slice to replace the encoded data slice assigned to the storage unit;

transmit, via the network interface, a rebuild request associated with the storage error from the storage unit to the another storage unit;

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:

identify the storage error based on a slice storage pattern of the set of storage units.

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

compare a calculated integrity value to a stored integrity value associated with the encoded data slice; and

identify a corrupted encoded data slice in response to an unfavorable comparison.

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

select the another storage unit from a plurality of candidate storage units, wherein selection is based on a rebuilding performance capability level of each candidate storage unit.

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.