Computer file system with path lookup tables

A namespace is provided in a file system that employs logical volumes. With the namespace, the file system can withstand data storage units going offline without compromising accessibility of the files in the data storage units that remain online. The files in the online data storage units remain accessible through the use of path lookup tables that are stored in the online data storage units.

BACKGROUND OF THE INVENTION

File systems typically organize objects as files in a hierarchy of directories, and an inode is assigned to each of the files and to each of the directories. A file inode includes references to data blocks of user data. A directory inode includes references to data blocks that contain filenames, which may correspond to either a directory or a file, and inode numbers corresponding to the filenames.

Applications access files using fully qualified paths to the files and a namespace indicates the paths that lead to valid inodes corresponding to such files on the file system. As such, the availability of the inodes and hence user data on the file system is a direct function of availability of the namespace, since files are accessed using their path names.

The availability of inodes becomes difficult to ensure when a file system employs a logical volume manager. A logical volume manager is a software or firmware component that organizes a plurality of data storage units into an ordered set of physical extents called a logical volume. The logical volume is available in the form of a logical device with a contiguous address space on which a file system is laid out. The logical volume enables useful enterprise features such as the ability to hot-replace data storage units without changing the file system address space, hot-extend logical volume length by adding new data storage units, provide software redundant array of inexpensive disks (RAID) availability features, implement data mirroring and replication over multiple data storage units, and the like.

When a file system uses logical volumes, the file system no longer controls physical placement of inodes on data storage units. The file system only controls inode layout in the logical volume address space. The mapping of inodes in the logical volume address space to data storage units is done outside the file system's control by the logical volume manager such as based on availability. Consequently, inodes may be scattered over data storage units with different inodes residing in different data storage units. As one example, a file represented by the path “/root/dir1/dir2/example.doc” may have inodes for the directories (directory inodes) and the file (file inode) residing in different data storage units.

Thus, in a file system that employs logical volumes, availability of the namespace and file objects referenced by paths is contingent on availability of all the data storage units that comprise a logical volume. If one or more of the data storage units comprising a logical volume go offline, a file may not be accessible by the file system, because the inode corresponding to one or more of the file's path components, e.g., /dir1 or /dir2, may not be available.

SUMMARY OF THE INVENTION

A file system according to an embodiment of the invention is able to access files of online data storage units using a path lookup table that is stored in each of the online data storage units. The path lookup table may be used with existing distributed, clustered, or local file systems irrespective of how the file system internally implements and lays out its file hierarchy. Alternatively, the path lookup table may be used as a stand-alone solution for addressing files in a hierarchy of a file system.

A method of generating a hierarchical file system, according to an embodiment of the invention, includes the steps of creating a first table of path entries that specify paths for a first set of file objects that are stored in a first data storage unit, storing the first table in the first data storage unit, creating a second table of path entries that specify paths for a second set of file objects that are stored in a second data storage unit, and storing the second table in the second data storage unit.

A method of determining an object identifier of a file object stored in a hierarchical file system having a first set of file objects and a first path lookup table stored in a first data storage unit and a second set of file objects and a second path lookup table stored in a second data storage unit, according to an embodiment of the invention, includes the steps of determining a path entry corresponding to a file object from one of the first and second path lookup tables, and reading an object identifier from the path entry corresponding to said file object.

DETAILED DESCRIPTION

FIG. 1Ais a block diagram illustrating a data center100configured to implement one or more embodiments of the invention. Several computers are configured as computer systems105to provide a large-scale data center100. In a typical enterprise level system, underlying data storage systems may adopt the use of storage area networks (SANs). As is conventionally well appreciated, SANs provide a number of technical capabilities and operation benefits, fundamentally including virtualization of data storage devices, e.g., storage systems110, redundancy of physical devices with transparent fault-tolerant fail-over and fail-safe controls, geographically distributed and replicated storage, centralized oversight, and storage configuration management decoupled from client-centric computer systems management. Although one or more embodiments of the invention are described in the context of a data center, one or more embodiments of the invention may be used to provide a hierarchical namespace for distributed, clustered, or local file systems.

Architecturally, a SAN storage subsystem is characteristically implemented as a large array of Small Computer System Interface (SCSI) protocol-based storage devices, e.g., computer systems105, redundant switches112, and storage systems110. The SAN can be implemented using any of a variety of technologies, though typically using Fibre Channel or iSCSI technology. These technologies allow construction of a redundant, failover and multipath capable interconnection network, using for example redundant switches112and network connections, that in turn, ensure overall reliability. In a typical implementation, additional data management features are implemented through logical volume managers and data access layers executed in a server tier of computer systems105. Client computer systems are constrained to mounting and accessing data storage volumes through the server tier and thereby effectively inherit the logical unit management functions implemented by the logical volume managers of the server tier. Logical volume managers, however, can be and frequently are implemented at multiple levels including in client computer systems.

A storage system manager118is executed on storage systems110to implement a virtualization of the physical, typically disk drive-based storage units. Storage system manager118is thus able to aggregate disk drives/physical storage units into one or more logical storage containers, e.g., data storage units125. This virtualization of data storage units125allows a more efficient utilization of the underlying physical storage through logical aggregation into a contiguous container storage space according to various policies. These data storage units125can be allocated by storage system manager118as externally visible and accessible data storage units with unique identifiers. Storage system manager118performs real to virtual translations necessary to support the presentation of data storage units125to computer systems105for use as, in effect, standard SCSI-based storage. The logical storage containers may be dynamically reconfigured and expanded depending on demand patterns without materially affecting the ongoing use of a particular data storage unit125by computer systems105. As a result, the presentation of data storage units125can be preserved even while maintenance is performed on an array of physical storage units.

FIG. 1Bis a block diagram illustrating a system architecture130that is configured to implement one or more embodiments of the invention. As generally illustrated inFIGS. 1A and 1B, a typical system architecture130implements a logical volume manager145on a computer system105, that is, at a system tier, above data storage units125, and, as a software layer, beneath a filesystem140. By execution of logical volume manager145, filesystem140is presented with a data storage view represented by one or more discrete data storage volumes150, each of which is capable of containing a complete filesystem data structure. The specific form and format of the filesystem data structure is determined by the particular filesystem140employed. Any of the New Technology filesystem (NTFS), the Unix filesystem (UFS), the VMware Virtual Machine filesystem (VMFS), and the Linux third extended filesystem (ext3FS) may be used as filesystem layer140.

Filesystem140creates and maintains an APL (alternate path lookup) table170as a data structure to provide a hierarchical namespace for data storage volumes150. Additionally, subsets of APL table170are stored on data storage units125, as described in conjunction withFIG. 2A. Any of computer systems105ofFIG. 1Amay be configured to store APL table170and restore the subsets of APL table170that are stored on data storage units125. APL table170may be used with existing distributed, clustered, or local file systems irrespective of how the file system internally implements and lays out its file hierarchy.

As is conventional for logical volume managers, each of data storage volumes150is functionally constructed by logical volume manager145from an administratively defined set of one or more data storage units125. Logical volume manager145is responsible for functionally managing and distributing data transfer operations to various data storage units125of particular target data storage volumes150. The operation of logical volume manager145, like the operation of a storage system manager118, is transparent to applications135executed directly by computer systems105or by clients of computer systems105.

Virtual Machine System

FIG. 1Cis a block diagram illustrating a virtual machine based system that is configured to implement one or more embodiments of the invention. A computer system105is constructed on a conventional, typically server-class hardware platform174, including host bus adapters (HBA)176in addition to conventional platform processor, memory, and other standard peripheral components (not separately shown). HBAs176connect to storage systems110through network connections, e.g., redundant switches112. Within the server, above HBAs176, storage access abstractions are characteristically implemented through a series of software layers, beginning with a low-level SCSI driver layer (not shown) and ending in an operating system specific filesystem layer in operating system178. The driver layer enables basic access to the target ports and data storage units125. A data access layer198may be implemented above the device driver to support multipath consolidation of data storage units125visible through HBAs176and other data access control and management functions.

Hardware platform174is used to execute a virtual machine (VMKernel) operating system178supporting a virtual machine execution space180within which virtual machines (VMs)182are executed. Virtual machine operating system178and virtual machines182may be implemented using an ESX Server virtualization product manufactured and distributed by VMware, Inc. of Palo Alto, Calif. Note that embodiments of the invention exist which do not require use of the ESX Server product and, further embodiments exist which do require use of a virtualized computer system architecture.

In summary, virtual machine operating system178provides the necessary services and support to enable concurrent execution of virtual machines182. In turn, each virtual machine182implements a virtual hardware platform184that supports the execution of a guest operating system186and one or more client application programs188. Guest operating systems186maybe instances of Microsoft Windows, Linux and Netware-based operating systems. Other guest operating systems can be used. In each instance, guest operating system186includes a native filesystem layer, typically either an NTFS or ext3FS type filesystem layer. These filesystem layers interface with virtual hardware platforms184to access, from the perspective of guest operating systems186, a data storage host bus adapter. In one embodiment, virtual hardware platforms184implement virtual HBA (host bus adapter)190that provides the appearance of the necessary system hardware support to enable execution of guest operating system186.

Filesystem calls initiated by guest operating systems186to implement filesystem-related data transfer and control operations are processed and passed through virtual HBA190to adjunct virtual machine monitor (VMM) layers192that implement the virtual system support necessary to coordinate operation with virtual machine kernel178. In particular, an HBA emulator194functionally enables the data transfer and control operations to be ultimately passed to HBAs176. The system cells that implement the data transfer and control operations are passed to a virtual machine filesystem, such as filesystem140, for coordinated implementation with respect to the ongoing operation of all of virtual machines182. That is, the native filesystems of guest operating systems186perform command and data transfer operations against virtual SCSI devices. These virtual SCSI devices are based on emulated data storage units presented to the HBA emulator194by a SCSI virtualization layer155. The virtual SCSI devices are actually maintained as files resident within the storage space managed by filesystem140. Permitted guest operating system186command and data transfer operations against the virtual SCSI devices are mapped between the virtual SCSI devices visible to guest operating systems186and the data storage volumes visible to virtual machine filesystem140. A further mapping is, in turn, performed by a virtual machine kernel-based logical volume manager162to data storage units125visible to logical volume manager162through data access layer198, including device drivers, and HBAs176.

One or more embodiments of the invention are generally applicable in computing environments where data storage volumes used by client computer systems are managed within a distributed storage system that supports typically automatic data replication operations. Accordingly, one environment for the implementation of one or more embodiments of the invention is in conventional storage area network (SAN) based data centers. From the following detailed description, however, those of ordinary skill in the art will readily understand that embodiments of the invention are not constrained to use in a particular environment, system or network architecture or by use of a particular operating system or set of data communications protocols. The following description is presented in the context of a data center application as illustrative of one embodiment of the invention for clarity of presentation and explanation.

File System Mapping

FIG. 2Ais a conceptual diagram of a block mapping between a file system200and logic volume215for the systems ofFIGS. 1A,1B, and1C, in accordance with one or more embodiments of the invention. Logical volume manager145aggregates data storage units230-0and230-1through230-N into logical volume215, with each data storage unit corresponding to a part of the logical volume, e.g., logical extents211,212, and213. Logical extents211and212through213represent a single contiguous address space. File system200is an array of file blocks,201,202,203,204,205,206,208,209, and210, where each block has a fixed size.

An APL table250(250-0and250-1through250-N) that is unique for each data storage unit230is stored and maintained for each one of data storage units230. Each APL table250stores a different portion of the entries in APL table170. Specifically, APL table250-0stores the entries of APL table170for file objects that are stored on data storage unit230-0.

FIG. 2Bis a conceptual diagram of the relationship between file system200, inodes240,245,255, and directory entries (DirEntry)243and248, in accordance with one or more embodiments of the invention. Each inode includes a pointer to one or more blocks of file system200that store file objects, e.g., directory entries or user data. For example, inode255includes a pointer to blocks201and205; inode240includes a pointer to block204; and inode245includes pointers to blocks206,209, and210. Each inode further includes inode attributes, such as a unique inode number, length (number of storage units, e.g., blocks or bytes), type, generation number, link count, and the like. The inode number may be 64 bits and is the unique number of the inode corresponding to the file object in file system200. The generation number may be 32 bits and is a monotonically increasing number that is incremented when a given file object's inode is reused for another file object. The link count indicates the number of file objects that link to the inode, such that a link count of zero indicates that the inode is no longer used and may be reused for another file object.

In general, blocks that are referenced by inodes may contain user data and/or directory entries. In the example given herein, it is assumed that blocks referenced by inodes240,245, and255are used to store directory entries, e.g., dirEntry243and248, each of which stores a filename, which corresponds to a directory, an inode number, and a generation number.

Fully qualified filesystem paths (fullpath) provide an unambiguous manner of addressing objects on a hierarchical file system from an application. For example, open(/foo/bar/baz.txt) is a request to open the file object baz.txt in a directory called bar, which in turn is stored in a directory called foo. Directory foo is a directory in the root directory “/” of the volume. Fully qualified paths to directories or file objects may be referred to as dirpath and filepath, respectively.

The inodes shown inFIG. 2Billustrate how different inodes are traversed to access the file /foo/bar/baz.txt. For illustrative purposes, it is assumed that the root directory, “/” is hardcoded as inode240, that dirEntry243corresponds to the “foo” directory, and that dirEntry248corresponds to the “bar” directory. Inode240points to block204and so the “foo” directory corresponding to dirEntry243is found somewhere in block204. DirEntry243is then read to obtain its inode number. In this example, it is assumed that the inode number corresponding to inode245is stored in dirEntry243(foo). Blocks206,209,210that are referenced by inode245are then accessed to find the “bar” directory corresponding to dirEntry248. DirEntry248is then read to obtain its inode number. In this example, it is assumed that the inode number corresponding to inode255is stored in dirEntry248(bar). Blocks201,205that are referenced by inode255are then accessed to find the file object “baz.txt.”

Referring toFIG. 2A, note that as the path is traversed, blocks are read from different data storage units230. If data storage unit230-1is unavailable, then block204cannot be read, and the path to file object baz.txt is broken, even when the data storage unit where baz.txt is stored (data storage unit230-0) is available. Similarly, if data storage unit230-N is unavailable, then block209cannot be read, and the path to file object baz.txt is broken. As described further herein, use of APL tables250prevents failures in the prefix portion of the path for baz.txt, e.g., “/”, “/foo”, or “/foo/bar,” from making baz.txt unavailable, as long as data storage unit230that stores baz.txt is available. When APL tables250are used, file objects stored on one of data storage units250can be accessed even if only that one data storage unit230is available.

Alternate Path Lookup Table

FIG. 3Ais a diagram of an APL table300, in accordance with one or more embodiments of the invention. As previously described, portions of APL table300are stored in APL tables250. APL table300is created as a data structure that is maintained by the filesystem driver directly as part of filesystem140metadata or it is maintained by a separate entity and is available to the filesystem driver through interface functions. In one embodiment of the invention, APL table300is maintained as a set of file objects on the filesystem volume that it services. APL table300is a logical array of entries, with each entry containing the following fields: length, index number, path, and OID (object identifier).

A first entry in APL table300for path /foo includes length311, index number314, and OID317. A second entry in APL table300for path /foo/bar includes length312, index number315, and OID318. A third entry in APL table300for path /foo/bar/baz.txt includes length313, index number316, and OID319. APL table300may include an entry for each file object in filesystem140or APL table300may only include entries for selected file objects or selected data storage units230.

Length is the length (in bytes) of the record (table entry). In one embodiment of the invention, this is a 32-bit field. In other embodiments of the invention, this field is not present in the entry (each APL entry is a fixed width). Index number is an integer unique among all the entries stored in APL table300. Index number is a primary key of the entry and may be a 64-bit number. Path is a fullpath to a file object, e.g., /foo, /foo/bar, /foo/bar/baz.txt, and the like. Since operating systems have an upper limit on fullpath length, say FS_MAX_PATH_LENGTH, this is a field of FS_MAX_PATH_LENGTH bytes in one embodiment. For example, on Unix-like operating systems, the upper limit on the fullpath length is 4096 bytes. In other embodiments of the invention, the fullpath length is variable length, and each tuple contains yet another field called length. For fixed length paths, the length field is optional since it is implicit.

Filesystem drivers typically manage and locate objects, e.g., file objects, symlinks, hardlinks, and the like, in memory and on disk by using binary values called object identifiers (OID). Unlike a filename or a file path which are ambiguous (the same name/path could refer to different objects at different points in time), the OID is unique per file object for the lifetime of the file system, even after said file object is removed from filesystem140. The OID typically encodes enough information for the driver to able to read/write the object from/to the logical extent211,212, or213representing data storage units230. A given object's OID is also unique across all file systems, especially for distributed and clustered file systems.

OID is OIDof(fullpath) and in some embodiments of the invention it is 28 bytes. An example OID consists of 3 values: the inode number, generation number, and UUID. The inode number may be 64 bits and is a unique number of an inode corresponding to a file object in a filesystem volume. The generation number may be 32 bits and is a monotonically increasing number that is stored in the inode. The generation number is incremented when a given file object's inode is reused for another file object. The UUID may be 128 bits and is a unique identifier for filesystem140, i.e. a file system identifier. The UUID distinguishes a given filesystem volume from other filesystem volumes visible to the computer on which the filesystem driver is running.

In some cases user data or directory entries corresponding to a file object may be stored in multiple blocks allocated to the inode of said file object and some of the blocks may be stored in different data storage units230. For example, directory entries may be stored in blocks206and209of directory inode245ofFIG. 2B, and physically stored in data storage units230-1and230-N, respectively. A DSUof(OID) command returns all of the data storage units230in which the inode attributes and data blocks of the file object corresponding to OID are stored. Therefore, when a file object is stored in a single data storage unit230, a single data storage unit identifier is returned. When a file object is stored on multiple data storage units230, multiple data storage unit identifiers are returned.

Filesystem140is augmented according to known methods to include new commands. These commands are used to create, access, and maintain APL table300. An apl_lookup(DSU, fullpath) command finds an entry in the APL table250of the specified DSU whose path field matches fullpath, and, if found, returns the OID field. For example, apl_lookup(DSU230-0, /foo/bar) returns OID318. An apl_insert(DSU, fullpath, OID) command creates a new entry in APL table300and in the APL table250of the specified DSU, sets the path and OID fields to fullpath and OID, respectively. An apl_delete(DSU, fullpath) command executes an apl_lookup(DSU, fullpath) command, and if an OID is returned, the entry is deleted from APL table300and APL table250of the specified DSU. An apl_rename command(DSU, srcfullpath, dstfullpath) executes an apl_lookup(DSU, srcfullpath) and if an OID is returned, dsfullpath is placed in the path field for the entry.

In some embodiments of the invention, APL table300is implemented as a B+ tree that is indexed by hash(DSU, fullpath). Inserting an entry in APL table300is performed by inserting an entry at a position determined by hash(DSU, fullpath). Similarly, deleting an entry from the B+ tree is performed by deleting an entry at a position determined by hash(DSU, fullpath), when the path field in the entry matches fullpath. Similarly, the DSU230specific APL table250is implemented as a B+ tree that is indexed by hash(fullpath).

The size of the path field may be reduced by storing path prefixes instead of fullpath names. The prefixes may be generated and referenced when new entries are inserted into APL table300. A path prefix is a part of a fullpath, e.g., /foo is a path prefix for /foo/bar and /foo/bar is a path prefix for /foo/bar/baz.txt. When APL table300contains the second entry (path=/foo/bar) the entry for /foo/bar/baz.txt can be represented as <i2>/baz.txt, where <i2> is the index number of the entry containing /foo/bar, i.e., index number315.

FIG. 3Bis a flow diagram of method steps for populating APL table300, in accordance with one or more embodiments of the invention. As previously described, APL table300represents the combination of APL tables250-0,250-1, . . . ,250-N. A complete APL table300may be stored on computer system105and portions of APL table300may be cached. When different components of a fullpath straddle a data storage unit230boundary, the last component of the fullpath (the tail) can be available when one or more data storage units230are unavailable by adding an entry in the APL table that is stored on the data storage unit230that stores the tail. In other words, each entry in APL table300represents a tail inode that does not rely on traversing intermediate inodes that reside on other data storage units230.

Fully populated APL table250-i for data storage unit230-i contains entries leading to all inodes that are stored on data storage unit230-i. In the illustration provided herein, APL table250-0includes an entry for inode255; APL table250-1includes an entry for inode240; and APL table250-N includes an entry for inode245. Thus, APL table250-0does not include entries for inodes240and245; APL table250-1does not include entries for inodes255and245; and APL table250-N does not include entries for inodes255and240. APL table300is highly scalable since there is only a single entry for each file object. In contrast, when mirroring is used to improve file object availability the entire contents of each data storage unit230is replicated. Furthermore, the availability of an inode on a mirrored DSU230is still dependent on the availability of other DSUs230that contain inodes making up the path prefix for said inode. Therefore, mirroring does not solve the inter-DSU dependency problems of path availability because the inode corresponding to one or more of a file's path components may not be available.

In step330filesystem140receives a fullpath that is used to populate APL table300, e.g., fullpath=/foo/bar/baz.txt. First, filesystem140determines if the path is already stored in APL table300. In step332the value of a variable called parentOID is computed according to one or more embodiments of the invention, using the apl_lookup command with the portion of the fullpath to the tail component, path_prefix_to_tail as the input to APL table300. The value of another variable called childname is set to the tail. The path_prefix_to_tail of /foo/bar/baz.txt is /foo/bar and the tail is baz.txt. In step334filesystem140determines if the lookup operation succeeded, and, if so, an entry for the fullpath exists in APL table300and filesystem140proceeds to step340. Otherwise, filesystem140proceeds to step335to check if other prefixes of the fullpath have entries in APL table300and resolves them using the conventional method if no such entries exist.

In step335the OID of the root directory is determined using the OIDof command, e.g., OIDof(“/”) and stored as parentOID. For example, OIDof(“/”) in the filesystem layout fromFIG. 2Bwill return the OID of inode240. The value of childname is determined using a next_token command to find the next component of the fullpath. For example, childname of /foo/bar/baz.txt is foo. DSUset is initialized to null. In step340DSUset is a set variable and is initialized to DSU of(parentOID), e.g., data storage unit230that stores the inode for the root directory “/” (inode240and data storage unit230-1).

In step345filesystem140determines if the childname is null, indicating that the file object specified by fullpath has been reached. When the childname is null, in step350filesystem140sets tailDSU to DSU of(parentOID). The tailDSU of the fullpath /foo/bar/baz.txt is DSU of(OIDof(baz.txt)) and the parent OID is OIDof(baz.txt). In step355the difference between DSUset and {tailDSU} is computed to determine if a data storage unit230boundary is straddled, and, if not then the difference is null, and in step365“no APL insert required” is output. If a data storage unit230boundary is straddled, then in step360an apl_insert command is executed using tailDSU, fullpath, and parentOID as inputs. The DSUset of the fullpath /foo/bar/baz.txt at step345will contain the DSUs of “/”, “foo” and “bar”, e.g. {230-1,230-N,230-0}.

If, in step345the childname is not null, then in step370filesystem140sets childOID to the result of a lookup command with the parentOID and childname as inputs. POSIX-like file systems support a standard set of operations. In the most general case, these operations work on file objects specified by using fullpath. Internally, the operations rely on resolving paths to OIDs. The most common operations implemented by the file system driver that are relevant to embodiments of the invention are: lookup, pathwalk, create, remove, and rename. The inputs to the lookup command are a directory OID and a filename. The OID of the file object of “filename” is returned if it exists as a child of the directory referenced by the directory OID. For example, lookup(OIDof(“/”), foo) returns the OID of foo by reading the directory entries of the root directory “/” and returning the OID of foo.

In step375filesystem140determines if the lookup operation succeeded, and, if so, in step395parentOID is set to childOID and childname is set to the next component in fullpath, the next component being bar. Filesystem140then returns to step345to see if the last component in the path has been reached. In step375, filesystem140determines that the lookup operation failed if the data storage unit230that stores the directory entry for foo is unavailable. When childOID is not a valid directory according to conventional path traversal, then in step380the childOID is computed according to the invention, using the apl_lookup command and filesystem140proceeds to step395. When conventional path traversal is used, the childOID may not be a valid directory when one or more data storage units230have failed and prevented the path traversal from reaching a dirEntry for childname. The input to apl_lookup is path_prefix_to_childname (/foo), and the OIDof path /foo from APL table300is returned, OID317. When all of the data storage units230are available, APL table300and APL table250can be populated for each file object.

APL table300may be used to improve the namespace availability during the execution of other standard commands, such as pathwalk, create, remove, and rename. Pathwalk receives a fullpath as an input, traverses the path specified by fullpath component-by-component using the lookup command, and returns the OID of the last component of the path. For example, pathwalk(/foo/bar) returns OID318. Create receives a directory OID (dirOID) and filename as inputs and creates a regular file, symlink, or other filesystem object in the directory referenced by dirOID. For example, create(OID317,bar) creates the directory bar in the directory /foo and create(OID318,baz.txt) creates the file object baz.txt in the directory /foo/bar.

The remove command receives a fullpath as an input and removes the object referred by fullpath from the file system. The rename command receives a source dirOID (srcdirOID), a source filename (srcfilename), a destination dirOID (dstdirOID), and a destination filename (dstfilename) as inputs and renames srcfilename in the directory referred by srcdirOID to dstfilename in directory referred by dstdirOID. For example, rename(OID318, baz.txt, OID318, vmw.txt) renames /foo/bar/baz.txt to /foo/bar/vmw.txt.

The commands that are visible to a user include create, remove, and rename. However, the user versions of these commands do not require OIDs as inputs. Specifically, the user visible create command receives a path (dirpath) and filename as inputs. Therefore, create is internally implemented using pathwalk to determine dirOID, e.g., pathwalk(dirpath). Similarly, pathwalk is used to determine srcdirOID and dstdirOID for the user visible rename command which receives two inputs, a source fullpath (srcfullpath) and a destination fullpath (dstfullpath). Execution of the pathwalk command, including use of APL table300, is described in conjunction withFIGS. 4A and 4B.

FIG. 3Cis a conceptual diagram illustrating the contents of data storage units303, in accordance with one or more embodiments of the invention. The blocks allocated to inodes304,320, and323are stored in data storage unit303-0. Inode320is hardcoded as the root directory. The blocks allocated to inodes321,357,333, and354are stored in data storage unit303-1. The blocks allocated to inodes308,302, and388are stored in data storage unit303-2. Each data storage unit303stores a unique APL table305. APL table305-0is stored on data storage unit303-0and includes entries for one or more file objects (directories or user data) that are stored on data storage unit303-0. Likewise, APL table305-1is stored on data storage unit303-1and includes entries for one or more file objects that are also stored on data storage unit303-1and APL table305-2is stored on data storage unit303-2and includes entries for one or more file objects that are also stored on data storage unit303-2.

When a user executes create(/Dir1/Dir2, foo) the pathwalk command is executed to obtain the OID for Dir2. Specifically, lookup(lookup(OIDof(/),Dir1, Dir2) is executed to traverse the /Dir1/Dir2 path. The root directory specified by inode320is read to find Dir1. Dir1 is stored in Inode321which is stored on data storage unit303-1. If data storage unit303-1is unavailable, the lookup command fails since the directory entries of inode321cannot be read, causing the pathwalk and create commands to fail as well. The unavailability of data storage unit303-1has prevented the creation of the file object foo on data storage units303-0or303-2which may be available. Similarly, if data storage unit303-0is unavailable, the root directory cannot be read and the lookup command fails, regardless of whether or not data storage units303-1and303-2are available.

The use of APL tables305instead allows for the creation of the file object foo on data storage unit303-2even if data storage units303-0and303-1are unavailable. If the conventional lookup command fails, apl_lookup is used. In this example, apl_lookup(/Dir1/Dir2) returns the OID of Dir2, i.e. inode308, which is stored in APL table305-2. The create command does not fail and instead the foo file object is created on data storage unit230-2. Note that the entire path prefix may be read from APL table305-2using a single read access, rather than traversing each component of the path prefix as is done using the conventional lookup command. An entry may be added to APL table305-2for the path /Dir1/Dir2/foo when the create command is executed or at a later time as a batch process using the pathwalk command.

The Pathwalk Command

FIG. 4Ais a flow diagram of method steps for executing the pathwalk command using APL table300, in accordance with one or more embodiments of the invention. In step400filesystem140receives an apl_pathwalk command with a fullpath input, e.g., apl_pathwalk(/foo/bar/baz.txt). In step405filesystem140determines the parentOID using OIDof (“/”) and determines the childname as the next component in the fullpath using next_token(fullpath). For the fullpath /foo/bar/baz.txt the parentOID is the OID of the root directory “/” and the childname is foo. In step410filesystem140determines if the childname is null, indicating that the file object specified by fullpath has been reached. When the childname is null, in step415filesystem140outputs parentOID. When the childname is not null, in step420the childOID is determined using the lookup command, e.g., lookup(parentOID, childname). For the fullpath /foo/bar/baz.txt, the lookup command inputs are (/,foo).

In step425filesystem140determines if lookup succeeded. If lookup succeeded in step425, the filesystem140proceeds to step445. In step425lookup fails when the data storage unit that stores the directory entry for childname is unavailable. When lookup fails according to conventional path traversal, then in step430the childOID is computed according to the invention, using the apl_lookup command and filesystem140proceeds to step445. The inputs to apl_lookup are path_prefix_to_childname (/foo) and the OID of path /foo from APL table300is returned, OID317. In step445parentOID is set to childOID and childname is set to the next component in fullpath (bar). Filesystem140then returns to step410to see if the last component in the path has been reached.

FIG. 4Bis another flow diagram of method steps for executing the pathwalk command using APL table300, in accordance with one or more embodiments of the invention. In step400filesystem140receives an apl_pathwalk command with a fullpath input, e.g., apl_pathwalk(/foo/bar/baz.txt). Rather than using conventional path traversal, the apl_lookup command is used to quickly traverse the path. In step450filesystem140determines the parentOID using apl_lookup(fullpath). In step455filesystem140determines if apl_lookup command succeeded, and, if so, then in step480filesystem140outputs the parentOID.

In step450apl_lookup fails if there is not a valid entry in APL table300for the fullpath. If, in step455filesystem140determines that apl_lookup failed, then the filesystem140attempts a slower conventional lookup by proceeding to step460. In step460filesystem140completes the previously described steps that are shown inFIG. 4A(steps400,405,410,415,420,425,430, and445).

The Create Command

FIG. 5Ais a flow diagram of method steps for executing a create command, in accordance with one or more embodiments of the invention. In step500filesystem140receives a create command with dirpath and filename inputs, e.g., create(dirpath,filename), where dirpath/filename is a fullpath for a file object. In step505filesystem140determines the dirOID using apl_pathwalk with dirpath as an input. For the input of /foo/bar apl_pathwalk returns the OID of /foo/bar, OID318. In step515filesystem140executes a create command with dirOID and filename as inputs to create the file object of filename. By using apl_pathwalk to determine dirOID the valid dirOID is obtained even when data storage units storing intermediate directories, e.g., / and /foo, are unavailable. In step520filesystem104filesystem140executes an apl_insert command with dsuof(filename), dirpath/filename and OIDof(dirpath/filename) as inputs to populate an entry for the path in the APL table on the data storage unit230that stores filename.

It may not be important to protect all objects in the file system hierarchy. For example, it is not important to maintain high availability to temporary file objects made by an application such as a web browser. For such file objects, the overhead (even if it is small) of a populating an APL entry during file create may not be worthwhile. In general, file systems may mark certain directories to be “unprotected” by the APL mechanism. Some examples of directories that may not be selected for protection are c:\windows\temp on Windows operating systems or /tmp on Unix-like operating systems. Additionally, rather than populating an APL entry at file create time, a background helper process may be implemented to populate new entries in the APL tables that are queued as a result of create command execution. The downside of queuing the population of new entries is that the availability of the newly created file object in the file system hierarchy is reduced if a data storage unit becomes unavailable between the time the file object is created and the APL table entry for the file object is populated. However, batching the population of multiple entries may result in better storage performance since fewer accesses may be needed for each data storage unit.

FIG. 5Bis another flow diagram of method steps for executing a create command, in accordance with one or more embodiments of the invention. Steps540,545,560, and585correspond to steps500,505,515, and520ofFIG. 5A, respectively, and are completed as previously described. In step565filesystem140determines if APL population is enabled for dirpath, and, if not, in step570an entry is not populated in APL table300or any of APL tables250.

If, in step565filesystem140determines that APL population is enabled for dirpath/filename (fullpath), then in step580filesystem140determines if an “eager” APL table population mode is enabled. The eager mode indicates whether or not to populate an entry at the time that a create command is executed. When the eager mode is not enabled, a lazy APL table population mechanism is used, i.e., the previously described background helper process. If, in step580filesystem140determines that the eager APL table population mode is enabled, then in step585filesystem140executes an apl_insert command with DSU of(filename), dirpath/filename and OIDof(dirpath/filename) as inputs to populate an entry for the path in the APL table on the data storage unit230that stores filename. Otherwise, in step590filesystem140queues an APL table entry for insertion to APL table300and the DSU APL table250by the background helper process.

The Delete Command

FIG. 6is a flow diagram of method steps for executing a delete command, in accordance with one or more embodiments of the invention. When deleting an existing object, the filesystem140removes the corresponding entry from the APL table250of the data storage unit230on which the inode of the object is located. OIDs have a generation number that is used to detect stale OIDs. It is possible to not delete APL table entry250when the corresponding file object is unlinked since a subsequent APL table lookup will return a false positive, and filesystem140will subsequently refuse to use the file object because the generation number in the OID from the APL table entry250does not match the generation number of the corresponding inode on the data storage unit230. Again, like the create command, it is possible to eagerly delete entries in APL tables230or to queue the entries for deletion. It is also possible to never delete APL table entries, however it may be desirable to reuse the invalid entries to store new, valid entries.

In step600filesystem140receives a remove command with a dirpath and filename inputs where filename is the file object to be removed from the directory referenced by dirpath. In step602filesystem140determines if APL population is enabled for the dirpath, and, if so, in step603filesystem140determines the parentOID using apl_lookup to obtain the OID of the fullpath prefix (dirpath), OIDof(/foo/bar) for the fullpath /foo/bar/baz.txt, and proceeds to step645. If, in step602filesystem140determines that APL population is not enabled for the dirpath, then filesystem140proceeds to step615. In step615filesystem140executes an apl_pathwalk command using the dirpath input to determine the OID of the dirpath and store it in parentOID, parentOID=apl_pathwalk(dirpath). In step615filesystem140completes the previously described steps that are shown inFIG. 4B(steps400,450,455,460, and480) before proceeding to step645. For the fullpath /foo/bar/baz.txt the parentOID is the OIDof(/foo/bar).

In step645the delete command is executed to delete the file object indicated by the filename. In step650filesystem140determines if APL population is enabled for the fullpath (dirpath/filename), and, if not, in step655an entry is not deleted in APL table300or any of APL tables250. If, in step650filesystem140determines that APL population is enabled for the fullpath, then in step660filesystem140determines if an “eager” APL table deletion mode is enabled. The eager APL deletion mode indicates whether or not to delete an entry at the time that a remove command is executed. When the eager deletion mode is not enabled, a lazy APL table deletion mechanism is used, i.e., the previously described background helper process. If, in step660filesystem140determines that the eager APL table deletion mode is enabled, then in step670filesystem140executes an apl_delete command with fullpath as an input to delete an entry for the path in the APL table on the data storage unit that stores the path matching fullpath. Otherwise, in step665filesystem140queues deletion of an APL table entry for processing by the background helper process.

The Rename Command

FIG. 7is a flow diagram of method steps for executing a rename command in accordance with one or more embodiments of the invention. When a component of any path is renamed, it is necessary to search for all APL table entries in all data storage units230of data storage volumes215and replace the old component name with new component name. This operation can be completed more efficiently when APL tables300and250use indexing based on path prefixes, as previously described. When path prefixes are used, only the entry that matches the path being renamed needs to be replaced. All other subtrees of the renamed path are implicitly updated because they hold an index reference to this path instead of a verbose reference. When path prefixes are not used multiple entries in one or more APL tables250may need to be modified. Since APL tables300and250are capable of withstanding duplicate entries because the indexing mechanism will resolve a fullpath to a relevant entry, in the worst case, the OID in the entry will be stale with respect to the generation number in the inode, and the entry can be ignored or discarded.

In step700filesystem140receives a user visible rename command with the inputs srcfullpath and dstfullpath. In step705filesystem140executes the conventional rename command. In step710filesystem140executes the apl_remove command to remove the file object specified by srcfullpath. In step715filesystem140determines if APL population is enabled for the dstfullpath prefix, and, if not, in step725an entry in not populated in APL table300or any of APL tables250.

If, in step715filesystem140determines that APL population is enabled for the dstfullpath prefix, then in step720filesystem140determines if the eager APL table population mode is enabled. If, in step720filesystem140determines that the eager APL table deletion mode is enabled, then in step730filesystem140executes an apl_insert command with dsuof(tail(dstfullpath)), dstfullpath, and OIDof(dstfullpath) as inputs to insert an entry for the path in the APL table on the data storage unit that stores the path matching fullpath. Otherwise, in step735filesystem140queues insertion of an APL table entry for processing by the background helper process.

Unlike traditional hierarchical file system lookup, when APL tables are used filesystem140is capable of looking up the path in single access. The average storage I/O complexity of looking up a N-component fullpath using the traditional hierarchical file system method is:

12×∑i=1N-1⁢dirsize⁡(i)+N×inodesize
where dirsize(i) is the size of the list of dirEntries of the ithdirectory and inodesize is the size of a directory inode. In contrast, the average storage I/O complexity of looking up a N-component fullpath using an APL table implemented as a B+ tree for M data storage units is:

M2×logb⁡(P)×sizeof⁡(treenode)+sizeof⁡(APL_table⁢_entry)
where b is the order of the B+ tree, P is the average number of entries in the APL table250, treenode is a node in the B+ tree containing hash values for the tuple (DSU, fullpath), and APL_table_entry is an entry in the APL table250. In one embodiment, treenode is comparable to inodesize, M is a small integer up to 32, b is of the order of 1000 and P is of the order of 100000. Also note that the storage complexity in case of APL does not depend on the number of components in fullpath. Hence, using APL table300reduces the storage I/O bandwidth compared with using a traditional lookup method. Therefore, the lookup and pathwalk commands may be executed more efficiently when APL table300is used.

APL table300data structure may also be used to manage the hierarchy of objects in a file system in a standalone manner. In the previous examples, APL table300has been described in the context of existing file system architectures. It is also possible to use APL table300in a new file system that does not use the traditional method of organizing file objects as a list of directory entries inside the data blocks of directory inodes (as shown inFIG. 3C). Instead, these file systems can use one or more embodiments of the methods of the invention to implement a file hierarchy/namespace based solely on APL table data structures. In those file systems the file system is not traversed inode-by-inode, but instead a single entry is read from an APL table250to perform a lookup or pathwalk command.

Whether used as a standalone file system or in addition to a conventional file system, the APL table data structure provides a hierarchical namespace that withstands data storage units of a logical volume going offline without compromising the access to the still online file objects in the hierarchy. Users of the file system are able to access all inodes of online data storage units through the APL table when the APL table is fully populated or access a portion of the inodes of the online data storage units when selection is used to limit the directories that are available. The APL table may be used with conventional logical volume managers to provide useful enterprise features such as the ability to hot-replace data storage units without changing the file system address space, hot-extend logical volume length by adding new data storage units, software redundant array of inexpensive disks (RAID) availability features, data mirroring and replication over multiple data storage units, and the like.

The invention has been described above with reference to specific embodiments. Persons skilled in the art, however, will understand that various modifications and changes may be made thereto without departing from the broader spirit and scope of the invention as set forth in the appended claims. One embodiment of the invention may be implemented as a program product for use with a computer system. The program(s) of the program product define functions of the embodiments (including the methods described herein) and can be contained on a variety of computer-readable storage media. Illustrative computer-readable storage media include, but are not limited to: (i) non-writable storage media (e.g., read-only memory devices within a computer such as CD-ROM disks readable by a CD-ROM drive, flash memory, ROM chips or any type of solid-state non-volatile semiconductor memory) on which information is permanently stored; and (ii) writable storage media (e.g., floppy disks within a diskette drive or hard-disk drive or any type of solid-state random-access semiconductor memory) on which alterable information is stored. The foregoing description and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense.