Securing data in a dispersed storage network using an encoding equation

• US 9,104,691 B2
• Filed: 01/16/2013
• Issued: 08/11/2015
• Est. Priority Date: 04/20/2009
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Resch, Jason K., Leggette, Wesley
• Primary Examiner(s): Armouche, Hadi
• Assistant Examiner(s): WRIGHT, BRYAN F
• Application Number:
  US13/742,577
• Publication Number:
  US 20130151470A1
• Time in Patent Office: 937 Days
• Field of Search: 713/193
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 16/1844 Management specifically adapted to replicated file systems
• CPC Class Codes: G06F 21/1083 Partial license transfers
• CPC Class Codes: G06F 2211/1059 Parity-single bit-RAID5, i.e. RAID 5 implementations
• CPC Class Codes: H04L 2209/34 Encoding or coding, e.g. Huffman coding or error correction
• 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: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions

Abstract

A method begins by dividing a data segment into data segment portions. The method continues by encoding the data segment portions to produce a plurality of sets of encoded data segment portions. A data segment portion is encoded by, first, selecting an encoding equation and an encoding constant(s). The encoding continues by setting a first variable to the data segment portion. The encoding continues by setting a second variable to one of a set of pillar numbers. The encoding continues by executing the encoding equation using the encoding constant, the first variable, and the second variable to produce one of the plurality of sets of encoded data segment portions. The method continues by arranging the plurality of sets of encoded data segment portions into a plurality of encoded data slices. The method continues by sending the plurality of encoded data slices to distributed storage units of a distributed storage network.

Claims

1. A method comprises:

dividing a data segment into a plurality of data segment portions;

encoding the plurality of data segment portions to produce a plurality of sets of encoded data segment portions, wherein a data segment portion of the plurality of data segment portions is encoded by;

selecting an encoding equation and at least one encoding constant for the encoding equation, wherein the encoding equation includes an equation for a geometric shape, wherein a given number of points are required to determine the geometric shape;

setting a first variable of the encoding equation to the data segment portion;

setting a second variable of the encoding equation to one of a set of pillar numbers;

executing the encoding equation using the encoding constant, the first variable, and the second variable to produce one of the plurality of sets of encoded data segment portions;

arranging the plurality of sets of encoded data segment portions into a plurality of encoded data slices; and

sending the plurality of encoded data slices to distributed storage units of a distributed storage network.

2. The method of claim 1 further comprises at least one of:

selecting a same encoding equation for each of the data segment portions and a same encoding constant; and

selecting a same encoding equation for each of the data segment portions and a different encoding constant.

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

selecting a first encoded equation and a first encoding constant for a first data segment portion of the plurality of data segment portions;

selecting a second encoded equation and the first encoding constant for a second data segment portion of the plurality of data segment portions; and

selecting a second encoded equation and a second encoding constant for a second data segment portion of the plurality of data segment portions.

4. The method of claim 1, wherein the selecting an encoding equation and at least one encoding constant comprises:

accessing vault information to identify the encoding equation and the at least one encoding constant for the data segment portion.

5. The method of claim 1, wherein the equation for the geometric shape comprises one of:

y=mx+b, where ‘

b’

is the at least one encoding constant, ‘

m’

is the first variable, ‘

x’

is the second variable, and ‘

y’

is one of the sets of encoded data segment portions; and

y=ax²+bx+c, where ‘

c’

is a first constant of the at least one encoding constant, ‘

b’

is a second constant of the at least one encoding constant, ‘

a’

is the first variable, ‘

x’

is the second variable, and ‘

y’

is the one of the set of encoded data segment portions.

6. The method of claim 1, wherein the encoding the plurality of data segment portions comprises:

entering a loop that includes;

selecting the data segment portion of the plurality of data segment portions;

selecting the encoding equation for the selected data segment portion;

selecting the encoding constant;

setting the first variable of the encoding equation to the selected data segment portion;

entering an inner loop that includes;

selecting a pillar number of a set of pillar numbers to produce a selected pillar number;

setting the second variable of the encoding equation to the selected pillar number;

executing the encoding equation using the first variable, the second variable, and the encoding constant to produce an encoded data segment portion;

exiting the inner loop when each pillar number of the selected pillar numbers has been selected, which creates a set of the plurality of sets of encoded data segment portions; and

repeating the inner loop when each pillar number of the selected pillar numbers has not been selected, wherein the inner loop is repeated using an unselect pillar number of the set of pillar numbers;

exiting the loop when each of the plurality of data segment portions has been selected, which creates the plurality of sets of encoded data segment portions; and

repeating the loop when each of the plurality of data segment portions has not been selected, wherein the loop is repeated using an unselected data segment portion of the plurality of data segment portions.

7. The method of claim 1, wherein the arranging the plurality of sets of encoded data segment portions into a plurality of encoded data slices comprises:

temporarily storing first encoded data segment portion from at least some of the plurality of sets of encoded data segment portions in a first cache memory;

temporarily storing second encoded data segment portions from at least some of the plurality of sets of encoded data segment portions in a second cache memory;

creating a first encoded data slices of the plurality of encoded data slices from encoded data segment portions stored in the first cache memory; and

creating a second encoded data slices of the plurality of encoded data slices from encoded data segment portions stored in the second cache memory.

8. An encoding device comprises:

an interface;

memory; and

a processing module operable coupled to the interface and the memory, wherein the processing module is operable to;

divide a data segment into a plurality of data segment portions;

encode the plurality of data segment portions to produce a plurality of sets of encoded data segment portions, wherein a data segment portion of the plurality of data segment portions is encoded by;

selecting an encoding equation and at least one encoding constant for the encoding equation, wherein the encoding equation includes an equation for a geometric shape, wherein a given number of points are required to determine the geometric shape;

setting a first variable of the encoding equation to the data segment portion;

setting a second variable of the encoding equation to one of a set of pillar numbers;

executing the encoding equation using the encoding constant, the first variable, and the second variable to produce one of the plurality of sets of encoded data segment portions;

arrange the plurality of sets of encoded data segment portions into a plurality of encoded data slices; and

send, via the interface, the plurality of encoded data slices to distributed storage units of a distributed storage network.

9. The encoding device of claim 8, wherein the processing module is further operable to perform at least one of:

selecting a same encoding equation for each of the data segment portions and a same encoding constant; and

selecting a same encoding equation for each of the data segment portions and a different encoding constant.

10. The encoding device of claim 8, wherein the processing module is further operable to perform at least one of:

selecting a first encoded equation and a first encoding constant for a first data segment portion of the plurality of data segment portions;

selecting a second encoded equation and the first encoding constant for a second data segment portion of the plurality of data segment portions; and

selecting a second encoded equation and a second encoding constant for a second data segment portion of the plurality of data segment portions.

11. The encoding device of claim 8, wherein the processing module is further operable to select the encoding equation and at least one encoding constant by:

accessing vault information to identify the encoding equation and the at least one encoding constant for the data segment portion.

12. The encoding device of claim 8, wherein the equation for the geometric shape comprises one of:

y=mx+b, where ‘

b’

is the at least one encoding constant, ‘

m’

is the first variable, ‘

x’

is the second variable, and ‘

y’

is one of the sets of encoded data segment portions; and

y=ax²+bx+c, where ‘

c’

is a first constant of the at least one encoding constant, ‘

b’

is a second constant of the at least one encoding constant, ‘

a’

is the first variable, ‘

x’

is the second variable, and ‘

y’

is the one of the sets of encoded data segment portions.

13. The encoding device of claim 8, wherein the processing module is further operable to encode the plurality of data segment portions by:

entering a loop that includes;

selecting the data segment portion of the plurality of data segment portions;

selecting the encoding equation for the selected data segment portion;

selecting the encoding constant;

setting the first variable of the encoding equation to the selected data segment portion;

entering an inner loop that includes;

selecting a pillar number of a set of pillar numbers to produce a selected pillar number;

setting the second variable of the encoding equation to the selected pillar number;

executing the encoding equation using the first variable, the second variable, and the encoding constant to produce an encoded data segment portion;

exiting the inner loop when each pillar number of the selected pillar numbers has been selected, which creates a set of the plurality of sets of encoded data segment portions; and

repeating the inner loop when each pillar number of the selected pillar numbers has not been selected, wherein the inner loop is repeated using an unselect pillar number of the set of pillar numbers;

exiting the loop when each of the plurality of data segment portions has been selected, which creates the plurality of sets of encoded data segment portions; and

repeating the loop when each of the plurality of data segment portions has not been selected, wherein the loop is repeated using an unselected data segment portion of the plurality of data segment portions.

14. The encoding device of claim 8, wherein the processing module is further operable to arrange the plurality of sets of encoded data segment portions into a plurality of encoded data slices by:

temporarily storing first encoded data segment portion from at least some of the plurality of sets of encoded data segment portions in a first cache memory;

temporarily storing second encoded data segment portions from at least some of the plurality of sets of encoded data segment portions in a second cache memory;

creating a first encoded data slices of the plurality of encoded data slices from encoded data segment portions stored in the first cache memory; and

creating a second encoded data slices of the plurality of encoded data slices from encoded data segment portions stored in the second cache memory.