Path lookup in a hierarchical file system

• US 10,019,451 B2
• Filed: 09/29/2011
• Issued: 07/10/2018
• Est. Priority Date: 09/29/2011
• Status: Active Grant

• Current Assignee: Quantum Corporation (Chi Ko Investment Co., Ltd.)
• Original Assignee: Quantum Corporation (Chi Ko Investment Co., Ltd.)
• Inventors: Preslan, Kenneth William
• Primary Examiner(s): Jalil, Neveen Abel
• Assistant Examiner(s): Conyers, Dawaune
• Application Number:
  US13/248,084
• Publication Number:
  US 20130086121A1
• Time in Patent Office: 2,476 Days
• Field of Search: 707829
• 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

Apparatus and methods are provided herein for path lookup in a hierarchical file system. An inode associated with a requested object is identified. The inode may be organized in an inode table and identified in the table using an inode number. Ancestry information and size constraint information may also be available for the inode. An inode chain associated with the pathway is identified based, at least in part, on ancestry information associated with the inode for the requested object. A size constraint analysis is performed for the requested object. The size altering operation is selectively performed based on the size constraint analysis.

Claims

1. A non-transitory computer-readable medium storing computer-executable instructions that when executed by an apparatus control the apparatus to perform a method, the method comprising:

identifying an inode associated with an object located in a hierarchical file system, where the hierarchical file system has a root directory, where the hierarchical file system has a subdirectory that branches out from the root directory along a pathway, and where the object is subject to a size altering operation;

identifying an inode chain that describes a pathway in the hierarchical file system from the object through a subdirectory based, at least in part, on ancestry information associated with the inode, where identifying the inode chain includes walking up the inode chain to the root directory by identifying a parent of the inode or by identifying a parent of the object;

performing a size constraint analysis for the subdirectory on the pathway based, at least in part, on size constraint information associated with the inodes on the inode chain, by calculating a change in size of the object based on a determination that the size altering operation were to be performed and comparing the calculated change in size of the object to a size constraint, where the size constraint limits the amount by which the size of the object is allowed to change in a transaction, where the size constraint information is stored in a size constraint information data structure external to an inode table, where the size constraint information data structure is a b-tree; and

selectively performing the size altering operation associated with the object based, at least in part, on the size constraint analysis,

wherein at least one of;

an inode associated with an object subject to a size constraint is stored more frequently in a cache memory in the apparatus than an inode that is associated with an object that is not subject to a size constraint, or the inode associated with an object subject to a size constraint is stored for a longer period of time in the cache memory than the inode that is associated with an object that is not subject to a size constraint, or the inode associated with an object subject to a size constraint is stored permanently in the cache memory.

2. The non-transitory computer-readable medium of claim 1, where the ancestry information is stored in an ancestry information data structure external to the inode table, and where the ancestry information data structure is a b-tree.

3. The non-transitory computer-readable medium of claim 2, where a portion of the ancestry information data structure is stored in the cache memory in the apparatus.

4. The non-transitory computer-readable medium of claim 1, where a portion of the size constraint information data structure is stored in the cache memory in the apparatus.

5. The non-transitory computer-readable medium of claim 1, where the inodes, ancestry information, and size constraint information are stored in the inode table.

6. The non-transitory computer-readable medium of claim 5, where a portion of the inode table is stored in the cache memory in the apparatus, where the portion of the inode table includes a root inode, where the root inode is stored more frequently in the cache memory than a non-root inode, or where the root inode is stored for a longer period of time in the cache memory than a non-root inode.

7. The non-transitory computer-readable medium of claim 1, where performing a size constraint analysis comprises detecting size constraint information for the subdirectory on the pathway.

8. The non-transitory computer-readable medium of claim 1, where the size constraint information comprises a binary size flag to indicate that the object is subject to a size constraint or that the object is not subject to a size constraint.

9. The non-transitory computer-readable medium of claim 1, where selectively performing the size altering operation comprises performing one of:

performing the size altering operation upon determining that performing the size altering operation would not violate the size constraint; and

cancelling the size altering operation upon determining that performing the size altering operation would violate the size constraint.

10. The non-transitory computer-readable medium of claim 1, where the size altering operation is one of, a save command, a create command, a write command, a write append command, a move command, a relocate command, and a delete command.

11. An apparatus, comprising:

a processor;

a memory configured to store a first data structure configured to store inodes and a second data structure configured to store ancestry information and size constraint information for objects located in a hierarchical file system and having entries in the first data structure, where the hierarchical file system has a root directory, and where the hierarchical file system organizes objects in a pathway, where the first data structure stores a root inode more frequently than a non-root inode, or where the first data structure stores the root inode for a longer period of time than a non-root inode, or where the first data structure stores the root inode permanently, and where the second data structure configured to store ancestry information and size constraint information is a b-tree;

a set of logics; and

an interface configured to connect the processor, the memory, and the set of logics,

the set of logics comprising;

an inode logic configured to identify an inode for an object, and to identify ancestry information and size constraint information associated with the inode; and

a path lookup logic configured to use the ancestry information to discover a pathway, where the pathway describes a path from the root directory to the object through parent objects, and determine whether an object associated with the inode is subject to a size limitation by identifying size constraint information for the parent objects on the pathway, where the size limitation limits the amount by which the size of the object is allowed to change in a transaction, or where the path lookup logic is configured to discover the pathway by walking up an inode chain to the root directory by identifying a parent of the inode or by identifying a parent of the object,

wherein at least one of;

an inode associated with an object subject to a size limitation is stored more frequently in a cache memory in the apparatus than an inode that is associated with an object that is not subject to a size limitation, or where the inode associated with an object subject to a size limitation is stored for a longer period of time in the cache memory than the inode that is associated with an object that is not subject to a size limitation, or where the inode associated with an object subject to a size limitation is stored permanently in the cache memory.

12. The apparatus of claim 11, comprising

a receiving logic configured to receive a size altering operation request associated with the object;

and

a performance logic configured to selectively perform the size altering operation based, at least in part, on the determination of the size constraint information of the pathway.

13. The apparatus of claim 11, where the first data structure is one of, an inode table, an inode tree, and an inode ranking, and where the b-tree is keyed by an inode number of the root directory.

14. The apparatus of claim 11, where the inode logic is configured to identify stored inodes in the memory using inode numbers, where an inode number is a unique identifier and where the ancestry information and the size constraint information for an object are associated with the object with the inode numbers.

15. The apparatus of claim 11, where the objects are one or more of, a file, a subdirectory, and a root directory.