Distributed storage network utilizing memory stripes

• US 8,554,994 B2
• Filed: 05/11/2010
• Issued: 10/08/2013
• Est. Priority Date: 09/29/2009
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Resch, Jason K.
• Primary Examiner(s): PATEL, KAUSHIKKUMAR M
• Application Number:
  US12/777,887
• Publication Number:
  US 20110078371A1
• Time in Patent Office: 1,246 Days
• Field of Search: 711/114, 711/170
• US Class Current: 711/114
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 2211/1011 Clustered RAID, i.e. clustered or de-clustered RAID where data and parity are spread over more disks than blocks in a parity group
• CPC Class Codes: G06F 3/0617 in relation to availability
• CPC Class Codes: G06F 3/0656 Data buffering arrangements
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• 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: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/101 based on network conditions
• 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: H04N 21/231 Content storage operation, e.g. caching movies for short term storage, replicating data over plural servers, prioritizing data for deletion
• CPC Class Codes: H04N 21/2405 Monitoring of the internal components or processes of the server, e.g. server load allocation of resources in multiprogramming arrangements G06F9/50; performance measurement of computer activity G06F11/34
• CPC Class Codes: H04N 21/442 Monitoring of processes or resources, e.g. detecting the failure of a recording device, monitoring the downstream bandwidth, the number of times a movie has been viewed, the storage space available from the internal hard disk arrangements for monitoring broadcast services or broadcast-related services H04H60/29; arrangements for identifying or recognising characteristics with a direct linkage to broadcast information H04H60/35; monitoring of user activities for profile generation for accessing a video database G06F16/739; monitoring in wireless networks H04W24/00

Abstract

Multiple data slices are generated from an original data segment. The data slices are constructed to prevent recovery of the original data segment using a single related data slice, but to allow recovery of the original data segment using fewer than all of the data slices. Each data slice is stored in the same memory stripe as the other data slices. The memory stripe extends across multiple memory devices and multiple different distributed storage units. The memory device in which each data slice is stored can be determined based on a source name associated with each data slice.

Claims

1. A method for storing error coded data slices in a dispersed storage network (DSN), wherein a data segment is encoded using an error coding dispersed storage function to produce a plurality of error coded data slices, wherein each of the plurality of error coded data slices has a unique slice name, and wherein each of the unique slice names includes a common source name and unique addressing information, the method comprising:

receiving, by a first dispersed storage unit of the DSN, a first error coded data slice of a plurality of error coded data slices and the unique slice name of the first error coded data slice;

performing, by the first dispersed storage unit, a deterministic function on the common source name of the unique slice name of the first error coded data slice to select a memory device of a plurality of memory devices of the first distributed storage unit; and

storing, by the first dispersed storage unit, the first error coded data slice in the memory device of the plurality of memory devices of the first dispersed storage unit based on the unique slice name of the first error coded data slice;

receiving, by a second dispersed storage unit of the DSN, a second error coded data slice of a plurality of error coded data slices and the unique slice name of the second error coded data slice;

performing, by the second dispersed storage unit, the deterministic function on the common source name of the unique slice name of the second error coded data slice to select a memory device of a plurality of memory devices of the second distributed storage unit; and

storing, by the second dispersed storage unit, the second error coded data slice in the memory device of the plurality of memory devices of the second dispersed storage unit based on the unique slice name of the second error coded data slice.

2. The method of claim 1 further comprising:

performing, by the first dispersed storage unit, a reducing function as the deterministic function to produce a reduced length source name;

selecting, by the first dispersed storage unit, the memory device of the plurality of memory devices of the first distributed storage unit based on the reduced length source name;

performing, by the second dispersed storage unit, the reducing function as the deterministic function to produce the reduced length source name; and

selecting, by the second dispersed storage unit, the memory device of the plurality of memory devices of the second distributed storage unit based on the reduced length source name.

3. The method of claim 2, wherein the reducing function comprising one or more of:

a hash function;

a truncating function; and

modulo function.

4. The method of claim 1, wherein the unique addressing information comprising:

vault information.

5. The method of claim 1 further comprising:

performing, by the first dispersed storage unit, a hash function as the deterministic function on the common source name to produce a hashed source name;

performing, by the first dispersed storage unit, a truncating function on the hashed source name to produce a truncated source name; and

selecting, by the first dispersed storage node, the memory device of a plurality of memory devices of the first distributed storage unit based on the truncated source name.

6. The method of claim 1, further comprising:

updating, by the first dispersed storage unit, a digital-storage-network-address to physical-location table to record storage of the first error coded data slice in the memory device of the plurality of memory devices of the first distributed storage unit.

7. A distributed storage unit comprising:

an interface to receive error coded data slice of a plurality of error data slices, wherein a data segment is encoded using an error coding dispersed storage function to produce the plurality of error coded data slices, wherein each of the plurality of error coded data slices has a unique slice name, and wherein each of the unique slice names includes a common source name and unique addressing information;

a plurality of memory devices; and

a processing module operable to;

perform a deterministic function on the common source name of the unique slice name of the error coded data slice to select a memory device of the plurality of memory devices; and

facilitate storing the error coded data slice in the memory device based on the unique slice name of the error coded data slice.

8. The distributed storage unit of claim 7, wherein the processing module is further operable to:

perform a reducing function as the deterministic function to produce a reduced length source name; and

select the memory device based on the reduced length source name.

9. The distributed storage unit of claim 8, wherein the reducing function comprising one or more of:

a hash function;

a truncating function; and

modulo function.

10. The distributed storage unit of claim 8, wherein the unique addressing information comprising:

vault information.

11. The distributed storage unit of claim 8, wherein the processing module is further operable to:

perform a hash function as the deterministic function on the common source name to produce a hashed source name;

perform a truncating function on the hashed source name to produce a truncated source name; and

select the memory device based on the truncated source name.