METHOD AND APPARATUS FOR NESTED DISBURSED STORAGE

• US 20110055661A1
• Filed: 02/25/2010
• Published: 03/03/2011
• Est. Priority Date: 08/27/2009
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: GRUBE, GARY W., MARKISON, TIMOTHY W.
• Granted Patent: US 8,949,695 B2
• Time in Patent Office: Days
• US Class Current: 714/763
• CPC Class Codes: G06F 11/1008 in individual solid state devices G06F11/1004 takes precedence
• CPC Class Codes: G06F 11/1088 Reconstruction on already foreseen single or plurality of spare disks
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 21/6272 by registering files or documents with a third party
• CPC Class Codes: H04L 63/126 the source of the received data

Abstract

A method begins by a DS processing module generating a plurality of encoded slices from a data segment using an error encoding function. The method continues with the DS processing module identifying a plurality of DS storage units for storing the plurality of encoded slices. The method continues with the DS processing module selecting an encoded slice of the plurality of encoded slices for sub-slicing using a sub-slicing encoding function to produce a selected encoded slice. The method continues with the DS processing module outputting the plurality of encoded slices to the plurality of DS storage units. The method continues with the DS processing module outputting a command to a DS storage unit of the plurality of DS storage units corresponding to the selected encoded slice, wherein the command includes an instruction to sub-slice the selected encoded slice.

Claims

1. A method for execution by a distributed storage (DS) processing unit, the method comprises:

generating a plurality of encoded slices from a data segment using an error encoding function;

identifying a plurality of DS storage units for storing the plurality of encoded slices;

selecting an encoded slice of the plurality of encoded slices for sub-slicing using a sub-slicing encoding function to produce a selected encoded slice;

outputting the plurality of encoded slices to the plurality of DS storage units; and

outputting a command to a DS storage unit of the plurality of DS storage units corresponding to the selected encoded slice, wherein the command includes an instruction to sub-slice the selected encoded slice.

2. The method of claim 1 further comprises:

maintaining a list of the DS storage units of the plurality of DS storage units for storing the plurality of encoded slices less the selected encoded slice; and

maintaining in the list the DS storage unit receiving the command.

3. The method of claim 1, wherein the command further comprises at least one of:

an instruction to send at least one of a plurality of encoded sub-slices for further sub-slicing, wherein the plurality of encoded sub-slices is generated by encoding the selected encoded slice using the sub-slicing encoding function;

an instruction for storing a plurality of encoded sub-slices in a second plurality of DS storage units, wherein the plurality of encoded sub-slices is generated by encoding the selected encoded slice using the sub-slicing encoding function; and

an instruction to use one of a plurality of sub-slicing encoding functions as the sub-slicing encoding function, wherein the plurality of sub-slicing encoding functions includes the error encoding function.

4. The method of claim 1, wherein the selecting the encoded slice comprises:

determining a security threshold for the plurality of encoded slices based on a read threshold of the error encoding function; and

selecting a set of encoded slices from the plurality of encoded slices based on the security threshold, wherein the set of encoded slices includes the selected encoded slice.

5. The method of claim 1, wherein the selecting the encoded slice comprises at least one of:

determining retrieval latency for each of the plurality of DS storage units;

determining priority of the selected encoded slice;

determining a data type of the data segment;

determining availability of each of the plurality of DS storage units; and

determining cost of storing an encoded slice of the plurality of encoded slices in each of the plurality of DS storage units.

6. The method of claim 1 further comprises:

outputting a second command to the plurality of DS storage units less the DS storage unit, wherein the second command includes an instruction not to perform a sub-slicing encoding function on a corresponding one of the plurality of encoded slices.

7. The method of claim 1 further comprises at least one of:

receiving, from the DS storage unit, information regarding the sub-slicing encoding function;

receiving, from the DS storage unit, information regarding a plurality of encoded sub-slices, wherein the plurality of encoded sub-slices is generated by encoding the selected encoded slice using the sub-slicing encoding function; and

receiving, from the DS storage unit, information regarding a second plurality of DS storage units identified for storing the plurality of encoded sub-slices.

8. A method for execution by a distributed storage (DS) processing unit, the method comprises:

generating a plurality of encoded slices from a data segment using an error encoding function;

selecting an encoded slice of the plurality of encoded slices for sub-slicing to produce a selected encoded slice;

generating a plurality of encoded sub-slices from the selected encoded slice using a sub-slicing encoding function;

outputting the plurality of encoded slices, less the selected encoded slice, to a first plurality of DS storage units; and

outputting the plurality of encoded sub-slices to a second plurality of DS storage units.

9. The method of claim 8 further comprises:

maintaining a list of the DS storage units of the first plurality of DS storage units for storing the plurality of encoded slices less the selected encoded slice; and

maintaining a list of the DS storage units of the second plurality of DS storage units for storing the plurality of encoded sub-slices.

10. The method of claim 8, wherein the selecting the encoded slice comprises:

determining a security threshold for the plurality of encoded slices based on a read threshold of the error encoding function; and

selecting a set of encoded slices from the plurality of encoded slices based on the security threshold, wherein the set of encoded slices includes the selected encoded slice.

11. The method of claim 8, wherein the selecting the encoded slice comprises at least one of:

determining retrieval latency for each of the first plurality of DS storage units;

determining retrieval latency for each of the second plurality of DS storage units;

determining priority of the selected encoded slice;

determining a data type of the data segment;

determining availability of each of the first plurality of DS storage units;

determining availability of each of the second plurality of DS storage units;

determining cost of storing an encoded slice of the plurality of encoded slices in each of the first plurality of DS storage units; and

determining cost of storing an encoded sub-slice of the plurality of encoded sub-slices in each of the second plurality of DS storage units.

12. The method of claim 8, wherein the generating of the plurality of encoded sub-slices comprises:

selecting a sub-slicing encoding function from a plurality of sub-slicing encoding functions to produce a selected sub-slicing encoding function, wherein the plurality of sub-slicing encoding functions includes the error encoding function; and

generating the plurality of encoded sub-slices from the selected encoded slice using the selected sub-slicing encoding function.

13. The method of claim 8 further comprises:

selecting an encoded sub-slice of the plurality of encoded sub-slices for further sub-slicing to produce a selected encoded sub-slice;

generating a plurality of encoded further sub-slices from the selected encoded sub-slice using the sub-slicing encoding function;

outputting the plurality of encoded sub-slices, less the selected encoded sub-slice, to the second plurality of DS storage units; and

outputting the plurality of encoded further sub-slices to the second plurality of DS storage units.

14. A distributed storage (DS) processing unit comprises:

a network interface; and

a processing module operable to;

generate a plurality of encoded slices from a data segment using an error encoding function;

identify a plurality of DS storage units for storing the plurality of encoded slices;

select an encoded slice of the plurality of encoded slices for sub-slicing using a sub-slicing encoding function to produce a selected encoded slice;

output, via the network interface, the plurality of encoded slices to the plurality of DS storage units; and

output, via the network interface, a command to a DS storage unit of the plurality of DS storage units corresponding to the selected encoded slice, wherein the command includes an instruction to sub-slice the selected encoded slice.

15. The DS storage unit of claim 14 further comprises:

memory, wherein the processing module is further operable to;

maintain, in the memory, a list of the DS storage units of the plurality of DS storage units for storing the plurality of encoded slices less the selected encoded slice; and

maintain in the list the DS storage unit receiving the command.

16. The DS storage unit of claim 14, wherein the command further comprises at least one of:

an instruction to send at least one of a plurality of encoded sub-slices for further sub-slicing, wherein the plurality of encoded sub-slices is generated by encoding the selected encoded slice using the sub-slicing encoding function;

an instruction for storing a plurality of encoded sub-slices in a second plurality of DS storage units, wherein the plurality of encoded sub-slices is generated by encoding the selected encoded slice using the sub-slicing encoding function; and

an instruction to use one of a plurality of sub-slicing encoding functions as the sub-slicing encoding function, wherein the plurality of sub-slicing encoding functions includes the error encoding function.

17. The DS storage unit of claim 14, wherein the processing module further functions to select the encoded slice by:

determining a security threshold for the plurality of encoded slices based on a read threshold of the error encoding function; and

selecting a set of encoded slices from the plurality of encoded slices based on the security threshold, wherein the set of encoded slices includes the selected encoded slice.

18. The DS storage unit of claim 14, wherein the processing module further functions to select the encoded slice by at least one of:

determining retrieval latency for each of the plurality of DS storage units;

determining priority of the selected encoded slice;

determining a data type of the data segment;

determining availability of each of the plurality of DS storage units; and

determining cost of storing an encoded slice of the plurality of encoded slices in each of the plurality of DS storage units.

19. The DS storage unit of claim 14, wherein the processing module further functions to:

output, via the network interface, a second command to the plurality of DS storage units less the DS storage unit, wherein the second command includes an instruction not to perform a sub-slicing encoding function on a corresponding one of the plurality of encoded slices.

20. The DS storage unit of claim 14, wherein the processing module further functions to receive from the DS storage unit via the network interface at least one of:

information regarding the sub-slicing encoding function;

information regarding a plurality of encoded sub-slices, wherein the plurality of encoded sub-slices is generated by encoding the selected encoded slice using the sub-slicing encoding function; and

information regarding a second plurality of DS storage units identified for storing the plurality of encoded sub-slices.

21. A distributed storage (DS) processing unit comprises:

a network interface; and

a processing module operable to;

generate a plurality of encoded slices from a data segment using an error encoding function;

select an encoded slice of the plurality of encoded slices for sub-slicing to produce a selected encoded slice;

generate a plurality of encoded sub-slices from the selected encoded using a sub-slicing encoding function;

output, via the network interface, the plurality of encoded slices, less the selected encoded slice, to a first plurality of DS storage units; and

output, via the network interface, the plurality of encoded sub-slices to a second plurality of DS storage units.

22. The DS processing unit of claim 21, wherein the processing module further functions to:

maintain a list of the DS storage units of the first plurality of DS storage units for storing the plurality of encoded slices less the selected encoded slice; and

maintain a list of the DS storage units of the second plurality of DS storage units for storing the plurality of encoded sub-slices.

23. The DS processing unit of claim 21, wherein the processing module further functions to select the encoded slice by:

determining a security threshold for the plurality of encoded slices based on a read threshold of the error encoding function; and

selecting a set of encoded slices from the plurality of encoded slices based on the security threshold, wherein the set of encoded slices includes the selected encoded slice.

24. The DS processing unit of claim 21, wherein the processing module further functions to select the encoded slice by at least one of:

determining retrieval latency for each of the first plurality of DS storage units;

determining retrieval latency for each of the second plurality of DS storage units;

determining priority of the selected encoded slice;

determining a data type of the data segment;

determining availability of each of the first plurality of DS storage units;

determining availability of each of the second plurality of DS storage units;

determining cost of storing an encoded slice of the plurality of encoded slices in each of the first plurality of DS storage units; and

determining cost of storing an encoded sub-slice of the plurality of encoded sub-slices in each of the second plurality of DS storage units.

25. The DS processing unit of claim 21, wherein the processing module further functions to generate the plurality of encoded sub-slices by:

selecting a sub-slicing encoding function from a plurality of sub-slicing encoding functions to produce a selected sub-slicing encoding function wherein the plurality of sub-slicing encoding functions includes the error encoding function; and

generating the plurality of encoded sub-slices from the selected encoded slice using the selected sub-slicing encoding function.

26. The DS processing unit of claim 21, wherein the processing module further functions to:

select an encoded sub-slice of the plurality of encoded sub-slices for further sub-slicing to produce a selected encoded sub-slice;

generate a plurality of encoded further sub-slices from the selected encoded sub-slice using the sub-slicing encoding function;

output the plurality of encoded sub-slices, less the selected encoded sub-slice, to the second plurality of DS storage units; and

output the plurality of encoded further sub-slices to the second plurality of DS storage units.