DISTRIBUTED STORAGE NETWORK EMPLOYING MULTIPLE ENCODING LAYERS IN DATA ROUTING

• US 20110107094A1
• Filed: 06/17/2010
• Published: 05/05/2011
• Est. Priority Date: 10/30/2009
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: RESCH, JASON K., BAPTIST, ANDREW
• Granted Patent: US 8,522,022 B2
• Time in Patent Office: Days
• US Class Current: 713/168
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 15/17331 Distributed shared memory [DSM], e.g. remote direct memory access [RDMA]
• CPC Class Codes: G06F 21/6272 by registering files or documents with a third party
• CPC Class Codes: G06F 2221/2107 File encryption
• 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 distributed storage processing unit creates multiple different data slices from the same data object, and generates a message including one or more of the different data slices. The distributed storage processing unit identifies a chain of distributed storage units, and encrypts the message into multiple nested layers using, for example, public keys of public/private key pairs associated with each of the storage units in the chain. The distributed storage processing unit sends the layered, encrypted message to the first storage unit in the chain, which decodes and removes the outermost layer, and forwards the message to the next storage unit in the chain. This process continues until the message reaches the endpoint distributed storage unit, which decodes the innermost layer and stores the data slice encoded in the message.

Claims

1. A method comprising:

generating, at a distributed storage processing unit, a plurality of different data slices from a same data object;

creating a message including at least one data slice of the plurality of different data slices;

determining a route through which the message is to be delivered to an endpoint distributed storage unit used to store the at least one data slice, the route including a chain of intermediate distributed storage units;

encoding the message into multiple nested layers, each of the multiple nested layers configured to permit each of the intermediate distributed storage units in the chain to decode and remove an outermost layer of the multiple nested layers, and forward the message to a next intermediate distributed storage unit in the chain until the message reaches the endpoint distributed storage unit, which decodes an innermost layer and stores the at least one data slice; and

sending the message to an initial intermediate distributed storage unit in the chain.

2. The method of claim 1, further comprising:

creating the message to include more than one data slice in a single message, each of the more than one data slices to be delivered to a different endpoint distributed storage unit for storage.

3. The method of claim 1, further comprising:

determining a first route through which a first message is to be delivered, the first route including the endpoint distributed storage unit; and

determining a second route through which a second message is to be delivered, the second route including the same endpoint distributed storage unit as the first route.

4. The method of claim 3, further comprising:

the first message and the second message each including a data slice generated from the same data object.

5. The method of claim 1, further comprising:

generating the multiple nested layers by encoding the message using a public key of the endpoint distributed storage unit to generate a first encoded layer;

encoding the first encoded layer using a public key of a next-to-last distributed storage unit to generate a subsequent encoded layer; and

successively encoding each subsequent encoded layer using a public key of an immediately previous distributed storage unit in the chain of distributed storage units.

20. The device of claim 1, further comprising:

the encoder further to generate the multiple nested layers by encoding the message using a public key of the endpoint distributed storage unit to generate a first encoded layer;

the encoder further to encode the first encoded layer using a public key of a next-to-last distributed storage unit to generate a subsequent encoded layer; and

the encoder further to successively encode each subsequent encoded layer using a public key of an immediately previous distributed storage unit in the chain of distributed storage units.

6. A method comprising:

receiving, at a distributed storage unit, a message constructed to include a plurality of nested, encoded layers, the message including an innermost layer including at least one data slice to be stored by an endpoint distributed storage unit;

decoding an outermost layer of the message;

determining if the distributed storage unit is the endpoint distributed storage unit;

in response to a favorable determining, storing the at least one data slice; and

in response to an unfavorable determining, forwarding the message to a next distributed storage unit in a chain of distributed storage units.

7. The method of claim 6, each of the plurality of nested, encoded layers, except the innermost layer, comprising an address of the next distributed storage unit.

8. The method of claim 6, further comprising:

decoding the outermost layer using a private key of the distributed storage unit; and

wherein a next-to-the outermost layer is encoded using a public key of the next distributed storage unit.

9. The method of claim 6, wherein the innermost layer of the message includes more than one data slice, each of the more than one data slices to be delivered to a different endpoint distributed storage unit for storage, the method further comprising:

determining that the distributed storage unit is the endpoint distributed storage unit for at least one data slice of the more than one data slices;

in response to the determining, storing the at least one data slice for which the distributed storage unit is the endpoint storage unit; and

forwarding a remainder of the message to the next distributed storage unit in the chain of distributed storage units.

10. The method of claim 6, wherein the innermost layer of the message includes more than one data slice, each of the data slices associated with a pillar, the method further comprising:

storing each of the more than one data slices in a device corresponding to the pillar associated with the data slice.

11. A distributed storage unit comprising:

an input coupled to a communication network to receive a message constructed to include a plurality of nested, encoded layers, the message including an innermost layer including at least one data slice to be stored by an endpoint distributed storage unit;

a processor to decode an outermost layer of the message and determine if the distributed storage unit is the endpoint distributed storage unit;

a memory to store the at least one data slice if the distributed storage unit is the endpoint distributed storage unit; and

an output to forward the message to a next distributed storage unit in a chain of distributed storage units if the distributed storage unit is not the endpoint distributed storage unit.

12. The distributed storage unit of claim 11, each of the plurality of nested, encoded layers, except the innermost layer, comprising an address of the next distributed storage unit.

13. The distributed storage unit of claim 11, further comprising:

the processor to decode the outermost layer using a private key of the distributed storage unit; and

wherein a next-to-the outermost layer is encoded using a public key of the next distributed storage unit.

14. The distributed storage unit of claim 11, wherein the innermost layer of the message includes more than one data slice, each of the more than one data slices to be delivered to a different endpoint distributed storage unit for storage, the distributed storage unit further comprising:

storage to store a data slice for which the distributed storage unit is the endpoint storage unit; and

an output to forward a remainder of the message to the next distributed storage unit in the chain of distributed storage units.

15. The distributed storage unit of claim 11, wherein the innermost layer of the message includes more than one data slice, each of the data slices associated with a pillar, the distributed storage unit further comprising:

storage to store each of the more than one data slices in a storage device corresponding to the pillar associated with the data slice.

16. A device comprising:

a processor to create a message including at least one data slice of a plurality of different data slices, each data slice representing different encodings of a data segment;

the processor further to determine a route through which the message is to be delivered to an endpoint distributed storage unit used to store the at least one data slice, the route including a chain of intermediate distributed storage units;

an encoder to encode the message into multiple nested layers, each of the multiple nested layers configured to permit each of the intermediate distributed storage units in the chain to decode and remove an outermost layer of the multiple nested layers, and forward the message to a next intermediate distributed storage unit in the chain, until the message reaches the endpoint distributed storage unit, which decodes an innermost layer and stores the at least one data slice; and

an interface to send the message to an initial intermediate distributed storage unit in the chain.

17. The device of claim 16, the processor further to:

include more than one data slice in a single message, each of the more than one data slices to be delivered to a different endpoint distributed storage unit for storage.

18. The device of claim 16, the processor further to:

determine a first route through which a first message is to be delivered, the first route including the endpoint distributed storage unit; and

determine a second route through which a second message is to be delivered, the second route including the same endpoint distributed storage unit as the first route.

19. The device of claim 18, further comprising:

the first message and the second message each including a different data slice generated from a same data object.