Identifying a storage error of a data slice

• US 9,043,689 B2
• Filed: 06/30/2014
• Issued: 05/26/2015
• Est. Priority Date: 04/26/2010
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Resch, Jason K., Quigley, John, Leggette, Wesley, Baptist, Andrew
• Primary Examiner(s): ABRAHAM, ESAW T
• Application Number:
  US14/319,372
• Publication Number:
  US 20140325259A1
• Time in Patent Office: 330 Days
• Field of Search: 714/770, 714/799, 714/758, 714/6.22
• US Class Current: 714/799
• CPC Class Codes: G06F 11/0727 in a storage system, e.g. in a DASD or network based storage system drivers for digital recording or reproducing units G06F3/06; circuits for error detection or correction within digital recording or reproducing units G11B20/18; 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], H04L67/1097
• CPC Class Codes: G06F 11/076 by exceeding a count or rate limit, e.g. word- or bit count limit
• CPC Class Codes: G06F 11/0763 by bit configuration check, e.g. of formats or tags
• CPC Class Codes: G06F 11/1004 to protect a block of data words, e.g. CRC or checksum G06F11/1076 takes precedence; security arrangements for protecting computers or computer systems against unauthorized activity G06F21/00
• CPC Class Codes: G06F 11/1008 in individual solid state devices G06F11/1004 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 11/1464 for networked environments
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 21/60 Protecting data
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 21/64 Protecting data integrity, e.g. using checksums, certificates or signatures
• CPC Class Codes: G06F 21/70 Protecting specific internal or peripheral components, in which the protection of a component leads to protection of the entire computer
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: H04L 2209/30 Compression, e.g. Merkle-Damgard construction
• CPC Class Codes: H04L 2209/34 Encoding or coding, e.g. Huffman coding or error correction
• 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]
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage

Abstract

A method begins by a processing module obtaining common storage name information regarding data that is stored in storage units of a distributed storage network (DSN) as a set of data slices. Each data slice of the set of data slices has a unique storage name, where each of the unique storage names for the set of data slices has common naming information regarding the data. The method continues where the processing module interprets the common storage name information to determine whether a difference exists between the common naming information of a data slice of the set of data slices and the common naming information of other data slices of the set of data slices. When the difference exists, the method continues where the processing module indicates a potential storage error of the data slice and implements a storage error process regarding the potential storage error of the data slice.

Claims

1. A computer readable storage device for storing operational instructions regarding detecting a storage error in a dispersed storage network (DSN), the computer readable storage device comprises:

a first computer readable memory that stores operational instructions that, when executed by a processing module of a storage unit of a set of storage units of the DSN, causes the processing module to;

generate error detection information regarding related encoded data slices stored by the storage unit, wherein each of the related encoded data slices is from a different set of encoded data slices of a plurality of sets of encoded data slices, wherein a data object is encoded into the plurality of sets of encoded data slices and a data segment of the data object is encoded into one set of encoded data slices of the plurality of sets of encoded data slices; and

sending the error detection information to a computing device of the DSN; and

a second computer readable memory that stores operational instructions that, when executed by the computing device, causes the computing device to;

receive the error detection information from the set of storage units;

compare the received error detection information; and

when the error detection information from a storage unit of the set of storage units does not substantially match the error detection information of other storage units of the set of storage units, indicate that one or more of the related encoded data slices stored by the storage unit has an error.

2. The computer readable storage device of claim 1, wherein the first computer readable memory further stores operational instructions that, when executed by the processing module of the storage unit, causes the processing module to generate error detection information by:

performing a deterministic function on common storage naming information of the related encoded data slices to produce the error detection information, wherein the common storage naming information includes a data object identifier of the data object and a data segment identifier.

3. The computer readable storage device of claim 2, wherein the common storage naming information further comprises:

revision level information for each of the related encoded data slices.

4. The computer readable storage device of claim 2, wherein the first computer readable memory further stores operational instructions that, when executed by the processing module of the storage unit, causes the processing module to perform a deterministic function by:

generating a hash tree by performing a plurality of layers of hash functions, wherein a first layer of the plurality of layers of hash functions includes;

performing a hash function on first and second related encoded data slices of the related encoded data slices to produce a first hash value; and

performing the hash function on third and fourth related encoded data slices of the related encoded data slices to produce a second hash value;

wherein a final layer of the plurality of layers of hash functions includes;

performing the hash function on a final intermediate hash value and a second final intermediate hash value to produce a root hash.

5. The computer readable storage device of claim 4 further comprises:

the first computer readable memory further stores operational instructions that, when executed by the processing module of the storage unit, causes the processing module to send the root hash as the error detection information; and

the second computer readable memory further stores operational instructions that, when executed by the computing device, causes the computing device to compare the root hash functions of the set of storage units.

6. The computer readable storage device of claim 4 further comprises:

the first computer readable memory further stores operational instructions that, when executed by the processing module of the storage unit, causes the processing module to send the hash tree as the error detection information; and

the second computer readable memory further stores operational instructions that, when executed by the computing device, causes the computing device to;

compare the root hash functions of the set of storage units;

when the root hash from the storage unit does not substantially match the root hash of the other storage units;

compare layers of hash values of the hash tree of the storage unit with the layers of hash values of the hash trees of the other storage units to identify the one or more related encoded data slices stored by the storage unit having the error.

7. The computer readable storage device of claim 1, wherein the second computer readable memory that stores operational instructions that, when executed by the computing device, causes the computing device to:

initiate a rebuild process to rebuild or replace the one or more of the related encoded data slices stored by the storage unit having the error.

8. A computer readable storage device comprises:

a first computer readable memory section that stores operational instructions that, when executed by a processing module of a storage unit of a set of storage units of a dispersed storage network (DSN), causes the processing module to;

identify related encoded data slices stored by the storage unit, wherein each of the related encoded data slices is from a different set of encoded data slices of a plurality of sets of encoded data slices, wherein a data object is encoded into the plurality of sets of encoded data slices and a data segment of the data object is encoded into one set of encoded data slices of the plurality of sets of encoded data slices;

a second computer readable memory section that stores operational instructions that, when executed by the processing module, causes the processing module to;

perform a deterministic function on common storage naming information of the related encoded data slices to produce error detection information for the related encoded data slices, wherein the common storage naming information includes a data object identifier of the data object and a data segment identifier; and

a third computer readable memory section that stores operational instructions that, when executed by the processing module, causes the processing module to;

send the error detection information to a computing device of the DSN.

9. The computer readable storage device of claim 8, wherein the common storage naming information further comprises:

revision level information for each of the related encoded data slices.

10. The computer readable storage device of claim 8, wherein the second computer readable memory section further stores operational instructions that, when executed by the processing module of the storage unit, causes the processing module to perform a deterministic function by:

generating a hash tree by performing a plurality of layers of hash functions, wherein a first layer of the plurality of layers of hash functions includes;

performing a hash function on the common storage naming information of first and second related encoded data slices of the related encoded data slices to produce a first hash value; and

performing the hash function on the common storage naming information of third and fourth related encoded data slices of the related encoded data slices to produce a second hash value;

wherein a final layer of the plurality of layers of hash functions includes;

performing the hash function on a final intermediate hash value and a second final intermediate hash value to produce a root hash.

11. The computer readable storage device of claim 10, wherein the third computer readable memory section further stores operational instructions that, when executed by the processing module of the storage unit, causes the processing module to:

send the root hash as the error detection information.

12. The computer readable storage device of claim 10, wherein the third computer readable memory section further stores operational instructions that, when executed by the processing module of the storage unit, causes the processing module to:

send the hash tree as the error detection information.

13. A computer readable storage device comprises:

a first computer readable memory section that stores operational instructions that, when executed by a computing device of a dispersed storage network (DSN), causes a processing module to;

obtain common storage name information regarding data that is stored in storage units of a distributed storage network (DSN) as a set of data slices, wherein each data slice of the set of data slices has a unique storage name, wherein each of the unique storage names for the set of data slices has common naming information regarding the data and individual naming information regarding a respective data slice of the set of data slices, and wherein the common storage name information is based on the common naming information for the set of data slices;

a second computer readable memory section that stores operational instructions that, when executed by the computing device, causes the processing module to;

interpret the common storage name information to determine whether a difference exists between the common naming information of a data slice of the set of data slices and the common naming information of other data slices of the set of data slices; and

a third computer readable memory section that stores operational instructions that, when executed by the computing device, causes the processing module to;

when the difference exists between the common naming information of the data slice and the common naming information of the other data slices;

indicate a potential storage error of the data slice; and

implement a storage error process regarding the potential storage error of the data slice.

14. The computer readable storage device of claim 13, wherein the common naming information comprises one or more of:

a data name;

a vault identifier;

a source name;

a vault generation number; and

a data revision number.

15. The computer readable storage device of claim 13, wherein the individual naming information comprises one or more of:

a data slice index;

a storage unit identifier; and

a pillar identifier.

16. The computer readable storage device of claim 13, wherein the third computer readable memory section further stores operational instructions that, when executed by the computing device, causes the processing module to implement the storage error process by:

rebuilding the data slice having the potential storage error.

17. The computer readable storage device of claim 13 further comprises:

the first computer readable memory section further stores operational instructions that, when executed by the computing device, causes the processing module to;

obtain tables from storage nodes, wherein a table from one of the storage nodes includes the common naming information for a plurality of data slices stored in the storage nodes;

the second computer readable memory section further stores operational instructions that, when executed by the computing device, causes the processing module to;

compare the tables to determine whether one of the tables includes an anomaly with respect to other tables; and

the third computer readable memory section further stores operational instructions that, when executed by the computing device, causes the processing module to;

when the one of the tables has the anomaly, indicate that the plurality of data slices associated with the one of the tables has potential storage errors.

18. The computer readable storage device of claim 17 further comprises:

the first computer readable memory section further stores operational instructions that, when executed by the computing device, causes the processing module to;

request first specific portions of the common storage name information from one of the storage units that provided the one of the tables with the anomaly;

request second specific portions of the common storage name information from another one of the storage units; and

the third computer readable memory section further stores operational instructions that, when executed by the computing device, causes the processing module to;

interpret the first and second specific portions of the common storage name information to identify the data slice of the plurality of data slices having the potential storage error.

19. The computer readable storage device of claim 17 further comprises:

the first computer readable memory section further stores operational instructions that, when executed by the computing device, causes the processing module to;

obtain a table of the tables as a hash of a plurality of common storage name information for the corresponding plurality of data slices.