Nested distributed storage unit and applications thereof

• US 9,047,217 B2
• Filed: 02/25/2010
• Issued: 06/02/2015
• Est. Priority Date: 08/27/2009
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Grube, Gary W., Markison, Timothy W.
• Primary Examiner(s): NGUYEN, STEVE N
• Application Number:
  US12/712,842
• Publication Number:
  US 20110055662A1
• Time in Patent Office: 1,923 Days
• Field of Search: 714/6.2, 714/6.24, 714/6.22, 714718- 72, 711/127, 711/5, 711/114, 711/157, 365200-201
• US Class Current: 1/1
• 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 for execution by a DS storage unit begins with the DS storage unit receiving an encoded slice of a plurality of encoded slices, wherein the plurality of encoded slices was generated from a data segment using an error encoding function. The method continues with the DS storage unit determining whether the encoded slice is to be sub-sliced using a sub-slicing encoding function. The method continues with the DS storage unit generating a plurality of encoded sub-slices from the encoded slices using the encoded sub-slicing encoding function when the encoded slice is to be sub-sliced. The method continues with the DS storage unit outputting the plurality of encoded sub-slices to a plurality of DS storage units.

Claims

1. A method comprises:

segmenting, by a dispersed storage (DS) processing module, a data object into data segments;

encoding, by the dispersed storage (DS) processing module and in accordance with a dispersed storage error encoding function, the data segments to produce a plurality of encoded data slices including slice names;

outputting, by the DS processing module, the plurality of encoded data slices to storage units of a dispersed storage network (DSN);

receiving, by one of the storage units, an encoded slice of the plurality of encoded slices;

determining, by the one of the storage units, whether the received encoded slice is to be sub-sliced using a sub-slicing error encoding function upon receiving a command to generate a plurality of encoded sub-slices;

when the encoded slice is to be sub-sliced, encoding, by the one of the storage units and in accordance with the sub-slicing error encoding function, the encoded slice to produce a plurality of encoded sub-slices; and

outputting, by the one of the storage units, the plurality of encoded sub-slices to a set of storage units.

2. The method of claim 1, wherein the outputting the plurality of encoded sub-slices further comprises:

outputting the plurality of encoded sub-slices to the set of storage units, wherein the set of storage units includes at least one of the storage units.

3. The method of claim 1, wherein the determining whether the encoded slice is to be sub-sliced further comprises:

determining to sub-slice the encoded slice based on at least one of;

retrieval latency for each of the set of storage units;

priority of the encoded slice;

a data type of the data segment;

availability of each of the set of storage units; and

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

4. The method of claim 1 further comprises:

selecting one of a plurality of sub-slicing error encoding functions as the sub-slicing encoding function, wherein the plurality of sub-slicing error encoding functions includes the error encoding function.

5. The method of claim 1 further comprises:

maintaining a list of the set of storage units storing the plurality of encoded sub-slices.

6. The method of claim 5 further comprises:

sending the list to the DS processing module.

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

outputting a command with an encoded sub-slice of the plurality of encoded sub-slices to enable further sub-slicing of the encoded sub-slice; and

outputting a command with at least one of the plurality of encoded sub-slices to prohibit further sub-slicing of the at least one of the plurality of encoded sub-slices.

8. A non-transitory computer readable storage device comprises:

a first section for storing operational instructions that, when executed by a dispersed storage (DS) processing module, causes the DS processing module to;

segment a data object into data segments;

encode, in accordance with a dispersed storage error encoding function, the data segments to produce a plurality of encoded data slices including slice names;

output, via a computing device interface, the plurality of encoded data slices to storage units of a dispersed storage network (DSN);

a second section for storing operational instructions that, when executed by one of the storage units, causes the one of the storage units to;

receive an encoded slice of the plurality of encoded slices;

determine whether the encoded slice is to be sub-sliced using a sub-slicing error encoding function upon receiving a command via the computing device interface to generate a plurality of encoded sub-slices;

when the encoded slice is to be sub-sliced, encode, in accordance with the sub-slicing error encoding function, the encoded slice to produce a plurality of encoded sub-slices; and

output at least some of the plurality of encoded sub-slices to a plurality of storage units;

outputting, by the one of the storage units, the plurality of encoded sub-slices to a set of storage units.

9. The non-transitory computer readable storage device of claim 8, wherein the second section further comprises operational instructions that, when executed by the one of the storage units, causes the one of the storage units to output the plurality of encoded sub-slices by:

outputting the plurality of encoded sub-slices to the set of storage units, wherein the set of storage units includes at least one of the storage units.

10. The non-transitory computer readable storage device of claim 8, wherein the second section further comprises operational instructions that, when executed by the one of the storage units, causes the one of the storage units to determine whether the encoded slice is to be sub-sliced further by:

determining to sub-slice the encoded slice based on at least one of;

retrieval latency for each of the plurality of storage units;

priority of the encoded slice;

a data type of the data segment;

availability of each of the set of storage units; and

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

11. The non-transitory computer readable storage device of claim 8, wherein the second section further comprises operational instructions that, when executed by the one of the storage units, causes the one of the storage units to:

select one of a plurality of sub-slicing error encoding functions as the sub-slicing error encoding function, wherein the plurality of sub-slicing error encoding functions includes the error encoding function.

12. The non-transitory computer readable storage device of claim 8, wherein the second section further comprises operational instructions that, when executed by the one of the storage units, causes the one of the storage units to:

maintain a list of the set of storage units storing the plurality of encoded sub-slices in a memory.

13. The non-transitory computer readable storage device of claim 8, wherein the second section further comprises operational instructions that, when executed by the one of the storage units, causes the one of the storage units to:

send list to the DS processing module.

14. The non-transitory computer readable storage device of claim 8, wherein the second section further comprises operational instructions that, when executed by the one of the storage units, causes the one of the storage units to at least one of:

generate a first command to enable further sub-slicing of the encoded sub-slice; and

generate a second command to prohibit further sub-slicing of the encoded sub-slice.

15. A method comprises:

segmenting, by a dispersed storage (DS) processing module, a data object into data segments;

encoding, by the dispersed storage (DS) processing module and in accordance with a dispersed storage error encoding function, the data segments to produce a plurality of encoded data slices;

outputting, by the DS processing module, the plurality of encoded data slices to storage units of a dispersed storage network (DSN);

receiving, by one of the storage units, an encoded slice of the plurality of encoded slices;

determining, by the one of the storage units, whether the encoded slice is to be sub-sliced using a sub-slicing error encoding function;

when the encoded slice is to be sub-sliced, encoding, by the one of the storage units and in accordance with the sub-slicing error encoding function, the encoded slice to produce a plurality of encoded sub-slices;

outputting a command with an encoded sub-slice of the plurality of encoded sub-slices to enable further sub-slicing of the encoded sub-slice; and

outputting, by the one of the storage units, the plurality of further sub-sliced encoded sub-slices to a set of storage units.

16. The method of claim 15 further comprising outputting a command with at least one of the plurality of encoded sub-slices to prohibit further sub-slicing of the at least one of the plurality of encoded sub-slices.

17. The method of claim 15, wherein the determining whether the encoded slice is to be sub-sliced further comprises:

receiving a command to generate the plurality of encoded sub-slices.

18. The method of claim 15, wherein the determining whether the encoded slice is to be sub-sliced further comprises:

determining to sub-slice the encoded slice based on at least one of;

retrieval latency for each of the set of storage units;

priority of the encoded slice;

a data type of the data segment;

availability of each of the set of storage units; and

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