Router-based dispersed storage network method and apparatus

• US 9,043,489 B2
• Filed: 08/04/2010
• Issued: 05/26/2015
• Est. Priority Date: 10/30/2009
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Grube, Gary W., Markison, Timothy W.
• Primary Examiner(s): COX, NATISHA D
• Application Number:
  US12/850,610
• Publication Number:
  US 20110106972A1
• Time in Patent Office: 1,756 Days
• Field of Search: 709/226
• US Class Current: 709/238
• CPC Class Codes: G06F 11/2089 Redundant storage control functionality
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 12/1009 using page tables, e.g. page table structures
• CPC Class Codes: G06F 12/1045 associated with a data cache
• CPC Class Codes: G06F 13/1668 Details of memory controller
• CPC Class Codes: G06F 2212/401 Compressed data
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0629 Configuration or reconfiguration of storage systems
• 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/0683 Plurality of storage devices
• 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/15 Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes H03M13/17 takes precedence
• 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: H04L 41/06 Management of faults, events, alarms or notifications
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 67/06 specially adapted for file transfer, e.g. file transfer protocol [FTP]
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• 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 router receiving data for storage and interpreting the data to determine whether the data is to be forwarded or error encoded. The method continues with the router obtaining a routing table when the data is to be error encoded. Next, the method continues with the router selecting a routing option from the plurality of routing options and determining error coding dispersal storage function parameters based on the routing option. Next, the method continues with the router encoding the data based on the error coding dispersal storage function parameters to produce a plurality of sets of encoded data slices. Next, the method continues with the router outputting at least some of the encoded data slices of a set of the plurality of sets of encoded data slices to an entry point of the routing option.

Claims

1. A method comprises:

disperse storage error encoding, by a processing module, a data segment of data to produce a set of encoded data slices;

determining, by the processing module, a storage location for each encoded data slice of the set of encoded data slices to be within one of a router of a routing storage layer and a storage unit of a distributed storage network (DSN) memory;

generating, by the processing module, a DSN address for each encoded data slice of the set of encoded data slices based on the determined storage location;

sending, by the processing module, the set of encoded data slices and the corresponding set of DSN addresses to at least one entry point router of the routing storage layer;

on an encoded data slice by encoded data slice basis;

determining, by the at least one entry point router, whether an encoded data slice of the set of encoded data slices is to be stored in the routing storage layer or in the DSN memory based on the DSN address of the encoded data slice;

when the encoded data slice is to be stored in the routing storage layer;

determining, by the at least one entry point router, whether the encoded data slice is to be locally stored or forwarded within the routing storage layer;

when the encoded data slice is to be forwarded, forwarding, by the at least one entry point router, the encoded data slice to another router of the routing storage layer in accordance with a routing table; and

when the encoded data slice is to be stored in the DSN memory;

determining, by the at least one entry point router, a routing path within the routing storage layer based on the routing table; and

sending, by the at least one entry point router, the encoded data slice to a first router of the routing path for routing to the DSN memory via the routing path.

2. The method of claim 1, wherein the sending the set of encoded data slices and the corresponding set of DSN addresses further comprises:

sending a first sub-set of the set of encoded data slices and a corresponding first sub-set of the set of DSN addresses to a first entry point router of the at least one entry point router; and

sending a second sub-set of the set of encoded data slices and a corresponding second sub-set of the set of DSN addresses to a second entry point router of the at least one entry point router.

3. The method of claim 1 further comprises:

obtaining the routing table by at least one of;

receiving the routing table in response to a request message;

retrieving the routing table from a routing table database; and

receiving the routing table in conjunction with receiving the data.

4. The method of claim 1, wherein the determining the routing path within the routing storage layer based on the routing table comprises:

selecting a routing option that includes at least one of;

a source associated with the source ID;

a destination associated with the destination ID;

routing ID;

a routing path priority; and

a routing path of routers.

5. The method of claim 1 further comprises:

receiving, by the entry point router, metadata associated with the data segment; and

utilizing, by the entry point router, the metadata to obtain the routing table.

6. The method of claim 1 , further comprises:

receiving, by the other router of the routing storage layer, the forwarded encoded data slice;

determining, by the other router, whether the forwarded encoded data slice is to be locally stored or forwarded to yet another router of the routing storage layer based on the corresponding DSN address of the forwarded encoded data slice; and

when the forwarded encoded data slice is to be locally stored, storing, by the other router, the forwarded encoded data slice.

7. A router for use in a routing storage network comprises:

an interface;

memory; and

a processing module operable to;

receive, via the interface and when operable in an entry point router mode, at least some encoded data slices of a set of encoded data slices, wherein a data segment of data was disperse storage error encoded to produce the set of encoded data slices, wherein each of the at least some of the encoded data slices has a corresponding distributed storage network (DSN) address that includes whether the encoded data slice is to be stored in a storage unit of DSN memory or in a router of a routing storage layer; and

on an encoded data slice by encoded data slice basis;

determine whether an encoded data slice of the at least some of the set of encoded data slices is to be stored in the routing storage layer or in the DSN memory based on the DSN address of the encoded data slice;

when the encoded data slice is to be stored in the routing storage layer;

determine whether the encoded data slice is to be locally stored or forwarded within the routing storage layer;

when the encoded data slice is to be forwarded, forward the encoded data slice to another router of the routing storage layer in accordance with a routing table; and

when the encoded data slice is to be stored in the DSN memory;

determine a routing path within the routing storage layer based on the routing table; and

send, via the interface, the encoded data slice to a first router of the routing path for routing to the DSN memory via the routing path.

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

when the encoded data slice is to be locally stored, store the encoded data in the memory.

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

receive, via the interface, the routing table in response to a request message;

retrieve the routing table from a routing table database; and

receive, via the interface, the routing table in conjunction with receiving the at least some of the set of encoded data slices.

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

select a routing option that includes at least one of;

a source associated with the source ID;

a destination associated with the destination ID;

routing ID;

a routing path priority; and

a routing path of routers.

11. The router of claim 7, wherein the processing module is further operable to:

receive, via the interface, metadata associated with the data segment; and

utilize the metadata to obtain the routing table.

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

receive, when not in the entry point mode, a forwarded encoded data slice;

determine whether the forwarded encoded data slice is to be locally stored or forwarded to another router of the routing storage layer based on the corresponding DSN address of the forwarded encoded data slice; and

when the forwarded encoded data slice is to be locally stored, store the forwarded encoded data slice in the memory.