Centralized metaobject ingest using a temporally-expanded bloom filter

• US 9,646,035 B1
• Filed: 04/26/2013
• Issued: 05/09/2017
• Est. Priority Date: 04/26/2013
• Status: Active Grant

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Inventors: Dickson, Christopher
• Primary Examiner(s): Morrison, Jay
• Assistant Examiner(s): Hoang, Ken
• Application Number:
  US13/871,832
• Time in Patent Office: 1,474 Days
• Field of Search: 707754, 707706, 707736, 707741, 707E17005, 707E17014, 707E17032, 707E17044, 707E17059, 707690, 707692, 707722, 707769, 707802, 707E17052, 707E17109, 707E17127, 707609, 707610, 707639, 707691, 707711, 707737, 707747, 707758, 707767, 707770, 707812, 709224, 709204, 709213, 709217, 709225, 709238, 709203, 709206, 709208, 709214, 709220, 709223, 711103, 711E12026, 711106, 711114, 711135, 711136, 711141
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/2477 Temporal data queries

Abstract

A server computer system identifies a first bloom filter using a schedule that rotates bloom filters based on time. The system identifies a first set of metaobjects to evaluate for ingestion using the first bloom filter and determines whether to add one or more of the metaobjects to a data store using the first bloom filter. The system identifies a second bloom filter using the rotation in the schedule and identifies a second set of metaobjects to evaluate for ingestion using the second bloom filter. The second set of metaobjects includes one or more metaobjects that are the same as one or more metaobjects in the first set of metaobjects. The system determines whether to add one or more of the second set of metaobjects to the data store using the second bloom filter.

Claims

1. A method comprising:

identifying a first bloom filter using a schedule comprising a rotation of a plurality of bloom filters based on time;

identifying at least a first metaobject to evaluate for ingestion using the first bloom filter;

deriving a first hash value from the first metaobject;

identifying a first subset of the first hash value based on the schedule, wherein the first subset is smaller in size than the first hash value;

determining, by a server computer system, whether to add the first metaobject to a data store using the first bloom filter and the first subset of the first hash value;

identifying a second bloom filter using the rotation in the schedule;

identifying at least a second metaobject to evaluate for ingestion using the second bloom filter;

deriving a second hash value from the second metaobject;

identifying a second subset of the second hash value based on the schedule, wherein the second subset is smaller in size than the second hash value; and

determining, by the server computer system, whether to add the second metaobject to the data store using the second bloom filter and the second subset of the second hash value.

2. The method of claim 1, wherein the plurality of bloom filters correspond to different time periods.

3. The method of claim 1, wherein the first metaobject and the second metaobject are associated with at least one of a backup data, archive data, data loss prevention data, anti-virus data, or discovery data.

4. The method of claim 1, further comprising:

encoding an initial set of metadata items to create an initial plurality of metaobjects;

performing a hash function on the initial plurality of metaobjects to generate a plurality of hash values;

dividing each of the plurality of hash values into subsets of hash values; and

setting bits in at least one of the first bloom filter or the second bloom filter using the subsets of hash values.

5. The method of claim 1, wherein the first metaobject and the second metaobject comprise at least one of an identifier of a file, an owner of the file, a time of modifying the file, protection bits for the file, or a pathname for the file.

6. The method of claim 1, wherein determining whether to add the first metaobject to the data store comprises:

locating a bit in the first bloom filter that corresponds to a binary value of the first subset of the first hash value; and

adding the first metaobject to the data store if the bit indicates that the first metaobject is not stored in the data store.

7. The method of claim 1, further comprising:

identifying data indicating a number of new metadata items;

determining that the number of new metadata items does not match a number of metaobjects added to the data store;

identifying one or more additional metadata items to be added to the data store; and

adding one or more metaobjects corresponding to the one or more additional metadata items to the data store.

8. A system comprising:

a memory; and

a processing device, coupled with the memory, to;

identify a first bloom filter using a schedule comprising a rotation of a plurality of bloom filters based on time;

identify at least a first metaobject to evaluate for ingestion using the first bloom filter;

derive a first hash value from the first metaobject;

identify a first subset of the first hash value based on the schedule, wherein the first subset is smaller in size than the first hash value;

determine whether to add the first metaobject to a data store using the first bloom filter and the first subset of the first hash value;

identify a second bloom filter using the rotation in the schedule;

identify at least a second metaobject to evaluate for ingestion using the second bloom filter;

derive a second hash value from the second metaobject;

identify a second subset of the second hash value based on the schedule, wherein the second subset is smaller in size than the second hash value; and

determine whether to add the second metaobject to the data store using the second bloom filter and the second subset of the second hash value.

9. The system of claim 8, wherein the plurality of bloom filters correspond to different time periods.

10. The system of claim 8, wherein the first metaobject and the second metaobject are associated with at least one of a backup data, archive data, data loss prevention data, anti-virus data, or discovery data.

11. The system of claim 8, wherein the processing device is further to:

encode an initial set of metadata items to create an initial plurality of metaobjects;

perform a hash function on the initial plurality of metaobjects to generate a plurality of hash values;

divide each of the plurality of hash values into subsets of hash values; and

set bits in at least one of the first bloom filter or the second bloom filter using the subsets of hash values.

12. The system of claim 8, wherein the first metaobject and the second metaobject comprise at least one of an identifier of a file, an owner of the file, a time of modifying the file, protection bits for the file, or a pathname for the file.

13. The system of claim 8, wherein determining whether to add the first metaobject to the data store comprises:

locating a bit in the first bloom filter that corresponds to a binary value of the first subset of the first hash value; and

adding the first metaobject to the data store if the bit indicates that the first metaobject is not stored in the data store.

14. The system of claim 8, wherein the processing device is further to:

identify data indicating a number of new metadata items;

determine that the number of new metadata items does not match a number of metaobjects added to the data store;

identify one or more additional metadata items to be added to the data store; and

add one or more metaobjects corresponding to the one or more additional metadata items to the data store.

15. A non-transitory computer readable storage medium including instructions that, when executed by a processing device, cause the processing device to perform a set of operations comprising:

identifying a first bloom filter using a schedule comprising a rotation of a plurality of bloom filters based on time;

identifying at least a first metaobject to evaluate for ingestion using the first bloom filter;

deriving a first hash value from the first metaobject;

identifying a first subset of the first hash value based on the schedule, wherein the first subset is smaller in size than the first hash value;

determining, by the processing device, whether to add the first metaobject to a data store using the first bloom filter and the first subset of the first hash value;

identifying a second bloom filter using the rotation in the schedule;

identifying at least a second metaobject to evaluate for ingestion using the second bloom filter;

deriving a second hash value from the second metaobject;

identifying a second subset of the second hash value based on the schedule, wherein the second subset is smaller in size than the second hash value; and

determining, by the processing device, whether to add the second metaobject to the data store using the second bloom filter and the second subset of the second hash value.

16. The non-transitory computer readable storage medium of claim 15, wherein the plurality of bloom filters correspond to different time periods.

17. The non-transitory computer readable storage medium of claim 15, wherein the first metaobject and the second metaobject are associated with at least one of a backup data, archive data, data loss prevention data, anti-virus data, or discovery data.

18. The non-transitory computer readable storage medium of claim 15, wherein the operations further comprise:

encoding an initial set of metadata items to create an initial plurality of metaobjects;

performing a hash function on the initial plurality of metaobjects to generate a plurality of hash values;

dividing each of the plurality of hash values into subsets of hash values; and

setting bits in at least one of the first bloom filter or the second bloom filter using the subsets of hash values.

19. The non-transitory computer readable storage medium of claim 15, wherein determining whether to add the first metaobject to the data store comprises:

locating a bit in the first bloom filter that corresponds to a binary value of the first subset of the first hash value; and

adding the first metaobject to the data store if the bit indicates that the first metaobject is not stored in the data store.

20. The non-transitory computer readable storage medium of claim 15, wherein the operations further comprise:

identifying data indicating a number of new metadata items;

determining that the number of new metadata items does not match a number of metaobjects added to the data store;

identifying one or more additional metadata items to be added to the data store; and

adding one or more metaobjects corresponding to the one or more additional metadata items to the data store.