Updating error recovery information in a dispersed storage network

• US 8,949,688 B2
• Filed: 03/06/2012
• Issued: 02/03/2015
• Est. Priority Date: 04/01/2011
• 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): Bhatia, Ajay
• Assistant Examiner(s): GANDHI, DIPAKKUMAR B
• Application Number:
  US13/413,320
• Publication Number:
  US 20120254689A1
• Time in Patent Office: 1,064 Days
• Field of Search: None
• US Class Current: 714/763
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: H04L 2209/34 Encoding or coding, e.g. Huffman coding or error correction
• CPC Class Codes: H04L 67/1004 Server selection for load balancing
• 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 67/5681 Pre-fetching or pre-delivering data based on network characteristics
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/0891 Revocation or update of secret information, e.g. encryption key update or rekeying
• 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/3247 involving digital signatures
• CPC Class Codes: H04N 21/8358 involving watermark protecting executable software by watermarking G06F21/16; image watermarking in general G06T1/0021; watermarks inserted in still images for transmission purposes H04N1/32144; inserting watermarks during video coding H04N19/467

Abstract

A method begins by a dispersed storage (DS) processing module updating an encoded data slice of a set of encoded data slices to produce an updated encoded data slice and sending the updated encoded data slice to a first DS unit of a set of DS units. The method continues with the first DS unit storing the updated encoded data slice and generating partial error recovery information to produce a collection of partial error recovery information. The method continues with the first DS unit outputting the collection of partial error recovery information for storage in at least some of the set of DS units. The method continues with one of the at least some of the set of DS units updating error recovery information of an encoded data slice based on a corresponding one of the collection of partial error recovery information.

Claims

1. A method comprises:

updating, by a dispersed storage (DS) processing module, an encoded data slice of a set of encoded data slices to produce an updated encoded data slice, wherein data is encoded in accordance with a dispersed storage error coding function to produce the set of encoded data slices and wherein at least some of the encoded data slices of the set of encoded data slices include error recovery information;

sending, by the DS processing module, the updated encoded data slice to a first DS unit of a set of DS units;

storing, by the first DS unit, the updated encoded data slice;

for each one of the at least some of the encoded data slices that include the error recovery information, generating, by the first DS unit, partial error recovery information based on one or more of;

the encoded data slice, the updated encoded data slice, update information, and the dispersed storage error coding function to produce a collection of partial error recovery information;

outputting, by the first DS unit, the collection of partial error recovery information for storage in at least some of the set of DS units, which store the at least some of the encoded data slices that include error recovery information; and

updating, by one of the at least some of the set of DS units, the error recovery information of an encoded data slice of the at least some of the encoded data slices that includes the error recovery information based on a corresponding one of the collection of partial error recovery information to produce an encoded data slice that includes updated error recovery information.

2. The method of claim 1 further comprises:

generating, by the DS processing module, the update information to include one or more of;

a slice name, a revision number of the updated encoded data slice, a generator matrix, an encoding matrix, a pillar number of the updated encoded data slice; and

sending, by the DS processing module, the update information to the first DS unit.

3. The method of claim 1, wherein the generating, by the first DS unit, one of the collection of partial error recovery information comprises:

generating a first term of a corresponding one of the at least some of the encoded data slices that includes the error recovery information based on the updated encoded data slice in accordance with the dispersed storage error coding function;

generating a second term of the corresponding one of the at least some of the encoded data slices that includes the error recovery information based on the encoded data slice in accordance with the dispersed storage error coding function; and

performing a mathematical function on the first and second terms to produce the one of the collection of partial error recovery information.

4. The method of claim 3, wherein the generating the first term comprises:

obtaining an encoding matrix of the dispersed storage error coding function;

reducing the encoding matrix to produce a square matrix that excludes one or more rows including a row associated with the corresponding one of the at least some of the encoded data slices that includes the error recovery information;

inverting the square matrix to produce an inverted matrix;

matrix multiplying the inverted matrix by the updated encoded data slice to produce a vector; and

matrix multiplying the vector by a row of the encoding matrix corresponding to the corresponding one of the at least some of the encoded data slices that includes the error recovery information to produce the first term.

5. The method of claim 4, wherein the generating the second term comprises:

matrix multiplying the inverted matrix by the encoded data slice to produce a second vector; and

matrix multiplying the second vector by the row of the encoding matrix corresponding to the corresponding one of the at least some of the encoded data slices that includes the error recovery information to produce the second term.

6. The method of claim 1, wherein the updating the error recovery information by one of the at least some of the set of DS units comprises:

executing a mathematical function on the encoded data slice that includes the error recovery information and the corresponding one of the collection of partial error recovery information to produce the encoded data slice that includes updated error recovery information.

7. A dispersed storage (DS) module comprises:

a first module, when operable within a computing device, causes the computing device to;

facilitate receiving an updated encoded data slice, wherein the updated encoded data slice is an updated version of an encoded data slice of a set of encoded data slices, wherein data is encoded in accordance with a dispersed storage error coding function to produce the set of encoded data slices and wherein at least some of the encoded data slices of the set of encoded data slices include error recovery information; and

facilitate storing the updated encoded data slice; and

a second module, when operable within the computing device, causes the computing device to;

for each one of the at least some of the encoded data slices that include the error recovery information, generate partial error recovery information based on one or more of;

the encoded data slice, the updated encoded data slice, update information, and the dispersed storage error coding function to produce a collection of partial error recovery information;

a third module, when operable within the computing device, causes the computing device to;

facilitate outputting the collection of partial error recovery information for storage in at least some of a set of DS units, which store the at least some of the encoded data slices that include error recovery information.

8. The DS module of claim 7, wherein the update information comprises one or more of:

a slice name, a revision number of the updated encoded data slice, a generator matrix, an encoding matrix, a pillar number of the updated encoded data slice.

9. The DS module of claim 7, wherein the second module functions to generate one of the collection of partial error recovery information by:

generating a first term of a corresponding one of the at least some of the encoded data slices that includes the error recovery information based on the updated encoded data slice in accordance with the dispersed storage error coding function;

generating a second term of the corresponding one of the at least some of the encoded data slices that includes the error recovery information based on the encoded data slice in accordance with the dispersed storage error coding function; and

performing a mathematical function on the first and second terms to produce the one of the collection of partial error recovery information.

10. The DS module of claim 9, wherein the second module functions to generate the first term by:

obtaining an encoding matrix of the dispersed storage error coding function;

reducing the encoding matrix to produce a square matrix that excludes one or more rows including a row associated with the corresponding one of the at least some of the encoded data slices that includes the error recovery information;

inverting the square matrix to produce an inverted matrix;

matrix multiplying the inverted matrix by the updated encoded data slice to produce a vector; and

matrix multiplying the vector by a row of the encoding matrix corresponding to the corresponding one of the at least some of the encoded data slices that includes the error recovery information to produce the first term.

11. The DS module of claim 10, wherein the second module functions to generate the second term by:

matrix multiplying the inverted matrix by the encoded data slice to produce a second vector; and

matrix multiplying the second vector by the row of the encoding matrix corresponding to the corresponding one of the at least some of the encoded data slices that includes the error recovery information to produce the second term.

12. A dispersed storage (DS) system comprises:

a first module, when operable within a first computing device, causes the first computing device to;

update an encoded data slice of a set of encoded data slices to produce an updated encoded data slice, wherein data is encoded in accordance with a dispersed storage error coding function to produce the set of encoded data slices and wherein at least some of the encoded data slices of the set of encoded data slices include error recovery information;

a second module, when operable within a second computing device, causes the second computing device to;

for each one of the at least some of the encoded data slices that include error recovery information, generate partial error recovery information based on one or more of;

the encoded data slice, the updated encoded data slice, update information, and the dispersed storage error coding function to produce a collection of partial error recovery information; and

a third module, when operable within the first or the second computing device, causes the first or the second computing device to;

update the error recovery information of an encoded data slice of the at least some of the encoded data slices that include the error recovery information based on a corresponding one of the collection of partial error recovery information to produce an encoded data slice that includes updated error recovery information.

13. The DS system of claim 12, wherein the update information comprises one or more of:

a slice name, a revision number of the updated encoded data slice, a generator matrix, an encoding matrix, a pillar number of the updated encoded data slice.

14. The DS system of claim 12, wherein the second module functions to generate one of the collection of partial error recovery information by:

generating a first term of a corresponding one of the at least some of the encoded data slices that includes the error recovery information based on the updated encoded data slice in accordance with the dispersed storage error coding function;

generating a second term of the corresponding one of the at least some of the encoded data slices that includes the error recovery information based on the encoded data slice in accordance with the dispersed storage error coding function; and

performing a mathematical function on the first and second terms to produce the one of the collection of partial error recovery information.

15. The DS system of claim 14, wherein the second module functions to generate the first term by:

obtaining an encoding matrix of the dispersed storage error coding function;

reducing the encoding matrix to produce a square matrix that excludes one or more rows including a row associated with the corresponding one of the at least some of the encoded data slices that includes the error recovery information;

inverting the square matrix to produce an inverted matrix;

matrix multiplying the inverted matrix by the updated encoded data slice to produce a vector; and

matrix multiplying the vector by a row of the encoding matrix corresponding to the corresponding one of the at least some of the encoded data slices that includes the error recovery information to produce the first term.

16. The DS system of claim 15, wherein the second module functions to generate the second term by:

matrix multiplying the inverted matrix by the encoded data slice to produce a second vector; and

matrix multiplying the second vector by the row of the encoding matrix corresponding to the corresponding one of the at least some of the encoded data slices that includes the error recovery information to produce the second term.

17. The DS system of claim 12, wherein the third module functions to update the error recovery information by:

executing a mathematical function on the encoded data slice that includes the error recovery information and the corresponding one of the collection of partial error recovery information to produce the encoded data slice that includes updated error recovery information.