Retrieving data segments from a dispersed storage network

• US 9,927,977 B2
• Filed: 02/07/2017
• Issued: 03/27/2018
• Est. Priority Date: 12/22/2010
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Volvovski, Ilya, Baptist, Andrew, Leggette, Wesley, Resch, Jason K.
• Primary Examiner(s): Dudek, Jr., Edward J
• Application Number:
  US15/426,698
• Publication Number:
  US 20170147218A1
• Time in Patent Office: 413 Days
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 12/1009 using page tables, e.g. page table structures
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/128 Details of file system snapshots on the file-level, e.g. snapshot creation, administration, deletion use of snapshots for error detection or correction G06F11/14, G06F11/16
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD
• 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 method includes generating a plurality of segment allocation tables (SATs) for pluralities of sets of encoded data slices. For a first SAT, the method further includes dispersed storage error encoding the first SAT to produce a first set of encoded SAT slices. The method further includes generating a first source name for the first plurality of sets of encoded data slices and the first SAT based on an object identifier associated with the data object. The method further includes generating, based on the first source name, a first plurality of sets of slices names for the first plurality of sets of encoded data slices and the first set of encoded SAT slices. The method further includes outputting, based on the first plurality of sets of slices names, the first plurality of sets of encoded data slices and the first set of encoded SAT slices to storage units.

Claims

1. A method for execution by a computing device of a dispersed storage network (DSN), the method comprises:

dispersed storage error encoding a data object into pluralities of sets of encoded data slices, wherein a region of the data object includes a set of contiguous data segments of the data object, and wherein encoding of the set of contiguous data segments corresponds to one of the pluralities of sets of encoded data slices;

generating a plurality of segment allocation tables (SATs) for the pluralities of sets of encoded data slices, wherein a first SAT of the plurality of SATs corresponds to a first plurality of sets of encoded data slices of the pluralities of sets of encoded data slices;

dispersed storage error encoding the first SAT to produce a first set of encoded SAT slices;

generating a first source name for the first plurality of sets of encoded data slices and the first SAT based on an object identifier associated with the data object;

generating, based on the first source name, a first plurality of sets of slices names for the first plurality of sets of encoded data slices and the first set of encoded SAT slices; and

outputting, based on the first plurality of sets of slices names, the first plurality of sets of encoded data slices and the first set of encoded SAT slices to storage units of the DSN for storage therein.

2. The method of claim 1, wherein the first SAT comprises one or more of:

a start segment vault source name field;

a segment size field;

a segmentation approach field; and

a total length of region field.

3. The method of claim 1, wherein generating the first plurality of sets of slices names comprises:

for a first set of encoded data slices of the first plurality of sets of encoded data slices;

generating a set of slice index values corresponding a pillar width number of the dispersed storage error encoding the data object;

generating a first segment number corresponding the first set of encoded data slices;

for a first encoded data slice of the first set of encoded data slices;

generating a first slice name of a first set of slice names of the first plurality of sets of slices based on a first slice index value of the set of slice index values, the first source name, and the first segment number.

4. The method of claim 3 further comprises:

for the first set of encoded SAT slices;

generating a reference segment number for affiliation with the first plurality of sets of encoded data slices;

for a first encoded SAT slice of the first set of encoded SAT slices;

generating a first slice name of another set of slice names of the first plurality of sets of slices based on the first slice index value of the set of slice index values, the first source name, and the reference segment number.

5. The method of claim 1 further comprises:

dispersed storage error encoding a second SAT of the plurality of SATs to produce a second set of encoded SAT slices, wherein the second SAT corresponds to a second plurality of sets of encoded data slices of the pluralities of sets of encoded data slices;

generating a second source name for the second plurality of sets of encoded data slices and the second SAT based on the object identifier;

generating, based on the second source name, a second plurality of sets of slices names for the second plurality of sets of encoded data slices and the second set of encoded SAT slices; and

outputting, based on the second plurality of sets of slices names, the second plurality of sets of encoded data slices and the second set of encoded SAT slices to the storage units.

6. The method of claim 5, wherein the second SAT comprises:

a first start segment vault source name field for the first region;

a first segment size field for the first region;

a first segmentation approach field for the first region;

a first total length of region field for the first region;

a second start segment vault source name field for the second region;

a second segment size field for the second region;

a second segmentation approach field for the second region;

a second total length of region field for the second region.

7. A computing device of a dispersed storage network (DSN), the computing device comprises:

an interface;

memory; and

a processing module operably coupled to the interface and the memory, wherein the processing module is operable to;

dispersed storage error encode a data object into pluralities of sets of encoded data slices, wherein a region of the data object includes a set of contiguous data segments of the data object, and wherein encoding of the set of contiguous data segments corresponds to one of the pluralities of sets of encoded data slices;

generate a plurality of segment allocation tables (SATs) for the pluralities of sets of encoded data slices, wherein a first SAT of the plurality of SATs corresponds to a first plurality of sets of encoded data slices of the pluralities of sets of encoded data slices;

dispersed storage error encode the first SAT to produce a first set of encoded SAT slices;

generate a first source name for the first plurality of sets of encoded data slices and the first SAT based on an object identifier associated with the data object;

generate, based on the first source name, a first plurality of sets of slices names for the first plurality of sets of encoded data slices and the first set of encoded SAT slices; and

output, via the interface and based on the first plurality of sets of slices names, the first plurality of sets of encoded data slices and the first set of encoded SAT slices to storage units of the DSN for storage therein.

8. The computing device of claim 7, wherein the first SAT comprises one or more of:

a start segment vault source name field;

a segment size field;

a segmentation approach field; and

a total length of region field.

9. The computing device of claim 7, wherein the processing module is further operable to generate the first plurality of sets of slices names by:

for a first set of encoded data slices of the first plurality of sets of encoded data slices;

generating a set of slice index values corresponding a pillar width number of the dispersed storage error encoding the data object;

generating a first segment number corresponding the first set of encoded data slices;

for a first encoded data slice of the first set of encoded data slices;

generating a first slice name of a first set of slice names of the first plurality of sets of slices based on a first slice index value of the set of slice index values, the first source name, and the first segment number.

10. The computing device of claim 9, wherein the processing module is further operable to:

for the first set of encoded SAT slices;

generate a reference segment number for affiliation with the first plurality of sets of encoded data slices;

for a first encoded SAT slice of the first set of encoded SAT slices;

generate a first slice name of another set of slice names of the first plurality of sets of slices based on the first slice index value of the set of slice index values, the first source name, and the reference segment number.

11. The computing device of claim 7, wherein the processing module is further operable to:

dispersed storage error encode a second SAT of the plurality of SATs to produce a second set of encoded SAT slices, wherein the second SAT corresponds to a second plurality of sets of encoded data slices of the pluralities of sets of encoded data slices;

generate a second source name for the second plurality of sets of encoded data slices and the second SAT based on the object identifier;

generating, based on the second source name, a second plurality of sets of slices names for the second plurality of sets of encoded data slices and the second set of encoded SAT slices; and

output, via the interface and based on the second plurality of sets of slices names, the second plurality of sets of encoded data slices and the second set of encoded SAT slices to the storage units.

12. The computing device of claim 11, wherein the second SAT comprises:

a first start segment vault source name field for the first region;

a first segment size field for the first region;

a first segmentation approach field for the first region;

a first total length of region field for the first region;

a second start segment vault source name field for the second region;

a second segment size field for the second region;

a second segmentation approach field for the second region;

a second total length of region field for the second region.