Distributed storage network employing multiple encoding layers in data routing

• US 8,522,022 B2
• Filed: 06/17/2010
• Issued: 08/27/2013
• 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: Resch, Jason K., Baptist, Andrew
• Primary Examiner(s): Popham, Jeffrey D
• Application Number:
  US12/817,201
• Publication Number:
  US 20110107094A1
• Time in Patent Office: 1,167 Days
• Field of Search: 713/168
• 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 for execution by a distributed storage processing module, the method comprising:

generating a plurality of data slices from a data segment;

creating a plurality of storage command messages, wherein a storage command message of the plurality of storage command messages includes a data slice of the plurality of data slices;

determining a set of intermediate distributed storage units that includes an entry distributed storage unit and an exit distributed storage unit;

encoding the plurality of storage command messages in accordance with a nested layer encoding to produce an encoded message, wherein the nested layer encoding includes adding an encoding layer for each distributed storage unit of the set of intermediate distributed storage units, wherein the encoding of the plurality of storage command messages includes;

encoding the plurality of storage command messages using a public key of the exit distributed storage unit to generate a first layer encoded message;

identifying a next distributed storage unit of the set of intermediate distributed storage units;

when the next distributed storage unit is the entry distributed storage unit, encoding the first layer encoded message using a public key of the entry distributed storage unit to produce the encoded message;

when the next distributed storage unit is not the entry distributed storage unit;

encoding the first layer encoded message using a public key of the next distributed storage unit to produce a next layer encoded message; and

repeating the identifying the next distributed storage unit of the set of intermediate distributed storage units for the next layer encoded message; and

sending the encoded message to the entry distributed storage unit, wherein each of the set of intermediate distributed storage units respectively removes a corresponding encoding layer of the encoded message such that the exit distributed storage unit recovers the plurality of storage command messages and sends the plurality of storage command messages to a storage set of distributed storage units such that the set of distributed storage units executes the plurality of storage command messages.

2. The method of claim 1, further comprising:

creating a second plurality of storage command messages for a second plurality of data slices;

determining a second set of intermediate distributed storage units that includes a second entry distributed storage unit and a second exit distributed storage unit;

encoding the second plurality of storage command messages in accordance with a second nested layer encoding to produce a second encoded message, wherein the second nested layer encoding includes adding an encoding layer for each distributed storage unit of the second set of intermediate distributed storage units; and

sending the second encoded message to the second entry distributed storage unit, wherein each of the second set of intermediate distributed storage units respectively removes a corresponding encoding layer of the second encoded message such that the second exit distributed storage unit recovers the second plurality of storage command messages and sends the second plurality of storage command messages to a storage set of distributed storage units.

3. The method of claim 1, further comprising at least one of:

determining the set of intermediate distributed storage units to include at least one distributed storage unit of the storage set of distributed storage units; and

determining the storage set of distributed storage units to include at least one distributed storage unit of the set of intermediate distributed storage units.

4. A device comprising:

a processing module operable to;

generate a plurality of data slices from a data segment;

create a plurality of storage command messages, wherein a storage command message of the plurality of storage command messages includes a data slice of the plurality of data slices; and

determine a set of intermediate distributed storage units that includes an entry distributed storage unit and an exit distributed storage unit;

an encoder operable to encode the plurality of storage command messages in accordance with a nested layer encoding to produce an encoded message, wherein the nested layer encoding includes adding an encoding layer for each distributed storage unit of the set of intermediate distributed storage units, wherein the encoder is further operable to encode the plurality of storage command messages by;

encoding the plurality of storage command messages using a public key of the exit distributed storage unit to generate a first layer encoded message;

identifying a next distributed storage unit of the set of intermediate distributed storage units;

when the next distributed storage unit is the entry distributed storage unit, encoding the first layer encoded message using a public key of the entry distributed storage unit to produce the encoded message;

when the next distributed storage unit is not the entry distributed storage unit;

encoding the first layer encoded message using a public key of the next distributed storage unit to produce a next layer encoded message; and

repeating the identifying the next distributed storage unit of the set of intermediate distributed storage units for the next layer encoded message; and

an interface operable to send the encoded message to the entry distributed storage unit, wherein each of the set of intermediate distributed storage units respectively removes a corresponding encoding layer of the encoded message such that the exit distributed storage unit recovers the plurality of storage command messages and sends the plurality of storage command messages to a storage set of distributed storage units such that the set of distributed storage units executes the plurality of storage command messages.

5. The device of claim 4 further comprises:

the processing module is further operable to;

create a second plurality of storage command messages for a second plurality of data slices;

determining a second set of intermediate distributed storage units that includes a second entry distributed storage unit and a second exit distributed storage unit;

the encoder is further operable to encode the second plurality of storage command messages in accordance with a second nested layer encoding to produce a second encoded message, wherein the second nested layer encoding includes adding an encoding layer for each distributed storage unit of the second set of intermediate distributed storage units; and

the interface is further operable to send the second encoded message to the second entry distributed storage unit, wherein each of the second set of intermediate distributed storage units respectively removes a corresponding encoding layer of the second encoded message such that the second exit distributed storage unit recovers the second plurality of storage command messages and sends the second plurality of storage command messages to a storage set of distributed storage units.

6. The device of claim 4, wherein the processing module is further operable to determine a set of intermediate distributed storage units by:

determining the set of intermediate distributed storage units to include at least one distributed storage unit of the storage set of distributed storage units; and

determining the storage set of distributed storage units to include at least one distributed storage unit of the set of intermediate distributed storage units.