Method and apparatus for representing file system metadata within a database for efficient queries

• US 7,844,646 B1
• Filed: 03/12/2004
• Issued: 11/30/2010
• Est. Priority Date: 03/12/2004
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Swartzlander, Benjamin, Schwartz, Barry, Deshmukh, Vijay
• Primary Examiner(s): Le; Miranda
• Application Number:
  US10/800,163
• Time in Patent Office: 2,454 Days
• Field of Search: 707 1- 10, 707100-102, 707/104.1, 707200-205, 707/825, 707827-829, 707/999.2, 711 11-114, 711/154, 711/162, 714 1- 6, 709215-219
• US Class Current: 707/825
• CPC Class Codes: G06F 16/10 File systems; File servers

Abstract

According to an embodiment of the present invention, a filer or other storage server is coupled to a network to store files for users of the network. An agent is coupled to the filer, and performs a scan or file walk for a Multi-Appliance Management Application (MMA) which is coupled to the filer and can monitor and manage the filer. The agent assigns identification (ID) numbers to the directories while scanning them. The ID numbers are assigned in a depth first search (DFS) order to reduce the amount of resources required for specific queries that may later be required. Several types of queries, including determining the parent of a node, determining all of the children of a node, determining the immediate children of a node, and determining all of the ancestors of a node may be easily accomplished using the ID numbers.

Claims

1. A method for creating a file information database comprising:

scanning a storage server having a directory structure;

collecting data regarding the directory structure;

for each directory of the directory structure, determining whether each member of the directory is a file or subdirectory;

using a first thread to;

traverse the directory structure in a depth first search (DFS) order; and

assign a first unique identification (ID) number to a first determined directory and a second unique ID number to a second determined directory in the directory structure, wherein the ID numbers are assigned while the directory structure is being traversed in the DFS order, and wherein the ID numbers correspond to the DFS order in which the determined directories are traversed;

using a second thread to examine the determined files;

writing a data structure including the first ID number, the second ID number and a relation between the first directory and the second directory, wherein the relation indicates that the first directory is an immediate child of the second directory;

receiving a request to determine an immediate child or parent of a specified directory, wherein the specified directory is the first directory or the second directory;

searching the data structure for any relation indicative that the specified directory is a child or a parent in said relation, wherein said searching produces as a result said relation between the first directory and the second directory; and

determining the immediate child or parent of the specified directory based on said any relation.

2. The method of claim 1, wherein scanning and collecting comprise scanning and collecting by using an agent separate from the storage server.

3. The method of claim 2, wherein the agent has a first file system, and the storage server has a second file system, and wherein the first file system is different from the second file system.

4. The method of claim 1, wherein assigning further comprises assigning the ID numbers while collecting the data.

5. The method of claim 1, wherein writing the data structure further comprises writing the data structure to a database server.

6. The method of claim 1, further comprising:

receiving a request to determine a set of ID numbers of every child of a third directory in the directory structure, wherein the third directory is assigned a third ID number;

determining a fourth ID number of a sibling of the third directory; and

determining the set of ID numbers between the third ID number and the fourth ID number.

7. The method of claim 1, wherein a top level directory of the directory structure is assigned an ID of “

0”

(zero).

8. A machine readable medium having stored thereon executable program code which, when executed, causes a machine to perform a method for creating a file information database, the method comprising:

scanning a storage server having a directory structure;

collecting data regarding the directory structure;

for each directory of the directory structure, determining whether each member of the directory is a file or subdirectory;

using a first thread to;

traverse the directory structure in a depth first search (DFS) order; and

assign a first unique identification (ID) number to a first determined directory and a second unique ID number to a second determined directory in the directory structure, wherein the ID numbers are assigned while the directory structure is being traversed in the DFS order, and wherein the ID numbers depend on the DFS order in which the determined directories are traversed;

using a second thread to examine the determined files;

writing a data structure including;

the first ID number,

the second ID number,

in association with the first ID number, an indication of a relation between the first directory and the second directory, wherein the relation indicates that the first directory is an immediate child of the second directory;

receiving a request to determine an immediate child or parent of a specified directory, wherein the specified directory is the first directory or the second directory;

searching the data structure for any relation indicative that the specified directory is a child or a parent in said relation, wherein said searching produces as a result said relation between the first directory and the second directory; and

determining the immediate child or parent of the specified directory based on said any relation.

9. The machine readable medium of claim 8, wherein scanning and collecting comprise scanning and collecting using an agent separate from the storage server.

10. The machine readable medium of claim 9, wherein the agent has a first file system, and the storage server has a second file system, and wherein the first file system is different from the second file system.

11. The machine readable medium of claim 8, wherein assigning further comprises assigning the ID numbers while collecting the data.

12. The machine readable medium of claim 8, wherein writing the data structure further comprises writing the data structure to a database server.

13. The machine readable medium of claim 8, further comprising:

receiving a request to determine a set of ID numbers of every child of a third directory in the directory structure, wherein the third directory is assigned a third ID number;

determining a fourth ID number of a sibling of the third directory; and

determining the set of ID numbers between the third ID number and the fourth ID number.

14. A method for creating a file information database comprising:

scanning a storage server having a directory structure;

for each directory of the directory structure, determining whether each member of the directory is a file or subdirectory;

using a first thread to assign a first unique identification (ID) number to a first determined directory and a second unique ID number to a second determined directory in the directory structure according to a depth first search (DFS) order, wherein the ID numbers are assigned while the directory structure is being traversed in the DFS order, and wherein the ID numbers are chronologically assigned in numerical order based on the DFS order in which the directory structure is traversed;

using a second thread to examine the determined files;

writing a data structure including the first ID number, the second ID number and a relation between the first directory and the second directory, wherein the relation indicates that the first directory is an immediate child of the second directory, and wherein the data structure is traversable based on the ID numbers to determine relationships between directories of the storage server;

receiving a request to determine an immediate child or parent of a specified directory, wherein the specified directory is the first directory or the second directory;

searching the data structure for any relation indicative that the specified directory is a child or a parent in said relation, wherein said searching produces as a result said relation between the first directory and the second directory; and

determining the immediate child or parent of the specified directory based on said any relation.