Index processing using transformed values

• US 7,627,609 B1
• Filed: 09/30/2005
• Issued: 12/01/2009
• 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): Le; Miranda
• Application Number:
  US11/242,179
• Time in Patent Office: 1,523 Days
• Field of Search: 707/1, 707/2, 707/3, 707/10, 707100-101, 707/104.1, 707/200
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1448 Management of the data involved in backup or backup restore
• CPC Class Codes: G06F 11/1458 Management of the backup or restore process
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

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, transforming the hash value into a plurality of bytes such that none of the bytes has the value of a flag used by the system, concatenating the transformed hashed values into a hint, and storing the hint in an index. In an embodiment, bytes having the flag value are mapped to an unused value during the transformation. In an embodiment, the hint is retrieved from the index and hashed values are transformed back. Mapped values are restored to the flag values. This allows use of the hint with a system that uses a flag in the index as an indicator; for example, to indicate that an endpoint has been reached.

Claims

1. A method of tracking a plurality of objects being stored in a computer system, comprising:

retrieving a hint comprising at least one hash value from an index of objects stored in the computer system;

obtaining a hash value from the hint;

transforming the hash value to contain instances of the flag;

wherein transforming the hash value includes identifying instances of a mapped value in the hash value

wherein transforming the hash value includes replacing an instance of the mapped value with an instance of the flag;

wherein transforming the hash value includes encoding the hash value into another base;

wherein encoding the hash value into another base includes encoding the hash value into another higher base;

wherein encoding the hash value into another base includes reducing space for storing the encoded hash value;

wherein reducing space for storing the encoded hash value includes dropping a portion not used for storing the encoded hash value;

wherein dropping the portion not used for storing the encoded hash value includes dropping a most significant byte; and

determining from the hash value whether an object has been stored in the computer system; and

utilizing the flag in the index as an indicator to indicate that an endpoint has been reached.

2. The method as recited in claim 1, wherein the plurality of objects is associated with a saveset, and the hint is associated with the saveset.

3. The method as recited in claim 2, wherein the index comprises descriptors for a plurality of savesets, and wherein retrieving the hint includes retrieving the hint from one of the descriptors.

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

5. The method as recited in claim 4, wherein retrieving the hint includes retrieving the hint from the savepoint.

6. A system for tracking a plurality of objects being stored in a computer system, comprising a processor configured to:

retrieve a hint comprising at least one hash value from an index of objects stored in the computer system;

obtaining a hash value from the hint;

transforming the hash value to contain instances of the flag;

wherein transforming the hash value includes identifying instances of a mapped value in the hash value;

wherein transforming the hash value includes replacing an instance of the mapped value with an instance of the flag;

wherein transforming the hash value includes encoding the hash value into another base;

wherein encoding the hash value into another base includes encoding the hash value into another higher base;

wherein encoding the hash value into another base includes reducing space for storing the encoded hash value;

wherein reducing space for storing the encoded hash value includes dropping a portion not used for storing the encoded hash value;

wherein dropping the portion not used for storing the encoded hash value includes dropping a most significant byte; and

determining from the hash value whether an object has been stored in the computer system; and

utilizing the flag in the index as an indicator to indicate that an endpoint has been reached.

7. A computer program product for tracking a plurality of objects being stored in a computer system, comprising a computer readable storage medium having machine readable code embodied therein for:

retrieving a hint comprising at least one hash value from an index of objects stored in the computer system;

obtaining a hash value from the hint;

transforming the hash value to contain instances of the flag;

wherein transforming the hash value includes identifying instances of a mapped value in the hash value;

wherein transforming the hash value includes replacing an instance of the mapped value with an instance of the flag;

wherein transforming the hash value includes encoding the hash value into another base;

wherein encoding the hash value into another base includes encoding the hash value into another higher base;

wherein encoding the hash value into another base includes reducing space for storing the encoded hash value;

wherein reducing space for storing the encoded hash value includes dropping a portion not used for storing the encoded hash value;

wherein dropping the portion not used for storing the encoded hash value includes dropping a most significant byte; and

determining from the hash value whether an object has been stored in the system; and

utilizing the flag in the index as an indicator to indicate that an endpoint has been reached.