Appending data to existing data stored in a dispersed storage network

• US 8,874,991 B2
• Filed: 03/06/2012
• Issued: 10/28/2014
• Est. Priority Date: 04/01/2011
• Status: Active Grant

• 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,302
• Publication Number:
  US 20120254688A1
• Time in Patent Office: 966 Days
• 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 processing module receiving a request to store data in dispersed storage network (DSN) memory and determining whether the data is to be appended to existing data. When the data is to be appended, the method continues with the processing module encoding, using an append dispersed storage error coding function, the data to produce a set of encoded append data slices, generating a set of append commands, wherein an append command of the set of append commands includes an encoded append data slice of the set of encoded append data slices and identity of one of a set of dispersed storage (DS) units, and outputting at least a write threshold number of the set of append commands to at least a write threshold number of the set of DS units.

Claims

1. A method for execution by a dispersed storage processing unit, the method comprises:

receiving a request to store data in dispersed storage network (DSN) memory;

determining whether the data is to be appended to existing data stored in the DSN memory, wherein the existing data is stored in the DSN memory as a set of encoded data slices and wherein the existing data is encoded using a dispersed storage error coding function to produce the set of encoded data slices; and

when the data is to be appended;

encoding, using an append dispersed storage error coding function, the data to produce a set of encoded append data slices;

generating a set of append commands, wherein an append command of the set of append commands includes an encoded append data slice of the set of encoded append data slices and identity of one of a set of dispersed storage (DS) units of the DSN memory; and

outputting at least a write threshold number of the set of append commands to at least a write threshold number of the set of DS units.

2. The method of claim 1, wherein the determining whether the data is to be appended further comprises at least one of:

receiving an append instruction with the data;

interpreting account information associated with an issuer of the request to store the data; and

interpreting directory information of at least one of the data and the existing data.

3. The method of claim 1, wherein the encoding the existing data using the dispersed storage error coding function comprises:

arranging data blocks of the existing data into a plurality of groups of data blocks; and

on a group of data block by group of data block basis, matrix-multiplying the plurality of groups of data blocks with a dispersed storage error encoding matrix to produce a plurality of sets of encoded data slice portions and wherein an encoded data slice of the set of encoded data slices includes an encoded data slice portion from each of the plurality of sets of encoded data slice portions.

4. The method of claim 3, wherein the encoding the data using the append dispersed storage error coding function comprises:

partitioning the data into data blocks based on size of the data blocks of the existing data;

arranging the data blocks of the data into a second plurality of groups of data blocks, wherein a group of data blocks of the second plurality of groups of data blocks includes a same number of data blocks as a group of data blocks of the plurality of groups of data blocks; and

on the group of data block by group of data block basis, matrix-multiplying the second plurality of groups of data blocks with the dispersed storage error encoding matrix to produce a second plurality of sets of encoded data slice portions and wherein an encoded append data slice of the set of encoded append data slices includes an encoded data slice portion from each of the second plurality of sets of encoded data slice portions.

5. The method of claim 1, wherein the append command further comprises at least one of:

a slice name of a corresponding one of set of encoded data slices;

an offset indicator; and

a column identifier of a slice matrix.

6. The method of claim 1 further comprises:

receiving second data for storage in the DSN memory;

determining whether the second data is to be appended to existing appended data stored in the DSN memory, wherein the existing appended data includes the set of encoded data slices and the set of encoded append data slices; and

when the second data is to be appended;

encoding, using the append dispersed storage error coding function, the second data to produce a second set of encoded append data slices;

generating a second set of append commands; and

outputting at least a write threshold number of the second set of append commands to the at least a write threshold number of the set of DS units.

7. A method for execution by a dispersed storage (DS) unit, the method comprises:

storing an encoded data slice of set of encoded data slices, wherein existing data is encoded using a dispersed storage error coding function to produce the set of encoded data slices;

receiving an append command that includes an encoded append data slice of a set of encoded append data slices and an instruction to append the encoded append data slice to the encoded data slice, wherein data is encoded using an append dispersed storage error coding function to produce the set of encoded append data slices; and

updating storage of the encoded data slice based on the encoded append data slice to produce an updated encoded data slice.

8. The method of claim 7 further comprises:

interpreting the append command to identify a slice name of the encoded append data slice;

identifying the encoded data slice based on the slice name;

appending the encoded append data slice to the encoded data slice to produce the updated encoded data slice; and

updating a slice table to associate the slice name with the updated encoded data slice.

9. The method of claim 7, wherein the updating storage of the encoded data slice comprises:

identifying the encoded data slice;

retrieving the encoded data slice to produce a retrieved encoded data slice;

appending the encoded append data slice to the retrieved encoded data slice to produce the updated encoded data slice; and

storing the updated encoded data slice.

10. The method of claim 7 further comprises:

receiving a second append command that includes a second encoded append data slice of a second set of encoded append data slices and another instruction to append the second encoded append data slice to the updated encoded data slice, wherein second data is encoded using the append dispersed storage error coding function to produce the second set of encoded append data slices; and

updating storage of the updated encoded data slice based on the second encoded append data slice to produce a second updated encoded data slice.

11. A module of a dispersed storage processing unit comprises:

a first module operable to receive a request to store data in dispersed storage network (DSN) memory;

a second module operable to determine whether the data is to be appended to existing data stored in the DSN memory, wherein the existing data is stored in the DSN memory as a set of encoded data slices and wherein the existing data is encoded using a dispersed storage error coding function to produce the set of encoded data slices; and

when the data is to be appended;

a third module operable to encode, using an append dispersed storage error coding function, the data to produce a set of encoded append data slices;

a fourth module operable to generate a set of append commands, wherein an append command of the set of append commands includes an encoded append data slice of the set of encoded append data slices and identity of one of a set of dispersed storage (DS) units of the DSN memory; and

a fifth module operable to output at least a write threshold number of the set of append commands to at least a write threshold number of the set of DS units.

12. The module of claim 11, wherein the second module functions to determine whether the data is to be appended by at least one of:

receiving an append instruction with the data;

interpreting account information associated with an issuer of the request to store the data; and

interpreting directory information of at least one of the data and the existing data.

13. The module of claim 11, wherein the third module is further operable to encode the existing data using the dispersed storage error coding function by:

arranging data blocks of the existing data into a plurality of groups of data blocks; and

on a group of data block by group of data block basis, matrix-multiplying the plurality of groups of data blocks with a dispersed storage error encoding matrix to produce a plurality of sets of encoded data slice portions and wherein an encoded data slice of the set of encoded data slices includes an encoded data slice portion from each of the plurality of sets of encoded data slice portions.

14. The module of claim 13, wherein the third module is operable to encode the data using the append dispersed storage error coding function by:

partitioning the data into data blocks based on size of the data blocks of the existing data;

arranging the data blocks of the data into a second plurality of groups of data blocks, wherein a group of data blocks of the second plurality of groups of data blocks includes a same number of data blocks as a group of data blocks of the plurality of groups of data blocks; and

on the group of data block by group of data block basis, matrix-multiplying the second plurality of groups of data blocks with the dispersed storage error encoding matrix to produce a second plurality of sets of encoded data slice portions and wherein an encoded append data slice of the set of encoded append data slices includes an encoded data slice portion from each of the second plurality of sets of encoded data slice portions.

15. The module of claim 11, wherein the append command further comprises at least one of:

a slice name of a corresponding one of set of encoded data slices;

an offset indicator; and

a column identifier of a slice matrix.

16. The module of claim 11 further comprises:

the first module is further operable to receive second data for storage in the DSN memory;

the second module is further operable to determine whether the second data is to be appended to existing appended data stored in the DSN memory, wherein the existing appended data includes the set of encoded data slices and the set of encoded append data slices; and

when the second data is to be appended;

the third module is further operable to encode, using the append dispersed storage error coding function, the second data to produce a second set of encoded append data slices;

the fourth module is further operable to generate a second set of append commands; and

the fifth module is further operable to output at least a write threshold number of the second set of append commands to the at least a write threshold number of the set of DS units.

17. A module of a dispersed storage (DS) unit comprises:

a first module operable to store an encoded data slice of set of encoded data slices, wherein existing data is encoded using a dispersed storage error coding function to produce the set of encoded data slices;

a second module operable to receive an append command that includes an encoded append data slice of a set of encoded append data slices and an instruction to append the encoded append data slice to the encoded data slice, wherein data is encoded using an append dispersed storage error coding function to produce the set of encoded append data slices; and

a third module operable to update storage of the encoded data slice based on the encoded append data slice to produce an updated encoded data slice.

18. The module of claim 17, the third module is further operable to:

interpret the append command to identify a slice name of the encoded append data slice;

identify the encoded data slice based on the slice name;

append the encoded append data slice to the encoded data slice to produce the updated encoded data slice; and

update a slice table to associate the slice name with the updated encoded data slice.

19. The module of claim 17, wherein the third module functions to update storage of the encoded data slice by:

identifying the encoded data slice;

retrieving the encoded data slice to produce a retrieved encoded data slice;

appending the encoded append data slice to the retrieved encoded data slice to produce the updated encoded data slice; and

storing the updated encoded data slice.

20. The module of claim 17 further comprises:

the second module is further operable to receive a second append command that includes a second encoded append data slice of a second set of encoded append data slices and another instruction to append the second encoded append data slice to the updated encoded data slice, wherein second data is encoded using the append dispersed storage error coding function to produce the second set of encoded append data slices; and

the third module is further operable to update storage of the updated encoded data slice based on the second encoded append data slice to produce a second updated encoded data slice.