Storing data in a distributed storage network

• US 9,009,564 B2
• Filed: 12/06/2012
• Issued: 04/14/2015
• Est. Priority Date: 12/12/2011
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Leggette, Wesley, Baptist, Andrew, Resch, Jason K.
• Primary Examiner(s): Alphonse, Fritz
• Application Number:
  US13/707,471
• Publication Number:
  US 20130151926A1
• Time in Patent Office: 859 Days
• Field of Search: 714/763, 714/774, 714/804, 714/795, 714/761, 714/45
• 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/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD
• CPC Class Codes: H03M 13/05 using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits H03M13/2906 takes precedence
• CPC Class Codes: H03M 13/611 Specific encoding aspects, e.g. encoding by means of decoding
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming
• CPC Class Codes: H04L 67/10 in which an application is distributed across nodes in the network software deployment G06F8/60; multiprogramming arrangements G06F9/46
• 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]

Abstract

A method begins by a dispersed storage (DS) processing module mapping a set of data partitions to a set of storage regions. For each data partition, the method continues with the DS processing module segmenting the data partition into a plurality of data segments and designating a first data segment. The method continues with the DS processing module generating data storage mapping information. The method continues with the DS processing module encoding the data storage mapping information to produce at least one set of encoded mapping information slices and for each data partition, encoding the plurality of data segments to produce a plurality of sets of encoded data slices. The method continues with the DS processing module outputting the at least one set of encoded mapping information slices and, for each data partition, the plurality of sets of encoded data slices to the DSN for storage therein.

Claims

1. A dispersed storage (DS) module comprises:

a first module, when operable within a computing device, causes the computing device to;

determine whether to use sequential data segment storage mapping or non-sequential data segment storage mapping for storage of data based on data read/write probabilities of the data;

a second module, when operable within the computing device, causes the computing device to;

when the non-sequential data segment storage mapping is to be used;

determine an initial set of storage regions of a distributed storage network (DSN) for storing the data;

map a set of data partitions to the initial set of storage regions, wherein the data is divided into the set of data partitions; and

for each data partition of the set of data partitions;

segment the data partition into a plurality of data segments; and

designate a first data segment of the plurality of data segments;

a third module, when operable within the computing device, causes the computing device to;

when the non-sequential data segment storage mapping is to be used;

generate data storage mapping information regarding at least one of;

the mapping of the set of data partitions to the initial set of storage regions;

the plurality of data segments for each data partition of the set of data partitions; and

the first data segment for each data partition of the set of data partitions;

a fourth module, when operable within the computing device, causes the computing device to;

when the non-sequential data segment storage mapping is to be used;

encode, in accordance with a first dispersed storage error coding function, the data storage mapping information to produce at least one set of encoded mapping information slices; and

for each data partition of the set of data partitions, encode, in accordance with a second dispersed storage error coding function, the plurality of data segments to produce a plurality of sets of encoded data slices; and

a fifth module, when operable within the computing device, causes the computing device to;

when the non-sequential data segment storage mapping is to be used;

output the at least one set of encoded mapping information slices and, for each data partition of the set of data partitions, the plurality of sets of encoded data slices to the DSN for storage therein.

2. The DS module of claim 1, wherein the data read/write probabilities comprises one or more of:

size of the data;

data type;

estimated regularity of editing at least a portion of the data;

estimated regularity of deleting the at least the portion of the data;

estimated regularity of expanding the data;

storage capabilities of the DSN;

parallel read/write preferences; and

non-sequential read/write preferences.

3. The DS module of claim 1, wherein the second module functions to determine the initial set of storage regions by:

determining the initial set of storage regions based on one or more of the data read/write probabilities.

4. The DS module of claim 1, wherein the third module functions to generate the data storage mapping information by:

generating an indication for the non-sequential data segment storage mapping; and

generating a segment allocation table, wherein an entry of the segment allocation table includes;

identity of one of the initial set of storage regions;

identity of the first data segment; and

information relating the first data segment to the plurality of data segments.

5. The DS module of claim 1 further comprises:

the first dispersed storage error coding function specifies dispersed storage error coding parameters;

the second dispersed storage error coding function specifies the dispersed storage error coding parameters; and

the fourth module further functions to;

encode, in accordance with the dispersed storage error coding parameters, the data storage mapping information and the first data segment of a first data partition of the set of data partitions to produce at least one set of encoded mapping information and data slices; and

for each remaining data segment of the plurality of data segments of the first data partition, encode, in accordance with the dispersed storage error coding parameters, the remaining data segment to produce a set of encoded data slices.

6. The DS module of claim 1 further comprises:

the first module further functions to receive additional data to store with the data;

the second module further functions to;

select another storage region of the DSN for storing the additional data;

update a set of storage regions to include the initial set of storage regions and the other storage region;

segment the additional data into an additional plurality of data segments; and

designate a first data segment of the additional plurality of data segments;

the third module further functions to update the data storage mapping information to include at least one of;

the mapping of the set of data partitions and the additional data to the set of storage regions;

the additional plurality of data segments; and

the first data segment of the additional plurality of data segments;

the fourth module further functions to;

encode, in accordance with the first dispersed storage error coding function, the updated data storage mapping information to produce at least one updated set of encoded mapping information slices; and

encode, in accordance with the second dispersed storage error coding function, the additional plurality of data segments to produce an additional plurality of sets of encoded data slices; and

the fifth module further functions to output the at least one updated set of encoded mapping information slices and the additional plurality of sets of encoded data slices to the DSN for storage therein.

7. The DS module of claim 1 further comprises:

when the sequential data segment storage mapping is to be used;

the second module further functions to;

segment the data into the plurality of data segments; and

designate the first data segment of the plurality of data segments;

the third module further functions to generate the data storage mapping information regarding at least one of;

the plurality of data segments; and

the first data segment;

the fourth module further functions to;

encode, in accordance with a dispersed storage error coding function, the data storage mapping information and the first data segment to produce at least one set of encoded mapping information and data slices; and

for each remaining data segment of the plurality of data segments, encode, in accordance with the dispersed storage error coding function, the remaining data segment to produce a set of encoded data slices; and

the fifth module further functions to output the at least one set of encoded mapping information and data slices and, for each remaining data segment of the plurality of data segments, the set of encoded data slices to the DSN for storage therein.

8. A dispersed storage (DS) module comprises:

a first module, when operable within a computing device, causes the computing device to;

map a set of data partitions to a set of storage regions, wherein data is divided into the set of data partitions; and

for each data partition of the set of data partitions;

segment the data partition into a plurality of data segments; and

designate a first data segment of the plurality of data segments;

a second module, when operable within the computing device, causes the computing device to;

generate data storage mapping information regarding at least one of;

the mapping of the set of data partitions to the set of storage regions;

the plurality of data segments for each data partition of the set of data partitions; and

the first data segment for each data partition of the set of data partitions;

a third module, when operable within the computing device, causes the computing device to;

encode, in accordance with a first dispersed storage error coding function, the data storage mapping information to produce at least one set of encoded mapping information slices; and

for each data partition of the set of data partitions, encode, in accordance with a second dispersed storage error coding function, the plurality of data segments to produce a plurality of sets of encoded data slices; and

a fourth module, when operable within the computing device, causes the computing device to;

output the at least one set of encoded mapping information slices and, for each data partition of the set of data partitions, the plurality of sets of encoded data slices to a dispersed storage network (DSN) for storage therein.

9. The DS module of claim 8, wherein the first module functions to map the set of data partitions to the set of storage regions by:

determining the set of storage regions based on data read/write probabilities, wherein the data read/write probabilities includes one or more of;

size of the data;

data type;

estimated regularity of editing at least a portion of the data;

estimated regularity of deleting the at least the portion of the data;

estimated regularity of expanding the data;

storage capabilities of the DSN;

parallel read/write preferences; and

non-sequential read/write preferences.

10. The DS module of claim 8 further comprises:

the first dispersed storage error coding function specifies dispersed storage error coding parameters;

the second dispersed storage error coding function specifies the dispersed storage error coding parameters; and

the third module further functions to;

encode, in accordance with the dispersed storage error coding parameters, the data storage mapping information and the first data segment of a first data partition of the set of data partitions to produce at least one set of encoded mapping information and data slices; and

for each remaining data segment of the plurality of data segments of the first data partition, encode, in accordance with the dispersed storage error coding parameters, the remaining data segment to produce a set of encoded data slices.

11. The DS module of claim 8, wherein the second module further functions to generate the data storage mapping information by:

generating an indication for non-sequential data segment storage mapping; and

generating a segment allocation table, wherein an entry of the segment allocation table includes;

identity of one of an initial set of storage regions;

identity of the first data segment; and

information relating the first data segment to the plurality of data segments.

12. The DS module of claim 8 further comprises:

the first module further functions to;

receive additional data to store with the data;

select another storage region of the DSN for storing the additional data;

update the set of storage regions to include the other storage region;

segment the additional data into an additional plurality of data segments; and

designate a first data segment of the additional plurality of data segments;

the second module further functions to update the data storage mapping information to include at least one of;

the mapping of the set of data partitions and the additional data to the updated set of storage regions;

the additional plurality of data segments; and

the first data segment of the additional plurality of data segments;

the third module further functions to;

encode, in accordance with the first dispersed storage error coding function, the updated data storage mapping information to produce at least one updated set of encoded mapping information slices; and

encode, in accordance with the second dispersed storage error coding function, the additional plurality of data segments to produce an additional plurality of sets of encoded data slices; and

the fourth module further functions to output the at least one updated set of encoded mapping information slices and the additional plurality of sets of encoded data slices to the DSN for storage therein.