Granted Patent B1

US 10,423,495 · App. 14/480,507 · Granted Sep 24, 2019

Inventors: Fanglu Guo (Los Angeles, CA); Weibao Wu (Vadnais Heights, MN); Xianbo Zhang (Plymouth, MN)

Assignee: Veritas Technologies LLC

G06F11/1453G06F16/285

Abstract

Claims (54)

1. A method for deduplication grouping, comprising:

identifying a new backup image;

enumerating a top N levels of directories and files in the backup image;

obtaining metadata of the top N levels of directories and files in the new backup image;

applying a hash function to the metadata to generate one or more first hash values;

obtaining one or more second hash values of metadata corresponding to a top N levels of directories and files of each of a first deduplication group and a second deduplication group, wherein the first deduplication group and the second deduplication group do not share hash values with one another;

comparing the one or more first hash values to one or more second hash values that correspond to hashes of metadata of the first deduplication group and the second deduplication group;

identifying which of the first deduplication group and the second deduplication group has hash values that match most of the one or more first hash values; and

designating the first deduplication group as a deduplication group for the new backup image, responsive to identifying the first deduplication group as having more hash values that match more of the one or more first hash values than the second deduplication group.

2. The method of claim 1 , further comprising:

comparing a hierarchical file structure of the file system in the new backup image to a hierarchical file structure of a file system in the backup image from each of the first and second deduplication groups.

3. The method of claim 1 , further comprising:

obtaining metadata from a data structure of a database management system in the backup image.

4. The method of claim 3 , further comprising:

comparing the metadata from the data structure of the database management system in the backup image with information from a data structure in the backup image from each of the first and second deduplication groups.

5. The method of claim 1 , wherein designating the first deduplication group is in further response to determining the given deduplication group meets a matching threshold level.

6. The method of claim 5 , wherein in response to determining the given deduplication group does not meet the matching threshold level:

creating a new deduplication group; and

storing the new backup image in the new deduplication group.

7. The method of claim 1 , further comprising:

upon failing to match the new backup image with any of the two or more deduplication groups, creating a new deduplication group; and

storing the new backup image in the new deduplication group.

8. The method of claim 1 , wherein said hash function is a locality-sensitive hash function.

9. A computing device configured for deduplication grouping, comprising:

a processor;

memory in electronic communication with the processor, wherein the memory stores computer executable instructions that when executed by the processor cause the processor to perform the steps of:

identifying a new backup image;

enumerating a top N levels of directories and files in the backup image;

obtaining metadata of the top N levels of directories and files in the new backup image;

applying a hash function to the metadata to generate one or more first hash values;

obtaining one or more second hash values of metadata corresponding to a top N levels of directories and files of each of a first deduplication group and a second deduplication group, wherein the first deduplication group and the second deduplication group do not share hash values with one another;

comparing the one or more first hash values to one or more second hash values that correspond to hashes of metadata of the first deduplication group and the second deduplication group;

identifying which of the first deduplication group and the second deduplication group has hash values that match most of the one or more first hash values; and

designating the first deduplication group as a deduplication group for the new backup image, responsive to identifying the first deduplication group as having more hash values that match more of the one or more first hash values than the second deduplication group.

10. The computing device of claim 9 , wherein the instructions executed by the processor cause the processor to perform the steps of:

comparing a hierarchical file structure of the file system in the new backup image to a hierarchical file structure of a file system in the backup image from each of the first and second deduplication groups.

11. The computing device of claim 9 , wherein the instructions executed by the processor cause the processor to perform the steps of:

obtaining metadata from a data structure of a database management system in the backup image.

12. The computing device of claim 11 , wherein the instructions executed by the processor cause the processor to perform the steps of in response to determining the first deduplication group does not meet a matching threshold level:

create a new deduplication group; and

store the new backup image in the new deduplication group.

13. The computing device of claim 9 , wherein designating the first deduplication group is in further response to determining the given deduplication group meets a matching threshold level.

14. The computing device of claim 13 , wherein in response to determining the first deduplication group does not meet the matching threshold level:

creating a new deduplication group; and

storing the new backup image in the new deduplication group.

15. A non-transitory computer-readable storage medium storing computer executable instructions that when executed by a processor cause the processor to perform the steps of:

identifying a new backup image;

enumerating a top N levels of directories and files in the backup image;

obtaining metadata of the top N levels of directories and files in the new backup image;

applying a hash function to the metadata to generate one or more first hash values;

obtaining one or more second hash values of metadata corresponding to a top N levels of directories and files of each of a first deduplication group and a second deduplication group, wherein the first deduplication group and the second deduplication group do not share hash values with one another;

comparing the one or more first hash values to one or more second hash values that correspond to hashes of metadata of the first deduplication group and the second deduplication group;

identifying which of the first deduplication group and the second deduplication group has hash values that match most of the one or more first hash values; and

designating the first deduplication group as a deduplication group for the new backup image, responsive to identifying the first deduplication group as having more hash values that match more of the one or more first hash values than the second deduplication group.

Assignments (13)

Cited By (2)

US 12,411,926 US 12,579,107