Techniques for managing references to containers

• US 9,679,007 B1
• Filed: 03/15/2013
• Issued: 06/13/2017
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Inventors: Feldman, Daniel Joshua, Navratil, Matthew Paul
• Primary Examiner(s): Perveen, Rehana
• Assistant Examiner(s): Skhoun, Hicham
• Application Number:
  US13/838,218
• Time in Patent Office: 1,551 Days
• Field of Search: 707690
• 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/2365 Ensuring data consistency and integrity

Abstract

Techniques for managing references to containers are disclosed. In one particular embodiment, the techniques may be realized as a method for managing references to containers comprising comparing at least one identifier to a first bloom filter, generating a first list of identifiers based on the comparison of the at least one identifier and the first bloom filter, comparing the first list of identifiers to a second bloom filter, generating a second list of identifiers based on the comparison of the first list and the second bloom filter, comparing the second list of identifiers to a main container list, and determining whether an image refers to a container based on the comparison of the second list and the main container list.

Claims

1. A method for managing references to containers comprising:

identifying a container stored in memory for analysis;

determining, using at least one computer processor, a cluster that includes the identified container;

retrieving a first bloom filter from the determined cluster, the first bloom filter storing image identifiers that reference containers within the determined cluster;

retrieving a second bloom filter from the determined cluster, the second bloom filter storing pairs of the image identifiers concatenated with container identifiers for the containers within the determined cluster, wherein the second bloom filter is different from the first bloom filter;

comparing at least one image identifier to the first bloom filter;

generating a first list of image identifiers based on the comparison of the at least one image identifier and the first bloom filter;

comparing the generated first list of image identifiers to the second bloom filter;

generating a second list of image identifiers based on the comparison of the first list and the second bloom filter;

determining a false positive rate of the second bloom filter based on a bit count of the second bloom filter;

comparing the false positive rate of the second bloom filter to a predetermined threshold;

comparing the generated second list of image identifiers to a main container list when it is determined that the false positive rate does not exceed the predetermined threshold; and

determining whether an image refers to the identified container based on the comparison of the second list and the main container list.

2. The method of claim 1, wherein the image identifier is an image ID of an image of data.

3. The method of claim 2, wherein the image of data is backup data.

4. The method of claim 1, wherein the first bloom filter and the second bloom filter are stored in the determined cluster.

5. The method of claim 4, wherein the cluster includes a plurality of containers.

6. The method of claim 5, wherein the cluster includes a reference counter for each of the plurality of containers.

7. The method of claim 5, wherein the first bloom filter includes a list of image identifiers that reference one of the plurality of containers.

8. The method of claim 5, wherein the second bloom filter includes a list of image identifiers paired with container identifiers.

9. The method of claim 8, wherein each of the pairs indicate that an image references a particular one of the plurality of containers within the cluster.

10. The method of claim 1, wherein the at least one image identifier is read from a list of image identifiers stored in the memory.

11. The method of claim 10, wherein the main container list indicates containers that an image references.

12. The method of claim 1, further comprising:

generating the first bloom filter; and

generating the second bloom filter.

13. The method of claim 1, further comprising:

separating an image into a plurality of first containers;

comparing the plurality of first containers to previously stored containers; and

storing at least one of the plurality of first containers based on the comparison of the plurality of first containers and the previously stored containers.

14. The method of claim 13, further comprising:

generating the main container list.

15. The method of claim 13, wherein the plurality of first containers are stored within a cluster.

16. The method of claim 15, further comprising:

updating the first bloom filter and the second bloom filter based on the comparison of the plurality of first containers and the previously stored containers.

17. At least one non-transitory processor readable storage medium storing a computer program of instructions configured to be readable by at least one processor for instructing the at least one processor to execute a computer process for performing the method as recited in claim 1.

19. The method of claim 3, wherein a size of the first and second bloom filters is dependent on at least one of a deduplication rate, temporal locality, and spatial locality of the backup data.

18. A system for managing references to containers comprising:

one or more computer processors and memory communicatively coupled to a network;

wherein the memory contains instructions that when executed by the one or more computer processors cause the one or more computer processors to;

identify a container for analysis;

determine a cluster that includes the identified container;

retrieve a first bloom filter from the determined cluster, the first bloom filter storing image identifiers that reference containers within the determined cluster;

retrieve a second bloom filter from the determined cluster, the second bloom filter storing pairs of the image identifiers concatenated with container identifiers for the containers within the determined cluster, wherein the second bloom filter is different from the first bloom filter;

compare an image identifier to the first bloom filter;

generate a first list of image identifiers based on the comparison of the at least one identifier and the first bloom filter;

compare the generated first list of image identifiers to the second bloom filter;

generate a second list of image identifiers based on the comparison of the first list and the second bloom filter;

determine a false positive rate of the second bloom filter based on a bit count of the second bloom filter;

compare the false positive rate of the second bloom filter to a predetermined threshold;

compare the generated second list of image identifiers to a main container list when it is determined that the false positive rate does not exceed the predetermined threshold; and

determine whether an image refers to the identified container based on comparison of the second list and the main container list.