Digest listing decomposition

• US 10,360,180 B2
• Filed: 07/31/2014
• Issued: 07/23/2019
• Est. Priority Date: 09/30/2005
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Vas, Sebastien, Mark, Zachary J., Resch, Jason K.
• Primary Examiner(s): Harper, Eliyah S.
• Application Number:
  US14/447,890
• Publication Number:
  US 20140344318A1
• Time in Patent Office: 1,818 Days
• Field of Search: 707652, 707679
• 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

To identify slice errors, a processing module of a computing device in a dispersed storage network (DSN) sends first list digest requests to at least first and second dispersed storage (DS) units. The requests indicates a first range of slice names to include in a first list digest. The processing module receives digest responses from the DS units, and compares the digest responses to determine whether they identify the same slices. If they do not identify the same slices, the processing module sends second list digest requests indicating a sub-range of the first range of slice names to include in second list digests. The sub-range continues to be narrowed until the processing module identifies at least one sub-range of slice names where a slice error exists.

Claims

1. A method for use in a processing module of a computing device included in a dispersed storage network (DSN), the method comprising:

sending first list digest requests to at least first and second dispersed storage (DS) units, the first list digest requests indicating a first range of slice names to include in a first list digest;

receiving, in response to the first list digest requests, first and second list digest responses from the first and second DS units;

determining whether the first list digest response compares favorably to the second list digest response; and

in response to an unfavorable determination, sending second list digest requests to the first and second DS units, the second list digest requests indicating a sub-range of the first range of slice names to include in second list digests.

2. The method of claim 1, further comprising:

continuing to narrow the sub-range until the processing module identifies at least one sub-range of slice names where a slice error exists.

3. The method of claim 1, further comprising;

sending the at least first and second DS units list range request messages;

receiving first and second list range request response messages from the at least first and second DS units; and

identifying a difference between the first and second list range request response messages.

4. The method of claim 3, wherein the list range request messages sent to the first and second DS units include a start slice name, an end slice name, and a maximum response count.

5. The method of claim 3, wherein the first and second list range response messages include the following for each slice name:

a slice revision count, a slice revision and slice length for each slice revision.

6. The method of claim 1, further comprising:

determining a test range of slice names to test for slice errors, wherein the test range of slice names to test for slice errors corresponds to the first range of slice names.

7. The method of claim 1, wherein the at least first and second DS units are included in a common DS unit storage set.

8. A dispersed storage network (DSN) comprising:

a plurality of targeted dispersed storage (DS) units configured to store encoded data slices;

a dispersed storage (DS) processing unit configured to identify slice errors in the encoded data slices, at least in part, by;

sending first list digest requests to at least first and second DS units, the first list digest requests indicating a first range of slice names to include in first list digests;

receiving, in response to the first list digest requests, first and second list digest responses from the first and second DS units;

determining whether the first list digest response compares favorably to the second list digest response; and

in response to an unfavorable determination, send second list digest requests to the first and second DS units, the second list digest requests indicating a sub-range of the first range of slice names to include in second list digests.

9. The DSN of claim 8, wherein the dispersed storage processing unit is further configured to:

continue narrowing the sub-range until at least one sub-range of slice names where a slice error exists is identified.

10. The DSN of claim 8, wherein the DS processing unit is further configured to:

send the at least first and second DS units a list range request message;

receive first and second list range request response messages from the at least first and second DS units; and

identify a difference between the first and second list range request response messages.

11. The DSN of claim 10, wherein the DS processing unit is further configured to include a start slice name, an end slice name, and a maximum response count in the list range request messages sent to the first and second DS units.

12. The DSN of claim 10, wherein the at least first and second DS units are further configured to:

include the following in the first and second list range response messages for each slice name;

a slice revision count, a slice revision and slice length for each slice revision.

13. The DSN of claim 8, wherein the at least first and second DS units are included in a common DS unit storage set.

14. A dispersed storage (DS) processing unit comprising:

an interface;

a memory; and

a processing module operable to;

send first list digest requests to at least first and second dispersed storage (DS) units, the first list digest requests indicating a first range of slice names to include in a first list digest;

receive, in response to the first list digest requests, first and second list digest responses from the first and second DS units;

determine whether the first list digest response compares favorably to the second list digest response; and

in response to an unfavorable determination, send second list digest requests to the first and second DS units, the second list digest requests indicating a sub-range of the first range of slice names to include in second list digests.

15. The DS processing unit of claim 14, wherein the processing module is further operable to:

continue narrowing the sub-range until the processing module identifies at least one sub-range of slice names where a slice error exists.

16. The DS processing unit of claim 14, wherein the processing module is further operable to:

send the at least first and second DS units list range request messages;

receive first and second list range request response messages from the at least first and second DS units; and

identify a difference between the first and second list range request response messages.

17. The DS processing unit of claim 15, wherein the list range request messages sent to a first and second DS units include a start slice name, an end slice name, and a maximum response count.

18. The DS processing unit of claim 15, wherein first and second list range response messages include the following for each slice name:

a slice revision count, a slice revision and slice length for each slice revision.

19. The DS processing unit of claim 14, further comprising:

determining a test range of slice names to test for slice errors, wherein the test range of slice names to test for slice errors corresponds to the first range of slice names.

20. The DS processing unit of claim 14, wherein the at least first and second DS units are included in a common DS unit storage set.