Systems and methods of reverse lookup

• US 7,590,652 B2
• Filed: 08/18/2006
• Issued: 09/15/2009
• Est. Priority Date: 08/18/2006
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Isilon Systems Incorporated (Dell Technologies Inc.)
• Inventors: Passey, Aaron J., White, Nathan N.
• Primary Examiner(s): Trujillo; James
• Assistant Examiner(s): Casanova; Jorge A
• Application Number:
  US11/507,075
• Publication Number:
  US 20080046445A1
• Time in Patent Office: 1,124 Days
• Field of Search: 707/103.R, 707/103.X, 707/103.Z, 707/104.1
• US Class Current: 1/1
• 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

One embodiment includes a process for reverse lookups using a map structure and a structure being referenced by the map structure that comprises receiving a structure that comprises a reference to the structure and a reverse lookup hint; locating one or more entries in a map structure that correspond to the reverse lookup hint; and identifying at least one matching entry in the map structure that corresponds to the structure.

Claims

1. A process for reverse lookups using a map structure and a structure referenced by the map structure comprising:

accessing, by a computer processor, a first data structure, the first data structure comprising a first reverse lookup hint and a reference to a second data structure, the first data structure related to a file or directory and the reference to the second data structure related to a parent directory of the file or directory;

identifying, by a computer processor, at least one matching entry in a first name map structure using the first reverse lookup hint, the first name map structure related to the parent directory, the at least one matching entry in the first name map structure corresponding to the file or directory and including a name of the file or directory;

using the reference to the second data structure to access, by a computer processor, the second data structure, the second data structure comprising a second reverse lookup hint and a reference to a third data structure, the reference to the third data structure related to a grandparent directory of the file or directory;

identifying, by a computer processor, at least one matching entry in a second name map structure using the second reverse lookup hint, the second name map structure related to the grandparent directory, the at least one matching entry in the second name map structure corresponding to the parent directory and including a name of the parent directory;

using the reference to the third data structure to access, by a computer processor, the third data structure, the third data structure comprising a third reverse lookup hint; and

identifying, by a computer processor, at least one matching entry in a third name map structure using the third reverse lookup hint, the at least one matching entry in the third name map structure corresponding to the grandparent directory and including a name of the grandparent directory.

2. The process for reverse lookups of claim 1, wherein the at least one matching entry in the first name map structure comprises a filename associated with the first data structure.

3. The process for reverse lookups of claim 1, wherein the first reverse lookup hint assists in locating a key in the first name map structure.

4. The process for reverse lookups of claim 1, further comprising returning the name associated with the at least one matching entry in the first name map structure.

5. The process for reverse lookups of claim 1, further comprising:

searching a subset of entries in the first name map structure for the at least one matching entry in the first name map structure; and

if the subset of entries does not comprise the at least one matching entry, searching all of the entries in the first name map structure for the at least one matching entry.

6. The process for reverse lookups of claim 1, further comprising returning a portion of a filename path related to the at least one matching entry in the first name map structure, wherein the portion of the filename path is less than a global filename path.

7. The process for reverse lookups of claim 1, further comprising returning a portion of a first filename path and a portion of a second filename path related to the at least one matching entry in the first name map structure, wherein the portion of the first filename path and the portion of the second filename path are less than a global filename path.

8. The process for reverse lookups of claim 1, wherein the first map structure, the second map structure, or the third map structure is at least one of a B-tree, a Patricia tree, a hash table, a red-black tree, and a flat file directory.

9. The process for reverse lookups of claim 1, wherein the first name map structure and the second name map structure correspond to a directory map, and the first data structure, the second data structure, and the third data structure correspond to an inode.

10. The process for reverse lookups of claim 1, wherein the first data structure relates to a file in a distributed file system, the second data structure relates to a user created directory in the distributed file system, and the third data structure relates to a user created directory in the distributed file system.

11. The process for reverse lookups of claim 1, wherein the first reverse lookup hint, the second reverse lookup hint, or the third reverse lookup hint is a hash value of a name.

12. A tangible storage medium having a computer program stored thereon for causing a suitable programmed system to process computer-program code by performing the process of claim 1 when such program is executed on the system.

13. A distributed file system configured to perform reverse lookups, the distributed file system comprising:

a plurality of storage devices each storage device in communication via a network, each storage device comprising a processor and a memory for storing data;

a plurality of files that are logically organized in a tree and each file distributed over the network so as to be stored, in parts, across the memory of two or more of the plurality of nodes;

at least one of the plurality storage devices storing structure data in the memory, the structure data comprising;

a name map structure corresponding to a parent directory of the tree and comprising;

a first set of structures corresponding to children files of the parent directory, each of the first set of structures comprising;

a filename associated with the corresponding structure; and

a file reference to a file metadata file corresponding to the filename;

the file metadata file comprising;

a parent directory reference to a directory metadata file corresponding to a parent directory of the corresponding file; and

a first reverse lookup hint that is used to locate the file reference in the name map structure.

14. The distributed file system of claim 13, the at least one storage device further comprising:

a reverse lookup module stored on the memory configured to;

receive the first reverse lookup hint and a file reference of one of the first set of structures;

locate one or more entries in the name map structure that correspond to the first reverse lookup hint; and

identify at least one matching entry in the name map structure that corresponds to the file reference.

15. The distributed file system of claim 14, wherein the at least one matching entry comprises at least one filename associated with one of the children files of the parent directory, and the reverse lookup module is further configured to return the at least one filename.

16. The distributed file system of claim 13, wherein the first reverse lookup hint comprises a key.

17. A distributed file system for processing reverse lookups, the distributed file system comprising:

a plurality of data storage devices configured to communicate with each other, each data storage device comprising a processor and a memory;

a first module stored in the memory of at least one of the plurality of data storage devices, the processor configured to run the first module, the first module configured to;

access a first data structure, the first data structure comprising a first reverse lookup hint and a reference to a second data structure, the first data structure related to a file or directory and the reference to the second data structure related to a parent directory of the file or directory;

identify at least one matching entry in a first name map structure using the first reverse lookup hint, the first name map structure related to the parent directory, the at least one matching entry in the first name map structure corresponding to the file or directory;

use the reference to the second data structure to access the second data structure, the second data structure comprising a second reverse lookup hint and a reference to a third data structure, the reference to the third data structure related to a grandparent directory of the file or directory;

identify at least one matching entry in a second name map structure using the second reverse lookup hint, the second name map structure related to the grandparent directory, the at least one matching entry in the second name map structure corresponding to the parent directory;

use the reference to the third data structure to access the third data structure, the third data structure comprising a third reverse lookup hint; and

identify at least one matching entry in a third name map structure using the third reverse lookup hint, the at least one matching entry in the third name map structure corresponding to the grandparent directory.

18. The distributed file system of claim 17 wherein each of the first data structure, the second data structure, and the third data structure are stored in memories of at least two of the plurality of storage devices.

19. The distributed file system of claim 17 wherein the first data structure relates to a file stored in the distributed file system, the second data structure relates to a user created directory in the distributed file system, and the third data structure relates to a user created directory in the distributed file system.