Mechanism for performing fast directory lookup in a server system

• US 8,266,136 B1
• Filed: 04/13/2009
• Issued: 09/11/2012
• Est. Priority Date: 04/13/2009
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Pogde, Prashant, Agarwal, Manish M.
• Primary Examiner(s): Tecklu, Isaac
• Assistant Examiner(s): Ortiz, Deric
• Application Number:
  US12/422,648
• Time in Patent Office: 1,247 Days
• Field of Search: 707/825
• US Class Current: 707/711
• CPC Class Codes: G06F 16/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06

Abstract

Embodiments of the present invention provide a novel technique for maintaining directory-based quota, for performing directory notification to a client system, and performing other such operations by efficiently finding ancestral directory associations on a server system without performing multiple accesses to data structures associated with the directory associations. Since data structures do not need to be accessed multiple times, performance of the server system can be improved.

Claims

1. A method for sending a notification by a server system of changes in a directory registered for notification, the server system including a processor, the method comprising:

generating an index for a node of a file system, the file system comprising a plurality of nodes, at least one of the nodes having an ancestor node, each node comprising a data container, each node associated with a unique numeric identifier;

in response to a request received by the server system to modify a node, determining whether a directory is an ancestor node of the modified node by dividing the numeric identifier of the directory node into the index of the modified node, whereby no remainder resulting from the division determines the directory node is an ancestor of the modified node;

sending a notification of a change in the directory registered for notification, wherein the directory registered for notification is associated with the directory node.

2. The method of claim 1, further comprising:

generating for each directory node, a first index representing a unique numeric identifier of the directory node, and a second index representing a product of mathematical manipulation of a first index and a second index of the immediate parent of the directory node so that the second index uniquely identifies the parents of the directory node;

generating, for each leaf node, a first index representing a product of mathematical manipulation of a first index and a second index of each immediate parent node of the leaf node, wherein a second index of the leaf node is a multiplication of a unique numeric identifier of each immediate parent of the leaf node.

3. The method of claim 2, wherein performing mathematical manipulation of the first index and the second index of the immediate parents of the directory node further comprises multiplying the first index and the second index of the immediate parents of the directory node.

4. The method of claim 2, wherein performing mathematical manipulation of the first index and the second index of the immediate parents of the leaf node further comprises multiplying the first index and the second index of the immediate parents of the leaf node.

5. The method of claim 1, further comprising:

generating prime factors of the index of the modified node, wherein the generated prime factors represent the numeric identifiers of one or more parent directories of the modified node; and

sending a quota update for a directory registered for notification, wherein the directory registered is within a set of the one or more parent directories of the modified node.

6. The method of claim 2, wherein mathematically manipulating the index to identify an ancestor node of the modified node further comprises:

generating prime factors of the second index of the modified node, the generated prime factors represent inode numbers identifying parent directories of the modified node; and

generating prime factors of the first index of the modified node, the generated prime factors represent inode numbers identifying all directory nodes on the path from a root to the modified node.

7. The method of claim 1, wherein the numeric identifier of each node represents a prime number, and wherein the index of the node represents a product of a plurality of prime numbers.

8. The method of claim 2, wherein mathematical manipulation to identify an ancestor node of the modified node further comprises:

generating prime factors of the first index of the modified node, the prime factors representing numeric identifiers of the directory nodes that are ancestors of the modified node; and

wherein the method further comprises sending a notification of a quota update on a directory node that is an ancestor of the modified node.

9. The method of claim 1, wherein a data structure for each data container is an inode data structure configured to store data describing a data container.

10. A server system for sending a notification of changes in a directory registered for notification, the server system comprising:

a processor;

an index generation engine generating a first index and a second index for each node of a file system, comprising a plurality of nodes, at least one of the nodes having an ancestor node, each node comprising a data container and comprising a first index and a second index;

an index manipulation engine configured, in response to a request received by the server system to modify a node, to divide the first index of the modified node by the inode number of the directory registered for notification and responsive to the result of the division not leaving a remainder, determine the directory registered for changes is an ancestor of the modified node, without performing a text-based comparison using a name of the ancestor node; and

a directory notification engine configured to send a notification of a modification in the directory registered for notification.

11. The system of claim 10, further comprising a quota updates engine configured to send a notification by the server system of a quota update on a directory node that is an ancestor of the modified node.

12. The system of claim 10, wherein the index generation engine is further configured to multiply the first index and the second index of the immediate parents of the node to generate a second index of each directory node.

13. The system of claim 10, wherein the index generation engine is further configured to multiply the first index and the second index of the immediate parents of the modified node to generate a first index of the modified node.

14. The system of claim 10, wherein the index manipulation engine is further configured to generate prime factors of the first index of the modified node, wherein the generated prime factors represent inode numbers of the parent directories of the modified node.

15. The system of claim 10, wherein the index manipulation engine is further configured to:

generate prime factors of the second index of the modified node, the generated prime factors represent inode numbers identifying the immediate parent directories of the modified node; and

generate prime factors of the first index of the modified node, the generated prime factors represent inode numbers identifying all directory nodes on the path from a root to the modified node.

16. A method for sending a change notification by a server of changes in a file system directory registered for notification, the server system including a processor, the method comprising:

generating, for each directory node of a file system, a first index and a second index, the first index representing an inode number of the directory, the second index representing a multiplication of a first index and a second index of an immediate parent of the directory node, the file system comprising a plurality of nodes including a root node, each node comprising a first index and a second index;

generating, for each data container node of the file system, a first index and a second index, the first index representing an inode number the immediate parent of the data container node, the second index representing a multiplication of a first index and second index of the immediate parent of the data container;

in response to a request received by the server system to modify a data container node, identifying an ancestor node by dividing the second index of the modified data container node by the first index of the directory registered for change, wherein the ancestor node is associated with the directory registered for change; and

in response to no remainder resulting from the division, sending a notification of a change in the file system directory registered for notification.

17. The method of claim 16, further comprising:

generating prime factors of the index of the modified data container node, the prime factors representing inode numbers identifying all the directory nodes that are on a path from the root node to the modified data container node; and

sending a notification of a quota update on a directory node on the path from the root node to the modified data container node.

18. A non-transitory computer readable medium containing executable program instructions for execution by a processor, comprising:

program instructions that generate an index in a data structure associated with each node of a file system, whereby the index of a root node identifies a node;

program instructions that in response to a request received via a file-based protocol to modify a node, identify an ancestor node by dividing the index associated with the modified node by the inode number of an ancestor node of the modified node, the ancestor node associated with a directory registered for notification, whereby no remainder resulting from the division identifies the directory registered for notification as an ancestor of the modified node; and

program instructions that send a notification via the file-based protocol of a change in the directory registered for notification.

19. The non-transitory computer readable medium of claim 18, further comprising:

program instructions that generate prime factors of the first index of the modified node, the generated prime factors represent inode numbers identifying all ancestor nodes on the path from the root to the modified node;

program instructions that send a quota update for an ancestor node on the path path from the root to the modified node.

20. The non-transitory computer readable medium of claim 18, wherein the index is a product of prime numbers.

21. The non-transitory computer readable medium of claim 18, wherein the index is a product of a set of prime numbers, the set of prime numbers identifying all ancestor nodes of the modified node.

22. A method for sending a notification by a server system of changes in a directory registered for notification, the server system including a processor, the method comprising:

generating a first index and a second index associated with each leaf node of a file system, comprising a plurality of nodes, each leaf node having at least one ancestor node, and each leaf node comprising a data container, a first index, and a second index, wherein the first index is a multiplication a plurality of prime numbers, and wherein the second index is a multiplication of a plurality of prime numbers;

in response to a request received by the server system to modify a leaf node, identifying an ancestor node by dividing the first index associated with the modified leaf node by a prime number associated with the ancestor node, the ancestor node associated with the directory registered for notification; and

sending a notification of a change in the directory registered for notification.

23. The method of claim 22, wherein the step of identifying an ancestor node is performed without a text-based comparison using a name of the ancestor node.

24. The method of claim 22, wherein a prime number identifying each ancestor of the modified leaf node is used to form the product of prime numbers of the first index.

25. A system for sending a notification by a server system of changes in a directory registered for notification, the server system comprising:

a processor;

an index generation engine generating a first index and a second index for each leaf node of a file system, comprising a plurality of nodes, each leaf node having at least one ancestor node, and each leaf node comprising a data container, a first index, and a second index, wherein the first index is a product of a first set of prime numbers, and wherein the second index is a product of a second set of prime numbers;

an index manipulation engine configured, in response to a request received by the server system to modify a leaf node, to divide the first index associated the modified leaf node by a prime number associated with a directory node, to determine whether the directory node is an ancestor of the modified leaf node, the ancestor node associated with the directory registered for notification; and

a directory notification engine configured to send a notification of a modification in the directory registered for notification.

26. Apparatus of claim 25, wherein the index manipulation engine determines an ancestor node of the modified leaf node without a text-based comparison using a name of the ancestor node.

27. Apparatus of claim 25, wherein the index generation engine uses a prime number identifying each ancestor of the modified leaf node to form the product of the first set of prime numbers of the first index.