Index processing for legacy systems

• US 7,698,325 B1
• Filed: 09/30/2005
• Issued: 04/13/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): Le; Miranda
• Application Number:
  US11/242,218
• Time in Patent Office: 1,656 Days
• Field of Search: 707 1- 3, 707/10, 707100-101, 707/104.1, 707/200, 707/698
• US Class Current: 707/698
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/289 Object oriented databases
• CPC Class Codes: Y10S 707/99955 Archiving or backup

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:

applying a hash function to a name of an object to generate a hash value;

transforming the hash value into a plurality of portions so that each portion has a value other than a flag, wherein the flag includes a null byte and wherein the plurality of portions include a plurality of bytes;

wherein transforming the hash value includes encoding the hash value into a base lower than a maximum base of one of the plurality of portions,

wherein transforming the hash value includes allocating at least one more portion to the plurality of portions to represent the hash value,

wherein transforming the hash value includes identifying a portion having a value corresponding to the flag, and replacing the portion value with an unused value, wherein the unused value is a value that can be represented by the portion and cannot be generated by the encoding into the lower base;

concatenating each transformed hash value into a hint;

storing the hint in an index stored in a storage device, wherein the index comprises a savepoint configured to store information about the longest pathname containing the plurality of objects; 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 transforming the hash value includes encoding the hash value into base-255.

3. The method as recited in claim 2, wherein transforming the hash value includes allocating at least one more byte to the plurality of bytes to represent the encoded hash value.

4. The method as recited in claim 3, wherein transforming the hash value includes allocating at least one more bit to the plurality of bytes to represent the encoded hash value.

5. The method as recited in claim 1, wherein the unused value includes the value 255.

6. 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.

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

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

9. The method as recited in claim 1, wherein storing the hint includes storing the hint in the savepoint.

10. A system for tracking a plurality of objects being stored in a system, comprising

a processor configured to apply a hash function to a name of an object to generate a hash value,

transform the hash value into a plurality of portions so that each portion has a value other than the flag, wherein the flag includes a null byte and wherein the plurality of portions include a plurality of bytes;

wherein transforming the hash value includes encoding the hash value into a base lower than a maximum base of one of the plurality of portions,

wherein transforming the hash value includes allocating at least one more portion to the plurality of portions to represent the hash value,

wherein transforming the hash value includes identifying a portion having a value corresponding to the flag, and replacing the portion value with an unused value, wherein the unused value is a value that can be represented by the portion and cannot be generated by the encoding into the lower base;

concatenate each transformed hash value into a hint, and store the hint in an index, wherein the index comprises a savepoint configured to store information about the longest pathname containing the plurality of objects; and

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

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

applying a hash function to a name of an object to generate a hash value;

transforming the hash value into a plurality of portions so that each portion has a value other than the flag, wherein the flag includes a null byte and wherein the plurality of portions include a plurality of bytes;

wherein transforming the hash value includes encoding the hash value into a base lower than a maximum base of one of the plurality of portions,

wherein transforming the hash value includes allocating at least one more portion to the plurality of portions to represent the hash value,

wherein transforming the hash value includes identifying a portion having a value corresponding to the flag, and replacing the portion value with an unused value, wherein the unused value is a value that can be represented by the portion and cannot be generated by the encoding into the lower base;

concatenating each transformed hash value into a hint, and storing the hint in an index, wherein the index comprises a savepoint configured to store information about the longest pathname containing the plurality of objects; and

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