DETECTING STORAGE ERRORS IN A DISPERSED STORAGE NETWORK

• US 20160147593A1
• Filed: 02/01/2016
• Published: 05/26/2016
• Est. Priority Date: 06/25/2012
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Kazi, Asimuddin, Resch, Jason K.
• Granted Patent: US 9,547,548 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/008 Reliability or availability analysis
• CPC Class Codes: G06F 11/08 Error detection or correction by redundancy in data representation, e.g. by using checking codes
• CPC Class Codes: G06F 11/10 Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
• CPC Class Codes: G06F 11/1068 in sector programmable memories, e.g. flash disk G06F11/1072 takes precedence
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 2211/109 Sector level checksum or ECC, i.e. sector or stripe level checksum or ECC in addition to the RAID parity calculation
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: H03M 13/05 using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits H03M13/2906 takes precedence
• 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: H03M 13/611 Specific encoding aspects, e.g. encoding by means of decoding

Abstract

A method includes dividing a data object into data partitions. The method further includes, for each data partition: dividing the data partition into data segments; dispersed storage error encoding the data segments to produce sets of encoded data slices; storing the sets of encoded data slices in a first set of storage units; and generating a segment allocation table regarding storage information of the sets of encoded data slices. The method further includes generating a directory of segment allocation tables. The method further includes receiving an access request regarding at least a portion of the data object. The method further includes accessing the directory to identify one or more segment allocation tables containing storage information for the at least a portion of the data object. The method further includes accessing encoded data slices of the at least the portion of the data object based on the storage information.

Claims

1. A method for execution by one or more computing devices, the method comprises:

dividing a data object into a plurality of data partitions;

for each data partition of the plurality of data partitions;

dividing the data partition into a plurality of data segments;

dispersed storage error encoding the plurality of data segments to produce a plurality of sets of encoded data slices;

storing the plurality of sets of encoded data slices in a first set of storage units of a distributed storage network (DSN);

generating a segment allocation table regarding storage information of the plurality of sets of encoded data slices;

generating a directory of a plurality of segment allocation tables from the segment allocation tables for each of the data partitions;

receiving an access request regarding at least a portion of the data object;

accessing the directory to identify one or more segment allocation tables of the plurality of segment allocation tables containing storage information for the at least a portion of the data object; and

accessing encoded data slices of the at least the portion of the data object based on the storage information of the identified segment allocation tables.

2. The method of claim 1, wherein the directory comprises:

a plurality of entries regarding the plurality of segment allocation tables, wherein an entry of the plurality of entries includes a data portion identifier field and a vault source name field, wherein the data portion identifier stores an identifier of one of the plurality of data partitions and the vault source name field stores a vault source name that is used to generate a DSN storage address for the corresponding segment allocation table.

3. The method of claim 1, wherein the segment allocation table comprises:

a start segment value source name field that stores a source name corresponds to a first set of encoded data slices of the plurality of sets of encoded data slices;

a segment size field stores a size value for the data segments, for the set of encoded data slices, or for an encoded data slice of the set of encoded data slices; and

a total length field stores a value corresponding to the number of data segments in the plurality of data segments, to the data size for the plurality of data segments, a number of sets of encoded data slices in the plurality of sets of encoded data slices, or a data size of the plurality of sets of encoded data slices.

4. The method of claim 1 further comprises:

dividing a first data partition of the plurality of data partitions into a first plurality of data segments;

dispersed storage error encoding, in accordance with first dispersed storage error encoding parameters, the first plurality of data segments to produce a first plurality of sets of encoded data slices;

storing the first plurality of sets of encoded data slices in the first set of storage units;

dividing a second data partition of the plurality of data partitions into a second plurality of data segments;

dispersed storage error encoding, in accordance with second dispersed storage error encoding parameters, the second plurality of data segments to produce a second plurality of sets of encoded data slices; and

storing the second plurality of sets of encoded data slices in a second set of storage units of the DSN.

5. The method of claim 1 further comprises:

dispersed storage error encoding the segment allocation table to produce a set of encoded SAT encoded slices; and

storing the set of encoded SAT encoded slices in storage units of the DSN.

6. The method of claim 1 further comprises:

when the access request is a read request, wherein the accessing encoded data slices of the portion of the data object based on the storage information of the identified segment allocation tables further includes;

identifying DSN addresses for a particular plurality of sets of encoded data slices corresponding to a data portion of the at least the portion of the data object;

retrieving a decode threshold number of encoded data slices for each set of the plurality of sets of encoded data slices; and

recovering the data portion of the at least the portion of the data object from the decode threshold number of encoded data slices for each set of the plurality of sets of encoded data slices.

7. A computing device comprises:

an interface;

memory; and

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

divide a data object into a plurality of data partitions;

for each data partition of the plurality of data partitions;

divide the data partition into a plurality of data segments;

dispersed storage error encode the plurality of data segments to produce a plurality of sets of encoded data slices;

output, via the interface, the plurality of sets of encoded data slices to a first set of storage units of a distributed storage network (DSN) for storage therein;

generate a segment allocation table regarding storage information of the plurality of sets of encoded data slices;

generate a directory of a plurality of segment allocation tables from the segment allocation tables for each of the data partitions;

receive an access request regarding at least a portion of the data object;

access the directory to identify one or more segment allocation tables of the plurality of segment allocation tables containing storage information for the at least a portion of the data object; and

access encoded data slices of the at least the portion of the data object based on the storage information of the identified segment allocation tables.

8. The computing device of claim 7, wherein the directory comprises:

a plurality of entries regarding the plurality of segment allocation tables, wherein an entry of the plurality of entries includes a data portion identifier field and a vault source name field, wherein the data portion identifier stores an identifier of one of the plurality of data partitions and the vault source name field stores a vault source name that is used to generate a DSN storage address for the corresponding segment allocation table.

9. The computing device of claim 7, wherein the segment allocation table comprises:

a start segment value source name field that stores a source name corresponds to a first set of encoded data slices of the plurality of sets of encoded data slices;

a segment size field stores a size value for the data segments, for the set of encoded data slices, or for an encoded data slice of the set of encoded data slices; and

a total length field stores a value corresponding to the number of data segments in the plurality of data segments, to the data size for the plurality of data segments, a number of sets of encoded data slices in the plurality of sets of encoded data slices, or a data size of the plurality of sets of encoded data slices.

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

divide a first data partition of the plurality of data partitions into a first plurality of data segments;

dispersed storage error encode, in accordance with first dispersed storage error encoding parameters, the first plurality of data segments to produce a first plurality of sets of encoded data slices;

output, via the interface, the first plurality of sets of encoded data slices to the first set of storage units for storage therein;

divide a second data partition of the plurality of data partitions into a second plurality of data segments;

dispersed storage error encode, in accordance with second dispersed storage error encoding parameters, the second plurality of data segments to produce a second plurality of sets of encoded data slices; and

output, via the interface, the second plurality of sets of encoded data slices to a second set of storage units of the DSN for storage therein.

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

dispersed storage error encode the segment allocation table to produce a set of encoded SAT encoded slices; and

output, via the interface, the set of encoded SAT encoded slices to storage units of the DSN for storage therein.

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

when the access request is a read request, wherein the accessing encoded data slices of the portion of the data object based on the storage information of the identified segment allocation tables further includes;

identify DSN addresses for a particular plurality of sets of encoded data slices corresponding to a data portion of the at least the portion of the data object;

retrieve, via the interface, a decode threshold number of encoded data slices for each set of the plurality of sets of encoded data slices; and

recover the data portion of the at least the portion of the data object from the decode threshold number of encoded data slices for each set of the plurality of sets of encoded data slices.

13. A non-transitory storage device comprises:

a first storage section that stores operational instructions that, when executed by a computing device, causes the computing device to;

divide a data object into a plurality of data partitions;

for each data partition of the plurality of data partitions;

divide the data partition into a plurality of data segments;

dispersed storage error encode the plurality of data segments to produce a plurality of sets of encoded data slices;

output the plurality of sets of encoded data slices to a first set of storage units of a distributed storage network (DSN) for storage therein;

generate a segment allocation table regarding storage information of the plurality of sets of encoded data slices;

generate a directory of a plurality of segment allocation tables from the segment allocation tables for each of the data partitions;

a second storage section that stores operational instructions that, when executed by the computing device or a second computing device, causes the computing device or the second computing device to;

receive an access request regarding at least a portion of the data object;

access the directory to identify one or more segment allocation tables of the plurality of segment allocation tables containing storage information for the at least a portion of the data object; and

access encoded data slices of the at least the portion of the data object based on the storage information of the identified segment allocation tables.

14. The non-transitory storage device of claim 13, wherein the directory comprises:

a plurality of entries regarding the plurality of segment allocation tables, wherein an entry of the plurality of entries includes a data portion identifier field and a vault source name field, wherein the data portion identifier stores an identifier of one of the plurality of data partitions and the vault source name field stores a vault source name that is used to generate a DSN storage address for the corresponding segment allocation table.

15. The non-transitory storage device of claim 13, wherein the segment allocation table comprises:

a start segment value source name field that stores a source name corresponds to a first set of encoded data slices of the plurality of sets of encoded data slices;

a segment size field stores a size value for the data segments, for the set of encoded data slices, or for an encoded data slice of the set of encoded data slices; and

a total length field stores a value corresponding to the number of data segments in the plurality of data segments, to the data size for the plurality of data segments, a number of sets of encoded data slices in the plurality of sets of encoded data slices, or a data size of the plurality of sets of encoded data slices.

16. The non-transitory storage device of claim 13, wherein the first storage section further stores operational instructions that, when executed by the computing device, causes the computing device to:

divide a first data partition of the plurality of data partitions into a first plurality of data segments;

dispersed storage error encode, in accordance with first dispersed storage error encoding parameters, the first plurality of data segments to produce a first plurality of sets of encoded data slices;

output the first plurality of sets of encoded data slices to the first set of storage units for storage therein;

divide a second data partition of the plurality of data partitions into a second plurality of data segments;

dispersed storage error encode, in accordance with second dispersed storage error encoding parameters, the second plurality of data segments to produce a second plurality of sets of encoded data slices; and

output, via the interface, the second plurality of sets of encoded data slices to a second set of storage units of the DSN for storage therein.

17. The non-transitory storage device of claim 13 further comprises:

a third storage section that stores operational instructions that, when executed by the computing device, causes the computing device to;

dispersed storage error encode the segment allocation table to produce a set of encoded SAT encoded slices; and

output the set of encoded SAT encoded slices to storage units of the DSN for storage therein.

18. The non-transitory storage device of claim 13, wherein the second storage section further stores operational instructions that, when executed by the computing device or a second computing device, causes the computing device or the second computing device to:

when the access request is a read request, wherein the accessing encoded data slices of the portion of the data object based on the storage information of the identified segment allocation tables further includes;

identify DSN addresses for a particular plurality of sets of encoded data slices corresponding to a data portion of the at least the portion of the data object;

retrieve, a decode threshold number of encoded data slices for each set of the plurality of sets of encoded data slices; and

recover the data portion of the at least the portion of the data object from the decode threshold number of encoded data slices for each set of the plurality of sets of encoded data slices.