Adaptive index processing

• US 7,752,211 B1
• Filed: 09/30/2005
• Issued: 07/06/2010
• Est. Priority Date: 09/30/2005
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Papadakis, Thomas, Ozekinci, Yasemin Ugur
• Primary Examiner(s): Rones; Charles
• Assistant Examiner(s): MUELLER, KURT A
• Application Number:
  US11/242,514
• Time in Patent Office: 1,740 Days
• Field of Search: None
• US Class Current: 707/755
• CPC Class Codes: G06F 11/1451 by selection of backup contents

Abstract

A method, article of manufacture, and apparatus for tracking a plurality of objects being stored are disclosed. In an embodiment, this comprises determining an application associated with the objects being stored, selecting a hint or longest pathname containing the plurality of objects, and storing the selection in the index. The hint may be generated by concatenating at least a portion of a name of each object being stored into the hint, concatenating hash values of the names of the objects, or producing a bitmap of hash values of the names of the objects, depending on available space. In an embodiment, each hint generation may be tried in succession based on determining whether the previous hint fits into the space available for storing the hint.

Claims

1. A computer implemented method of tracking a plurality of objects being stored in a storage device, wherein information about the plurality of objects is stored in a plurality of first layers and a plurality of second layers, each first layer consisting of an index header and each second layer consisting of a keyfile, comprising:

determining an application associated with the plurality of objects;

selecting a hint for locating the plurality of objects, wherein selecting the hint is based on determining the application associated with the plurality of objects, and wherein the hint includes at least one of a group comprising a concatenation of object names, a concatenation of hash values, and a bitmap array;

searching the plurality of first layers with the selected hint to determine the second layer to search;

searching the determined second layer for a target; and

storing the results of the first and second search in a storage device.

2. The computer implemented method as recited in claim 1, wherein selecting the hint includes selecting the hint from a group comprising at least one hint.

3. The computer implemented method as recited in claim 2, further comprising generating the at least one hint by concatenating at least a portion of a name of each object being stored into the hint, to produce a concatenation of at least portions of the names of objects.

4. The computer implemented method as recited in claim 3, wherein concatenating at least a portion of a name of each object into the hint includes concatenating the name of each object into the hint.

5. The computer implemented method as recited in claim 3, wherein concatenating at least a portion of a name of each object into the hint includes selecting a portion of the name of each object.

6. The computer implemented method as recited in claim 3, further comprising determining whether the concatenation of at least portions of names of objects will fit into a space available for storing the concatenation.

7. The computer implemented method as recited in claim 6, further comprising

generating at least one hint by applying a hash function to a name of each object to generate a hash value, and

concatenating each hash value into the hint to produce a concatenation of hash values upon determining that the concatenation of at least portions of names of objects will not fit into the space available.

8. The computer implemented method as recited in claim 7, further comprising determining whether the concatenation of hash values will fit into a space available for storing the concatenation.

9. The computer implemented method as recited in claim 8, further comprising

generating at least one hint by providing a bitmap array,

applying a hash function to a name of each object to generate a hash value, and

setting at least one bit in the bitmap array that corresponds to at least one hash value upon determining that the concatenation of hash values will not fit into the space available.

10. The computer implemented method as recited in claim 9, wherein the plurality of objects is associated with a saveset, and the hint is associated with the saveset.

11. The computer implemented method as recited in claim 10, wherein the index comprises descriptors for a plurality of savesets, and storing the hint includes storing the hint in one of the descriptors.

12. The computer implemented method as recited in claim 2, further comprising

generating the at least one hint by applying a hash function to a name of each object to generate a hash value, and

concatenating each hash value into the hint.

13. The computer implemented method as recited in claim 12, wherein generating the hint includes determining an amount of space to be allocated to each hash value.

14. The computer implemented method as recited in claim 13, wherein determining the amount of space to be allocated to each hash value includes dividing a number of the objects in the plurality of the objects into a space available for storing the concatenation.

15. The computer implemented method as recited in claim 2, further comprising

generating the at least one hint by providing a bitmap array,

applying a hash function to a name of each object to generate a hash value, and

setting at least one bit in the bitmap array that corresponds to at least one hash value.

16. The computer implemented method as recited in claim 15, further comprising determining a size of the bitmap array.

17. The computer implemented method as recited in claim 16, wherein determining the size of the bitmap array includes choosing a largest prime number smaller than a space available for storing the bitmap array.

18. The computer implemented method as recited in claim 17, further comprising generating the at least one hint by:

concatenating at least a portion of a name of each object being stored into the hint;

applying a hash function to a name of each object to generate a hash value, and concatenating each hash value into the hint;

or

providing a bitmap array, applying a hash function to a name of each object to generate a hash value, and setting at least one bit in the bitmap array that corresponds to at least one hash value.

19. A computer storage medium containing computer readable instructions for tracking a plurality of objects being stored, wherein information about the plurality of objects is stored in a plurality of first layers and a plurality of second layers, each first layer consisting of an index header and each second layer consisting of a keyfile, the computer readable instructions comprising:

computer program code for determining an application associated with the plurality of objects;

computer program code for selecting a hint for locating the plurality of objects, wherein selecting the hint is based on determining the application associated with the plurality of objects, and wherein the hint is generated by;

concatenating at least a portion of a name of each object being stored into the hint;

applying a hash function to a name of each object to generate a hash value, and

concatenating each hash value into the hint;

or

providing a bitmap array, applying a hash function to a name of each object to generate a hash value, and

setting at least one bit in the bitmap array that corresponds to at least one hash value;

computer program code for searching the plurality of first layers with the selected hint to determine the second layer to search;

computer program code for searching the determined second layer for a target; and

storing the results of the first and second search in a storage device.