Accessing data stored in a dispersed storage memory

• US 9,684,558 B2
• Filed: 12/16/2013
• Issued: 06/20/2017
• Est. Priority Date: 06/22/2010
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Grube, Gary W., Markison, Timothy W.
• Primary Examiner(s): NGUYEN, STEVE N
• Application Number:
  US14/107,157
• Publication Number:
  US 20140108890A1
• Time in Patent Office: 1,282 Days
• 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 begins by a processing module forward error correction (FEC) encoding data to produce FEC encoded data and dividing the FEC encoded data into a set of FEC encoded words. The method continues with the processing module generating integrity information based on the data and generating a word name for an FEC encoded word of the set of FEC encoded words. The method continues with the processing module affiliating an address of allocated address space of a dispersed storage memory with the word name and storing the integrity information, the word name, and the address. The method continues with the processing module creating a write command to store the FEC encoded word at the address in the dispersed storage memory.

Claims

1. A method for execution by a processing module, the method comprises:

retrieving, for a data segment of a data file, integrity information and a set of addresses, wherein the data file is segmented into a plurality of data segments, wherein the plurality of data segments of the data file are dispersed error encoded in accordance with an error coding dispersal storage function to generate sets forward error correction (FEC) encoded words, wherein the error coding dispersal storage function specifies parameters including a pillar number, a read threshold, and a write threshold, wherein each set of FEC encoded words includes a pillar number of FEC encoded words, wherein a decode threshold number of FEC encoded words that is less than a total number of FEC encoded words in a set of FEC encoded words are needed to recover the data segment, wherein a read threshold number of FEC encoded words provides for reconstruction of the data segment, wherein a write threshold number of FEC encoded words provides for a successful transfer of the set of FEC encoded words from a first at least one location in a dispersed storage memory to a second at least one location in the dispersed storage memory, and wherein the write threshold is greater than or equal to the read threshold for the pillar number;

creating a set of read commands to retrieve at least the decode threshold number of FEC encoded words based on the set of addresses in the dispersed storage memory;

sending the set of read commands to a set of storage units of the dispersed storage memory, wherein each storage unit includes a processing module and memory, wherein the set of FEC encoded words are distributedly stored in the set of storage units of the dispersed storage memory;

when the at least the decode threshold number of FEC encoded words are retrieved from at least some of the set of storage units;

decoding the at least the decode threshold number of FEC encoded words to produce a recaptured data segment;

generating recaptured integrity information based on the recaptured data segment;

comparing the recaptured integrity information with the integrity information; and

when the comparing is favorable, indicating that the recaptured data segment is valid.

2. The method of claim 1 further comprises:

identifying a set of word names based on the data segment; and

utilizing the set of word names to index a table to retrieve the integrity information and the set of addresses.

3. The method of claim 1, wherein the dispersed storage memory comprises at least one of:

a local memory of a device executing the method;

a memory of a storage service provider; and

a network coupled memory unit.

4. The method of claim 1, wherein the generating the recaptured integrity information comprises at least one of:

performing a hash algorithm on the recaptured data segment to produce the integrity information;

performing a hash-based message authentication code (HMAC) on the recaptured data segment to produce the integrity information;

performing a parity function on the recaptured data segment to produce the integrity information;

performing a cyclic redundancy check function on the recaptured data segment to produce the integrity information; and

performing a mask generating function (MGT) on the recaptured data segment to produce the integrity information.

5. A computer comprises:

an interface;

a memory; and

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

retrieve, for a data segment of a data file, integrity information and a set of addresses, wherein the data file is segmented into a plurality of data segments, wherein the plurality of data segments of the data file are dispersed error encoded in accordance with an error coding dispersal storage function to generate sets forward error correction (FEC) encoded words, wherein the error coding dispersal storage function specifies parameters including a pillar number, a read threshold, and a write threshold, wherein each set of FEC encoded words includes a pillar number of FEC encoded words, wherein a decode threshold number of FEC encoded words that is less than a total number of FEC encoded words in a set of FEC encoded words are needed to recover the data segment, wherein a read threshold number of FEC encoded words provides for reconstruction of the data segment, wherein a write threshold number of FEC encoded words provides for a successful transfer of the set of FEC encoded words from a first at least one location in a dispersed storage memory to a second at least one location in the dispersed storage memory, and wherein the write threshold is greater than or equal to the read threshold for the pillar number;

create a set of read commands to retrieve at least the decode threshold number of FEC encoded words based on the set of addresses in the dispersed storage memory;

send the set of read commands to a set of storage units of the dispersed storage memory, wherein each storage unit includes a processing module and memory, wherein the set of FEC encoded words are distributedly stored in the set of storage units of the dispersed storage memory;

when the at least the decode threshold number of FEC encoded words are retrieved from at least some of the set of storage units;

decode the at least the decode threshold number of FEC encoded words to produce a recaptured data segment;

generate recaptured integrity information based on the recaptured data segment;

compare the recaptured integrity information with the integrity information; and

when the comparing is favorable, indicate that the recaptured data segment is valid.

6. The computer of claim 5, wherein the processing module further functions to:

identify a set of word names based on the data segment; and

utilize the set of word names to index a table to retrieve the integrity information and the set of addresses.

7. The computer of claim 5, wherein the dispersed storage memory comprises at least one of:

a local memory;

a memory of a storage service provider; and

a network coupled memory unit.

8. The computer of claim 5, wherein the processing module functions to generate the recaptured integrity information by at least one of:

performing a hash algorithm on the recaptured data segment to produce the integrity information;

performing a hash-based message authentication code (HMAC) on the recaptured data segment to produce the integrity information;

performing a parity function on the recaptured data segment to produce the integrity information;

performing a cyclic redundancy check function on the recaptured data segment to produce the integrity information; and

performing a mask generating function (MGT) on the recaptured data segment to produce the integrity information.