RETRIEVING DATA SEGMENTS FROM A DISPERSED STORAGE NETWORK

• US 20120166757A1
• Filed: 12/01/2011
• Published: 06/28/2012
• Est. Priority Date: 12/22/2010
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Volvovski, Ilya, Baptist, Andrew, Leggette, Wesley, Resch, Jason K.
• Granted Patent: US 9,170,882 B2
• Time in Patent Office: Days
• US Class Current: 711/206
• 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 begins by a processing module receiving a file retrieval request for a file, wherein the file includes one or more data regions, and wherein a data region of the one or more data regions is divided into a plurality of data segments and stored as a plurality of sets of encoded data slices in a dispersed storage network (DSN) memory. The method continues with the processing module retrieving a segment allocation table (SAT), wherein a SAT entry of a plurality of SAT entries includes information regarding storing the data region in the DSN memory and a segmentation scheme regarding the dividing of the data region into the plurality of data segments. The method continues with the processing module identifying the plurality of sets of encoded data slices and retrieving at least a sufficient number of the plurality of sets of encoded data slices to regenerate the data region.

Claims

1. A method comprises:

receiving a file retrieval request for a file, wherein the file includes one or more data regions, and wherein a data region of the one or more data regions is divided into a plurality of data segments and stored as a plurality of sets of encoded data slices in a dispersed storage network (DSN) memory;

retrieving a segment allocation table (SAT) based on the file retrieval request, wherein the SAT includes a plurality of entries, and wherein an entry of the plurality of entries includes information regarding storing the data region in the DSN memory and a segmentation scheme regarding the dividing of the data region into the plurality of data segments;

identifying the plurality of sets of encoded data slices based on the segmentation scheme and the information regarding storing the data region; and

retrieving at least a sufficient number of the plurality of sets of encoded data slices to regenerate the data region.

2. The method of claim 1, wherein the identifying the plurality of sets of encoded data slices comprises:

identifying the plurality of data segments based on the segmentation scheme; and

identifying the plurality of sets of encoded data slices based on the plurality of data segments and the information regarding storing the data region.

3. The method of claim 1, wherein the identifying the plurality of sets of encoded data slices further comprises:

extracting a start segment vault source name and a total length of the data region from the information regarding storing the data region;

extracting a segment size and a segmentation approach from the segmentation scheme;

generating a plurality of segment vault source names for the plurality of data segments based on the start segment vault source name, the total length of the data region, the segment size, and the segmentation approach; and

generating a plurality of sets of slices names for the plurality of sets of encoded data slices based on the plurality of segment vault source names.

4. The method of claim 1 further comprises:

identifying a second entry of the segment allocation table corresponding to a second data region of the one or more data regions, wherein the second entry includes second information regarding storing the second data region in the DSN memory and a second segmentation scheme regarding the dividing of the second data region into a second plurality of data segments;

identifying a second plurality of sets of encoded data slices based on the second segmentation scheme and the second information regarding storing the second data; and

retrieving at least a sufficient number of the second plurality of sets of encoded data slices to regenerate the second data region.

5. The method of claim 1 further comprises:

receiving the file retrieval request, wherein the file includes a plurality of data regions as the one or more data regions;

identifying corresponding entries of the plurality of entries in the segment allocation table for the plurality of data regions;

identifying corresponding pluralities of sets of encoded data slices based on corresponding segmentation schemes and corresponding information regarding storing the corresponding data region from the corresponding entries; and

retrieving at least a sufficient number of the corresponding pluralities of sets of encoded data slices to regenerate the file.

6. A method comprises:

receiving a file retrieval request for a file, wherein the file includes one or more data regions, and wherein a data region of the one or more data regions is divided into a plurality of data segments and stored as a plurality of sets of encoded data slices in a dispersed storage network (DSN) memory; and

for the data region;

estimating information regarding storing the data region in the DSN memory and a segmentation scheme regarding the dividing of the data region into the plurality of data segments to produce estimated information and an estimated segmentation scheme;

retrieving at least some of the plurality of sets of encoded data slices based on the estimated segmentation scheme and the estimated information;

retrieving a segment allocation table (SAT) based on the file retrieval request, wherein the SAT includes a plurality of entries, and wherein an entry of the plurality of entries includes actual information regarding storing the data region in the DSN memory and an actual segmentation scheme regarding the dividing of the data region into the plurality of data segments;

comparing the estimated information and the estimated segmentation scheme with the actual information regarding storing the data region and the actual segmentation scheme; and

when the comparison is favorable, regenerating the data region from the at least some of the plurality of sets of encoded data slices.

7. The method of claim 6 further comprises:

when the comparison is unfavorable due to a lack of sets of encoded data slices, retrieving additional sets of encoded data slices based on a difference between the estimated information, the estimated segmentation scheme, the actual information regarding storing the data region, and the actual segmentation scheme.

8. The method of claim 6 further comprises:

when the comparison is unfavorable due to an excess of sets of encoded data slices, sending a cancellation message for the excess sets of encoded data slices based on a difference between the estimated information, the estimated segmentation scheme, the actual information regarding storing the data region, and the actual segmentation scheme.

9. The method of claim 6, wherein the retrieving at least some of the plurality of sets of encoded data slices comprises:

extracting a start segment vault source name and a total length of the data region from the estimated information;

extracting a segment size and a segmentation approach from the estimated segmentation scheme;

generating a plurality of segment vault source names for the plurality of data segments based on the start segment vault source name, the total length of the data region, the segment size, and the segmentation approach; and

generating a plurality of sets of slices names for the at least some of the plurality of sets of encoded data slices based on the plurality of segment vault source names.

10. The method of claim 6 further comprises:

for second data region of the one or more data regions;

estimating second information regarding storing the second data region in the DSN memory and a second segmentation scheme regarding dividing of the second data region into a second plurality of data segments to produce second estimated information and a second estimated segmentation scheme;

retrieving at least some of a second plurality of sets of encoded data slices based on the second estimated segmentation scheme and the second estimated information;

accessing a second entry of the segment allocation table, wherein the second entry includes second actual information regarding storing the second data region in the DSN memory and a second actual segmentation scheme regarding the dividing of the second data region into the second plurality of data segments;

comparing the second estimated information and the second estimated segmentation scheme with the second actual information regarding storing the data region and the second actual segmentation scheme; and

when the comparison is favorable, regenerating the second data region from the at least some of the second plurality of sets of encoded data slices.

11. A dispersed storage (DS) module comprises:

a first module for facilitating receiving a file retrieval request for a file, wherein the file includes one or more data regions, and wherein a data region of the one or more data regions is divided into a plurality of data segments and stored as a plurality of sets of encoded data slices in a dispersed storage network (DSN) memory;

a second module for facilitating retrieving a segment allocation table (SAT) based on the file retrieval request, wherein the SAT includes a plurality of entries, and wherein an entry of the plurality of entries includes information regarding storing the data region in the DSN memory and a segmentation scheme regarding the dividing of the data region into the plurality of data segments;

a third module for identifying the plurality of sets of encoded data slices based on the segmentation scheme and the information regarding storing the data region; and

a fourth module for facilitating retrieving at least a sufficient number of the plurality of sets of encoded data slices to regenerate the data region.

12. The DS module of claim 11, wherein the third module identifies the plurality of sets of encoded data slices by:

identifying the plurality of data segments based on the segmentation scheme; and

identifying the plurality of sets of encoded data slices based on the plurality of data segments and the information regarding storing the data region.

13. The DS module of claim 11, wherein the third module further identifies the plurality of sets of encoded data slices by:

extracting a start segment vault source name and a total length of the data region from the information regarding storing the data region;

extracting a segment size and a segmentation approach from the segmentation scheme;

generating a plurality of segment vault source names for the plurality of data segments based on the start segment vault source name, the total length of the data region, the segment size, and the segmentation approach; and

generating a plurality of sets of slices names for the plurality of sets of encoded data slices based on the plurality of segment vault source names.

14. The DS module of claim 11 further comprises:

a fifth module for identifying a second entry of the segment allocation table corresponding to a second data region of the one or more data regions, wherein the second entry includes second information regarding storing the second data region in the DSN memory and a second segmentation scheme regarding the dividing of the second data region into a second plurality of data segments;

the third module for identifying a second plurality of sets of encoded data slices based on the second segmentation scheme and the second information regarding storing the second data; and

the fourth module for facilitating retrieving at least a sufficient number of the second plurality of sets of encoded data slices to regenerate the second data region.

15. The DS module of claim 11 further comprises:

the first module for facilitating receiving the file retrieval request, wherein the file includes a plurality of data regions as the one or more data regions;

a fifth module for identifying corresponding entries of the plurality of entries in the segment allocation table for the plurality of data regions;

the third module for identifying corresponding pluralities of sets of encoded data slices based on corresponding segmentation schemes and corresponding information regarding storing the corresponding data region from the corresponding entries; and

the fourth module for facilitating retrieving at least a sufficient number of the corresponding pluralities of sets of encoded data slices to regenerate the file.

16. A dispersed storage (DS) module comprises:

a first module for facilitating receiving a file retrieval request for a file, wherein the file includes one or more data regions, and wherein a data region of the one or more data regions is divided into a plurality of data segments and stored as a plurality of sets of encoded data slices in a dispersed storage network (DSN) memory; and

for the data region;

a second module for estimating information regarding storing the data region in the DSN memory and a segmentation scheme regarding the dividing of the data region into the plurality of data segments to produce estimated information and an estimated segmentation scheme;

a third module for;

facilitating retrieving at least some of the plurality of sets of encoded data slices based on the estimated segmentation scheme and the estimated information; and

facilitating retrieving a segment allocation table (SAT) based on the file retrieval request, wherein the SAT includes a plurality of entries, and wherein an entry of the plurality of entries includes actual information regarding storing the data region in the DSN memory and an actual segmentation scheme regarding the dividing of the data region into the plurality of data segments;

a fourth module for comparing the estimated information and the estimated segmentation scheme with the actual information regarding storing the data region and the actual segmentation scheme; and

a fifth module for regenerating the data region from the at least some of the plurality of sets of encoded data slices when the comparison is favorable.

17. The DS module of claim 16 further comprises:

the third module for facilitating retrieving additional sets of encoded data slices based on a difference between the estimated information, the estimated segmentation scheme, the actual information regarding storing the data region, and the actual segmentation scheme when the comparison is unfavorable due to a lack of sets of encoded data slices.

18. The DS module of claim 16 further comprises:

a sixth module for sending a cancellation message for the excess sets of encoded data slices based on a difference between the estimated information, the estimated segmentation scheme, the actual information regarding storing the data region, and the actual segmentation scheme when the comparison is unfavorable due to an excess of sets of encoded data slices.

19. The DS module of claim 16, wherein the third module retrieves at least some of the plurality of sets of encoded data slices by:

extracting a start segment vault source name and a total length of the data region from the estimated information;

extracting a segment size and a segmentation approach from the estimated segmentation scheme;

generating a plurality of segment vault source names for the plurality of data segments based on the start segment vault source name, the total length of the data region, the segment size, and the segmentation approach; and

generating a plurality of sets of slices names for the at least some of the plurality of sets of encoded data slices based on the plurality of segment vault source names.

20. The DS module of claim 16 further comprises:

for second data region of the one or more data regions;

the second module for estimating second information regarding storing the second data region in the DSN memory and a second segmentation scheme regarding dividing of the second data region into a second plurality of data segments to produce second estimated information and a second estimated segmentation scheme;

the third module for;

facilitating retrieving at least some of a second plurality of sets of encoded data slices based on the second estimated segmentation scheme and the second estimated information; and

accessing a second entry of the segment allocation table, wherein the second entry includes second actual information regarding storing the second data region in the DSN memory and a second actual segmentation scheme regarding the dividing of the second data region into the second plurality of data segments;

the fourth module for comparing the second estimated information and the second estimated segmentation scheme with the second actual information regarding storing the data region and the second actual segmentation scheme; and

the fifth module for regenerating the second data region from the at least some of the second plurality of sets of encoded data slices when the comparison is favorable.