Detecting Duplicative Hierarchical Sets Of Files

• US 20100114842A1
• Filed: 10/24/2008
• Published: 05/06/2010
• Est. Priority Date: 08/18/2008
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Inventors: Eshghi, Kave, Forman, George H.
• Granted Patent: US 9,063,947 B2
• Time in Patent Office: Days
• US Class Current: 707/692
• CPC Class Codes: G06F 16/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 Class Codes: G06F 16/2255 Hash tables

Abstract

To detect duplicative hierarchically arranged sets of files in a storage system, a method includes generating, for hierarchically arranged plural sets of files, respective collections of values computed based on files in corresponding sets of files. For a further set of files that is an ancestor of at least one of the plural sets of files, a respective collection of values that is based on the collection of values computed for the at least one set is generated. Duplicative sets according to comparisons of the collections of values are identified.

Claims

1. A method of detecting duplicative hierarchically arranged sets of files in a storage system, comprising:

generating, for hierarchically arranged plural sets of files, respective collections of values computed based on files in corresponding sets of files;

generating, for a further set of files that is an ancestor of at least one of the plural sets of files, a respective collection of values that is based on the collection of values computed for the at least one set; and

identifying duplicative sets according to comparisons of the collections of values.

2. The method of claim 1, wherein generating collections of values for corresponding hierarchically arranged plural sets of files comprises generating collections of values for corresponding directories.

3. The method of claim 1, wherein generating the collection of values for a particular one of the sets of files comprises:

computing at least one hash value for each respective file of the particular set; and

selecting at least a subset of the hash values to output as the collection of values for the particular set.

4. The method of claim 3, wherein computing the hash values for respective files of the particular set comprises:

using plural hash functions to compute the hash values for the respective files in the particular set; and

selecting, from among the hash values for the files of the particular set, a subset of the hash values to output as the collection of values for the particular set.

5. The method of claim 4, wherein using the plural hash functions comprises applying plural permutations to a hash value of each of the files in the particular set.

6. The method of claim 4, wherein selecting the subset of the hash values comprises selecting an extreme of the hash values computed by each of the hash functions on the files of the particular set.

7. The method of claim 3, wherein selecting at least the subset of the hash values to output as the collection of values for the particular set comprises:

adding hash values for the respective files of the particular set to a data structure; and

once the data structure has become full, removing hash values from the data structure according to a criterion to make room for adding additional hash values.

8. The method of claim 7, wherein adding hash values to the data structure comprises adding the hash values to a heap.

9. The method of claim 1, further comprising:

determining a count of each of the values in the collections to track values that originate in more than one set of files,

wherein identifying duplicative sets takes into account the counts.

10. The method of claim 9, further comprising:

pruning values from the collections where such values originate in just one set; and

removing a particular set of files from further processing if all values in the collection corresponding to the particular set are pruned.

11. The method of claim 1, further comprising:

adding values and sets to a bi-partite graph, wherein the bi-partite graph has nodes representing respective sets, and wherein nodes corresponding to sets sharing at least one file are linked,

wherein identifying the duplicative sets uses the bi-partite graph.

12. The method of claim 11, further comprising:

adding a particular set to the bi-partite graph; and

outputting a first pair of sets that includes the particular set and a second set unless the second set is an ancestor of the particular set.

13. The method of claim 1, further comprising receiving, by a central system, the collections of values from plural file storage systems.

14. A method of detecting duplicative directories, comprising:

computing sketches for corresponding plural directories, wherein the sketches contain values based on files in the directories;

computing a further sketch for a further directory that is an ancestor of at least one of the plural directories, wherein the further sketch contains one or more values from the sketch of the at least one of the plural directories; and

identifying duplicative directories based on comparing the sketches.

15. An article comprising at least one computer-readable storage medium containing instructions that when executed cause a computer to:

generate, for hierarchically arranged plural sets of files, respective collections of values computed based on files in corresponding sets of files;

generate, for a further set of files that is an ancestor of at least one of the plural sets of files, a respective collection of values that is based on the collection of values computed for the at least one set; and

identify duplicative sets according to comparisons of the collections of values.