Efficient index processing

• US 8,161,005 B1
• Filed: 06/30/2005
• Issued: 04/17/2012
• Est. Priority Date: 06/30/2005
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Ozekinci, Yasemin Ugur, Papadakis, Thomas
• Primary Examiner(s): Cottingham, John R.
• Assistant Examiner(s): REYES, MARIELA D
• Application Number:
  US11/173,910
• Time in Patent Office: 2,483 Days
• Field of Search: 707/640, 707/648
• US Class Current: 707/640
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1458 Management of the backup or restore process
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31

Abstract

A method, article of manufacture, and apparatus for tracking a plurality of objects being stored are disclosed. In an embodiment, this comprises computing the hash value of the name of each object being stored, setting the corresponding bits in a bitmap, and storing the bitmap as a hint in an index. The size of the bitmap is determined by the space available for storing the hint, and the range of hash values is determined by the size of the bitmap. The range may be determined by choosing a prime number smaller than the space available for storing the bitmap. Either the hint or the longest pathname containing the objects can be stored, and this may be selected based on the application.

Claims

1. A method of tracking a plurality of file system objects being stored, wherein the plurality of objects is associated with a saveset, comprising:

providing a bitmap;

applying a hash function to a name of each file system object to generate a hash value k;

setting the k^th bit in the bitmap to ON;

storing the bitmap as a hint in an index, wherein the hint is associated with the saveset; and

wherein applying the hash function includes applying an equation

s[0]*x^k+s[1]*x<sup>k−

1</sup>+s[2]*x<sup>k−

2</sup>+ . . . +s[k−

1]*x¹+s[k]*x⁰

wherein x equals 231.

2. The method as recited in claim 1, further comprising storing in the index a longest pathname containing the plurality of objects.

3. The method as recited in claim 1, wherein the index comprises descriptors for a plurality of savesets.

4. The method as recited in claim 3, wherein storing the hint includes storing the hint in one of the descriptors.

5. The method as recited in claim 1, wherein the index comprises a savepoint configured to store information about a longest pathname containing the plurality of objects.

6. The method as recited in claim 5, wherein storing the hint includes storing the hint in the savepoint.

7. The method as recited in claim 1, further comprising determining a size of the bitmap.

8. The method as recited in claim 7, wherein determining the size of the bitmap includes choosing a largest prime number smaller than a space available for storing the bitmap.

9. The method as recited in claim 8, further comprising storing, in the hint, information relating to the size of the bitmap.

10. The method as recited in claim 9, further comprising storing, in the hint, information indicating a type of algorithm being used for the hint.

11. The method as recited in claim 1, wherein applying the hash function further includes applying an equation

h(k)=k mod m.

12. The method as recited in claim 11, wherein m is a largest prime number smaller than a largest number that can be represented by the space available for storing the bitmap.

13. A method of tracking a plurality of file system objects being stored, wherein the plurality of objects is associated with a saveset, comprising:

providing a bitmap;

applying a hash function to a name of each file system object to generate a hash value k;

setting the k^th bit in the bitmap to ON;

storing in an index, the bitmap as a hint or a longest pathname containing the plurality of objects, wherein the hint is associated with the saveset; and

wherein applying the hash function further includes applying an equation

h(k)=k mod m.

14. The method as recited in claim 13, further comprising determining whether to store the hint or the longest pathname containing the plurality of objects.

15. The method as recited in claim 14, wherein determining whether to store includes determining an application associated with the plurality of objects.

16. The method as recited in claim 13, wherein m is a largest prime number smaller than a space available for storing the bitmap.

17. A computer program product for tracking a plurality of file system objects being stored, wherein the plurality of objects is associated with a saveset, comprising a computer usable medium having machine readable code embodied therein for:

providing a bitmap;

applying a hash function to a name of each file system object to generate a hash value k;

setting the k^th bit in the bitmap to ON;

storing the bitmap as a hint in an index, wherein the hint is associated with the saveset; and

wherein applying the hash function further includes applying an equation

h(k)=k mod m.