Abstract:
A method and apparatus for operating a data storage system is disclosed. An original active file system holds incoming write transactions. Data is written at a selected time to blocks in a data storage device of the original active file system, the data written to blocks which do not hold old data of the data storage system. Pointers to data of the original active file system are written at the selected time to the data storage device, the pointers written to blocks which do not hold old data of the data storage system, the pointers and a previously saved data of the active file system forming a consistency point of the original active file system at the selected time. A new active file system is started using the consistency point of the original active file system at the selected time.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     The present application is a continuation of U.S. patent application Ser. No. 11/057,409, which was filed on Feb. 14, 2005 and is now issued as U.S. Pat. No. 7,685,169 on Mar. 23, 2010, by David Hitz et al. for MULTIPLE CONCURRENT ACTIVE FILE SYSTEMS, which is a continuation of U.S. patent application Ser. No. 10/165,188, which was filed on Jun. 7, 2002 and is now issued as U.S. Pat. No. 6,857,001 on Feb. 15, 2005. Both applications are hereby incorporated by reference. 
    
    
     BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     This invention relates to multiple concurrent writeable file systems. 
     2. Description of the Related Art 
     A file system provides a structure for storing information, for example application programs, file system information, other data, etc. (hereinafter collectively referred to as simply data) on storage devices such as disk drives, CD-ROM drives, etc. One problem with many file systems is that if the file system is damaged somehow, a large quantity of data can be lost. 
     In order to prevent such loss of data, backups are often created of a file system. One very efficient method for creating a backup of a file system is to create a snapshot of the file system. A snapshot is an image of the file system at a consistency point, a point at which the file system is self-consistent. A file system is self-consistent if the data stored therein constitutes a valid file system image. 
     In some file systems, for example Write Anywhere File System Layout (WAFL) file systems, a snapshot of a file system can be created by copying information regarding the organization of data in the file system. Then, as long as the data itself is preserved on the storage device, the data can be accessed through the snapshot. A mechanism is provided in these file systems for preserving this data, for example through a block map. 
     Conventionally, snapshots are read-only. A read-only snapshot can be used to recall previous versions of data and to repair damage to a file system. These capabilities can be extremely useful. However, these types of snapshots do not provide certain other capabilities that might be useful. 
     SUMMARY OF THE INVENTION 
     It would be advantageous if snapshots could be written to as well, so that a user desiring to modify a snapshot could do so. This would have several advantages:
         It would become possible to correct an erroneous entry that had been memorialized in a snapshot.   It would become possible to delete material that was desired to be purged from the file system.   It would become possible to make changes to an “experimental” version of the file system (or on data maintained by the file system). An “experimental” version of the file system would be a version of the file system for which catastrophic errors would not cause loss of data in a “real” active version of the file system.   It would become possible to reverse erroneous upgrades to operation of the file system, or to operation of some programs or databases operating under the aegis of that file system.       

     A writable snapshot is actually another active file system. Because this active file system is based on data from another active file system, experimental modifications and changes for the active file system can be made to the writable snapshot without risking harm to the original active file system. In addition, because a snapshot can be created by simply copying organizational information and preserving existing data, writable snapshots (i.e. new active file systems) can be created easily and with utilization of few system resources. 
     These advantages and others are provided in an embodiment of the invention, described herein, in which plural active file systems are maintained, wherein each of the active file systems initially access data shared with another of the active file systems, and wherein changes made to each of the active file systems are not reflected in other active file systems. 
     In the preferred embodiment, when a second active file system is created based on a first active file system, the first active file system and the second active file system initially share data. When changes are made to the first active file system, modified data is recorded in the first active file system in a location that is not shared with the second active file system. When changes are made to the second active file system, modified data is recorded in the second active file system in a location that is not shared with the first active file system. 
     Further snapshots preferably are made of ones of the plural active file systems, each snapshot forming an image of its respective active file system at a past consistency point. Each snapshot includes a complete hierarchy for file system data, separate and apart from active file system data for the plural active file systems. One of these snapshots in turn can be converted into a new active file system by making the snapshot writable and by severing snapshot pointers from any of the active file systems to the new active file system. 
     The invention also encompasses memories that include instructions for performing the foregoing operations and storage systems that implement those operations. 
     This brief summary has been provided so that the nature of the invention may be understood quickly. A more complete understanding of the invention may be obtained by reference to the following description of the preferred embodiments thereof in connection with the attached drawings. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  illustrates creation of a snapshot that can be converted into an active file system according to the invention. 
         FIG. 2  illustrates divergence of an active file system from a snapshot of that file system. 
         FIG. 3  illustrates the relationship between the active file system and the snapshot in  FIG. 2 . 
         FIG. 4  illustrates a chain of snapshots that can be converted into active file systems according to the invention. 
         FIG. 5  illustrates the relationship between the active file system and the snapshots in  FIG. 4 . 
         FIG. 6  illustrates a snapshot that has been converted into an active file system according to the invention. 
         FIG. 7  illustrates the relationship between the active file system, new active file system, and snapshot in  FIG. 6 . 
         FIG. 8  illustrates a more complex chain of snapshots that can be converted into active file systems according to the invention. 
         FIG. 9  illustrates the chain shown in  FIG. 8  with one of the snapshots converted into an active file system according to the invention. 
         FIG. 10  illustrates some more possible relationships between plural active file systems and their associated snapshots according to the invention. 
         FIG. 11  shows a block diagram of a storage system including plural active file systems according to the invention. 
         FIG. 12  shows a block diagram of a file system cluster including multiple concurrent active file systems being used by multiple concurrent file servers according to the invention. 
     
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENT 
     Related Applications 
     Inventions described herein can be used in conjunction with inventions described in the following documents:
         U.S. patent application Ser. No. 09/642,061, filed Aug. 18, 2000, in the name of inventors Lewis, Edwards and Viswanathan, now issued as U.S. Pat. No. 7,072,916 on Jul. 4, 2006, titled “Instant Snapshot.”   U.S. patent application Ser. No. 09/932,578, filed Aug. 17, 2001, in the name of inventors Lewis, Edwards and Viswanathan, now issued as U.S. Pat. No. 7,454,445 on Nov. 18, 2008, titled “Instant Snapshot.”   U.S. patent application Ser. No. 08/071,643, filed Jun. 3, 1993, in the name of inventors Hitz, Malcolm, Lau and Rakitzis, titled “Write Anywhere File-System Layout,” now abandoned.   U.S. patent application Ser. No. 08/454,921, filed May 31, 1995, in the name of inventors Hitz, Malcolm, Lau and Rakitzis, titled “Write Anywhere File-System Layout,” now U.S. Pat. No. 5,819,292.   U.S. patent application Ser. No. 09/108,022, filed Jun. 30, 1998, in the name of inventors Hitz, Malcolm, Lau and Rakitzis, titled “Write Anywhere File-System Layout,” now U.S. Pat. No. 5,963,962.   U.S. patent application Ser. No. 09/153,094, filed Sep. 14, 1998, in the name of inventors Ritz, Malcolm, Lau and Rakitzis, titled “Write Anywhere File-System Layout,” now U.S. Pat. No. 6,289,356 B1.   U.S. patent application Ser. No. 09/954,522, filed Sep. 11, 2001, in the name of inventors Ritz, Malcolm, Lau and Rakitzis, now issued as U.S. Pat. No. 6,721,764 on Apr. 13, 2004, titled “Write Anywhere File-System Layout.”   U.S. patent application Ser. No. 09/642,065, filed Aug. 18, 2000, in the name of inventors Doucette, Lewis and Edwards, now issued as U.S. Pat. No. 6,636,879 on Oct. 21, 2003, titled “Improved Space Allocation in a Write Anywhere File System.”       

     These documents are hereby incorporated by reference as if fully set forth herein. These documents are referred to as the “incorporated disclosures”. 
     Changes to the file system are tightly controlled to maintain the file system in a consistent state. The file system progresses from one self-consistent state to another self-consistent state. The set of self-consistent blocks on disk that is rooted by the root inode is referred to as a consistency point (CP). To implement consistency points, WAFL always writes new data to unallocated blocks on disk. It never overwrites existing data. A new consistency point occurs when the fsinfo block is updated by writing a new root inode for the inode file into it. Thus, as long as the root inode is not updated, the state of the file system represented on disk does not change. 
     The present invention also creates snapshots, which are virtual read-only copies of the file system. A snapshot uses no disk space when it is initially created. It is designed so that many different snapshots can be created for the same file system. Unlike prior art file systems that create a clone by duplicating the entire inode file and all of the indirect blocks, the present invention duplicates only the inode that describes the inode file. Thus, the actual disk space required for a snapshot is only the 128 bytes used to store the duplicated inode. The 128 bytes of the present invention required for a snapshot is significantly less than the many megabytes used for a clone in the prior art. 
     The present invention prevents new data written to the active file system from overwriting “old” data that is part of a snapshot(s). It is necessary that old data not be overwritten as long as it is part of a snapshot. This is accomplished by using a multi-bit free-block map. Most prior art file systems use a free block map having a single bit per block to indicate whether or not a block is allocated. The present invention uses a block map having 32-bit entries. A first bit indicates whether a block is used by the active file system, and 20 remaining bits are used for up to 20 snapshots, however, some bits of the 31 bits may be used for other purposes. 
     Lexicography 
     
         
         
           
             The following terms refer or relate to aspects of the invention as described below. The descriptions of general meanings of these terms are not intended to be limiting, only illustrative. 
             data—In general, any information. With regard to a storage device or file system, any information stored in the storage device or file system, including but not limited to application programs and data, multimedia data, organizational data for the storage device or file system, etc. 
             organizational data—In general, data that specifies the layout of other data in a file system. In a Write Anywhere File system Layout (WAFL) design, the organizational data includes a root inode that points either directly or indirectly (i.e., through other inodes) to blocks of data for all files in the file system. In a WAFL design, all data including the organizational data (and thus root inode and other inodes) are stored in blocks. 
             inode—In general, an information node. In a W AFL design, an information node that contains data about other blocks in the file system. 
             self-consistent (in the context of a file system)—In general, a file system is self-consistent when the data stored in the file system, including data about the organization of the file system, constitutes a valid file system image. 
             consistency point—In general, a consistency point refers either to (a) a time when a file system is self-consistent; or to (b) a set of data in a file system at a time of a consistency point. 
             snapshot—In general, a snapshot is a written record of the data maintained by the file system at a time of a consistency point. Although in a preferred embodiment, each snapshot is both (a) maintained in a format similar to the active file system and (b) is referenceable using the file system namespace, there is no particular limitation of the invention to require either of those conditions. 
             active file system—In general, an active file system is a set of data that can be accessed and modified. 
             file system hierarchy—In general, a file system hierarchy refers to either (a) an organization of data into a namespace, or (b) a set of data blocks and their interconnections used to record and access information, whether data or metadata, being maintained on a storage device. 
           
         
       
    
     As noted above, these descriptions of general meanings of these terms are not intended to be limiting, only illustrative. Other and further applications of the invention, including extensions of these terms and concepts, would be clear to those of ordinary skill in the art after perusing this application. These other and further applications are part of the scope and spirit of the invention, and would be clear to those of ordinary skill in the art, without further invention or undue experimentation. 
     Snapshots and Active File Systems 
       FIG. 1  illustrates creation of a snapshot that can be converted into an active file system according to the invention. 
     File system  100  in  FIG. 1  resides on one or more storage devices, for example hard disk drives, CD-ROMs, or other devices. In a preferred embodiment, file system  100  is a W AFL system, although this does not have to be the case. W AFL file systems are described in detail in the incorporated disclosures. 
     File system  100  includes root inode  110  and data  120 , as well as other data. All of the inodes and data in file system  100  preferably are stored in blocks, although this also does not have to be the case. 
     Root inode  110  stores parts of the organizational data for file system  100 . In particular, root inode  110  points to data and to other inodes and data that in turn point to data for all information stored in file system  100 . Thus, any information stored in a file system  100  can be reached by starting at root inode  110 . 
     Snapshot  130  has been formed from file system  100 . In  FIG. 1 , elements of snapshot  130  are shown using dashed lines to assist in distinguishing those elements from file system  100 . According to a preferred embodiment of the invention, the snapshot can be formed by simply copying root inode  110  to snapshot root inode  140  at a consistency point for file system  100 . In some embodiments, additional organizational data may have to be copied. Then, as long as all of the data and inodes pointed to by root inode  110  (and any other copied organizational data) are preserved, snapshot root inode  140  will point to a valid copy of file system  100 . 
     After snapshot root inode  140  has been created, snapshot  130  and file system  100  actually share data on the storage device or devices. Thus, snapshot  130  preferably includes the same physical data  120  on the storage device or devices as file system  100 , as indicated by the duel solid and dashed borders around data  120  in  FIG. 1 . In other words, the snapshot and the file system overlap. This allows for rapid creation of snapshot  130  with efficient use of storage space and other system resources. 
     File system  100  preferably includes snapshot data  150  that points to snapshots of file system  100 . In particular, pointers  160  in the snapshot data preferably point to root inodes of those snapshots. 
     Snapshot  130  also preferably includes snapshot data  170  that points to other snapshots. However, snapshot data  170  of snapshot  130  can be different from snapshot data  150  of file system  100  because snapshot  130  preferably does not point to itself. This difference is shown in  FIG. 1  by the cutout of snapshot  130  around snapshot data  150  in file system  100 . 
     Preferably, a snapshot of a file system according to the invention includes a complete hierarchy for file system data, separate and apart from active file system data for the active file systems. This hierarchy is included in the root inode for the snapshot and possibly in other nodes and data copied for the snapshot (not shown). 
     There is no particular requirement for the file system hierarchies for a snapshot to duplicate the name space originally used for the associated active file system. In one preferred embodiment, file names in a snapshot&#39;s root inode (and other organizational data) can be compressed using a hash code or other technique, so as to minimize the organizational data that must be stored for each snapshot. However, in an alternative embodiment, in some circumstances possibly preferable, it might be superior to maintain the original name space and other organizational data for each snapshot in a form relatively easy to read by a human user. This might have the salutary effect of aiding human users with backup and restore operations based on such snapshots. 
       FIG. 2  illustrates divergence of an active file system from a snapshot of that file system. 
     Because file system  100  is active, a mechanism must be provided for changing data in the file system. However, in order to maintain the integrity of snapshot  130 , data pointed to by snapshot root inode  140  must be preserved. Thus, for example, when data  120  is changed in file system  100 , modified data  120 ′ is stored in the storage device or devices. Root inode  110  of file system  100  and any intervening inodes and organizational data are updated to point to modified data  120 ′. In addition, the unmodified data  120  is preserved on the storage device or devices. Snapshot root inode  140  continues to point to this unmodified data, thereby preserving the integrity of snapshot  130 . 
     Likewise, when data is deleted from active file system  100 , pointers to that data are removed from the file system. However, the data itself is preserved if it is included in snapshot  130 . (This data can actually be deleted when the snapshot itself is removed.) 
     In actual practice, changes to root inode  110 , other inodes, and data for many changes to file system  100  are accumulated before being written to the storage device or devices. After such changes have been written, file system  100  is self-consistent (i.e., at a consistency point). Preferably, snapshots are only made at such consistency point. 
     According to the invention, snapshot  130  can be converted into a new active file system by making the snapshot writable. In order to modify data in a writable snapshot  130 , modified data is written to the storage device or devices. Root inode  140  and any intervening inodes and organizational data pointing to the modified data are updated. Furthermore, an unmodified copy of the data is preserved if it is still included in file system  100 . This process is substantially identical to the process that occurs when modifications are made to file system  100 , only the unmodified data that is preserved is data pointed to by root inode  110 . 
     In other words, when changes are made to the first active file system (e.g., file system  100 ), modified data is recorded in the first active file system in a location that is not shared with the second active file system (e.g., writable snapshot  130 ). Likewise, when changes are made to the second active file system, modified data is recorded in the second active file system in a location that is not shared with the first active file system. As a result, changes made to the first active file system not reflected in the second active file system, and changes made to the second active file system not reflected in the first active file system. 
     When created, snapshot  130  substantially overlaps file system  100 . If the snapshot is made writable shortly after its creation, the new active file system formed by the writable snapshot will initially share almost all of its data with the existing active file system. As a result, the invention allows for creation of an entire new active file system with efficient utilization of resources such as processing time and storage space. 
     The process of storing modified data and preserving unmodified data causes file system  100  and snapshot  130  (whether read-only or writable) to diverge from one another. This divergence is representationally shown in  FIG. 2  by a reduction in overlap between file system  100  and snapshot  130 . 
       FIG. 3  illustrates the relationship between the active file system and the snapshot in  FIG. 2 . This type of diagram provides a simplified view of the relationship between file systems and their snapshots. In  FIG. 3 , file system  100  points to snapshot  130 . In addition, both file system  100  and snapshot  130  point to other snapshots (not shown). 
       FIG. 4  illustrates a chain of snapshots that can be converted into active file systems according to the invention. In this figure, second snapshot  180  has been created from file system  100 . Because snapshot  100  still pointed to snapshot  130  at the time of the creation of the second snapshot, snapshot  180  includes snapshot data  190  that points to snapshot  130 . 
     Either or both of snapshots  130  and  180  can be turned into active file systems by making those snapshots writable. As a data is written to any of the active file systems (i.e., file system  100 , writable snapshot  130 , or writable snapshot  180 ), the file systems will diverge from one another. 
       FIG. 5  illustrates the relationship between the active file system and the snapshots in  FIG. 4 . In  FIG. 5 , file system  100  points to snapshots  130  and  180 . Likewise, snapshot  180  points to snapshot  130 , which in turn can point to another snapshot or snapshots. 
       FIG. 6  illustrates a snapshot that has been converted into an active file system according to the invention. In this figure, snapshot  180  has been turned into active file system  180 ′ by being made writable. Because this new active file system can be modified, it no longer represents a true snapshot of file system  100 . As a result, the snapshot pointer to snapshot  180  in snapshot data  150  of file system  100  has been severed, for example by being deleted. 
       FIG. 7  illustrates the relationship between the active file system, new active file system, and snapshot in  FIG. 6 . In this figure, active file system  100  points to snapshot  130 . Likewise, active file system  180 ′ also points to snapshot  130 . As discussed above, file system  100  preferably no longer includes a snapshot pointer to snapshot  180 . However, file system  100  can still included a pointer to file system  180 ′, for example to allow traversal from one file system to the other. This inter-file-system pointer is shown as a dashed line in  FIG. 7  to distinguish it from a snapshot pointer. 
       FIG. 8  illustrates a more complex chain of snapshots that can be converted into active file systems according to the invention. In  FIG. 8 , file system  800  is an active file system. Four snapshots have been made of this file system. Snapshot  810  is the oldest, snapshot  820  is the next oldest, snapshot  830  is the next oldest after its snapshot  820 , and snapshot  840  is the newest. Any snapshots older than snapshot  810  have been deleted, thereby freeing up storage space that was occupied by data that was not overlapped by any of the other snapshots or the active file system. Each of snapshots  810  to  840  can be turned into an active file system by being made writable. 
       FIG. 9  illustrates the chain shown in  FIG. 8  with one of the snapshot converted into an active file system according to the invention. 
     In  FIG. 9 , snapshot  830  has been converted into active file system  830 ′ in which data can be modified, added, and deleted. As a result, file system  800  preferably no longer points to snapshot  830  as a snapshot. Active file system  830 ′ can continue to point to snapshots  810  and  820 . 
       FIG. 10  illustrates some more possible relationships between plural active file systems and their associated snapshots according to the invention. 
     The top portion of  FIG. 10  corresponds to  FIG. 9 , except that additional snapshots have been made from the active file systems. Thus, snapshot  1000  has been made of file system  800 , and snapshot  1010  has been made of file system  830 ′. In addition, snapshot  810  has been deleted to free up space on the storage device or devices. 
     Both of active file systems  800  and  830 ′ can trace back to a common snapshot  820 . However, when that snapshot is deleted, the active file systems will no longer share a common snapshot. This situation has occurred with respect to file system  1020  and snapshots  1030  to  1050 . This arrangement illustrates that it is possible to have a “forest” (i.e., a collection of unconnected trees) formed by the links between active file systems and their associated snapshots, all on one storage device or set of storage devices. Despite the fact that the file systems and their snapshots no longer point to a common snapshot, these snapshots and even the active file systems could still share some data (i.e., overlap), thereby preserving the efficiency of the invention. 
     In the foregoing discussion, new active file systems are created from snapshots. However, the invention does not require the actual creation of a snapshot in order to create a new active file system. Rather, all that is required is creation of structures along the lines of those found in a snapshot, namely organizational data along the lines of that found in a snapshot&#39;s root inode, along with preservation of the data pointed to by that organizational data. 
     Furthermore, the invention is not limited to the particular arrangements discussed above. Rather, those arrangements illustrate some possible types of relationships between active file systems, snapshots, and new active file-systems. Other arrangements are possible and are within the scope of the invention. 
     System Elements 
       FIG. 11  shows a block diagram of a storage system including plural active file systems according to the invention. 
     A system  1100  includes at least one file system processor  1110  (i.e., controller) and at least one storage device  1120  such as a hard disk or CD-ROM drive. The system also preferably includes interface  1130  to at least one computing device or network for receiving and sending information. In an alternative embodiment, processor  1100  is the processor for a computing device connected to the storage system via interface  1130 . 
     Processor  1110  performs the tasks associated with the file system, as described herein, under control of program and data memory, the program and data memory including appropriate software for controlling processor  1110  to perform operations on storage device  1120  (and possibly for controlling storage device  1120  to cooperate with processor  1110 ). 
     In a preferred embodiment, at least one such storage device  1120  includes one or more boot records  1140 . Each boot record  1140  includes two or more (preferably two) entries designating a root data block (i.e., inode) in a file system hierarchy for an active file system. Where there is a single active file system, there preferably is a single such boot record; where there is more than one such active file system, there preferably is more than one such boot record. 
     As noted above, more than one active file system might be present in storage device  1120 . In such cases, the file system maintainer (i.e., processor  1110  operating under program control) preferably will designate and orderly maintain more than one boot record  1140 , one for each such active file system. 
     Read-only snapshots also can be present in storage device  1120 . In this case, pointers from active file systems to snapshots and from snapshots to other snapshots are stored in the storage device, as discussed above. 
     High Availability 
       FIG. 12  shows a block diagram of a file system cluster including multiple concurrent active file systems being used by multiple concurrent file servers according to the invention. 
     A file system cluster includes a plurality of file system processors  1200  and one or more file system disks  1210 . In a preferred embodiment, each such processor  1200  is disposed for operating as a file server, capable of receiving file server requests and making file server responses, such as using a known file server protocol. In a preferred embodiment, the one or more file system disks  1210  include a plurality of such disks, so that no individual disk  1210  presents a single point of failure for the entire highly-available cluster. The Write Anywhere File System Layout (WAFL), which preferably is used with the invention, incorporates such an arrangement. 
     As discussed above, the plurality of processors  1200  can maintain multiple parallel writeable active file systems  1210 , along with all associated snapshots for those parallel writeable active file systems. The active file systems and snapshots can be maintained on the same set of disks  1220 . Thus, the set of processors  1200  and the set of disks  1220  can provide a highly available cluster without need for substantial duplication of resources. 
     Alternative Embodiments 
     The invention can be embodied in methods for creating and maintaining plural active file systems, as well as in software and/or hardware such as a storage device or devices that implement the methods, and in various other embodiments. 
     In the preceding description, a preferred embodiment of the invention is described with regard to preferred process steps and data structures. However, those skilled in the art would recognize, after perusal of this application, that embodiments of the invention may be implemented using one or more general purpose processors or special purpose processors adapted to particular process steps and data structures operating under program control, that such process steps and data structures can be embodied as information stored in or transmitted to and from memories (e.g., fixed memories such as DRAMs, SRAMs, hard disks, caches, etc., and removable memories such as floppy disks, CD-ROMs, data tapes, etc.) including instructions executable by such processors (e.g., object code that is directly executable, source code that is executable after compilation, code that is executable through interpretation, etc.), and that implementation of the preferred process steps and data structures described herein using such equipment would not require undue experimentation or further invention. 
     Furthermore, although preferred embodiments of the invention are disclosed herein, many variations are possible which remain within the content, scope and spirit of the invention, and these variations would become clear to those skilled in the art after perusal of this application.