Systems and methods of reverse lookup

• US 8,027,984 B2
• Filed: 09/04/2009
• Issued: 09/27/2011
• Est. Priority Date: 08/18/2006
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Passey, Aaron J., White, Nathan N.
• Primary Examiner(s): Trujillo; James
• Assistant Examiner(s): Casanova; Jorge A
• Application Number:
  US12/554,752
• Publication Number:
  US 20090327218A1
• Time in Patent Office: 753 Days
• Field of Search: 707/736, 707/793, 707/747, 707/829, 707/956
• US Class Current: 707/747
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• CPC Class Codes: Y10S 707/956 Hierarchical
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

In one embodiment, a system and method is provided for reverse lookups using a reverse lookup hint stored in metadata associated with a file or directory. The reverse lookup hint is used to retrieve an entry, comprising a name of the file or directory, which is stored in a map structure related to a parent directory of the file or directory. In an embodiment, the reverse lookup hint comprises a hash value generated from the name of the file or directory.

Claims

1. A method of reverse lookup using a reverse lookup hint, the method comprising:

processing, by a computer processor, a request to determine a name of a file using a unique identifier corresponding to the file;

accessing, by a computer processor, metadata related to the file, the metadata comprising a unique identifier and a first reverse lookup hint corresponding to the file, wherein the first reverse lookup hint comprises at least a portion of a hash value generated by applying a hash function to a name of the file;

accessing, by a computer processor, a map structure related to a parent of the file, the map structure comprising a plurality of entries corresponding to links between the parent of the file and children of the parent of the file, wherein each entry in the plurality of entries corresponds to a child of the parent and includes a name of the corresponding child of the parent, wherein each of one or more entries in the plurality of entries is associated with a child reverse lookup hint, and wherein each child reverse lookup hint comprises at least a portion of a hash value generated by applying a hash function to a name of the child of the parent corresponding to the associated entry;

identifying, by a computer processor, one or more entries in the map structure based at least on a comparison of one or more child reverse lookup hints from the map structure and the first reverse lookup hint corresponding to the file; and

identifying, by a computer processor, an entry of the identified one or more entries based at least on the unique identifier, wherein the entry of the identified one or more links corresponds to the file and includes the name of the file.

2. The method of claim 1, further comprising:

accessing, by a computer processor, one or more ancestor metadata related to one or more ancestor directories of the file, each of the one or more ancestor metadata comprising a unique identifier and a reverse lookup hint;

accessing, by a computer processor, one or more map structures related to one or more parents of the one or more ancestor directories, each of the one or more map structures comprising entries;

identifying, by a computer processor, one or more entries in the one or more map structures using at least the unique identifier and the reverse lookup hint of at least one of the one or more ancestor metadata, each of the one or more entries comprising a name of one of the one or more ancestor metadata; and

constructing, by a computer processor, one or more global paths of the file.

3. The method of claim 1, wherein the identifying comprises:

searching, by a computer processor, the map structure for a range of zero or more entries which correspond to the reverse lookup hint;

if one or more entries are found that correspond to the first reverse lookup hint, identifying which of the one or more entries, if any, correspond to the unique identifier; and

if zero entries within the range are found that correspond to the first reverse lookup hint and the unique identifier, identifying which of the plurality of entries of the map structure, if any, correspond to the unique identifier.

4. The method of claim 1, wherein the first reverse lookup hint further comprises at least a portion of a sequence number associated with the at least a portion of the hash value.

5. The method of claim 1, wherein the metadata further comprises a count of links between each parent of the file and the file.

6. The method of claim 1, wherein the identifying further comprises using an identifier stored in the plurality of entries.

7. A system for processing reverse lookups, the system comprising:

at least one computer processor; and

at least one executable software module executed by the at least one computer processor and configured to;

process a request to determine a name of a file using a unique identifier corresponding to the file;

access metadata related to the file, the metadata comprising a unique identifier and a first reverse lookup hint corresponding to the file, wherein the first reverse lookup hint comprises at least a portion of a hash value generated by applying a hash function to a name of the file;

access a map structure related to a parent of the file, the map structure comprising a plurality of entries corresponding to links between the parent of the file and children of the parent of the file, wherein each entry in the plurality of entries corresponds to a child of the parent and includes a name of the corresponding child of the parent, wherein each of one or more entries in the plurality of entries is associated with a child reverse lookup hint, and wherein each child reverse lookup hint comprises at least a portion of a hash value generated by applying a hash function to a name of the child of the parent corresponding to the associated entry;

identify one or more entries in the map structure based at least on a comparison of one or more child reverse lookup hints from the map structure and the first reverse lookup hint corresponding to the file; and

identify an entry of the identified one or more entries based at least on the unique identifier, wherein the entry of the identified one or more links corresponds to the file and includes the name of the file.

8. The system of claim 7, wherein the at least one executable software module is further configured to:

access one or more ancestor metadata related to one or more ancestor directories of the file, each of the one or more ancestor metadata comprising a unique identifier and a reverse lookup hint;

access one or more map structures related to one or more parents of the one or more ancestor directories, each of the one or more map structures comprising entries;

identify one or more entries in the one or more map structures using at least the unique identifier and the reverse lookup hint of at least one of the one or more ancestor metadata, each of the one or more entries comprising a name of one of the one or more ancestor metadata; and

construct one or more global paths of the file.

9. The system of claim 7, wherein the at least one executable software module is further configured to:

search the map structure for a range of zero or more entries which correspond to the reverse lookup hint;

if one or more entries are found that correspond to the first reverse lookup hint, identify which of the one or more entries, if any, correspond to the unique identifier; and

if zero entries within the range are found that correspond to the first reverse lookup hint and the unique identifier, identify which of the plurality of entries of the map structure, if any, correspond to the unique identifier.

10. The system of claim 7, wherein the at least one executable software module is further configured to:

generate the first reverse lookup hint for the file;

add an entry in the map structure, the entry comprising the first reverse lookup hint; and

modify the metadata to include the first reverse lookup hint.

11. The system of claim 10, wherein the entry further comprises the unique identifier and at least a name of the file.

12. The system of claim 7, wherein the first reverse lookup hint further comprises at least a portion of a sequence number associated with the at least a portion of the hash value and the at least one executable software module is further configured to generate the sequence number to be different than a previously generated sequence number associated with the at least a portion of the hash value.

13. The system of claim 7, wherein the metadata further comprises a count of links between each parent of the file and the file.

14. The system of claim 7, wherein the at least one executable software module is further configured to identify the one or more entries in the map structure using an identifier stored in the one or more entries.

15. A computer-readable, non-transitory storage medium having at least one computer-executable component for processing reverse lookups, the at least one computer-executable component comprising:

a reverse lookup processing module operative to;

process a request to determine a name of a file using a unique identifier corresponding to the file;

access metadata related to the file, the metadata comprising a unique identifier and a first reverse lookup hint corresponding to the file, wherein the first reverse lookup hint comprises at least a portion of a hash value generated by applying a hash function to a name of the file;

access a map structure related to a parent of the file, the map structure comprising a plurality of entries corresponding to links between the parent of the file and children of the parent of the file, wherein each entry in the plurality of entries corresponds to a child of the parent and includes a name of the corresponding child of the parent, wherein each of one or more entries in the plurality of entries is associated with a child reverse lookup hint, and wherein each child reverse lookup hint comprises at least a portion of a hash value generated by applying a hash function to a name of the child of the parent corresponding to the associated entry;

identify one or more entries in the map structure based at least on a comparison of one or more child reverse lookup hints from the map structure and the first reverse lookup hint corresponding to the file; and

identify an entry of the identified one or more entries based at least on the unique identifier, wherein the entry of the identified one or more links corresponds to the file and includes the name of the file.

16. The computer-readable, non-transitory storage medium of claim 15, wherein the at least reverse lookup processing module is further operative to:

access one or more ancestor metadata related to one or more ancestor directories of the file, each of the one or more ancestor metadata comprising a unique identifier and a reverse lookup hint;

access one or more map structures related to one or more parents of the one or more ancestor directories, each of the one or more map structures comprising entries;

identify one or more entries in the one or more map structures using at least the unique identifier and the reverse lookup hint of at least one of the one or more ancestor metadata, each of the one or more entries comprising a name of one of the one or more ancestor metadata; and

construct one or more global paths of the file.

17. The computer-readable, non-transitory storage medium of claim 15, wherein the reverse lookup processing module is further operative to:

search the map structure for a range of zero or more entries which correspond to the reverse lookup hint;

if one or more entries are found that correspond to the first reverse lookup hint, identify which of the one or more entries, if any, correspond to the unique identifier; and

if zero entries within the range are found that correspond to the first reverse lookup hint and the unique identifier, identify which of the plurality of entries of the map structure, if any, correspond to the unique identifier.

18. The computer-readable, non-transitory storage medium of claim 15, wherein the first reverse lookup hint further comprises at least a portion of a sequence number associated with the at least a portion of the hash value and the at least one executable software module is further configured to generate the sequence number to be different than a previously generated sequence number associated with the at least a portion of the hash value.

19. The computer-readable, non-transitory storage medium of claim 15, wherein the metadata further comprises a count of links between each parent of the file and the file.

20. The computer-readable, non-transitory storage medium of claim 15, wherein the reverse lookup processing module is further operative to identify the one or more entries in the map structure using an identifier stored in the one or more entries.