Source: http://www.google.com/patents/US20060041718?ie=ISO-8859-1&dq=5,884,272
Timestamp: 2015-09-04 12:29:23
Document Index: 687692848

Matched Legal Cases: ['Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60', 'Application No. 60']

Patent US20060041718 - Fault-tolerant computer network file systems and methods - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentsA system and method for replacing file system processors, also known as hot swapping, is described. The system and method operate on a fault-tolerant network file system that includes a first file server that is operably connected to a network fabric and a second file server that is operably connected...http://www.google.com/patents/US20060041718?utm_source=gb-gplus-sharePatent US20060041718 - Fault-tolerant computer network file systems and methodsAdvanced Patent SearchPublication numberUS20060041718 A1Publication typeApplicationApplication numberUS 11/238,308Publication dateFeb 23, 2006Filing dateSep 29, 2005Priority dateJan 29, 2001Also published asUS6990547, US20020194523Publication number11238308, 238308, US 2006/0041718 A1, US 2006/041718 A1, US 20060041718 A1, US 20060041718A1, US 2006041718 A1, US 2006041718A1, US-A1-20060041718, US-A1-2006041718, US2006/0041718A1, US2006/041718A1, US20060041718 A1, US20060041718A1, US2006041718 A1, US2006041718A1InventorsThomas Ulrich, James Schweitzer, Gregory Bolstad, Jay Randall, John Staub, Wilbur PriesterOriginal AssigneeUlrich Thomas R, Schweitzer James R, Bolstad Gregory D, Randall Jay G, Staub John R, Priester Wilbur GExport CitationBiBTeX, EndNote, RefManReferenced by (19), Classifications (7), Legal Events (3) External Links: USPTO, USPTO Assignment, EspacenetFault-tolerant computer network file systems and methods
US 20060041718 A1Abstract
A system and method for replacing file system processors, also known as hot swapping, is described. The system and method operate on a fault-tolerant network file system that includes a first file server that is operably connected to a network fabric and a second file server that is operably connected to the network fabric. The fault-tolerant network file system includes a first disk array that is operably coupled to the first file server and to the second file server and a second disk array that is operably coupled to the first file server and to the second file server. First file system information is loaded on the first file server. The first file system information includes a first intent log of proposed changes to first metadata. Second file system information is loaded on the second file server. The second file system information includes a second intent log of proposed changes to second metadata. The first file server has a copy of the second metadata, and the second file server maintains a copy of the first metadata, thereby allowing the first file server to access files on the second disk array in the event of a failure of the second file server. Images(47) Claims(20)
1. A computer network file system, comprising: a first file server operably connected to a network fabric and to a first disk array and to a second disk array; a second file server operably connected to said network fabric and to said first disk array and to said second disk array; means for locating files stored by said first file server and files stored by said second file server by traversing a directory structure that spans. at least said first file server and said second file server; and means for allowing said first file server to complete file system changes intended by said second file server but not completed due to said second file server going offline. 2. The computer network file system of claim 1, wherein said directory structure comprises location information for a first file, said location information comprising a server id that identifies at least said first file server or said second file server. 3. The computer network file system of claim 1, wherein said directory structure comprises server ids of servers that contain sub-directories. 4. The computer network file system of claim 1, further comprising means for sharing workload between said first file server and said second file server. 5. The computer network file system of claim 1, further comprising means for detecting that said second file server has come online and handing at least a portion of file system operations dealing with said second disk array over to said second file server. 6. The computer network file system of claim 1, wherein said network fabric comprises a Fibre channel network. 7. The computer network file system of claim 1, wherein said network fabric comprises an ethernet network. 8. A method for hot-swapping file servers in a computer network, the method comprising: connecting a first file server to a network fabric and to a first disk array and to a second disk array; connecting a second file server to said network fabric and to said first disk array and to said second disk array; locating files stored by said first file server and files stored by said second file server by traversing a directory structure that spans at least said first file server and said second file server; and completing, with said first file server file system, changes intended by said second file server but not completed due to said second file server going offline. 9. The method of claim 8, wherein said directory structure comprises location information for a first file, said location information comprising a server id that identifies at least said first file server or said second file server. 10. The method of claim 8, wherein said directory structure comprises server ids of servers that contain sub-directories. 11. The method of claim 8, additionally comprising sharing a workload between said first file server and said second file server. 12. The method of claim 8, additionally comprising detecting that said second file server has come online and handing at least a portion of file system operations dealing with said second disk array over to said second file server. 13. The method of claim 8, wherein said network fabric comprises a Fibre channel network. 14. The method of claim 8, further comprising detecting with said first file server when said second file server goes offline. 15. A fault-tolerant computer network file system, comprising: a first file server operably connected to a network fabric and to a first disk array and to a second disk array; a second file server operably connected to said network fabric and to said first disk array and to said second disk array; and metadata comprising information indicative of locations of files stored by said first file server and files stored by said second file server, said metadata further comprising directory information describing a directory structure that spans at least said first file server and said second file server, wherein said first file server is capable of completing file system changes intended by said second file server but not completed due to said second file server going offline. 16. The fault-tolerant computer network file system of claim 15, wherein said directory structure comprises location information for a first file, said location information comprising a server id that identifies at least said first file server or said second file server. 17. The fault-tolerant computer network file system of claim 15, wherein said directory structure comprises server ids of servers that contain sub-directories. 18. The fault-tolerant computer network file system of claim 15, further comprising means for sharing workload between said first file server and said second file server. 19. The fault-tolerant computer network file system of claim 15, further comprising means for detecting that said second file server has come online and handing at least a portion of file system operations dealing with said second disk array over to said second file server. 20. The fault-tolerant computer network file system of claim 15, wherein said network fabric comprises a Fibre channel network.
RELATED APPLICATIONS This application is a divisional application of and claims priority benefit under 35 U.S.C. � 120 from U.S. application Ser. No. 10/060,908 filed Jan. 29, 2002, which is hereby incorporated herein by reference in its entirety, and which claims priority benefit under 35 U.S.C. � 119(e) from each of the following U.S. Provisional Applications, each of which is hereby incorporated herein by reference in its entirety. U.S. Provisional Application No. 60/264671, filed Jan. 29, 2001, titled “DYNAMICALLY DISTRIBUTED FILE SYSTEM”; U.S. Provisional Application No. 60/264694, filed Jan. 29, 2001, titled “A DATA PATH ACCELERATOR ASIC FOR HIGH PERFORMANCE STORAGE SYSTEMS”; U.S. Provisional Application No. 60/264672, filed Jan. 29, 2001, titled “INTEGRATED FILE SYSTEM/PARITY DATA PROTECTION”; U.S. Provisional Application No. 60/264673, filed Jan. 29, 2001, titled “DISTRIBUTED PARITY DATA PROTECTION”; U.S. Provisional Application No. 60/264670, filed Jan. 29, 2001, titled “AUTOMATIC IDENTIFICATION AND UTILIZATION OF RESOURCES IN A DISTRIBUTED FILE SERVER”; U.S. Provisional Application No. 60/264669, filed Jan. 29, 2001, titled “DATA FLOW CONTROLLER ARCHITECTURE FOR HIGH PERFORMANCE STORAGE SYSTEMS”; U.S. Provisional Application No. 60/264668, filed Jan. 29, 2001, titled “ADAPTIVE LOAD BALANCING FOR A DISTRIBUTED FILE SERVER”; and U.S. Provisional Application No. 60/302424, filed Jun. 29, 2001, titled “DYNAMICALLY DISTRIBUTED FILE SYSTEM.” BACKGROUND OF THE INVENTION 1. Field of the Invention This invention relates to the field of data storage and management. More particularly, this invention relates to high-performance mass storage systems and methods for data storage, backup, and recovery. 2. Description of the Related Art In modern computer systems, collections of data are usually organized and stored as files. A file system allows users to organize, access, and manipulate these files and also performs administrative tasks such as communicating with physical storage components and recovering from failure. The demand for file systems that provide high-speed, reliable, concurrent access to vast amounts of data for large numbers of users has been steadily increasing in recent years. Often such systems use a Redundant Array of Independent Disks (RAID) technology, which distributes the data across multiple disk drives, but provides an interface that appears to users as one, unified disk drive system, identified by a single drive letter. In a RAID system that includes more than one array of disks, each array is often identified by a unique drive letter, and in order to access a given file, a user must correctly identify the drive letter for the disk array on which the file resides. Any transfer of files from one disk array to another and any addition of new disk arrays to the system must be made known to users so that they can continue to correctly access the files. RAID systems effectively speed up access to data over single-disk systems, and they allow for the regeneration of data lost due to a disk failure. However, they do so by rigidly prescribing the configuration of system hardware and the block size and location of data stored on the disks. Demands for increases in storage capacity that are transparent to the users or for hardware upgrades that lack conformity with existing system hardware cannot be accommodated, especially while the system is in use. In addition, such systems commonly suffer from the problem of data fragmentation, and they lack the flexibility necessary to intelligently optimize use of their storage resources. RAID systems are designed to provide high-capacity data storage with built-in reliability mechanisms able to automatically reconstruct and restore saved data in the event of a hardware failure or data corruption. In conventional RAID technology, techniques including spanning, mirroring, and duplexing are used to create a data storage device from a plurality of smaller single disk drives with improved reliability and storage capacity over conventional disk systems. RAID systems generally incorporate a degree of redundancy into the storage mechanism to permit saved data to be reconstructed in the event of single (or sometimes double) disk failure within the disk array. Saved data is further stored in a predefined manner that is dependent on a fixed algorithm to distribute the information across the drives of the array. The manner of data distribution and data redundancy within the disk array impacts the performance and usability of the storage system and may result in substantial tradeoffs between performance, reliability, and flexibility. A number of RAID configurations have been proposed to map data across the disks of the disk array. Some of the more commonly recognized configurations include RAID-1, RAID-2, RAID-3, RAID-4, and RAID-5. In most RAID systems, data is sequentially stored in data stripes and a parity block is created for each data stripe. The parity block contains information derived from the sequence and composition of the data stored in the associated data stripe. RAID arrays can reconstruct information stored in a particular data stripe using the parity information, however, this configuration imposes the requirement that records span across all drives in the array resulting in a small stripe size relative to the stored record size. FIG. 21 illustrates the data mapping approach used in many conventional RAID storage device implementations. Although the diagram corresponds most closely to RAID-3 or RAID-4 mapping schemas, other RAID configurations are organized in a similar manner. As previously indicated, each RAID configuration uses a striped disk array 2110 that logically combines two or more disk drives 2115 into a single storage unit. The storage space of each drive 2115 is organized by partitioning the space on the drives into stripes 2120 that are interleaved so that the available storage space is distributed evenly across each drive. Information or files are stored on the disk array 2110. Typically, the writing of data to the disks occurs in a parallel manner to improve performance. A parity block is constructed by performing a logical operation (exclusive OR) on the corresponding blocks of the data stripe to create a new block of data representative of the result of the logical operation. The result is termed a parity block and is written to a separate area 2130 within the disk array. In the event of data corruption within a particular disk of the array 10, the parity information is used to reconstruct the data using the information stored in the parity block in conjunction with the remaining non-corrupted data blocks. In the RAID architecture, multiple disks a typically mapped to a single ‘virtual disk’. Consecutive blocks of the virtual disk are mapped by a strictly defined algorithm to a set of physical disks with no file level awareness. When the RAID system is used to host a conventional file system, it is the file system that maps files to the virtual disk blocks where they may be mapped in a sequential or non-sequential order in a RAID stripe. The RAID stripe may contain data from a single file or data from multiple files if the files are small or the file system is highly fragmented. The aforementioned RAID architecture suffers from a number of drawbacks that limit its flexibility and scalability for use in reliable storage systems. One problem with existing RAID systems is that the data striping is designed to be used in conjunction with disks of the same size. Each stripe occupies a fixed amount of disk space and the total number of stripes allowed in the RAID system is limited by the capacity of the smallest disk in the array. Any additional space that may be present on drives having a capacity larger than the smallest drive goes unused as the RAID system lacks the ability to use the additional space. This further presents a problem in upgrading the storage capacity of the RAID system, as all of the drives in the array must be replaced with larger capacity drives if additional storage space is desired. Therefore, existing RAID systems are inflexible in terms of their drive composition, increasing the cost and inconvenience to maintain and upgrade the storage system. A further problem with conventional RAID arrays resides in the rigid organization of data on the disks of the RAID array. As previously described, this organization typically does not use available disk space in an efficient manner. These systems further utilize a single fixed block size to store data which is implemented with the restriction of sequential file storage along each disk stripe. Data storage in this manner is typically inefficient as regions or gaps of disk space may go unused due to the file organization restrictions. Furthermore, the fixed block size of the RAID array is not able to distinguish between large files, which benefit from larger block size, and smaller files, which benefit from smaller block size for more efficient storage and reduced wasted space. Although conventional RAID configurations are characterized as being fault-tolerant, this capability is typically limited to single disk failures. Should more than one (or two) disk fail or become inoperable within the RAID array before it can be replaced or repaired there is the potential for data loss. This problem again arises from the rigid structure of data storage within the array that utilizes sequential data striping. This problem is further exacerbated by the lack of ability of the RAID system to flexibly redistribute data to other disk areas to compensate for drive faults. Thus, when one drive becomes inoperable within the array, the likelihood of data loss increases significantly until the drive is replaced resulting in increased maintenance and monitoring requirements when using conventional RAID systems. With respect to conventional data storage systems or other computer networks, conventional load balancing includes a variety of drawbacks. For example, decisions relating to load balancing are typically centralized in one governing process, one or more system administrators, or combinations thereof. Accordingly, such systems have a single point of failure, such as the governing process or the system administrator. Moreover, load balancing occurs only when the centralized process or system administrator can organize performance data, make a decision, and then transmit that decision throughout the data storage system or computer network. This often means that the such load balancing can be slow to react, difficult to optimize for a particular server, and difficult to scale as the available resources expand or contract. In addition, conventional load balancing typically is limited to balancing processing and communications activity between servers only. SUMMARY OF THE INVENTION The present invention solves these and other problems by providing a dynamically distributed file system that accommodates current demands for high capacity, throughput, and reliability, while presenting to the users a single-file-system interface that appears to include every file in the system on a single server or drive. In this way, the file system is free to flexibly, transparently, and on-the-fly distribute and augment physical storage of the files in any manner that suits its needs, across disk drives, and across servers, and users can freely access any file without having specific knowledge of the files current physical location. One embodiment includes a storage device and architecture which possesses features such as transparent scalability where disks of non-identical capacity can be fully-utilized without the “dead-space” restrictions associated with conventional disk arrays. In one embodiment a flexible storage space allocation system handles storing large and small file types to improve disk space utilization. In another embodiment an improved method for maintaining data integrity overcomes the single drive (or double) fault limitation of conventional systems in order to increase storage reliability while at the same time reducing maintenance and monitoring requirements. In one embodiment, distributed parity groups (DPG) are integrated into the distributed file storage system technology. This architecture provides capabilities for optimizing the use of disk resources by moving frequently and infrequently accessed data blocks between drives so as to maximize the throughput and capacity utilization of each drive. In one embodiment, the architecture supports incorporation of new disk drives without significant reconfiguration or modification of the exiting distributed file storage system to provide improved reliability, flexibility, and scalability. Additionally, the architecture permits the removal of arbitrary disk drives from the distributed file storage system and automatically redistributes the contents of these drives to other available drives as necessary. The distributed file storage system can proactively position objects for initial load balancing, such as, for example, to determine where to place a particular new object. Additionally, the distributed file storage system can continue to proactively position objects, thereby accomplishing active load balancing for the existing objects throughout the system. According to one embodiment, one or more filters may be applied during initial and/or active load balancing to ensure one or a small set of objects are not frequently transferred, or churned, throughout the resources of the system. As used herein, load balancing can include, among other things, capacity balancing, throughput balancing, or both. Capacity balancing seeks balance in storage, such as the number of objects, the number of Megabytes, or the like, stored on particular resources within the distributed file storage system. Throughput balancing seeks balance in the number of transactions processed, such as, the number of transactions per second, the number of Megabytes per second, or the like, handled by particular resources within the distributed file storage system. According to one embodiment, the distributed file storage system can position objects to balance capacity, throughput, or both, between objects on a resource, between resources, between the servers of a cluster of resources, between the servers of other clusters of resources, or the like. The distributed file storage system can comprise resources, such as servers or clusters, which can seek to balance the loading across the system by reviewing a collection of load balancing data from itself, one or more of the other servers in the system, or the like. The load balancing data can include object file statistics, server profiles, predicted file accesses, or the like. A proactive object positioner associated with a particular server can use the load balancing data to generate an object positioning plan designed to move objects, replicate objects, or both, across other resources in the system. Then, using the object positioning plan, the resource or other resources within the distributed file storage system can execute the plan in an efficient manner. According to one embodiment, each server pushes objects defined by that server's respective portion of the object positioning plan to the other servers in the distributed file storage system. By employing the servers to individually push objects based on the results of their object positioning plan, the distributed file storage system provides a server-, process-, and administrator-independent approach to object positioning, and thus load balancing, within the distributed file storage system. In one embodiment, the network file storage system includes a first file server operably connected to a network fabric; a second file server operably connected to the network fabric; first file system information loaded on the first file server; and second file system information loaded on the second file server, the first file system information and the second file system information configured to allow a client computer operably connected to the network fabric to locate files stored by the first file server and files stored by the second file server without prior knowledge as to which file server stores the files. In one embodiment, the first file system information includes directory information that describes a directory structure of a portion of the network file system whose directories are stored on the first file server, the directory information includes location information for a first file, the location information includes a server id that identifies at least the first file server or the second file server. In one embodiment, the network file storage system loads first file system metadata on a first file server operably connected to a network fabric; loads second file system metadata on a second file server connected to the network fabric, the first file system metadata and the second file system metadata include information to allow a client computer operably connected to the network fabric to locate a file stored by the first file server or stored by the second file server without prior knowledge as to which file server stores the file. In one embodiment, the network file storage system performs a file handle lookup on a computer network file system by: sending a root-directory lookup request to a first file server operably connected to a network fabric; receiving a first lookup response from the first file server, the first lookup response includes a server id of a second file server connected to the network fabric; sending a directory lookup request to the second file server; and receiving a file handle from the second file server. In one embodiment, the network file storage system allocates space by; receiving a file allocation request in a first file server, the first file server owning a parent directory that is to contain a new file, the file allocation request includes a file handle of the parent directory; determining a selected file server from a plurality of file servers; sending a file allocation request from the first server to the selected server; creating metadata entries for the new file in file system data managed by the selected file server; generating a file handle for the new file; sending the file handle to the first file server; and creating a directory entry for the new file in the parent directory. In one embodiment, the network file storage system includes: a first file server operably connected to a network fabric; a second file server operably connected to the network fabric; first file system information loaded on the first file server; and second file system information loaded on the second file server, the first file system information and the second file system information configured to allow a client computer operably connected to the network fabric to locate files owned by the first file server and files owned by the second file server without prior knowledge as to which file server owns the files, the first file server configured to mirror at least a portion of the files owned by the second file server, the first file server configured to store information sufficient to regenerate the second file system information, and the second file server configured to store information sufficient to regenerate the first file system information. In one embodiment, the network file storage system: loads first file system metadata on a first file server operably connected to a network fabric; loads second file system metadata on a second file server connected to the network fabric, the first file system metadata and the second file system metadata include information to allow a client computer operably connected to the network fabric to locate a file stored by the first file server or stored by the second file server without prior knowledge as to which file server stores the file; maintains information on the second file server to enable the second file server to reconstruct an information content of the first file system metadata; and maintains information on the first file server to enable the first file server to reconstruct an information content of the second file system metadata. In one embodiment the computer network file storage system is fault-tolerant and includes: a first file server operably connected to a network fabric; a second file server operably connected to the network fabric; a first disk array operably coupled to the first file server and to the second file server; a second disk array operably coupled to the first file server and to the second file server; first file system information loaded on the first file server, the first file system information including a first intent log of proposed changes to the first metadata; second file system information loaded on the second file server, the second file system information including a second intent log of proposed changes to the second metadata, the first file server having a copy of the second intent log, the second file server maintaining a copy of the first intent log, thereby allowing the first file server to access files on the second disk array in the event of a failure of the second file server. In one embodiment, a distributed file storage system provides hot-swapping of file servers by: loading first file system metadata on a first file server operably connected to a network fabric, the first file system operably connected to a first disk drive and a second disk drive; loading second file system metadata on a second file server connected to the network fabric, the second file system operably connected to the first disk drive and to the second disk drive; copying a first intent log from the first file server to a backup intent log on the second file server, the first intent log providing information regarding future changes to information stored on the first disk drive; and using the backup intent log to allow the second file server to make changes to the information stored on the first disk drive. In one embodiment, a distributed file storage system includes: a first file server operably connected to a network fabric; a file system includes first file system information loaded on the first file server, the file system configured to create second file system information on a second file server that comes online sometime after the first file server has begun servicing file requests, the file system configured to allow a requester to locate files stored by the first file server and files stored by the second file server without prior knowledge as to which file server stores the files. In one embodiment, a distributed file storage system adds servers during ongoing file system operations by: loading first file system metadata on a first file server operably connected to a network fabric; creating at least one new file on a second file server that comes online while the first file server is servicing file requests, the at least one new file created in response to a request issued to the first file server, the distributed file system configured to allow a requester to locate files stored by the first file server and files stored by the second file server without prior knowledge as to which file server stores the files. In one embodiment, a distributed file storage system includes: first metadata managed primarily by a first file server operably connected to a network fabric, the first metadata includes first file location information, the first file location information includes at least one server id; and second metadata managed primarily by a second file server operably connected to the network fabric, the second metadata includes second file location information, the second file location information includes at least one server identifier, the first metadata and the second metadata configured to allow a requester to locate files stored by the first file server and files stored by the second file server in a directory structure that spans the first file server and the second file server. In one embodiment, a distributed file storage system stores data by: creating first file system metadata on a first file server operably connected to a network fabric, the first file system metadata describing at least files and directories stored by the first file server; creating second file system metadata on a second file server connected to the network fabric, the second file system metadata describing at least files and directories stored by the second file server, the first file system metadata and the second file system metadata includes directory information that spans the first file server and the second file server, the directory information configured to allow a requestor to find a location of a first file catalogued in the directory information without prior knowledge as to a server location of the first file. In one embodiment, a distributed file storage system balances the loading of servers and the capacity of drives associated with the servers, the file system includes: a first disk drive including a first unused capacity; a second disk drive including a second unused capacity, wherein the second unused capacity is smaller than the first unused capacity; a first server configured to fill requests from clients through access to at least the first disk drive; and a second server configured to fill requests from clients through access to at least the second disk drive, and configured to select an infrequently accessed file from the second disk drive and push the infrequently accessed files to the first disk drive, thereby improving a balance of unused capacity between the first and second disk drives without substantially affecting a loading for each of the first and second servers. In one embodiment, a distributed file storage system includes: a first file server operably connected to a network fabric; a second file server operably connected to the network fabric; first file system information loaded on the first file server; and second file system information loaded on the second file server, the first file system information and the second file system information configured to allow a client computer operably connected to the network fabric to locate files stored by the first file server and files stored by the second file server without prior knowledge as to which file server stores the files. In one embodiment, a data engine offloads data transfer operations from a server CPU. In one embodiment, the server CPU queues data operations to the data engine. In one embodiment, a distributed file storage system includes: a plurality of disk drives for storing parity groups, each parity group includes storage blocks, the storage blocks includes one or more data blocks and a parity block associated with the one or more data blocks, each of the storage blocks stored on a separate disk drive such that no two storage blocks from a given parity set reside on the same disk drive, wherein file system metadata includes information to describe the number of data blocks in one or more parity groups. In one embodiment, a distributed file storage system stores data by: determining a size of a parity group in response to a write request, the size describing a number of data blocks in the parity group; arranging at least a portion of data from the write request according to the data blocks; computing a parity block for the parity group; storing each of the data blocks on a separate disk drive such that no two data blocks from the parity group reside on the same disk drive; and storing each the parity block on a separate disk drive that does not contain any of the data blocks. In one embodiment, a distributed file storage system includes: a plurality of disk drives for storing parity groups, each parity group includes storage blocks, the storage blocks includes one or more data blocks and a parity block associated with the one or more data blocks, each of the storage blocks stored on a separate disk drive such that no two storage blocks from a given parity set reside on the same disk drive; a redistribution module to dynamically redistribute parity groups by combining some parity groups to improve storage efficiency. In one embodiment, a distributed file storage system stores data by: determining a size of a parity group in response to a write request, the size describing a number of data blocks in the parity group; arranging at least a portion of data from the write request according to the data blocks; computing a parity block for the parity group; storing each of the data blocks on a separate disk drive such that no two data blocks from the parity group reside on the same disk drive; storing the parity block on a separate disk drive that does not contain any of the data blocks; and redistributing the parity groups to improve storage efficiency. In one embodiment, a distributed file storage system includes: a plurality of disk drives for storing parity groups, each parity group includes storage blocks, the storage blocks includes one or more data blocks and a parity block associated with the one or more data blocks, each of the storage blocks stored on a separate disk drive such that no two storage blocks from a given parity set reside on the same disk drive; and a recovery module to dynamically recover data lost when at least a portion of one disk drive in the plurality of disk drives becomes unavailable, the recovery module configured to produce a reconstructed block by using information in the remaining storage blocks of a parity set corresponding to an unavailable storage block, the recovery module further configured to split the parity group corresponding to an unavailable storage block into two parity groups if the parity group corresponding to an unavailable storage block spanned all of the drives in the plurality of disk drives. In one embodiment, a distributed file storage system stores data by: determining a size of a parity group in response to a write request, the size describing a number of data blocks in the parity group; arranging at least a portion of data from the write request according to the data blocks; computing a parity block for the parity group; storing each of the data blocks on a separate disk drive such that no two data blocks from the parity group reside on the same disk drive; storing the parity block on a separate disk drive that does not contain any of the data blocks; reconstructing lost data by using information in the remaining storage blocks of a parity set corresponding to an unavailable storage block to produce a reconstructed parity group; splitting the reconstructed parity group corresponding to an unavailable storage block into two parity groups if the reconstructed parity group is too large to be stored on the plurality of disk drives. In one embodiment, a distributed file storage system integrates parity group information into file system metadata.
BRIEF DESCRIPTION OF THE DRAWINGS These and other aspects, advantages, and novel features of the invention will become apparent upon reading the following detailed description and upon reference to the accompanying drawings: FIG. 1 is a general overview of a distributed file storage system showing clients, a communication fabric, and a plurality of servers with associated disk arrays. FIG. 2 is a block diagram of a server node. FIG. 3 is a block diagram of five metadata structures and connections between the five metadata structures. FIG. 4 shows an example portion of a Filename Table. FIG. 5 shows an example of a Gee-string stored in a Gee Table. FIG. 6 shows one embodiment of the structure of a G-node. FIG. 7 shows one embodiment of the structure of a Gnid-string. FIG. 8A shows one embodiment of the structure of a Cache Node. FIG. 8B shows a conceptual division of a Cache Node Table into three lists. FIG. 9 shows a sample portion of a lock string. FIG. 10 shows one embodiment of Refresh Nodes configured as a binary tree. FIG. 11 shows one embodiment of Refresh Nodes configured as a doubly- linked list. FIG. 12 shows one embodiment of the structure of an Intent Log Entry. FIG. 13 shows one embodiment of the structure of a file handle. FIG. 14A is a block diagram depicting one embodiment of a file handle look-up process. FIG. 14B is a block diagram depicting one embodiment of a file access process. FIG. 15 is a flow chart depicting one embodiment of performing a file access. FIG. 16 is a flow chart depicting one embodiment of performing a file handle look-up. FIG. 17 is a flow chart depicting one embodiment of caching file data. FIG. 18 is a flow chart depicting one embodiment of file allocation. FIG. 19 shows one embodiment of Super G-nodes. FIG. 20A shows one embodiment of a Super G-node. FIG. 20B shows one embodiment of a scheme to use Super G-nodes to hold metadata for files of widely varying sizes. FIG. 21 illustrates a conventional disk array that incrementally stripes data in a RAID mapping architecture. FIG. 22A illustrates one embodiment of a distributed file storage system. FIG. 22B illustrates another embodiment of a distributed file storage system having built in data redundancy. FIG. 23 illustrates a distributed file storage mechanism. FIG. 24A illustrates a data and parity information storage method. FIG. 24B illustrates another data and parity information storage method. FIG. 25 illustrates another embodiment of a distributed file storage system having a variable capacity disk array. FIG. 26A illustrates an embodiment of variable block number parity groups. FIG. 26B illustrates an embodiment of variable size parity groups. FIG. 27 illustrates one embodiment of a G-table used to determine parity group mapping. FIG. 28 illustrates a method for storing data in the distributed file storage system. FIG. 29 illustrates another embodiment of a G-table mapping structure. FIG. 30 illustrates one embodiment of a fault-tolerant restoration process. FIG. 31 illustrates a method for recovering corrupted or lost data in the distributed file storage system. FIG. 32A illustrates one embodiment of a variably sized parity group used to store files. FIG. 32B illustrates another embodiment of a variably sized parity group used to store files. FIG. 33 illustrates a data storage process used by the distributed file storage system. FIGS. 34A-C illustrate a parity set redistribution process. FIG. 35A illustrates one embodiment of a parity group dissolution process. FIG. 35B illustrates one embodiment of a parity group consolidation process. FIG. 36 illustrates a parity group monitoring process. FIG. 37 illustrates a parity group optimization/de-fragmentation process. FIG. 38 illustrates a load balancing method used by the distributed file storage system. FIG. 39 depicts a block diagram of an exemplary embodiment of servers and disk arrays of a distributed file storage system, which highlights the proactive object positioning of aspects of an exemplary embodiment of the invention. FIG. 40 depicts a block diagram of an exemplary server of FIG. 39, according to aspects of an exemplary embodiment of the invention. FIG. 41 depicts an object positioning plan for Server F3 of FIG. 39, according to aspects of an exemplary embodiment of the invention. FIG. 42 is a block diagram of a server that provides efficient processing of data transfers between one or more client computers and one or more disk drives. FIG. 43 is a block diagram of a data engine. FIG. 44 is a map of data fields in a 64-bit data transfer instruction to the data engine for use with a 64-bit PCI bus.
DETAILED DESCRIPTION Introduction As data storage requirements increase, it is desirable to be able to easily increase the data storage capacity and/or performance of a data storage system. That is, it is desirable to be able to increase the available capacity and performance of a storage system without modifying the configuration of the clients accessing the system. For example, in a typical Personal Computer (PC) network environment, if a database accesses a network drive “M”, it is desirable to be able to add storage to this drive, all the while still calling the drive “M”, as opposed to adding, say, drives “N”, “O”, and “P” as storage requirements increase. In some cases, having to switch from a single drive “M” to four drives, “M”, “N”, “O”, “P” is a mere nuisance. However, in some cases such a change requires significant reconfiguration of client configurations. In other cases, such a change requires modification of existing application software, and in some instances such a change simply will not work with the application being used. The objective for more capacity can be met in some storage systems by adding additional disk drives to the system. However, this may not result in increasing performance. In fact, adding additional drives may cause a significant decrease in performance. This is because: (1) if more ports are not added to the system when new drives are added, the performance decreases because now more data is available (and presumably being accessed) through the same performance ports; and (2) the controller managing the file system metadata has more operations to perform and can become a bottleneck. Adding drives to existing systems may also limited by physical form factors. That is to say, that some systems have physical limits to how many drives can be added. In one embodiment, the system described herein provides a Distributed File Storage System (DFSS) that can scale disk capacity, scale data throughput (e.g., megabytes per second of data delivery); and scale transaction processing throughput (e.g., processing of file system metadata). In one embodiment, the system also provides load balancing such that the scaled components handle the workload with improved efficiency. In one embodiment, the DFSS is dynamically distributed. In one embodiment, the DFSS allows the integration of multiple servers so that the aggregation of servers appears to a client as a single storage device. With the DFSS, multiple servers can access and control the same disk array, separate disk arrays, or both simultaneously. The DFSS is designed so that each server can continue to read and write data to the drives it controls even when other controllers in the DFSS fail. The DFSS also provides a mechanism for balancing the load on the controllers and the drives. In one embodiment, the DFSS is designed such that when multiple controllers are controlling a single array of disk drives (also called a drive array), some or all of the servers connected to the drive array have valid copies of the file system metadata describing the data on that drive array. This means that each server has direct access to all of the file system metadata for one or more of the drive arrays it can access. Thus: (1) a server can continue to operate normally if the other servers in the system fail; and (2) there is little or no performance degradation due to one server polling another server regarding location of data on drive arrays. The DFSS provides inter-server communication to maintains synchronization of the file system metadata. The DFSS is designed such that a server can read from more than one drive array and can read from drive arrays maintained by another server. In one embodiment, only one controller attached to a particular drive array has write privileges for that particular drive array at a given time. The DFSS maintains a description of which servers have read and write privileges to a