VERIFYING INTEGRITY OF DATA STORED IN A DISPERSED STORAGE MEMORY

• US 20110314356A1
• Filed: 06/06/2011
• Published: 12/22/2011
• Est. Priority Date: 06/22/2010
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Grube, Gary W., Markison, Timothy W.
• Granted Patent: US 8,555,142 B2
• Time in Patent Office: Days
• US Class Current: 714/763
• 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/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/3409 for performance assessment
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• 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/23 using convolutional codes, e.g. unit memory codes
• CPC Class Codes: H03M 13/353 Adaptation to the channel
• 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

Abstract

A method for verifying integrity of data stored in dispersed storage memory begins by a processing module retrieving integrity information of the data that is stored as a set of forward error correction (FEC) encoded words in the dispersed storage memory and continues with the processing module receiving FEC encoded words of the set of FEC encoded words from the dispersed storage memory to produce received FEC encoded words and decoding a unique subset of the received FEC encoded words to produce recovered data. The method continues with the processing module generating recovered integrity information from the recovered data and comparing the recovered integrity information with the integrity information. The method continues with the processing module indicating that at least one of the received FEC encoded words of the unique subset of the received FEC encoded words is corrupt when the recovered integrity information compares unfavorably with the integrity information.

Claims

1. A method for verifying integrity of data stored in dispersed storage memory, the method comprises:

retrieving integrity information of the data that is stored as a set of forward error correction (FEC) encoded words in the dispersed storage memory;

receiving FEC encoded words of the set of FEC encoded words from the dispersed storage memory to produce received FEC encoded words;

decoding a unique subset of the received FEC encoded words to produce recovered data;

generating recovered integrity information from the recovered data;

comparing the recovered integrity information with the integrity information; and

when the recovered integrity information compares unfavorably with the integrity information, indicating that at least one of the received FEC encoded words of the unique subset of the received FEC encoded words is corrupt.

2. The method of claim 1 further comprises:

retrieving a set of addresses with the integrity information; and

creating a set of read commands to retrieve the set of FEC encoded words from the dispersed storage memory, wherein a read command of the set of read commands includes an address of the set of addresses.

3. The method of claim 1 further comprises:

entering a loop;

decoding the unique subset of the received FEC encoded words to produce the recovered data;

generating the recovered integrity information from the recovered data;

comparing the recovered integrity information with the integrity information;

when the recovered integrity information compares favorably with the integrity information;

determining whether unique subset combinations of the received FEC encoded words have been substantially exhausted;

when the unique subset combinations of the received FEC encoded words have not been substantially exhausted, repeating the loop for another unique subset of the unique subset combinations; and

when the unique subset combinations of the received FEC encoded words have been substantially exhausted, indicating that the data is validly stored in the dispersed storage memory and exiting the loop; and

when the recovered integrity information compares unfavorably with the integrity information, indicating that the at least one of the received FEC encoded words of the unique subset of the received FEC encoded words is corrupt and exiting the loop.

4. The method of claim 1 further comprises:

determining whether another unique subset of the received FEC encoded words generated another recovered integrity information that compared favorably to the integrity information;

when the other recovered integrity information compared favorably to the integrity information, encoding another recaptured data to produce another set of FEC encoded words, wherein the other unique subset of the received FEC encoded words is decoded to produce the other recaptured data; and

facilitating overwriting of the set of FEC encoded words with the other set of FEC encoded words within the dispersed storage memory.

5. The method of claim 1 further comprises:

identifying the at least one of the received FEC encoded words of the unique subset of the received FEC encoded words that is corrupt based on other unique subsets of the received FEC encoded words;

rebuilding the at least one of the received FEC encoded words of the unique subset of the received FEC encoded words that is corrupt based on at least one of the other unique subsets of the received FEC encoded words to produce at least one rebuilt FEC encoded words; and

facilitating overwriting the at least one of the received FEC encoded words of the unique subset of the received FEC encoded words that is corrupt with the at least one rebuilt FEC encoded words.

6. The method of claim 1 further comprises:

when a count of the received FEC encoded words is less than a number of FEC encoded words in the set of FEC encoded words, identifying a missing FEC encoded word of the set of FEC encoded words;

rebuilding the missing FEC encoded word based on another unique subset of the received FEC encoded words to produce a rebuilt FEC encoded word, wherein the other unique subset of the received FEC encoded words generated another recovered integrity information that compared favorably to the integrity information; and

facilitating overwriting the missing FEC encoded word with the rebuilt FEC encoded word.

7. A computer comprises:

an interface;

a memory; and

a processing module operable to;

retrieve, from the memory, integrity information of data that is stored as a set of forward error correction (FEC) encoded words in a dispersed storage memory;

receive, via the interface, FEC encoded words of the set of FEC encoded words from the dispersed storage memory to produce received FEC encoded words;

decode a unique subset of the received FEC encoded words to produce recovered data;

generate recovered integrity information from the recovered data;

compare the recovered integrity information with the integrity information; and

when the recovered integrity information compares unfavorably with the integrity information, indicate that at least one of the received FEC encoded words of the unique subset of the received FEC encoded words is corrupt.

8. The computer of claim 7, wherein the processing module further functions to:

retrieve, from the memory, a set of addresses with the integrity information; and

create a set of read commands to retrieve, via the interface, the set of FEC encoded words from the dispersed storage memory, wherein a read command of the set of read commands includes an address of the set of addresses.

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

enter a loop to;

decode the unique subset of the received FEC encoded words to produce the recovered data;

generate the recovered integrity information from the recovered data;

compare the recovered integrity information with the integrity information;

when the recovered integrity information compares favorably with the integrity information;

determine whether unique subset combinations of the received FEC encoded words have been substantially exhausted;

when the unique subset combinations of the received FEC encoded words have not been substantially exhausted, repeat the loop for another unique subset of the unique subset combinations; and

when the unique subset combinations of the received FEC encoded words have been substantially exhausted, indicate that the data is validly stored in the dispersed storage memory and exit the loop; and

when the recovered integrity information compares unfavorably with the integrity information, indicate that the at least one of the received FEC encoded words of the unique subset of the received FEC encoded words is corrupt and exit the loop.

10. The computer of claim 7, wherein the processing module further functions to:

determine whether another unique subset of the received FEC encoded words generated another recovered integrity information that compared favorably to the integrity information;

when the other recovered integrity information compared favorably to the integrity information, encode another recaptured data to produce another set of FEC encoded words, wherein the other unique subset of the received FEC encoded words is decoded to produce the other recaptured data; and

facilitate overwriting, via the interface, of the set of FEC encoded words with the other set of FEC encoded words within the dispersed storage memory.

11. The computer of claim 7, wherein the processing module further functions to:

identify the at least one of the received FEC encoded words of the unique subset of the received FEC encoded words that is corrupt based on other unique subsets of the received FEC encoded words;

rebuild the at least one of the received FEC encoded words of the unique subset of the received FEC encoded words that is corrupt based on at least one of the other unique subsets of the received FEC encoded words to produce at least one rebuilt FEC encoded words; and

facilitate overwriting, via the interface, the at least one of the received FEC encoded words of the unique subset of the received FEC encoded words that is corrupt with the at least one rebuilt FEC encoded words.

12. The computer of claim 7, wherein the processing module further functions to:

when a count of the received FEC encoded words is less than a number of FEC encoded words in the set of FEC encoded words, identify a missing FEC encoded word of the set of FEC encoded words;

rebuild the missing FEC encoded word based on another unique subset of the received FEC encoded words to produce a FEC encoded word, wherein the other unique subset of the received FEC encoded words generated another recovered integrity information that compared favorably to the integrity information; and

facilitate overwriting, via the interface, the missing FEC encoded word with the rebuilt FEC encoded word.