EFFICIENT STORAGE OF DATA IN A DISPERSED STORAGE NETWORK

• US 20140297776A1
• Filed: 02/04/2014
• Published: 10/02/2014
• Est. Priority Date: 04/01/2013
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Volvovski, Ilya, Gladwin, S. Christopher, Grube, Gary W., Markison, Timothy W., Resch, Jason K., Shirley, Thomas Franklin Jr., Dhuse, Greg, Motwani, Manish, Baptist, Andrew, Leggette, Wesley
• Granted Patent: US 10,075,523 B2
• Time in Patent Office: Days
• US Class Current: 709/212
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: G06F 3/0643 Management of files
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• 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 method begins by a dispersed storage (DS) processing module receiving data for storage and generating a dispersed storage network (DSN) source name for the data. The method continues with the DS processing module determining whether substantially identical data to the data has been previously stored in memory of the DSN. When the substantially identical data has been previously stored in the memory of the DSN, the method continues with the DS processing module generating an object linking file that links the data to the substantially identical data, dispersed storage error encoding the object linking file to produce a set of encoded link file slices, and outputting the set of encoded link file slices for storage in the memory of the DSN.

Claims

1. A method for execution by one or more processing modules of one or more computing devices of a dispersed storage network (DSN), the method comprises:

receiving data for storage;

generating a DSN source name for the data;

determining whether substantially identical data to the data has been previously stored in memory of the DSN;

when the substantially identical data has been previously stored in the memory of the DSN, generating an object linking file that links the data to the substantially identical data;

dispersed storage error encoding the object linking file to produce a set of encoded link file slices; and

outputting the set of encoded link file slices for storage in the memory of the DSN.

2. The method of claim 1, wherein the generating the DSN source name comprises:

obtaining a vault identifier;

generating a random number; and

combining the vault identifier and the random number to produce the DSN source name.

3. The method of claim 1, wherein the determining whether the substantially identical data to the data has been previously stored in the memory of the DSN further comprises:

generating a data tag;

accessing a data tag list to determine whether the previously stored data has a substantially identical data tag;

when the previously stored data has the substantially identical data tag, indicating that the substantially identical data has been stored.

4. The method of claim 1, wherein the determining whether the substantially identical data to the data has been previously stored in the memory of the DSN further comprises:

generating a data tag;

accessing a dispersed hierarchical index using the data tag; and

when an entry in the dispersed hierarchical index is indexed by the data tag, indicating that the substantially identical data has been stored.

5. The method of claim 1, wherein the determining whether the substantially identical data to the data has been previously stored in the memory of the DSN further comprises:

performing a data comparison function between the data and stored data in the memory of the DSN to determine whether the substantially identical data has been previously stored in the memory of the DSN.

6. The method of claim 1, wherein the generating the object linking file comprises:

generating a file that includes a DSN address of the substantially identical data; and

labeling the file with the DSN source name.

7. The method of claim 6, wherein the generating the file further comprises:

generating a data tag;

accessing, based on the data tag, a data tag list to identify an entry associated with the substantially identical data; and

retrieving the DSN address of the substantially identical data from the identified entry.

8. The method of claim 6, wherein the generating the file further comprises:

generating a data tag;

searching, based on the data tag, a dispersed hierarchical index to identify an entry associated with the substantially identical data; and

retrieving the DSN address of the substantially identical data from the identified entry.

9. The method of claim 1 further comprises:

when the substantially identical data has not been previously stored in the memory of the DSN, dispersed storage error encoding the data to produce a plurality of sets of encoded data slices;

outputting the plurality of sets of encoded data slices to the memory of the DSN for storage; and

creating an entry in a data tag list or a dispersed hierarchical index regarding the data.

10. A dispersed storage (DS) module comprises:

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

receive data for storage; and

generate a dispersed storage network (DSN) source name for the data;

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

determine whether substantially identical data to the data has been previously stored in memory of the DSN; and

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

when the substantially identical data has been previously stored in the memory of the DSN, generate an object linking file that links the data to the substantially identical data;

dispersed storage error encode the object linking file to produce a set of encoded link file slices; and

output the set of encoded link file slices for storage in the memory of the DSN.

11. The DS module of claim 10, wherein the first module functions to cause the computing device to generate the DSN source name by:

obtaining a vault identifier;

generating a random number; and

combining the vault identifier and the random number to produce the DSN source name.

12. The DS module of claim 10, wherein the second module further functions to cause the computing device to determine whether the substantially identical data to the data has been previously stored in the memory of the DSN by:

generating a data tag;

accessing a data tag list to determine whether the previously stored data has a substantially identical data tag;

when the previously stored data has the substantially identical data tag, indicating that the substantially identical data has been stored.

13. The DS module of claim 10, wherein the second module further functions to cause the computing device to determine whether the substantially identical data to the data has been previously stored in the memory of the DSN by:

generating a data tag;

accessing a dispersed hierarchical index using the data tag; and

when an entry in the dispersed hierarchical index is indexed by the data tag, indicating that the substantially identical data has been stored.

14. The DS module of claim 10, wherein the second module further functions to cause the computing device to determine whether the substantially identical data to the data has been previously stored in the memory of the DSN by:

performing a data comparison function between the data and stored data in the memory of the DSN to determine whether the substantially identical data has been previously stored in the memory of the DSN.

15. The DS module of claim 10, wherein the third module functions to cause the computing device to generate the object linking file by:

generating a file that includes a DSN address of the substantially identical data; and

labeling the file with the DSN source name.

16. The DS module of claim 15, wherein the third module further functions to cause the computing device to generate the file by:

generating a data tag;

accessing, based on the data tag, a data tag list to identify an entry associated with the substantially identical data; and

retrieving the DSN address of the substantially identical data from the identified entry.

17. The DS module of claim 15, wherein the third module further functions to cause the computing device to generate the file by:

generating a data tag;

searching, based on the data tag, a dispersed hierarchical index to identify an entry associated with the substantially identical data; and

retrieving the DSN address of the substantially identical data from the identified entry.

18. The DS module of claim 10 further comprises:

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

when the substantially identical data has not been previously stored in the memory of the DSN, dispersed storage error encode the data to produce a plurality of sets of encoded data slices;

output the plurality of sets of encoded data slices to the memory of the DSN for storage; and

create an entry in a data tag list or a dispersed hierarchical index regarding the data.