Scalable de-duplication for storage systems

Patent metadata

Field	Value
Publication number	US-9239843-B2
Application number	US-63890709-A
Country	US
Kind code	B2
Filing date	Dec 15, 2009
Priority date	Dec 15, 2009
Publication date	Jan 19, 2016
Grant date	Jan 19, 2016

Abstract

A method for performing storage system de-duplication. The method includes accessing a plurality of initial partitions of files of a storage system and performing a de-duplication on each of the initial partitions. For each duplicate found, an indicator comprising the metadata that is similar across said each duplicate is determined. For each indicator, indicators are determined that infer a likelihood that data objects with said indicators contain duplicate data is high. Optimized partitions are generated in accordance with the chosen indicators. A de-duplication process is subsequently performed on each of the optimized partitions.

First claim

What is claimed is:

1. A method for performing storage system de-duplication, comprising:
accessing a plurality of initial partitions of files of a storage system, wherein each of the plurality of initial partitions has object properties;
performing a de-duplication on each of the initial partitions;
for each duplicate partition found from the plurality of initial partitions, determining an indicator comprising metadata that is similar across said each duplicate partition, wherein the metadata is determined based on the object properties of the initial partitions;
for each of the determined indicators, determining a ratio of the number of times the respective metadata is common across duplicate partitions of the initial partitions to the number of times the respective metadata is common across non-duplicate partitions of the initial partitions, wherein the determined indicators having high ratios weighted across all of the initial partitions are designated as chosen indicators;
generating optimized partitions in accordance with the chosen indicators, wherein the chosen indicators are combined to generate the optimized partitions, wherein each optimized partition includes a separate de-duplication index structure, wherein each separate de-duplication index structure is distributed across data servers, and wherein each data server is responsible for performing de-duplication between a subset of the files according to the separate de-duplication index structure; and
performing a de-duplication on each of the optimized partitions.

2. The method of claim 1 , wherein the plurality of initial partitions are randomly selected partitions of files of the storage system.

3. The method of claim 1 , wherein the chosen indicators enable the generation of optimized partitions in a plurality of different directions across the files of the storage system.

4. The method of claim 1 , wherein Boolean operations are used to combine chosen indicators to generate optimized partitions.

5. The method of claim 1 , wherein optimized partitions are generated iteratively to detect duplicates within the files of the storage system.

6. The method of claim 1 , wherein the de-duplication performed on each of the optimized partitions is performed out of band with respect to the storage system.

7. The method of claim 1 , wherein the de-duplication performed on each of the optimized partitions is performed in-band with respect to the storage system.

8. A non-transitory computer readable storage medium having stored thereon computer executable instructions that, if executed by a computer system, cause the computer system to perform a method comprising:
out of a plurality of partitions of files on a file storage system, accessing a plurality of initial partitions, wherein each of the plurality of initial partitions has object properties;
performing a de-duplication on each of the initial partitions;
for each duplicate partition found from the plurality of initial partitions, determining an indicator comprising metadata that is similar across said each duplicate partition, wherein the metadata is determined based on the object properties of the initial partitions;
for each of the determined indicators, determining a ratio of the number of times the respective metadata is common across duplicate partitions of the initial partitions to the number of times the respective metadata is common across non-duplicate partitions of the initial partitions, wherein the determined indicators having high ratios weighted across all of the initial partitions are designated as chosen indicators;
generating optimized partitions in accordance with the chosen indicators, wherein the chosen indicators are combined to generate the optimized partitions, wherein each optimized partition includes a separate de-duplication index structure, wherein each separate de-duplication index structure is distributed across data servers, and wherein each data server is responsible for performing de-duplication between a subset of the files according to the separate de-duplication index structure; and
performing a de-duplication on each of the optimized partitions.

9. The non-transitory computer readable storage medium of claim 8 , wherein the plurality of initial partitions are user defined partitions of files of the storage system.

10. The non-transitory computer readable storage medium of claim 8 , wherein the chosen indicators enable the generation of optimized partitions in a plurality of different directions across the files of the storage system.

11. The non-transitory computer readable storage medium of claim 8 , wherein Boolean operations are used to combine chosen indicators to generate optimized partitions.

12. The non-transitory computer readable storage medium of claim 8 , wherein optimized partitions are generated iteratively to detect duplicates within the files of the storage system.

13. The non-transitory computer readable storage medium of claim 8 , wherein the de-duplication performed on each of the optimized partitions is performed out of band with respect to the storage system.

14. The non-transitory computer readable storage medium of claim 8 , wherein the de-duplication performed on each of the optimized partitions is performed in-band with respect to the storage system.

15. A server computer system, comprising:
a computer system having a computer processor coupled to non-transitory computer readable storage media and executing computer readable code which causes the computer system to:
access a plurality of initial partitions of files of a storage system, wherein each of the plurality of initial partitions has object properties;
perform a de-duplication on each of the initial partitions;
for each duplicate partition found from the plurality of initial partitions, determine an indicator comprising metadata that is similar across said each duplicate partition, wherein the metadata is determined based on the object properties of the initial partitions;
for each of the determined indicators, determining a ratio of the number of times the respective metadata is common across duplicate partitions of the initial partitions to the number of times the respective metadata is common across non-duplicate partitions of the initial partitions, wherein the determined indicators having high ratios weighted across all of the initial partitions are designated as chosen indicators;
generate optimized partitions in accordance with the chosen indicators, wherein the chosen indicators are combined to generate the optimized partitions, wherein each optimized partition includes a separate de-duplication index structure, wherein each separate de-duplication index structure is distributed across data servers, and wherein each data server is responsible for performing de-duplication between a subset of the files according to the separate de-duplication index structure; and
perform a de-duplication on each of the optimized partitions.

16. The server computer system of claim 1 , wherein the plurality of initial partitions are randomly selected partitions of files of the storage system.

17. The server computer system of claim 1 , wherein the chosen indicators enable the generation of optimized partitions in a plurality of different directions across the files of the storage system.

18. The server computer system of claim 1 , wherein Boolean operations are used to combine chosen indicators to generate optimized partitions.

19. The server computer system of claim 1 , wherein optimized partitions are generated

Assignees

• Agrawal Mukund
• Sridharan Srineet
• Symantec Corp

Inventors

• Agrawal Mukund
• Sridharan Srineet

Classifications

• G06F16/1752 Primary

  based on file chunks · CPC title

• G06F16/1748

  De-duplication implemented within the file system, e.g. based on file segments (de-duplication techniques in storage systems for the management of data blocks G06F3/0641) · CPC title

• G06F17/30159 Primary

  Physics · mapped topic

• G06F17/30156

  Physics · mapped topic