Identifying a slice name information error in a dispersed storage network

• US 8,621,269 B2
• Filed: 06/07/2011
• Issued: 12/31/2013
• Est. Priority Date: 06/22/2010
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Vas, Sebastien, Mark, Zachary J.
• Primary Examiner(s): KO, CHAE M
• Application Number:
  US13/154,735
• Publication Number:
  US 20110314346A1
• Time in Patent Office: 938 Days
• Field of Search: 714/6.1, 714/6.2, 714/6.22, 714/6.24
• US Class Current: 714/6.2
• 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/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 11/141 for bus or memory accesses
• CPC Class Codes: G06F 11/167 Error detection by comparing the memory output
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 21/31 User authentication
• CPC Class Codes: G06F 21/6209 to a single file or object, e.g. in a secure envelope, encrypted and accessed using a key, or with access control rules appended to the object itself
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: H04L 2209/043 of tables, e.g. lookup, substitution or mapping
• 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 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 2209/80 Wireless network architectures or network communication protocols for wireless network security H04W12/00
• CPC Class Codes: H04L 63/0428 wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 63/06 for supporting key management in a packet data network cryptographic mechanisms or cryptographic arrangements for key management H04L9/08
• CPC Class Codes: H04L 63/12 Applying verification of the received information cryptographic mechanisms or cryptographic arrangements for data integrity or data verification H04L9/32
• CPC Class Codes: H04L 67/06 specially adapted for file transfer, e.g. file transfer protocol [FTP]
• 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/3242 involving keyed hash functions, e.g. message authentication codes [MACs], CBC-MAC or HMAC
• CPC Class Codes: H04L 9/3247 : involving digital signatures
• CPC Class Codes: H04L 9/3263 : involving certificates, e.g. public key certificate [PKC] or attribute certificate [AC]; Public key infrastructure [PKI] arrangements network architectures or network communication protocols for supporting authentication of entities using certificates in a packet data network H04L63/0823
• CPC Class Codes: H04L 9/3271 : using challenge-response
• CPC Class Codes: H04W 12/041 : Key generation or derivation
• CPC Class Codes: H04W 12/0431 : Key distribution or pre-distribution; Key agreement
• CPC Class Codes: H04W 12/10 : Integrity
• CPC Class Codes: H04W 12/35 : Protecting application or service provisioning, e.g. securing SIM application provisioning

Abstract

A method begins by a processing module sending list digest requests to a set of dispersed storage (DS) units. The method continues with the processing module receiving list digest responses from at least some of the set of DS units and determining whether an inconsistency exists between first and second list digest responses of the list digest responses. The method continues with the processing module requesting at least a portion of each of the slice name information lists from first and second DS units of the set of DS units and identifying a slice name information error associated with the inconsistency based on the at least a portion of each of the slices name information lists of the first and second DS units when the inconsistency exists between first and second list digest responses of the list digest responses.

Claims

1. A method comprises:

sending list digest requests to a set of dispersed storage (DS) units, wherein a list digest request of the list digest requests is requesting a representation of a slice name information list regarding encoded data slices stored by a DS unit of the set of DS units;

receiving list digest responses from at least some of the set of DS units;

determining whether an inconsistency exists between first and second list digest responses of the list digest responses; and

when the inconsistency exists between first and second list digest responses of the list digest responses;

requesting at least a portion of each of the slice name information lists from first and second DS units of the set of DS units, wherein the first DS unit provided the first list digest response and the second DS unit provided the second list digest response; and

identifying a slice name information error associated with the inconsistency based on the at least a portion of each of the slices name information lists of the first and second DS units.

2. The method of claim 1, wherein the representation of the slice name information list comprises at least one of:

a hash value resulting from a hash function performed on entries of the slice name information list;

a compression value resulting from a compression function performed on entries of the slice name information list;

a checksum value resulting from a checksum function performed on the entries of the slice name information list;

a hash-based message authentication code (HMAC) value resulting from an HMAC function performed on the entries of the slice name information list; and

a mask generating function (MGF) value resulting from an MGF performed on the entries of the slice name information list.

3. The method of claim 1, wherein the determining whether the inconsistency exists between the first and the second list digest responses comprises at least one of:

a first hash value of the first list digest response is not substantially equal to a second hash value of the second list digest response;

a first checksum value of the first list digest response is not substantially equal to a second checksum value of the second list digest response;

a first HMAC value of the first list digest response is not substantially equal to a second HMAC value of the second list digest response; and

a first MGF value of the first list digest response is not substantially equal to a second MGF value of the second list digest response.

4. The method of claim 1, wherein the identifying the slice name information error comprises:

establishing the at least a portion of the slice name information list from the first DS unit as a current slice name information list; and

identifying an entry of the at least a portion of the slice name information list from the second DS unit that differs from a corresponding entry of the at least a portion of the slice name information list from the first DS unit to identify the slice name information error.

5. The method of claim 4, wherein the establishing the at least a portion of the slice name information list from the first DS unit as the current slice name information list comprises:

determining that the at least a portion of the slice name information list from the first DS unit substantially matches at least a portion of the slice name information list from a third DS unit of the set of DS units.

6. The method of claim 1 further comprises:

the slice name information list including a plurality of entries for a range of slice names, wherein an entry of the plurality of entries includes;

a slice name of a corresponding one of the encoded data slices;

a slice revision count indicating a number of revisions of the slice name; and

for a revision of the revisions of the slice names;

a revision number; and

a slice length indicator.

7. The method of claim 1 further comprises:

adding the slice name information error to a rebuild list.

8. The method of claim 1, wherein the slice name information error comprises at least one of:

a missing encoded data slice error;

a non-deleted encoded data slice error; and

a revision error.

9. A computer comprises:

an interface;

a memory; and

a processing module operable to;

send, via the interface, list digest requests to a set of dispersed storage (DS) units, wherein a list digest request of the list digest requests is requesting a representation of a slice name information list regarding encoded data slices stored by a DS unit of the set of DS units;

receive, via the interface, list digest responses from at least some of the set of DS units;

determine whether an inconsistency exists between first and second list digest responses of the list digest responses; and

when the inconsistency exists between first and second list digest responses of the list digest responses;

request, via the interface, at least a portion of each of the slice name information lists from first and second DS units of the set of DS units, wherein the first DS unit provided the first list digest response and the second DS unit provided the second list digest response; and

identify a slice name information error associated with the inconsistency based on the at least a portion of each of the slices name information lists of the first and second DS units.

10. The computer of claim 9, wherein the representation of the slice name information list comprises at least one of:

a hash value resulting from a hash function performed on entries of the slice name information list;

a compression value resulting from a compression function performed on entries of the slice name information list;

a checksum value resulting from a checksum function performed on the entries of the slice name information list;

a hash-based message authentication code (HMAC) value resulting from an HMAC function performed on the entries of the slice name information list; and

a mask generating function (MGF) value resulting from an MGF performed on the entries of the slice name information list.

11. The computer of claim 9, wherein the processing module functions to determine whether the inconsistency exists between the first and the second list digest responses by at least one of:

a first hash value of the first list digest response is not substantially equal to a second hash value of the second list digest response;

a first checksum value of the first list digest response is not substantially equal to a second checksum value of the second list digest response;

a first HMAC value of the first list digest response is not substantially equal to a second HMAC value of the second list digest response; and

a first MGF value of the first list digest response is not substantially equal to a second MGF value of the second list digest response.

12. The computer of claim 9, wherein the processing module functions to identify the slice name information error by:

establishing the at least a portion of the slice name information list from the first DS unit as a current slice name information list; and

identifying an entry of the at least a portion of the slice name information list from the second DS unit that differs from a corresponding entry of the at least a portion of the slice name information list from the first DS unit to identify the slice name information error.

13. The computer of claim 12, wherein the processing module functions to establish the at least a portion of the slice name information list from the first DS unit as the current slice name information list by:

determining that the at least a portion of the slice name information list from the first DS unit substantially matches at least a portion of the slice name information list from a third DS unit of the set of DS units.

14. The computer of claim 9 further comprises:

the slice name information list including a plurality of entries for a range of slice names, wherein an entry of the plurality of entries includes;

a slice name of a corresponding one of the encoded data slices;

a slice revision count indicating a number of revisions of the slice name; and

for a revision of the revisions of the slice names;

a revision number; and

a slice length indicator.

15. The computer of claim 9, wherein the processing module further functions to:

add the slice name information error to a rebuild list.

16. The computer of claim 9, wherein the slice name information error comprises at least one of:

a missing encoded data slice error;

a non-deleted encoded data slice error; and

a revision error.