JP2019537097A - Tracking I-node access patterns and pre-empting I-nodes - Google Patents

Abstract

Disclosed herein are methods, systems, and processes for tracking access patterns of inodes and issuing read ahead instructions to pre-fetch inodes into memory. A location of a metadata unit in a metadata storage area is determined. An alternative location in the metadata storage area corresponding to a current metadata read operation is determined. It is determined whether a metadata read ahead operation can be performed using the location of the metadata unit and the alternative location. In response to determining that a metadata read ahead operation can be performed, a metadata read ahead operation is issued. Additionally, the inode is accessed and a directory of the inode is determined. Also, it is determined whether an entry for the directory exists in a global inode list. If the entry exists in the global inode list, it is determined whether the file structure of the directory is sequential or non-sequential. If the entry does not exist in the global inode list, a new entry for the directory is added to the global inode list.

Description

This disclosure relates to data access. In particular, this disclosure relates to tracking inode access patterns and issuing inode read-ahead instructions to prefetch inodes.

A file system is used to control how data is stored and retrieved for computing purposes (e.g., to store and execute applications). Data objects (e.g., files, directories, etc.) in a file system have one or more inodes. An inode is a data structure used to identify data belonging to a data object in a file system. An inode stores attributes (e.g., metadata) and disk block location(s) of the data object's data.

Accessing a file in a file system requires reading the file's inode from disk (e.g., from a non-volatile storage unit). Data operations such as backups, periodic scans, and administrative operations typically access multiple inodes on disk. Reading such "on-disk" inodes from disk can adversely affect application performance. For example, if the underlying disk is slow, reading the on-disk inode from disk can result in inappropriate and/or significant input/output (I/O) latency before an application can be served the required data.

The contents of a file can be loaded into memory (e.g., Random Access Memory (RAM)) so that when the file is subsequently accessed, the file contents are read from RAM instead of from disk (e.g., Hard Disk Drive (HDD)). However, loading the contents of a file into memory requires the inode corresponding to the file contents being accessed from disk.

Disclosed herein are methods, systems, and processes for tracking access patterns of inodes to accelerate data access by prefetching inodes in memory. One such method includes determining a location of a metadata unit in a metadata storage area in a non-volatile storage unit. The method determines another location in the metadata storage area that corresponds to a current metadata read operation, and determines whether a metadata read ahead operation can be performed using the location of the metadata unit and the another location. In response to determining that a metadata read ahead operation can be performed, the method issues a metadata read ahead operation.

In a particular embodiment, the metadata storage area includes an on-disk inode. The on-disk inode includes a metadata unit and is part of a structural file. The structural file is stored in a non-volatile storage unit. The method creates an in-core inode corresponding to the structural file and stores a location of the metadata unit in the in-core inode. In this example, the metadata unit is the last read metadata chunk, and the location of the metadata unit identifies and includes the ending offset of the metadata unit.

In some embodiments, determining whether a metadata read ahead operation can be performed includes accessing an ending offset of a metadata unit and determining whether another location is adjacent to the ending offset. In this example, issuing a metadata read ahead operation includes updating the ending offset by replacing it with another ending offset of another metadata unit read by the metadata read ahead operation (e.g., another last read metadata chunk), and if the other location is not adjacent to the ending offset, updating the ending offset by replacing it with the ending offset of the current metadata read operation.

In another embodiment, the method intercepts a command to read one or more on-disk inodes in response to an input/output (I/O) operation. In this example, the method analyzes the issued metadata readahead value in the metadata readahead operation by comparing the issued readahead value to the chunk total in the command. The method waits for the I/O operation to complete and/or waits to issue an asynchronous metadata readahead command.

In certain embodiments, determining whether the I/O operation is complete includes generating a queue if the I/O operation is complete. The queue includes remaining chunks of metadata in the chunk total that are not included in the asynchronous metadata read ahead instruction. The method updates the chunk total in the metadata read ahead operation if the I/O operation is not complete.

Some embodiments include accessing an inode, determining a directory of the inode (e.g., an on-disk inode), and determining whether an entry for the directory exists in a global inode list. If the entry exists in the global inode list, the method determines whether the file structure of the directory is sequential or non-sequential, and if the entry does not exist in the global inode list, the method adds a new entry for the directory in the global inode list.

In certain embodiments, determining whether the directory is in the global inode list includes searching the global inode list for an entry. The method determines whether the directory includes a sequential flag if the file structure of the directory is sequential. If the directory includes the sequential flag, the method issues a metadata read ahead operation on an inode in the directory. If the file structure of the parent directory is non-sequential, the method retrieves the inode list of the directory and issues a metadata read ahead operation on an inode on the inode list. In some embodiments, the method intercepts a command to read one or more on-disk inodes in response to an input/output (I/O) operation. In this example, the method parses the issued metadata read ahead value in the metadata read ahead operation by comparing the issued metadata read ahead value to the chunk total in the command. The method waits for the I/O operation to complete and/or issue an asynchronous metadata read ahead command.

In another embodiment, determining whether the I/O operation is complete includes generating a queue if the I/O operation is complete. The queue includes remaining chunks of metadata in the chunk total that are not included in the asynchronous metadata read ahead instruction. The method updates the chunk total in the metadata read ahead operation if the I/O operation is not complete.

The foregoing is a summary and thus necessarily contains simplifications, generalizations, and omissions of detail, and as a result, those skilled in the art will appreciate that the summary is merely illustrative and not limiting in any way. Other aspects, features, and advantages of the present disclosure, as defined solely by the claims, will become apparent in the non-limiting detailed description set forth below.

The present disclosure may be better understood, and most of its objects, features, and advantages made apparent to those skilled in the art, by referring to the accompanying drawings.

FIG. 2 is a block diagram of a system for tracking inode access patterns and prefetching inodes according to one embodiment of the present disclosure.

FIG. 2 is a block diagram of a structure file according to an embodiment of the present disclosure.

FIG. 2 is a block diagram of a structural file and an in-core inode according to one embodiment of the present disclosure.

FIG. 2 is a block diagram of a system for tracking inode access patterns and issuing metadata read-ahead instructions according to one embodiment of the present disclosure.

FIG. 2 is a block diagram of offset metadata for an inode according to one embodiment of the present disclosure.

1 is a table illustrating the contents of a global inode list/parent directory list according to one embodiment of the present disclosure.

FIG. 2 is a block diagram of a directory access tracker according to one embodiment of the present disclosure.

FIG. 2 is a block diagram of a metadata lookahead generator according to an embodiment of the present disclosure.

FIG. 2 is a block diagram of a directory with sequential inodes according to one embodiment of the present disclosure.

FIG. 2 is a block diagram of a directory with non-sequential inodes according to one embodiment of the present disclosure.

FIG. 2 is a block diagram of a cache implementing a global inode list according to an embodiment of the present disclosure.

1 is a flowchart illustrating a process for performing inode prefetching in accordance with an embodiment of the present disclosure.

1 is a flowchart illustrating a process for storing offset metadata associated with an on-disk inode according to an embodiment of the present disclosure.

1 is a flow chart illustrating a process for determining the file structure of a directory according to one embodiment of the present disclosure.

10 is a flowchart illustrating a process for issuing a metadata read ahead command to an on-disk inode in accordance with one embodiment of the present disclosure.

1 is a flowchart illustrating a process for handling input/output (I/O) operations related to inode prefetching in accordance with one embodiment of the present disclosure.

1 is a flowchart illustrating a process for handling I/O operations related to inode prefetching in accordance with an embodiment of the present disclosure.

1 is a flowchart illustrating a process for handling access of an on-disk inode according to one embodiment of the present disclosure.

1 is a flowchart illustrating a process for handling a request to access an on-disk inode according to one embodiment of the present disclosure.

FIG. 2 is a block diagram of a computing system illustrating how an access pattern tracker and metadata read-ahead generator may be implemented in software according to one embodiment of the present disclosure.

FIG. 1 is a block diagram of a networked system illustrating how various computing devices may communicate over a network in accordance with one embodiment of the present disclosure.

While the present disclosure is susceptible to various modifications and alternative forms, specific embodiments of the disclosure are provided by way of example in the drawings and detailed description. It should be understood that the drawings and detailed description are not intended to limit the disclosure to the particular forms disclosed. Instead, the intention is to cover all modifications, equivalents, and alternatives falling within the spirit and scope of the disclosure as defined by the appended claims.

Introduction A file system (e.g., the Unix file system) is used to organize data and control how that data is stored and retrieved. A file system is responsible for organizing data objects such as files and directories, and keeping track of which regions of a storage device (e.g., a Hard Disk Drive (HDD), a Solid State Drive (SSD), and/or the like) belong to which data object. Typically, each data object in a file system (e.g., a file, a directory, etc.) has a corresponding node.

An inode is a data structure used to locate data within a file system. An inode stores the attributes (e.g., metadata) and disk block location(s) of a data object's data, and may be identified by an integer number (e.g., called the inode number). A directory may contain a list of names assigned to inodes. A directory contains an entry for itself, an entry for the directory's parent, and an entry for each of the directory's children.

Accessing a file in a file system typically involves reading the file's inode from disk (e.g., from a non-volatile storage unit) to, for example, determine changes and/or modifications to the file's contents and in some cases to verify ownership and permission information (e.g., group ID, user ID, permissions, etc.). Thus, before the file's contents can be accessed, the file's inode (metadata) must first be read from disk.

Data operations (e.g., input/output (I/O) operations) typically require access of multiple inodes to disk, and reading such "on-disk" inodes from disk can adversely affect application performance (e.g., in the form of I/O latency before a given I/O operation can be completed). Also, as previously described, file contents can be "read ahead" and loaded into memory (e.g., random access memory (RAM)) so that when the file is subsequently accessed, the file contents are read from RAM rather than from disk (e.g., HDD). Thus, prefetching data in this manner (e.g., to accelerate data access) requires tracking of the access pattern(s) of inodes in order to "read ahead" these inodes before their associated data (e.g., files, directories, etc.) can be preloaded into memory.

Unfortunately, unlike file data, efficient tracking of inode metadata access pattern(s) is difficult for at least two reasons. First, multiple I/O operations (e.g., from multiple applications running in a cluster) can access the same inode simultaneously. Tracking the inode access pattern(s) of multiple I/O operations can be memory and computational resource intensive and can result in significant overhead. Second, tracking the inode access pattern(s) also requires efficient "read-ahead" of such inodes (e.g., by issuing read-ahead instructions) without adversely affecting system performance at the same time.

Disclosed herein are methods, systems and processes that are capable of tracking access patterns of inodes based on chunk access, sequential access and non-sequential access and issuing read-ahead instructions to inodes, among other capabilities.
Example system for tracking inode access pattern(s) and issuing read-aheads

1A is a block diagram of a computing system 100A configured to track inode access pattern(s) and preempt inodes, according to one embodiment. As shown in FIG. 1A, computing device 105 includes a processor 110 and memory 115. Computing device 105 may be any type of computing system, including a server, desktop, laptop, tablet, etc., and is communicatively coupled to storage system 145 via network 185. Network 185 may be any type of network and/or interconnection (e.g., a Local Area Network (LAN), a Wide Area Network (WAN), a Storage Area Network (SAN), the Internet, etc.).

Storage system 145 may include a variety of different storage devices, including one or more logical storage devices, such as hard disks, compact disks, digital versatile disks, SSD memory such as flash memory, or volumes implemented on one or more such physical storage devices. Storage system 145 includes one or more of such storage devices (e.g., disks 150). In one embodiment, disks 150 are non-volatile storage units. In other embodiments, disks 150 are HDDs or SSDs. Disks 150 include file system 155. File system 155 may be any type of file system (e.g., a Unix file system, an extent-based file system, etc.).

The operating system 120 and applications 135 and 140 are stored in memory 115 and executed by the operating system 120. The operating system 120 further includes an in-core inode list 125 (e.g., having multiple in-core inodes 126(1)-(N)), which includes directory inodes 130(1)-(N). The directory inodes 130(1)-(N) are, for example, parent directory representations of the on-disk inodes of the in-core inode list 125 (which includes in-core inodes for files, directories, etc.). The file system 155 includes a structural file 160, a directory data structure 170, and data 180. The structural file 160 includes on-disk inodes 165(1)-(N), and the directory data structure 170 includes an inode list 175. In one embodiment, the structural file 160 is an iList file. In this embodiment, an iList file is a file that maintains a listing of on-disk inodes (e.g., on-disk inodes 165(1)-(N)).

Data objects (e.g., files, directories, and/or the like) in file system 155 are associated with corresponding inodes (e.g., on-disk inodes 165(1)-(N)). Each on-disk inode has a specific inode number and is stored on disk 150 (e.g., as on-disk inodes 165(1)-(N) and as part of structure file 160). In-core inode list 125 is an in-memory data structure (or list) for one (or more) on-disk inodes. In-core inode list 125 contains metadata stored as part of on-disk inodes 165(1)-(N) as well as other additional metadata.

File system 155 includes directory data structure 170. Directory data structure 170 includes inode list 175. The parent of a data object (e.g., a file, a subdirectory, etc.) is the directory of which the given data object is a part. For example, if a given directory (e.g., /home/john) contains four data objects (e.g., file1, file2, file3, and dir1, with pathnames /home/john/file1, /home/john/file2, /home/john/file3, and /home/john/dir1, respectively), then the parent directory of the parent directories of these directory entries (e.g., file1, file2, file3, and dir1) is "john". Each data object also has a corresponding and/or associated on-disk inode (e.g., on-disk inode 165(1) for "john", on-disk inode 165(2) for "file1", on-disk inode 165(3) for "file2", on-disk inode 165(4) for "file3", and on-disk inode 165(5) for "dir1". In this scenario, the parent (directory) inode number of on-disk inodes 165(2), 165(3), 165(4), and 165(5) is on-disk inode 165(1) (shown as directory inode 130(1) in in-core inode list 125 for clarity).

According to some embodiments, FIG. 1B is a block diagram 100B of a structural file, and FIG. 1C is a block diagram 100C of a structural file and an in-core inode. A directory in file system 155 contains a list of tuples (e.g., <filename, file inode number>). Inode list 175 is an example of such a list of tuples in file system 155. The data portion of on-disk inode 165(1) includes <file1, on-disk inode 165(2)>, <file2, on-disk inode 165(3)>, <file3, on-disk inode 165(4)>, and <dir1, on-disk inode 165(5)>. As shown in FIG. 1B, these "on-disk" inodes are maintained as data for structural file 160 (e.g., an iList file). Since structural file 160 is also a file, structural file 160 also has its own inode with a unique inode number. As shown in FIG. 1C, when structural file 160(1) is brought into core (e.g., into memory 115), an in-core inode is created for structural file 160(1) (e.g., in-core inode 126(1) in an in-core inode list, such as in-core inode list 125). Each structural file and on-disk inode has an associated in-core inode.

Figure 2A is a block diagram of a computing system 200A that tracks access patterns of inodes and issues metadata read-ahead instructions, according to one embodiment. As shown in Figure 2A, computing device 105 includes memory 115. Memory 115 implements cache 205, access pattern tracker 225, and metadata read-ahead generator 240. Cache 205 implements global inode list 215, which includes one or more entries from the in-core inode list. In-core inode 126(1) is an in-memory data structure (or list) created for structural file 160(1).

In-core inode 126(1) includes offset metadata 210. Global inode list 215 is a global in-memory inode list. Offset metadata 210 includes location information for on-disk inode access patterns, and global inode list 215 (also referred to as parent directory list) includes directory inodes 130(1)-(N) (e.g., in-core parent directory inode numbers of the on-disk inodes) and sequential flags 220(1)-(N). Sequential flags 220(1)-(N) may be stored as part of the in-core inode for a parent directory (e.g., a parent directory identified in memory by its in-core parent directory inode number and shown in FIG. 2A as directory inodes 130(1)-(N)). Access pattern tracker 225 includes chunk access tracker 230 (e.g., for tracking chunk accesses of the on-disk inodes) and a directory access tracker (e.g., for tracking sequential and non-sequential accesses of the on-disk inodes within the directory). The aforementioned elements of FIG. 2A are described in more detail with respect to FIGS. 2B-2E.
Example of tracking inode chunk access patterns

2B is a block diagram 200B of offset metadata according to one embodiment. The offset metadata 210 includes the ending offset of the last read metadata chunk 245 and the starting offset of the current metadata read operation 250. Because the file system 155 persistently stores the in-core inodes 165(1)-(N) on the disk 150, if a particular inode is not found in-core (e.g., in the cache 205), the chunk access tracker 230, which is part of the access pattern tracker 225, reads the on-disk inode in the structural file 160 from the disk 150 in chunks (e.g., 1 KB, 2 KB, 4 KB, or other suitable size). In this manner, the chunk access tracker 230 can be configured to track the access patterns of chunks of metadata (e.g., on-disk inodes) and facilitate a determination as to whether an application (e.g., application 135 or application 140) is accessing the on-disk inodes sequentially (or near sequentially).

In one embodiment, chunk access tracker 230 determines the location of the metadata unit in the metadata storage area (e.g., in structure file 160) (the location/ending offset of the 1 KB chunk in on-disk inodes 165(1)-(4) as shown in FIG. 1B). Chunk access tracker 230 determines another location (e.g., starting offset) in the metadata storage area (e.g., in structure file 160) that corresponds to the current metadata read operation. Metadata read ahead generator 240 then uses the location of the data chunk and the other location that corresponds to the current metadata read operation to determine whether a metadata read ahead operation is required. If a metadata read ahead operation is required, metadata read ahead generator 240 issues a metadata read ahead operation.

The chunk access tracker 230 maintains the ending offset (e.g., the end of the logical offset in the structural file 160(1)) of the last read metadata chunk 245 from the disk 150 in the in-core inode 126(1) associated with the structural file 160(1). For example, if application 135 and/or application 140 attempts to access data 180 in the disk 150 that causes (and requires) a read of a 1 KB chunk of the on-disk inode, the chunk access tracker 230 stores the ending offset of the 1 KB chunk of the on-disk inode (e.g., the ending offset of the 1 KB chunk of the on-disk inodes 165(1)-(4) as shown in FIG. 1B) as a "stored value" in the in-core inode 126(1) of the structural file 160(1).

In some embodiments, the starting offset of the current metadata read operation 250 (e.g., on-disk inode 165(5) as shown in FIG. 1B) is adjacent to the stored value (e.g., the ending offset of on-disk inodes 165(1)-(4) minus the ending offset of the last read metadata chunk 245), and the metadata readahead generator 240 issues a metadata readahead command to retrieve 1 KB-2 KB of the on-disk inode (e.g., on-disk inodes 165(5)-(8) as shown in FIG. 1B) in the structure file 160 into the cache 205. Because the chunk access tracker 230 determines that the on-disk inode accesses are occurring sequentially, the metadata readahead generator 240 issues a metadata readahead command to retrieve the next 1 KB chunk of the on-disk inode (e.g., 1 KB-2 KB) from disk 150 to the in-core inode list 125.

When the metadata read-ahead command is triggered (e.g., the starting offset of the current metadata read operation 250 is next to the ending offset of the last read metadata chunk 245), the access pattern tracker 225 updates the stored value in the in-core inode list 125 (e.g., the ending offset of on-disk inodes 165(1)-(4) - the ending offset of the last read metadata chunk 245) by replacing the stored value in the cache 205 read by the metadata read-ahead operation with another ending offset of another last read metadata chunk (e.g., on-disk inodes 165(5)-(8) (at 2 KB) as shown in FIG. 1B, since the metadata read-ahead operation reads ahead 1 KB-2 KB of on-disk inodes as a result of the (issued) metadata read-ahead command). On the other hand, if the starting offset of the current metadata read operation 250 is not adjacent to the ending offset of the last read metadata chunk 245, and therefore no metadata read-ahead is triggered, the access pattern tracker 225 resets the stored value (e.g., the ending offset of on-disk inodes 165(1)-(4) - the ending offset of the last read metadata chunk 245) with the ending offset of the current metadata read operation.

It will be appreciated that inode chunk access pattern(s) can be tracked and metadata read ahead instructions and/or operations can prefetch applicable inodes from disk to memory to accelerate subsequent accesses of those inodes. Methods, systems, and processes for tracking access patterns to inodes for nodes that are part of a directory are now described.
Example of tracking inode access patterns using parent directories

It will be appreciated that inode allocation policies may keep on-disk inodes close to each other in the same directory, referred to herein as close location. For example, on-disk inodes for files that are frequently accessed and accessed together may be kept in the same directory. This close location of on-disk inodes within a directory may be used to track directory access of inodes. For example, a global inode list 215 (or parent directory list) may be created and maintained to track access of on-disk inodes.

2C is a table 200C illustrating the contents of such a global inode list, and FIG. 2D is a block diagram 200D of a directory access tracker 235 that uses a global inode list, according to a particular embodiment. Global inode list 215 (which is the parent directory list of directories 265(1)-(N)) includes directory inode field 255 and sequential flag field 260. Global inode list 215 is created and maintained in memory and includes directory inodes 130(1)-(N) and sequential flags 220(1)-(N). The sequential flags may be stored as part of the in-core inode for the parent directory. Directory access tracker 235 includes sequential directory access tracker 270 and non-sequential directory access tracker 275.

In one embodiment, an application accesses an inode (e.g., on-disk inode 165(4)). Directory access tracker 235 determines the parent directory of the node (e.g., directory 265(1)) and determines whether an entry for the directory exists in global inode list 215. If the directory entry exists in global inode list 215, directory access tracker 235 determines whether the file structure of the directory is sequential or non-sequential (e.g., by determining whether the on-disk inodes in that directory are listed and therefore accessed sequentially or non-sequentially). If the directory entry does not exist in global inode list 215, directory access tracker 235 adds a new entry for the parent directory inode in global inode list 215. It should be noted that, as shown in Figures 1A, 2A, 2C, and 3C, a directory inode (e.g., directory inodes 130(1)-(N)) is simply a directory-specific representation of the on-disk inode that represents the parent directory (e.g., instead of an individual file). For example, directory inode 130(1) is an in-memory data structure that represents the parent directory of one or more on-disk inodes.

To track sequential directory accesses of an on-disk inode, sequential directory access tracker 270 first finds the parent directory of the given on-disk inode (e.g., finds the inode number of the parent directory). For example, if on-disk inode 165(4) is read from disk 150, sequential directory access tracker 270 finds the parent directory of on-disk inode 165(4) (e.g., directory inode 130(1)). Sequential directory access tracker 270 then searches global inode list 215 for an entry of the parent directory (inode) of the given on-disk inode (e.g., whether the parent directory inode number exists in cache 205).

If an entry for the parent directory (inode) exists in the global inode list 215, the sequential directory access tracker 270 checks the global inode list 215 to determine whether the parent directory has the sequential flag set (e.g., in this case, inode 130(1), which is the parent directory inode number and has the directory sequential flag set, as shown in FIG. 2C). If the sequential flag is set, the metadata readahead generator 240 issues a metadata readahead command (e.g., to retrieve all remaining on-disk inodes in directory 265(1) since the on-disk inode access is sequential). If the sequential directory access tracker 270 does not find an entry for the parent directory in the global inode list 215, the sequential directory access tracker 270 adds a new entry for the parent directory inode number to the global inode list 215.

To track non-sequential directory accesses of an on-disk inode, non-sequential directory access tracker 275 first finds the parent directory of a given on-disk inode (e.g., the inode number of the parent directory). Then, non-sequential directory access tracker 275 searches global inode list 215 for an existing entry of the parent directory (e.g., whether the parent directory inode number exists in cache 205). If an entry of the parent directory exists in global inode list 215, non-sequential directory access tracker 275 retrieves (or reads) the parent directory's inode list (e.g., the portion or part of inode list 175 applicable to the parent directory in question) from disk 150 to cache 205, and metadata readahead generator 240 issues metadata readahead commands for the on-disk inodes listed on the read inode list (e.g., the on-disk inodes associated with and that are part of the parent directory). If the parent directory entry does not exist in the global inode list 215, the non-sequential directory access tracker 275 adds a new entry for the parent directory's inode number to the global inode list 215.
Example of issuing a metadata prefetch command to an I-node

2E is a block diagram 200E of a metadata read-ahead generator according to one embodiment. The metadata read-ahead generator 240 is implemented by the computing device 105 and includes a queue generator 290 that stores issued metadata read-ahead values 280 and asynchronous metadata read-ahead instructions 285. The directory access tracker 235 identifies one or more on-disk inodes to prefetch, but if these on-disk inodes are not prefetched, I/O operations associated with these on-disk inodes cannot be completed.

Thus, in one embodiment, metadata readahead generator 240 intercepts commands to read on-disk inodes in response to I/O operations (e.g., read or write operations). An I/O operation that accesses data may result (or cause) a command to access and read the on-disk inode(s) (e.g., metadata) associated with that data (e.g., to determine if and how the requested data has changed, etc.). Metadata readahead generator 240 analyzes the issued metadata readahead value 280 in the metadata readahead operation by comparing the issued metadata readahead value 280 to the chunk total in the command.

The issued metadata read-ahead value 280 includes all on-disk inodes to be read ahead (e.g., detected based on sequential/near-sequential chunk accesses and/or sequential or non-sequential accesses of on-disk inodes in the directory). The chunk total is the total number of chunks of the on-disk inode to read ahead (e.g., represented herein as an integer "N" for purposes of illustration). For example, the chunk access tracker 230 and the sequential directory access tracker 270 may identify and determine that a 1 KB chunk of the on-disk inode (e.g., on-disk inodes 165(1)-(4)) or a 2 k chunk of the on-disk inode (e.g., on-disk inodes 165(1)-(8)) must be read ahead (e.g., based on sequential/near-sequential chunk accesses and/or sequential or non-sequential accesses of on-disk inodes in the directory). However, as discussed above, the non-sequential directory access tracker 275 may identify several non-sequential on-disk inodes (e.g., which may be part of various different chunks) to read ahead (e.g., as shown in the case of directory 265(2) in FIG. 3B). Thus, it will be appreciated that in certain scenarios, the published metadata read ahead value 280 may or may not be equal to N.

In some embodiments, the metadata read ahead generator 240 waits for the I/O operation to complete or issues an asynchronous metadata read ahead instruction 285 based on comparing the metadata read ahead value 280 to the chunk total in the command. If the I/O operation is complete, the queue generator 290 creates a queue containing the remaining chunks of metadata in the chunk total that are not included in the asynchronous metadata read ahead instruction 285. On the other hand, if the I/O operation is not complete, the queue generator 290 updates the chunk total in the metadata read ahead operation.

For example, after an I/O operation is issued (e.g., by application 130), a command (or request) to read the on-disk inode going to disk 150 is intercepted. This command triggers the inode access pattern detection method described above (e.g., sequential/near sequential chunk accesses, and/or sequential or non-sequential accesses of the on-disk inode in a directory). If the inode access pattern detection method does not trigger an on-disk inode read-ahead, metadata read-ahead generator 240 simply waits for the I/O operation to complete. On the other hand, if the inode access pattern detection method does trigger an on-disk inode read-ahead, metadata read-ahead generator 240 determines whether the total issued metadata read-ahead (e.g., issued metadata read-ahead value 280) is less than or equal to N (e.g., the total number of on-disk inode chunks to read ahead).

If the total issued metadata read ahead is less than or equal to N, the metadata read ahead generator 240 issues an asynchronous metadata read ahead instruction 285 with the next chunk of asynchronous metadata read (e.g., the next chunk of issued metadata read ahead value 280 after N). If the original I/O operation is complete, the queue generator 290 generates a separate thread that issues an asynchronous metadata read ahead instruction 285 with the remaining chunk of asynchronous metadata read (e.g., the remaining chunk of issued metadata read ahead value 280 after N). If the original I/O operation is not complete, the metadata read ahead generator 240 increments a counter of issued metadata read ahead value 280, determines whether issued metadata read ahead value 280 is equal to N, and waits for the original I/O operation to complete.

It will be appreciated that metadata read-ahead detection and issuance of asynchronous metadata read-ahead instructions are performed in the context of a blocking thread while the original I/O operation waits to complete in the background. These methods reduce the overhead of inode access pattern detection on system performance and also avoid the creation and scheduling of a separate thread, which can delay the availability of blocks for subsequent reads.
Example of tracking sequential and non-sequential directory access patterns of inodes

According to some embodiments, FIG. 3A is a block diagram of a directory with a sequential inode structure 300A, FIG. 3B is a block diagram of a directory with a non-sequential inode structure 300B, and FIG. 3C is a block diagram of a cache 300C that implements a global inode list (e.g., a parent directory list or a global in-memory inode list). It will be appreciated that listing of a directory is initially performed by an application (e.g., by application 135, application 140, or some other application). During listing of a directory, the on-disk inode number associated with each directory entry is returned. If the on-disk inode numbers in a given directory are sequential (e.g., directory 265(1) as shown in FIG. 3A), sequential directory access tracker 270 sets the sequential flag for that particular directory in the in-core inode for that directory (e.g., the sequential flag for directory 265(1) is set in global inode list 215 as shown in FIGS. 2C and 3C).

For example, because the on-disk inode for directory 265(1) is sequential (e.g., on-disk inodes 165(4)-(9) are listed sequentially), sequential directory access tracker 270 sets a sequential flag in directory inode 130(1) (e.g., in the in-core inode) for directory 265(1) (e.g., indicated by a "1" in sequential flag field 260 of global inode list 215 in Figures 2C and 3C). In contrast, because the on-disk inode for directory 265(2) is non-sequential (e.g., on-disk inodes 165(4), 165(9), 165(15), 165(11), 165(19), and 165(6) are listed non-sequentially), non-sequential directory access tracker 275 does not set the sequential flag in directory inode 130(2) (e.g., in the in-core inode) for directory 265(2) (e.g., as indicated by a "0" in sequential flag field 260 of global inode list 215 in FIGS. 2C and 3C).

As previously discussed, a metadata read-ahead command to perform a metadata read-ahead operation may be issued after a directory listing has been performed. In one embodiment, an application performs a listing of a directory that is part of disk 150. For example, listing directory 265(2) as shown in FIG. 3B returns file 315(1) with on-disk inode 165(4), file 315(2) with on-disk inode 165(9), file 315(3) with on-disk inode 165(15), file 315(4) with on-disk inode 165(11), file 315(5) with on-disk inode 165(19), and file 315(6) with on-disk inode 165(6). In this scenario, directory access tracker 235 creates and maintains an in-memory data structure (e.g., an in-memory inode list) that contains a list of the aforementioned inode numbers (e.g., on-disk inodes 165(4), 165(9), 165(15), 165(11), 165(19), and 165(6)) and associates this in-memory inode list with the in-core inode of directory 265(2) (e.g., directory inode 130(2)).

For example, if application 130 accesses file 315(1) and therefore needs to access and read on-disk inode 165(4), non-sequential directory access tracker 275 reads on-disk inode 165(4) from disk 150 and determines that the parent directory inode number of on-disk inode 165(4) is directory inode 130(2). Next, non-sequential directory access tracker 275 checks whether directory inode 130(2) is present in cache 205, as shown in FIG. 3C. If directory inode 130(2) is not present in cache 205, non-sequential directory access tracker 275 adds directory inode 130(2) to cache 205 (e.g., as shown in bold in FIGS. 2C and 3C).

Next, if application 130 accesses file 315(2), and therefore accesses and reads disk inode 165(9) from disk 150, non-sequential directory access tracker 275 determines that the parent directory inode number of on-disk inode 165(9) is also directory inode 130(2). Because directory inode 130(2) has been added to cache 205, metadata read-ahead generator 240 determines that the remaining files under directory 265(2) (e.g., files 315(3)-(6)) are available for read-ahead. Metadata read ahead generator 240 then accesses the in-memory inode list, identifies the remaining on-disk inode numbers associated with files 315(3)-(6) (e.g., on-disk inodes 165(15), 165(11), 165(19), and 165(6)), and generates metadata read ahead instructions that cause metadata read ahead operations to retrieve on-disk inodes 165(15), 165(11), 165(19), and 165(6) from disk 150 to memory 115.

It will be appreciated that the directory access tracker 235 tracks the chunk access pattern(s) of on-disk inodes, as well as the sequential and non-sequential access pattern(s) of on-disk inodes that are part of a directory, to identify on-disk inodes that are candidates for metadata read-ahead operations to accelerate inode and data access.
A process that tracks inode access pattern(s) and issues metadata read-ahead instructions

FIG. 4A is a flow chart 400A illustrating a process for issuing a read-ahead command to prefetch an on-disk inode from disk to memory, according to one embodiment. The process begins at 405 by accessing a metadata storage area (e.g., structural file 160). At 410, the process determines the location of the last read metadata chunk (e.g., the ending offset of the last read metadata chunk 245). At 415, the process determines whether a command (or request) (e.g., to read an on-disk inode) has been received. If a command has not yet been received, the process loops back to 415. However, if a command has been received, the process determines at 420 the location of the command's object in the metadata storage area (e.g., the starting offset of the current metadata read operation 250).

At 425, the process determines whether metadata read-ahead can be performed (or whether metadata read-ahead is required or feasible). If metadata read-ahead cannot be performed, the process allows normal processing at 430 (e.g., no metadata read-ahead operation is performed and the on-disk inode is not prefetched from disk to memory). On the other hand, if metadata read-ahead can be performed (and/or is required and/or feasible), the process issues a metadata read-ahead operation at 435 (or issues a metadata read-ahead command, e.g., using the metadata read-ahead generator 240, to cause the computing device 105 to perform a metadata read-ahead operation to retrieve chunk(s) of the on-disk inode from disk to memory). At 440, the process determines whether there is a new command (e.g., accessing and/or reading the on-disk inode). If there is a new command accessing and/or reading the on-disk inode, the process loops back to 405. Otherwise, the process ends.

Figure 4B is a flow chart 400B illustrating a process for storing offset metadata associated with an on-disk inode according to one embodiment. The process begins at 445 by determining the offset location of a metadata chunk (e.g., the ending offset of the last read metadata chunk 245) in a metadata storage area (e.g., structural file 160). At 450, the process creates an in-core inode (e.g., in-core inode list 125) in memory (e.g., memory 115), and at 455, the process stores the offset location of the metadata chunk in the in-core inode.

At 455, the process determines whether the location of the current metadata read operation (e.g., the start offset of the current metadata read operation 250) is next to (or adjacent to) the offset location of the metadata chunk. If the location of the current metadata read operation is not next to the offset location of the metadata chunk, the process stores the offset location of the metadata chunk read by the current metadata read operation (e.g., the end offset of the current metadata read operation) at 465. On the other hand, if the location of the current metadata read operation is next to the offset location of the metadata chunk, the process issues a metadata read ahead operation (or issues a metadata read ahead command) at 470 and stores the offset location of the metadata chunk read by the metadata read ahead operation at 475. At 480, the process determines whether there is a new read request (e.g., a command to read the on-disk inode caused by an application I/O operation). If there is a new read request to read the on-disk inode, the process loops back to 460. If not, the process ends.

It will be appreciated that the process illustrated in flowchart 400A of FIG. 4A and flowchart 400B of FIG. 4B are examples of tracking chunk access patterns of on-disk inodes. Because on-disk inodes are persistently stored on disk (e.g., disk 150), chunk access tracker 230 can access structure file 160 to determine the ending offset of the last read metadata chunk, as well as the starting offset of the current metadata read operation. Chunk access tracker 230 can save this location information so that chunk access tracker 230 can determine whether on-disk inodes are being accessed sequentially or near sequentially by application 135 or application 140. Based on this stored location information, on-disk inodes that are likely to be accessed can be read ahead and pre-fetched from disk to memory, thus accelerating subsequent inode accesses to those on-disk inodes.

Figure 5A is a flow chart 500A illustrating a process for determining the file structure of a directory, according to one embodiment. The process begins at 505 by accessing a file in the directory (e.g., file 135(1) in directory 265(1) as shown in Figure 3A, or file 135(1) in directory 265(2) as shown in Figure 3B). At 510, the process searches the global inode list for an entry (e.g., inode number) for the directory. At 515, the process determines whether the directory exists in the global inode list (e.g., whether directory inode 130(1), which is the inode number of directory inode 265(1), exists and is listed in global inode list 215).

If the directory does not exist in the global inode list, the process adds a new entry (e.g., adds the parent directory inode number) for the on-disk inode (e.g., as shown for directory 265(3) in FIGS. 2C and 3C) in the global inode list at 520. If the directory does exist in the global inode list, the process determines the file structure of the directory (e.g., whether the on-disk inodes in the directory are listed sequentially or non-sequentially) at 525. At 530, the process determines whether there is another access of the on-disk inode. If there is another access of the on-disk inode, the process loops back to 505. Otherwise, the process ends.

Figure 5B is a flow chart 500B illustrating a process for issuing metadata read-ahead instructions for on-disk inodes according to one embodiment. The process begins at 535 by determining whether the on-disk inode numbers of entries in a given directory are sequential or non-sequential (e.g., listed sequentially or non-sequentially as a result of performing a directory listing). For example, in Figure 3A, the on-disk inode numbers of the entries are listed sequentially, and in Figure 3B, the on-disk inode numbers of the entries are listed non-sequentially.

If the on-disk inode numbers of the entries are listed non-sequentially, the process accesses the global inode list (e.g., the parent directory list as shown in FIG. 3C) at 540. At 545, the process identifies the parent directory node on the global inode list (e.g., using the parent directory inode number of the on-disk inode). At 550, the process retrieves the inode list associated with the directory in question (either from disk 150 or from memory, since inode lists may be stored and maintained in memory during the listing process) and issues metadata read-ahead commands for the on-disk inodes on the inode list at 555.

On the other hand, if the on-disk inode numbers of the entries are listed sequentially, the process accesses the global inode list at 560 and identifies the in-memory inode of the parent directory of the accessed file on the global inode list at 565 (e.g., using the parent directory number of the on-disk inode). At 570, the process verifies that the directory has the sequential flag set and issues metadata read-ahead instructions at 575 for the remaining on-disk inodes listed in the directory in question. At 580, the process determines whether there is another access of the on-disk inode(s). If there is another access of the on-disk inode(s), the process loops back to 535. If not, the process terminates.

It will be appreciated that the processes illustrated in flowchart 500A of FIG. 5A and flowchart 500B of FIG. 5B are examples of using a parent directory list to track the access pattern(s) of on-disk inodes when a directory is involved. As previously described, an application may perform a listing of one or more directories to determine whether the on-disk inodes in a given directory are listed sequentially or non-sequentially. Because directories are typically stored on disk (e.g., disk 150), determining the data and/or file structure of a directory every time a file is accessed in the given directory may consume significant computing resources. However, because both the access pattern tracker 225 and the parent directory list are part of memory 115, and because the parent directory list holds listings of the data and/or file structures of multiple directories, the access pattern tracker 225 may simply use the parent directory list to determine whether the in-core inodes of a given directory are sequential or non-sequential without accessing disk 150 every time a file in the given directory is accessed.

Figure 6A is a flow chart 600A illustrating a process for handling input/output (I/O) operations, according to one embodiment. The process begins by detecting an I/O operation issued to a metadata chunk associated with an on-disk inode (e.g., a metadata unit in structural file 160) at 605. At 610, the process determines whether an I/O operation is detected. If an I/O operation is not detected, the process returns to 605. However, if an I/O operation is detected, the process intercepts a command (or request) to access and/or read the on-disk inode(s) at 615.

At 620, the process accesses the metadata read ahead value of the metadata read ahead operation and analyzes it by comparing the (total issued) metadata read ahead value with the total number of metadata chunks to read ahead at 625. At 630, the process waits for the I/O operation to complete and issues an asynchronous metadata read ahead instruction (e.g., using metadata read ahead generator 240) at 635. At 640, the process determines whether there is another I/O operation. If there is another I/O operation, the process loops to 605. If not, the process ends.

Figure 6B is a flow chart illustrating a process for handling I/O operations related to prefetching an inode, according to one embodiment. The process begins by determining whether a given I/O operation is complete, at 645. If the I/O operation is not complete, the process updates the chunk total, at 650 (e.g., the total number of metadata chunks to read ahead, or "N"), and proceeds to 625 (Figure 6A). On the other hand, if the I/O operation is complete, the process creates a queue, at 660 (e.g., a separate thread), to issue a metadata read ahead, at 665, that includes the remaining chunks of metadata not included in the asynchronous metadata read ahead instruction (e.g., of Figure 6A). At 670, the process determines whether there is another command to be intercepted (e.g., a request to read the on-disk inode(s)). If there is another command to be intercepted, the process returns to 615 (in Figure 6A). If not, the process ends.

It will be appreciated that the processes illustrated in flowchart 600A of FIG. 6A and flowchart 600B of FIG. 6B can be used to identify and prefetch on-disk inodes that are part of various heterogeneous chunks of metadata by comparing issued metadata read-ahead values to chunk totals. Because all or part of the inode list can be prefetched into memory during the directory listing process, on-disk inodes that are candidates for metadata read-ahead instructions can be identified when such on-disk inodes are not accessed sequentially. It will also be appreciated that metadata read-ahead detection and issuance of asynchronous metadata read-ahead instructions are performed in the context of a blocking thread, while the original I/O operation waits to complete in the background. These methods reduce the overhead of inode access pattern detection on system performance and also avoid the creation and scheduling of a separate thread, which can delay the availability of blocks for subsequent reads.

Figure 7A is a flow chart illustrating a process for handling on-disk inode accesses and adding directory entries to a global inode list according to a particular embodiment. The process begins at 705 by determining whether there is an on-disk inode access(s) (e.g., a read command/request for on-disk inode(s) caused by one or more I/O operations). If there is no on-disk inode(s) access, the process loops back to 705. However, if there is an on-disk inode(s) access, the process identifies the directory associated with the on-disk inode(s) at 710 (e.g., using the parent directory inode number). At 715, the process accesses the global inode list (e.g., the global inode list 215 and/or the parent directory list).

At 720, the process determines whether the directory is on the global inode list (e.g., whether the inode's parent directory inode number is on the global inode list). If the directory is not on the global inode list, the process adds the directory to the global inode list (e.g., by adding an entry for the inode's parent directory inode number to the global inode list) at 725. On the other hand, if the directory is on the global inode list, the process verifies that the sequential flag is set for the directory at 730 and issues a metadata read-ahead instruction (e.g., listed in the directory (or part of the directory)) at 735. At 740, the process determines whether there is another access of the on-disk inode(s). If there is another access, the process loops back to 705. Otherwise, the process ends.

Figure 7B is a flow chart illustrating a process for handling a request to access an on-disk inode, according to one embodiment. The process begins by detecting an I/O operation, at 745. At 750, the process intercepts a command (or request) to access (or read) an on-disk inode(s). At 755, the process determines whether the on-disk inode access pattern (e.g., detected based on chunk access and sequential or non-sequential access, among other methods) triggers, causes, or results in metadata read-ahead for the on-disk inode(s). If the on-disk inode access pattern (e.g., based on chunk access, sequential access, or non-sequential access), does not trigger metadata read-ahead, at 760, the process waits for the I/O operation to complete. Note that an example process for waiting for an I/O operation to complete is shown in flow chart 600B of Figure 6B.

On the other hand, if the on-disk inode access pattern does trigger a metadata read ahead, the process determines at 765 whether the chunk total (e.g., the total number of on-disk inode metadata chunks to read ahead, or "N") is less than or equal to the metadata read ahead value (e.g., the issued metadata read ahead value 280 or the total issued metadata read ahead value). If the chunk total is greater than or equal to the metadata read ahead value, the process waits at 760 for the I/O operation to complete. On the other hand, if the chunk total is less than or equal to the metadata read ahead value, the process issues the next chunk of asynchronous metadata read ahead at 770 and determines at 775 whether the I/O operation is complete. If the I/O operation is not complete, the process increments a counter (e.g., for issued metadata read aheads) at 780 and loops back to 765. On the other hand, if the I/O operation is complete, the process spawns a separate thread at 785 to issue the remaining chunks of asynchronous metadata read ahead. At 790, the process determines whether another I/O operation exists. If another I/O operation exists, the process loops back to 745. If not, the process ends.

Typically, when an I/O operation is blocked, the thread does not progress further. It will be appreciated that the inode access pattern detection and metadata read-ahead generation methods, systems and processes execute in the context of a blocked thread (and wait for the original I/O to complete in the background), reducing the inode access pattern detection overhead on system performance. Additionally, allowing the original I/O operation to complete can also avoid the cost of creating and scheduling a separate thread (which can delay the availability of the data block to a subsequent read operation).

It should also be noted that other data structures, such as attributes, may be associated with the nodes. The methods, systems, and processes relating to inode access pattern detection and issuing metadata read ahead instructions described herein may pre-populate these (other) data structures in memory and may asynchronously initialize various inode locks. Thus, it will be appreciated that the methods, systems, and processes described herein are capable of tracking access patterns of inodes based on chunk access, sequential access, and non-sequential access, among other capabilities, and may issue read ahead instructions for inodes, among other capabilities.
Example computing environment

8 is a block diagram of a computing system 800 illustrating how an access pattern tracker and metadata read-ahead generator may be implemented in software, according to one embodiment. Computing system 800 broadly represents any single or multi-processor computing device or system capable of executing computer-readable instructions. Examples of computing system 800 include, but are not limited to, any one or more of a variety of devices, including workstations, personal computers, laptops, client-side terminals, servers, distributed computing systems, portable devices (e.g., personal digital assistants and cell phones), network appliances, storage controllers (e.g., array controllers, tape drive controllers, or hard disk controllers), and the like. In its most basic configuration, computing system 800 may include at least one processor 110 and memory 115. By executing the software implementing computing device 105, computing system 800 becomes a dedicated computing device configured to track access pattern(s) to inodes and issue read-ahead instructions to inodes.

Processor 110 generally represents any type or form of processing unit capable of processing data or interpreting and executing instructions. In certain embodiments, processor 110 may receive instructions from a software application or module. These instructions may cause processor 110 to perform one or more functions of the embodiments described and/or illustrated herein. For example, processor 110 may perform and/or be a means for performing all or a portion of the operations described herein. Processor 110 may also perform and/or be a means for performing any other operations, methods, and processes described or illustrated herein.

Memory 115 generally represents any type or form of volatile or non-volatile storage device or medium capable of storing data and/or other computer-readable instructions. Examples include, but are not limited to, random access memory (RAM), read only memory (ROM), flash memory, or any other suitable memory device. Although not required, in certain embodiments, computing system 800 may include both volatile memory units and non-volatile storage devices. In one embodiment, program instructions implementing an access pattern tracker and a metadata read-ahead generator may be loaded into memory 115.

In certain embodiments, the computing system 800 may also include one or more components or elements in addition to the processor 110 and/or memory 115. For example, as shown in FIG. 8, the computing system 800 may include a memory controller 820, an input/output (I/O) controller 835, and a communication interface 845, each of which may be interconnected via a communication infrastructure 805. The communication infrastructure 805 generally represents any type or form of infrastructure capable of facilitating communication between one or more components of a computing device. Examples of the communication infrastructure 805 include, but are not limited to, a communication bus (such as an Industry Standard Architecture (ISA), Peripheral Component Interconnect (PCI), PCI express (PCIe), or similar bus), and a network.

Memory controller 820 generally represents any type or form of device capable of manipulating memory or data or controlling communication between one or more components of computing system 800. In particular embodiments, memory controller 820 may control communication between processor 110, memory 115, and I/O controller 835 via communication infrastructure 805. In particular embodiments, memory controller 820 may perform and/or be a means for performing one or more operations or functions described or illustrated herein, either alone or in combination with other elements.

I/O controller 835 generally represents any type or form of module capable of coordinating and/or controlling the input and output functions of one or more computing devices, such as computing device 105. For example, in certain embodiments, I/O controller 835 may control or facilitate the transfer of data between one or more elements of computing system 800, such as processor 110, memory 115, communications interface 845, display adapter 815, input interface 825, and/or storage interface 840.

Communication interface 845 broadly represents any type or form of communication device or adapter capable of facilitating communication between computing system 800 and one or more other devices. Communication interface 845 may facilitate communication between computing system 800 and a private or public network including additional computing systems. Examples of communication interface 845 include, but are not limited to, a wired network interface (such as a network interface card), a wireless network interface (such as a wireless network interface card), a modem, and any other suitable interface. Communication interface 845 may provide a direct connection to a remote server via a direct link to a network such as the Internet, or may provide such a connection indirectly, for example, through a local area network (e.g., an Ethernet network), a personal area network, a telephone or cable network, a cellular phone connection, a satellite data connection, or any other suitable connection.

Communications interface 845 may also represent a host adapter configured to facilitate communication between computing system 800 and one or more additional networks or storage devices over an external bus or communication channel. Examples of host adapters include, but are not limited to, Small Computer System Interface (SCSI) host adapters, Universal Serial Bus (USB) host adapters, Electrical and Electronics Engineers (IEEE) 1394 host adapters, Serial Advanced Technology Attachment (SATA), Serial Attached SCSI (SAS), and external SATA (eSATA) host adapters, Advanced Technology Attachment (ATA), and Parallel ATA (PATA) host adapters, Fibre Channel interface adapters, Ethernet adapters, and the like. Communications interface 845 may also enable computing system 800 to participate in distributed or remote computing (e.g., by sending instructions to and receiving instructions from remote devices for execution).

As shown in FIG. 8, the computing system 800 may also include at least one display device 810 connected to the communications infrastructure 805 via a display adapter 815. The display device 810 generally represents any type or form of device capable of visually displaying information transferred by the display adapter 815. Similarly, the display adapter 815 generally represents any type or form of device configured to transfer graphics, text, and other data from the communications infrastructure 805 (or from a frame buffer, as known in the art) for display on the display device 810. The computing system 800 may also include at least one input device 830 connected to the communications infrastructure 805 via an input interface 825. The input device 830 generally represents any type or form of input device capable of providing input generated by either a computer or a human to the computing system 800. Examples of the input device 830 include a keyboard, a pointing device, a voice recognition device, or any other input device.

The computing system 800 may also include a storage device 850 (e.g., disk 150) coupled to the communications infrastructure 805 via a storage interface 840. The storage device 850 generally represents any type or form of storage device or medium capable of storing data and/or other computer-readable instructions. For example, the storage device 850 may include a magnetic disk drive (e.g., a so-called hard drive), a floppy disk drive, a magnetic tape drive, an optical disk drive, a flash drive, etc. The storage interface 840 generally represents any type or form of interface or device for transferring and/or transmitting data between the storage device 850 and other components of the computing system 800. The storage device 850 may be configured to read from and/or write to a removable storage unit configured to store computer software, data, or other computer-readable information. Examples of suitable removable storage units include, but are not limited to, floppy disks, magnetic tapes, optical disks, flash memory devices, etc. Storage device 850 may also include other similar structures or devices for allowing computer software, data, or other computer-readable instructions to be loaded into computing system 800. For example, storage device 850 may be configured to read and write software, data, or other computer-readable information. Storage device 850 may also be part of computing system 800 or may be a separate device accessed by another interface system.

Many other devices or subsystems may be connected to the computing system 800. Conversely, not all of the components and devices shown in FIG. 8 need to be present to practice the embodiments described and/or illustrated herein. The devices and subsystems described above may also be interconnected in a manner different from that shown in FIG. 8. The computing system 800 may also employ any number of software, firmware, and/or hardware configurations. For example, one or more of the embodiments disclosed herein may be coded as a computer program (also referred to as computer software, software application, computer readable instructions, or computer control logic) on a computer-readable storage medium. Examples of computer-readable storage media include magnetic storage media (e.g., hard disk drives and floppy disks), optical storage media (e.g., CD- or DVD-ROM), electronic storage media (e.g., solid-state drives and flash media), and the like. Such computer programs may also be transferred to the computing system 800 for storage in memory or on a carrier medium via a network such as the Internet.

A computer readable medium containing a computer program may be loaded into the computing system 800. All or a portion of the computer program stored on the computer readable medium may then be stored in various portions of the memory 860 and/or the storage device 850. When executed by the processor 110, the computer program loaded into the computing system 800 may cause the processor 110 to perform and/or may be a means for performing one or more of the functions of the embodiments described and/or illustrated herein. Additionally or alternatively, one or more of the exemplary embodiments described and/or illustrated herein may be implemented in firmware and/or hardware. For example, the computing system 800 may be configured as an application specific integrated circuit (ASIC) adapted to perform one or more of the embodiments disclosed herein.
Networking environment example

9 is a block diagram of a networked system 900 illustrating how various devices may communicate over a network, according to one embodiment of the present disclosure. In certain embodiments, network-attached storage (NAS) devices may be configured to communicate with computing device 105 and storage system 145 using various protocols, such as Network File System (NFS), Server Message Block (SMB), or Common Internet File System (CIFS).

Network 185 generally represents any type or form of computer network or architecture that can facilitate communication between computing device 105 and storage system 145. In certain embodiments, a communication interface such as communication interface 845 of FIG. 8 may be used to provide connectivity between computing node 105, storage system 145, and network 155. It should be noted that the embodiments described and/or illustrated herein are not limited to the Internet or any particular network-based environment. For example, network 185 may be a storage area network (SAN). Computing device 105 and storage system 145 may be integrated or separated. If separated, for example, computing device 105 and storage system 145 may be coupled by a local connection (e.g., using Bluetooth, Peripheral Component Interconnect (PCI), Small Computer System Interface (SCSI), etc.) or via one or more networks such as the Internet, a LAN, or a SAN.

In one embodiment, all or a portion of one or more of the disclosed embodiments may be coded as a computer program and loaded onto and executed by the computing device 105, the inode access pattern tracking and metadata read ahead command issuing system 910, the inode access pattern tracking system 940 and/or the metadata read ahead command generating system 950. All or a portion of one or more of the embodiments disclosed herein may also be coded as a computer program and stored on the computing device 105, the inode access pattern tracking and metadata read ahead command issuing system 910 and/or the inode access pattern tracking system 940 and distributed over the network 185.

In some examples, all or a portion of computing device 105 may represent part of a cloud computing or network-based environment. A cloud computing environment may provide various services and applications over the Internet. These cloud-based services (e.g., software as a service, platform as a service, infrastructure as a service, etc.) may be accessible through a web browser or other remote interface. Various functionality described herein may be provided through a remote desktop environment or any other cloud-based computing environment.

In addition, one or more of the components described herein may convert data, physical devices, and/or representations of physical devices from one form to another. For example, the computing device 105 and/or the inode access pattern tracking and metadata read-ahead issuing system 910 may convert the behavior of the computing device 105 to cause the computing device 105 and/or the inode access pattern tracking and/or metadata read-ahead instruction issuing system 910 to track the access pattern(s) of the inode and issue read-ahead instructions.

Although the present disclosure has been described in connection with certain embodiments, the present disclosure is not intended to be limited to the particular form set forth herein. On the contrary, it is intended to cover all alternatives, modifications, and equivalents that may reasonably be included within the scope of the present disclosure as defined by the appended claims.

Claims (40)

determining a location of a metadata unit within a metadata storage area,
determining that the metadata storage area is in a non-volatile storage unit;
determining another location within the metadata storage area,
determining that the other location corresponds to a current metadata read operation;
determining whether a metadata read ahead operation can be performed using the location and the another location of the metadata unit;
in response to determining that the metadata read ahead operation may be performed, issuing the metadata read ahead operation. the metadata storage area includes a plurality of on-disk inodes;
the on-disk inode contains the metadata unit;
the on-disk inode is part of a structural file;
The method of claim 1 , wherein the configuration file is stored in the non-volatile storage unit. Creating an in-core inode,
creating an in-core inode corresponding to the structural file;
storing the location of the metadata unit within the in-core inode;
the metadata unit is the last read metadata chunk,
3. The method of claim 2, further comprising: storing, the location of the metadata unit identifying an ending offset of the metadata unit. determining whether the metadata read ahead operation can be performed,
accessing the ending offset of the metadata unit;
and determining whether the other location is adjacent to the ending offset. Issuing the metadata read ahead operation
updating the ending offset by replacing the ending offset with another ending offset of another metadata unit read by the metadata read ahead operation;
The method of claim 3 , wherein the other metadata unit is another last-read metadata chunk. The method of claim 3, further comprising updating the ending offset by replacing the ending offset with the ending offset of a current metadata read operation if the other location is not adjacent to the ending offset. Intercepting a command to read one or more on-disk inodes, comprising:
the one or more on-disk inodes are a portion of the plurality of on-disk inodes;
the interception is performed in response to an input/output (I/O) operation;
Intercepting the I/O operation resulting in the command;
analyzing metadata look-ahead values issued in the metadata look-ahead operation,
analyzing, the analyzing including comparing the issued metadata readahead value to a chunk total in the command;
waiting for the I/O operation to complete if the analysis indicates that the I/O operation will complete;
The method of claim 2 , further comprising: if the analysis indicates that an asynchronous metadata read ahead instruction can be issued, issuing an asynchronous metadata read ahead instruction. determining whether the I/O operation is complete;
creating a queue if the I/O operation is completed;
the queue includes one or more remaining chunks of metadata for the chunk total;
generating the one or more remaining chunks of metadata not included in the asynchronous metadata read ahead instructions;
8. The method of claim 7, further comprising: if the I/O operation is not complete, updating the chunk total in the metadata read ahead operation. A non-transitory computer readable storage medium containing program instructions, the program instructions comprising:
determining a location of a metadata unit within a metadata storage area,
determining that the metadata storage area is in a non-volatile storage unit;
determining another location within the metadata storage area,
determining that the other location corresponds to a current metadata read operation;
determining whether a metadata read ahead operation can be performed using the location and the another location of the metadata unit;
in response to determining that the metadata read ahead operation may be performed, issuing the metadata read ahead operation. the metadata storage area includes a plurality of on-disk inodes;
the on-disk inode contains the metadata unit;
the on-disk inode is part of a structural file;
The non-transitory computer readable storage medium of claim 9 , wherein the configuration file is stored in the non-volatile storage unit. creating an in-core inode,
creating an in-core inode corresponding to the structural file;
storing the location of the metadata unit within the in-core inode;
the metadata unit is the last read metadata chunk,
11. The non-transitory computer-readable storage medium of claim 10, further comprising: storing, the location of the metadata unit identifying an ending offset of the metadata unit. determining whether the metadata read ahead operation can be performed,
accessing the ending offset of the metadata unit;
and determining whether the another location is adjacent to the ending offset. Issuing the metadata read ahead operation
updating the ending offset by replacing the ending offset with another ending offset of another metadata unit read by the metadata read ahead operation if the other location is adjacent to the ending offset;
updating, wherein the other metadata unit is another last-read metadata chunk;
and updating the ending offset by replacing the ending offset with an ending offset of a current metadata read operation if the other location is not adjacent to the ending offset. Intercepting a command to read one or more on-disk inodes, comprising:
the one or more on-disk inodes are a portion of the plurality of on-disk inodes;
the interception is performed in response to an input/output (I/O) operation;
Intercepting the I/O operation resulting in the command;
analyzing metadata look-ahead values issued in the metadata look-ahead operation,
analyzing, the analyzing including comparing the issued metadata readahead value to a chunk total in the command;
waiting for the I/O operation to complete if the analysis indicates that the I/O operation will complete;
issuing an asynchronous metadata prefetch instruction if the analysis indicates that an asynchronous metadata prefetch instruction may be issued; and
determining whether the I/O operation is complete;
creating a queue if the I/O operation is completed;
the queue includes one or more remaining chunks of metadata for the chunk total;
generating the one or more remaining chunks of metadata not included in the asynchronous metadata read ahead instructions;
11. The non-transitory computer-readable storage medium of claim 10, further comprising: if the I/O operation is not complete, updating the chunk total in the metadata read ahead operation. one or more processors;
a memory coupled to the one or more processors, the memory storing program instructions executable by the one or more processors, the program instructions comprising:
determining a location of a metadata unit within a metadata storage area,
determining that the metadata storage area is in a non-volatile storage unit;
determining another location within the metadata storage area,
determining that the other location corresponds to a current metadata read operation;
determining whether a metadata read ahead operation can be performed using the location and the another location of the metadata unit;
in response to determining that the metadata read ahead operation may be performed, issuing the metadata read ahead operation. the metadata storage area includes a plurality of on-disk inodes;
the on-disk inode contains the metadata unit;
the on-disk inode is part of a structural file;
The system of claim 15 , wherein the configuration file is stored in the non-volatile storage unit. creating an in-core inode,
creating an in-core inode corresponding to the structural file;
storing the location of the metadata unit within the in-core inode;
the metadata unit is the last read metadata chunk,
20. The system of claim 16, further comprising: storing the location of the metadata unit identifying an ending offset of the metadata unit. determining whether the metadata read ahead operation can be performed,
accessing the ending offset of the metadata unit;
and determining whether the another location is adjacent to the ending offset. Issuing the metadata read ahead operation
updating the ending offset by replacing the ending offset with another ending offset of another metadata unit read by the metadata read ahead operation if the other location is adjacent to the ending offset;
updating, wherein the other metadata unit is another last-read metadata chunk;
and updating the ending offset by replacing the ending offset with an ending offset of a current metadata read operation if the other location is not adjacent to the ending offset. Intercepting a command to read one or more on-disk inodes, comprising:
the one or more on-disk inodes are a portion of the plurality of on-disk inodes;
the interception is performed in response to an input/output (I/O) operation;
Intercepting the I/O operation resulting in the command;
analyzing metadata look-ahead values issued in the metadata look-ahead operation,
analyzing, the analyzing including comparing the issued metadata readahead value to a chunk total in the command;
waiting for the I/O operation to complete if the analysis indicates that the I/O operation will complete;
issuing an asynchronous metadata prefetch instruction if the analysis indicates that an asynchronous metadata prefetch instruction may be issued; and
determining whether the I/O operation is complete;
creating a queue if the I/O operation is completed;
the queue includes one or more remaining chunks of metadata for the chunk total;
generating the one or more remaining chunks of metadata not included in the asynchronous metadata read ahead instructions;
17. The system of claim 16, further comprising: if the I/O operation is not complete, updating the chunk total in the metadata read ahead operation. Accessing the inode;
determining a directory of the inode;
determining whether an entry for said directory exists in a global inode list;
if the entry exists in the global inode list, determining whether the file structure of the directory is sequential or non-sequential;
adding a new entry for the directory into the global inode list if the entry does not exist in the global inode list. Determining whether the directory exists in a global inode list includes:
22. The method of claim 21, comprising searching the global inode list for the entry. if the file structure of the directory is sequential, determining whether the directory includes a sequential flag;
22. The method of claim 21, further comprising: issuing a metadata read ahead operation to one or more inodes of a plurality of inodes on an inode list if the directory includes the sequential flag. retrieving the inode list of the plurality of inodes of the directory if the file structure of the parent directory is non-sequential;
24. The method of claim 23, further comprising: issuing the metadata read ahead operation to the one or more inodes on the inode list. Intercepting a command to read one or more inodes, comprising:
the one or more inodes are a portion of the plurality of inodes;
the interception is performed in response to an input/output (I/O) operation;
25. The method of claim 24, further comprising intercepting the I/O operation that results in the command. analyzing metadata look-ahead values issued in the metadata look-ahead operation,
analyzing, the analyzing including comparing the issued metadata readahead value to a chunk total in the command;
waiting for the I/O operation to complete if the analysis indicates that the I/O operation will complete;
26. The method of claim 25, further comprising: if the analysis indicates that an asynchronous metadata read ahead instruction can be issued, issuing an asynchronous metadata read ahead instruction. determining whether the I/O operation is complete;
creating a queue if the I/O operation is completed;
the queue includes one or more remaining chunks of metadata for the chunk total;
generating the one or more remaining chunks of metadata not included in the asynchronous metadata read ahead instructions;
27. The method of claim 26, further comprising: if the I/O operation is not complete, updating the chunk total in the metadata read ahead operation. The method of claim 21, wherein the inode is an on-disk inode. A non-transitory computer readable storage medium comprising program instructions, the program instructions comprising:
Accessing the inode;
determining a directory of the inode;
determining whether an entry for said directory exists in a global inode list;
if the entry exists in the global inode list, determining whether the file structure of the directory is sequential or non-sequential;
and adding a new entry for the directory into the global inode list if the entry does not exist in the global inode list. Determining whether the directory exists in a global inode list
searching the global inode list for the entry;
30. The non-transitory computer-readable storage medium of claim 29, wherein the inode is an on-disk inode. if the file structure of the directory is sequential, determining whether the directory includes a sequential flag;
issuing a metadata read ahead operation to one or more inodes in the directory if the directory includes the sequential flag;
retrieving the inode list of the plurality of inodes of the directory if the file structure of the parent directory is non-sequential;
30. The non-transitory computer-readable storage medium of claim 29, further comprising: issuing the metadata read ahead operation for the one or more inodes on the inode list. Intercepting a command to read one or more inodes, comprising:
the one or more inodes are a portion of the plurality of inodes;
the interception is performed in response to an input/output (I/O) operation;
32. The non-transitory computer-readable storage medium of claim 31, further comprising intercepting the I/O operation resulting in the command. analyzing metadata look-ahead values issued in the metadata look-ahead operation,
analyzing, the analyzing including comparing the issued metadata readahead value to a chunk total in the command;
waiting for the I/O operation to complete if the analysis indicates that the I/O operation will complete;
33. The non-transitory computer-readable storage medium of claim 32, further comprising: if the analysis indicates that an asynchronous metadata read ahead instruction may be issued, issuing an asynchronous metadata read ahead instruction. determining whether the I/O operation is complete;
creating a queue if the I/O operation is completed;
the queue includes one or more remaining chunks of metadata for the chunk total;
generating the one or more remaining chunks of metadata not included in the asynchronous metadata read ahead instructions;
34. The non-transitory computer-readable storage medium of claim 33, further comprising: if the I/O operation is not complete, updating the chunk total in the metadata read ahead operation. one or more processors;
a memory coupled to the one or more processors, the memory storing program instructions executable by the one or more processors, the program instructions comprising:
Accessing the inode;
determining a directory of the inode;
determining whether an entry for said directory exists in a global inode list;
if the entry exists in the global inode list, determining whether the file structure of the directory is sequential or non-sequential;
adding a new entry for the directory into the global inode list if the entry does not exist in the global inode list. Determining whether the directory exists in a global inode list
searching the global inode list for the entry;
36. The system of claim 35, wherein the inode is an on-disk inode. if the file structure of the directory is sequential, determining whether the directory includes a sequential flag;
issuing a metadata read ahead operation to one or more inodes in the directory if the directory includes the sequential flag;
retrieving the inode list of the plurality of inodes of the directory if the file structure of the parent directory is non-sequential;
36. The system of claim 35, further comprising: issuing the metadata read ahead operation for the one or more inodes on the inode list. Intercepting a command to read one or more inodes, comprising:
the one or more inodes are a portion of the plurality of inodes;
the interception is performed in response to an input/output (I/O) operation;
40. The system of claim 37, further comprising intercepting the I/O operation effecting the command. analyzing metadata look-ahead values issued in the metadata look-ahead operation,
analyzing, the analyzing including comparing the issued metadata readahead value to a chunk total in the command;
waiting for the I/O operation to complete if the analysis indicates that the I/O operation will complete;
40. The system of claim 38, further comprising: if the analysis indicates that an asynchronous metadata read ahead instruction can be issued, issuing an asynchronous metadata read ahead instruction. determining whether the I/O operation is complete;
creating a queue if the I/O operation is completed;
the queue includes one or more remaining chunks of metadata for the chunk total;
generating the one or more remaining chunks of metadata not included in the asynchronous metadata read ahead instructions;
40. The method of claim 39, further comprising: if the I/O operation is not complete, updating the chunk total in the metadata read ahead operation.

Images