Unlimited file system snapshots and clones

[0001] This application claims benefit of U.S. Provisional Application Ser. No. 60/734,039 filed on Nov. 4, 2005, entitled “UNLIMITED FILESYSTEM SNAPSHOTS AND CLONES” in the names of Matthew A. Ahrens, Mark J. MAYBEE, and Jeffrey S. Bonwick.

[0002] The present application contains subject matter that may be related to the subject matter in the following U.S. patent applications, which are all assigned to a common assignee: “Method and Apparatus for Self-Validating Checksums in a File System” (application Ser. No. 10/828,573) filed on Apr. 24, 2004; “Method and Apparatus for Dynamic Striping” (application Ser. No. 10/828,677) filed on Apr. 21, 2004; “Method and Apparatus for Vectored Block-Level Checksum for File System Data Integrity” (application Ser. No. 10/828,715) filed on Apr. 21, 2004; “Method and Apparatus for Identifying Tampering of Data in a File System” (application Ser. No. 10/853,874) filed on May 26, 2004; “Method and System for Detecting and Correcting Data Errors Using Checksums and Replication” (application Ser. No. 10/853,837) filed on May 26, 2004; “Method and System for Detecting and Correcting Data Errors Using Data Permutations” (application Ser. No. 10/853,870) filed on May 26, 2004; “Method and Apparatus for Compressing Data in a File System” (application Ser. No. 10/853,868) filed on May 26, 2004; “Gang Blocks” (application Ser. No. 10/919,878) filed on Aug. 17, 2004; “Method and Apparatus for Enabling Adaptive Endianness” (application Ser. No. 10/919,886) filed on Aug. 17, 2004; “Automatic Conversion of All-Zero Data Storage Blocks into File Holes” (application Ser. No. 10/853,915) filed on May 26, 2004; “Multiple Replication Levels with Pooled Devices” (application Ser. No. 60/733,848) filed on Nov. 4, 2005; “Multiple Replication Levels with Pooled Devices” (Attorney Docket No. 03226/750001; SUN060258) filed on Apr. 19, 2006; “Method and System Supporting Per-File and Per-Block Replication” (Attorney Docket No. 03226/751001; SUN060259) filed on Apr. 19, 2006; “Ditto Blocks” (Attorney Docket No. 03226/761001; SUN060269) filed on Apr. 19, 2006; and “Method and System for Adaptive Metadata Replication” (Attorney Docket No. 03226/762001; SUN060270).

[0003] A typical operating system includes a file system. The file system provides a mechanism for the storage and retrieval of files and a hierarchical directory structure for the naming of multiple files. More specifically, the file system stores information provided by the user (i.e., data) and information describing the characteristics of the data (i.e., metadata). The file system also provides extensive programming interfaces to enable the creation and deletion of files, reading and writing of files, performing seeks within a file, creating and deleting directories, managing directory contents, etc. In addition, the file system also provides management interfaces to create and delete file systems.

[0004] File systems are typically controlled and restricted by operating system parameters. For example, most operating systems limit the maximum number of file names that can be handled within their file system. Some operating systems also limit the size of files that can be managed under a file system.

[0005] An application, which may reside on the local system (i.e., computer) or may be located on a remote system, uses files as an abstraction to address data. Conventionally, this data is stored on a storage device, such as a disk.

[0006] To access a file, the operating system (via the file system) typically provides file manipulation interfaces to open, close, read, and write the data within each file. More specifically, the file system stores data on the storage device by managing the allocation of space within the storage device. Typically, the volume manager provides space which is managed by the file system. Two common types of file system space allocation strategies are known as block-based allocation and extent-based allocation. Block-based allocation creates incremental disk space for each file, each time the file is extended (i.e., modified via a write request to add information). Whereas extent-based allocation creates a large series of contiguous blocks (i.e., extents) each time the file exhausts the space available in the last extent of the file.

[0007] When allocating space, both block-based and extent-based allocation use space provided by the volume manager. The volume manager allows multiple physical disks to be used as a single volume (i.e., a virtual disk) to provide larger consolidated storage sizes and simpler management. The volume manager allows users to organize data along volume boundaries (i.e., each volume has physical disk space allocated to the volume such that the volume is tied only to that dedicated physical disk). The volume manager is typically implemented as a separate layer between the physical disks and the file system, and is presented to the user as a virtual disk device. In other words, volume managers organize the collections of physical devices (e.g., disks) into virtual devices. Additionally, the space allocated within the volume manager is handled by the file system. Consequently, the volume manager is not aware of which blocks within the available storage space are in use and which blocks are free for data to be stored.

[0008] Further, file systems may be mounted on the virtual disk devices. Thus, physical disks are partitioned and allocated to multiple virtual disk devices, and each virtual disk device is capable of having a file system that exclusively uses that particular virtual disk device. A request to access a file is typically performed by an application, via the file system, using a file name and logical offset. This file name and logical offset (i.e., the manner in which applications express file operation requests) corresponds to a location within the virtual disk device. Subsequently, the request is translated to physical disk space on the storage device by the volume manager, allowing the user of the application to access the data within a particular file.

[0009] In general, in one aspect, the invention relates to a system. The system includes a file system configured to create a snapshot of a hierarchical block tree (HBT) and a storage pool. After the snapshot has been created, the storage pool includes the snapshot comprising a copy of a first version of a root block, the HBT comprising a second version of the root block, and wherein the copy of the first version of the root block is created prior to overwriting the first version of the root block with the second version of the root block, wherein the second version of the root block comprises references to a first block and a second block, and wherein the copy of the first version of the root block comprises a reference to the first block and no reference to the second block.

[0010] In general, in one aspect, the invention relates to a computer readable medium comprising computer executable instructions for creating a snapshot of a hierarchical block tree (HBT). The executable instructions including instructions for obtaining a copy of a first version of a root block of the HBT prior to overwriting the first version of the root block with a second version of the root block, instructions for designating the copy of a first version of a root block as a root block of the snapshot, instructions for associating a dead list of the HBT with the snapshot, instructions for overwriting the first version of the root block with a second version of the root block, and instructions for associating the HBT with an empty dead list, wherein the HBT comprises the second version of the root block.

[0011] Other aspects of the invention will be apparent from the following description and the appended claims.

[0012] FIG. 1 shows a system architecture in accordance with an embodiment of the invention.

[0013] FIG. 2 shows a storage pool allocator in accordance with an embodiment of the invention.

[0014] FIG. 3 shows a hierarchical block tree in accordance with an embodiment of the invention.

[0015] FIG. 4 shows a hierarchical block tree, a snapshot, and a clone in accordance with an embodiment of the invention.

[0016] FIGS. 5A-5F show examples to illustrate one or more embodiments of the invention.

[0017] FIG. 6 shows a flow chart in accordance with an embodiment of the invention.

[0018] FIG. 7 shows an example of freeing blocks in accordance with an embodiment of the invention.

[0019] FIG. 8 shows a flow chart in accordance with an embodiment of the invention.

[0020] FIG. 9 shows an example of freeing blocks in accordance with an embodiment of the invention.

[0021] FIG. 10 shows a computer system in accordance with an embodiment of the invention.

[0022] Specific embodiments of the invention will now be described in detail with reference to the accompanying figures. Like elements in the various figures are denoted by like reference numerals for consistency. Further, the use of “ST” in the drawings is equivalent to the use of “Step” in the detailed description below.

[0023] In the following detailed description of one or more embodiments of the invention, numerous specific details are set forth in order to provide a more thorough understanding of the invention. However, it will be apparent to one of ordinary skill in the art that the invention may be practiced without these specific details. In other instances, well-known features have not been described in detail to avoid obscuring the invention.

[0024] In general, embodiments of the invention relate to a method and apparatus for creating snapshots of a hierarchical block tree. Further, embodiments of the invention relate to a method and apparatus for creating clones of the snapshots.

[0025] FIG. 1 shows a system architecture in accordance with one embodiment of the invention. The system architecture includes an operating system (103) interacting with a file system (100), which in turn interfaces with a storage pool (108). In one embodiment of the invention, the file system (100) includes a system call interface (102), a data management unit (DMU) (104), and a storage pool allocator (SPA) (106).

[0026] The operating system (103) typically interfaces with the file system (100) via a system call interface (102). The operating system (103) provides operations (101) for users to access files within the file system (100). These operations (101) may include read, write, open, close, etc. In one embodiment of the invention, the file system (100) is an object-based file system (i.e., both data and metadata are stored as objects). More specifically, the file system (100) includes functionality to store both data and corresponding metadata in the storage pool (108). Thus, the aforementioned operations (101) provided by the operating system (103) correspond to operations on objects.

[0027] More specifically, in one embodiment of the invention, a request to perform a particular operation (101) (i.e., a transaction) is forwarded from the operating system (103), via the system call interface (102), to the DMU (104). In one embodiment of the invention, the DMU (104) translates the request to perform an operation on an object directly to a request to perform a read or write operation at a physical location within the storage pool (108). More specifically, the DMU (104) represents the objects as data blocks and indirect blocks as described in FIG. 3 below. Additionally, in one embodiment of the invention, the DMU (104) includes functionality to group related work (i.e., modifications to data blocks and indirect blocks) into I/O requests (referred to as a “transaction group”) allowing related blocks to be forwarded to the SPA (106) together. The SPA (106) receives the transaction group from the DMU (104) and subsequently writes the blocks into the storage pool (108). The operation of the SPA (106) is described in FIG. 2 below.

[0028] In one embodiment of the invention, the storage pool (108) includes one or more physical disks (110A-110N). Further, in one embodiment of the invention, the storage capacity of the storage pool (108) may increase and decrease dynamically as physical disks are added and removed from the storage pool. In one embodiment of the invention, the storage space available in the storage pool (108) is managed by the SPA (106).

[0029] FIG. 2 shows the SPA (106) in accordance with one embodiment of the invention. The SPA (106) may include an I/O management module (200), a compression module (201), an encryption module (202), a checksum module (203), and a metaslab allocator (204). Each of these aforementioned modules are described in detail below.

[0030] As noted above, the SPA (106) receives transactions from the DMU (104). More specifically, the I/O management module (200), within the SPA (106), receives transactions from the DMU (104) and groups the transactions into transaction groups in accordance with one embodiment of the invention. The compression module (201) provides functionality to compress larger logical blocks (i.e., data blocks and indirect blocks) into smaller segments, where a segment is a region of physical disk space. For example, a logical block size of 8K bytes may be compressed to a size of 2K bytes for efficient storage. Further, in one embodiment of the invention, the encryption module (202) provides various data encryption algorithms. The data encryption algorithms may be used, for example, to prevent unauthorized access. In one embodiment of the invention, the checksum module (203) includes functionality to calculate a checksum for data (i.e., data stored in a data block) and metadata (i.e., data stored in an indirect block) within the storage pool. The checksum may be used, for example, to ensure data has not been corrupted.

[0031] As discussed above, the SPA (106) provides an interface to the storage pool and manages allocation of storage space within the storage pool (108). More specifically, in one embodiment of the invention, the SPA (106) uses the metaslab allocator (204) to manage the allocation of storage space in the storage pool (108).

[0032] In one embodiment of the invention, the storage space in the storage pool (108) is divided into contiguous regions of data, i.e., metaslabs. The metaslabs may in turn be divided into segments (i.e., portions of the metaslab). The segments may all be the same size, or alternatively, may be a range of sizes. The metaslab allocator (204) includes functionality to allocate large or small segments to store data blocks and indirect blocks. In one embodiment of the invention, allocation of the segments within the metaslabs is based on the size of the blocks within the I/O requests. That is, small segments are allocated for small blocks, while large segments are allocated for large blocks. The allocation of segments based on the size of the blocks may allow for more efficient storage of data and metadata in the storage pool by reducing the amount of unused space within a given metaslab. Further, using large segments for large blocks may allow for more efficient access to data (and metadata) by reducing the number of DMU (104) translations and/or reducing the number of I/O operations. In one embodiment of the invention, the metaslab allocator (204) may include a policy that specifies a method to allocate segments.

[0033] As noted above, the storage pool (108) is divided into metaslabs, which are further divided into segments. Each of the segments within the metaslab may then be used to store a data block (i.e., data) or an indirect block (i.e., metadata). FIG. 3 shows the hierarchical block tree (hereinafter referred to as a “HBT”) for storing data blocks and indirect blocks within the storage pool in accordance with one embodiment of the invention. In one embodiment of the invention, the HBT includes a root block (300), one or more levels of indirect blocks (302, 304, 306), and one or more data blocks (308, 310, 312, 314). In one embodiment of the invention, the location of the root block (300) is in a particular location within the storage pool. The root block (300) typically points to subsequent indirect blocks (302, 304, and 306). In one embodiment of the invention, indirect blocks (302, 304, and 306) may be arrays of block pointers (e.g., 302A, 302B, etc.) that, directly or indirectly, reference to data blocks (308, 310, 312, and 314). The data blocks (308, 310, 312, and 314) contain actual data of files stored in the storage pool. One skilled in the art will appreciate that several layers of indirect blocks may exist between the root block (300) and the data blocks (308, 310, 312, 314).

[0034] In contrast to the root block (300), indirect blocks and data blocks may be located anywhere in the storage pool (108 in FIG. 1). In one embodiment of the invention, the root block (300) and each block pointer (e.g., 302A, 302B, etc.) includes data as shown in the expanded block pointer (302B). One skilled in the art will appreciate that data blocks do not include this information; rather data blocks contain actual data of files within the file system.

[0035] In one embodiment of the invention, each block pointer includes a metaslab ID (318), an offset (320) within the metaslab, a birth value (322) of the block referenced by the block pointer, and a checksum (324) of the data stored in the block (data block or indirect block) referenced by the block pointer. In one embodiment of the invention, the metaslab ID (318) and offset (320) are used to determine the location of the block (data block or indirect block) in the storage pool. The metaslab ID (318) identifies a particular metaslab. More specifically, the metaslab ID (318) may identify the particular disk (within the storage pool) upon which the metaslab resides and where in the disk the metaslab begins. The offset (320) may then be used to reference a particular segment in the metaslab. In one embodiment of the invention, the data within the segment referenced by the particular metaslab ID (318) and offset (320) may correspond to either a data block or an indirect block. If the data corresponds to an indirect block, then the metaslab ID and offset within a block pointer in the indirect block are extracted and used to locate a subsequent data block or indirect block. The HBT may be traversed in this manner to eventually retrieve a requested data block.

[0036] In one embodiment of the invention, copy-on-write transactions are performed for every data write request to a file. Specifically, all write requests cause new segments to be allocated for the modified data. Therefore, the retrieved data blocks and indirect blocks are never overwritten (until a modified version of the data block and indirect block is committed). More specifically, the DMU writes out all of the modified data blocks in the HBT to unused segments within the storage pool. Subsequently, the DMU writes out the corresponding block pointers (within indirect blocks) to unused segments in the storage pool. In one embodiment of the invention, fields (i.e., metaslab ID, offset, birth, checksum) for the corresponding block pointers are populated by the DMU prior to sending an I/O request to the SPA. The indirect blocks containing the block pointers are typically written one level at a time. To complete the copy-on-write transaction, the SPA issues a single write that atomically changes (i.e., overwrites) the root block to reference the indirect blocks referencing the modified data block.

[0037] Using the infrastructure shown in FIGS. 1-3, the following discussion describes the creation of a snapshot of the HBT and the creation of a clone from the snapshot.

[0038] In one embodiment of the invention, the HBT corresponds to a group of blocks referenced, directly or indirectly, by a root block. As discussed above, as the blocks referenced by the root block are modified, the modified blocks are written to unused locations in the storage pool and the root block is modified to include references to the modified blocks.

[0039] A snapshot corresponds to a state of the HBT at a given time, where the state of the HBT corresponds to all blocks referenced, directly or indirectly, by the root block of the HBT at the aforementioned time.

[0040] In one embodiment of the invention, a clone corresponds to an HBT where the initial state of the clone is obtained from a snapshot of the HBT. Said another way, the clone corresponds to a pre-populated HBT where the clone initially includes only blocks referenced, directly or indirectly, by the root block of the HBT at the time the snapshot was created. In one embodiment of the invention, file system may also create snapshot(s) of the clones.

[0041] In one embodiment of the invention, the HBT and the clone may each be modified independently. For example, modifying the contents of the HBT will not affect the clone and vise versa. Further, the file system is configured to manage HBTs, snapshots and clones concurrently. For example, FIG. 4 shows a hierarchical block tree, a snapshot, and a clone in accordance with an embodiment of the invention. As shown in FIG. 4, each block (e.g., B1 (408), B2 (410), B3 (412), B4 (406)) may be referenced by, and therefore be a part of, the HBT (400), the snapshot (402), and the clone (404).

[0042] Specifically, the HBT (400) includes a second version of the root block R′ (418). The second version of the root block R′ (418) in turn references blocks B1 (408), B2 (410), and B3 (412). Further, the snapshot (402) includes a first version of the root block R (416). The first version of the root block R (416) in turn references blocks B1 (408) and B2 (410). Finally, the clone (404) includes a copy of the first version of the root block CR (i.e., the clone root block) (414). The clone root block CR (414) in turn references blocks B2 (408) and B4 (406).

[0043] As discussed above, the snapshot of the HBT correspond to the state of the HBT at a given time. Accordingly, in FIG. 4, the snapshot (402) corresponds to the state of the HBT (400) prior to the addition of block B3 (412) to the HBT (400). Similarly, as discussed above, the initial state of the clone corresponds to the snapshot. Accordingly, in FIG. 4, the initial state of the clone (404) (i.e., the blocks initially referenced by the clone root block CR (414)) are blocks B1 (406) and B2 (408).

[0044] Finally, as discussed above, the clone and the HBT may be modified independently of one another. As shown in FIG. 4, the clone (404) is modified to remove the reference to block B1 (408) and to add a reference to block B4 (406). The removal of the reference to block B1 (408) from the clone (404) did not affect the reference to block B1 (408) by the HBT (400).

[0045] In one embodiment of the invention, the HBT (400) and the snapshot (402) are each associated with their own dead list (not shown). In one embodiment of the invention, the dead list associated with the HBT (400) is initially empty. As the HBT is modified, the dead list associated with the HBT is updated to list all block pointers (along with the referenced birth time of the block) corresponding to blocks which are referenced in the snapshot (402), but are no longer referenced in the HBT (400). Further, the dead list associated with the snapshot (402) corresponds to the dead list associated with the HBT (400) at the time the snapshot was created.

[0046] In one embodiment of the invention, the clone is also associated with a dead list (not shown). When the clone (404) is initially created, its dead list is empty. As the clone (404) is modified, the dead list associated with the clone (404) is updated to list all block pointers (along with the referenced block's birth time) corresponding to blocks which are referenced in the snapshot (402), but are no longer referenced in the clone (404). Dead lists are further discussed below in FIGS. 7 and 8.

[0047] FIG. 5A-5F show examples to illustrate one or more embodiments of the invention. More specifically, FIGS. 5A-5F show an example of the creation of an HBT, a snapshot, and a clone in accordance with one embodiment of the invention. Referring to FIG. 5A, the HBT (500) initially includes a root block (R) and block (B1), where R references B1. Referring to FIG. 5B, HBT (500) is subsequently modified to include a reference to block (B2). In accordance with the copy-on-write mechanism implemented by the file system, R (in FIG. 5A) is overwritten with a modified copy of the root block (R′), where the R′ references both B1 and B2.

[0048] Referring to FIG. 5C, at some later point in time a snapshot (502) of HBT (500) is created. The snapshot (502) is created prior to modifying R′ to obtain R″, where R″ is a modified version of R′ and references B1, B2 and block (B3). As shown in FIG. 5C, the snapshot (502) includes a copy of R′ (denoted as R_c′). R_c′ references B1 and B2. Note that the snapshot (502) does not include an additional copy of B1 and B2.

[0049] Referring to FIG. 5D, HBT (500) is subsequently modified to include a reference to block (B4). In accordance with the copy-on-write mechanism implemented by the file system, R″ (in FIG. 5C) is overwritten with a modified copy of the root block (R″′), where the R″′ references both B1, B2, B3 and B4.

[0050] Referring to FIG. 5E, at some later point in time, a clone (504) is created from the snapshot (502). As shown in FIG. 5E, the clone (504) includes a copy of R′ (denoted as CR_c′). CR_c′ references B1 and B2. Note that the clone (504) does not include an additional copy of B1 and B2.

[0051] Finally, referring to FIG. 5F, HBT (500) is subsequently modified to delete a reference to B3 and to include a reference to block (B6). In accordance with the copy-on-write mechanism implemented by the file system, R″′ (in FIG. 5D) is overwritten with a modified copy of the root block (R″″), where the R″″ references both B1, B2, B4 and B6. In addition, the clone (504) is modified to delete a reference to B2 and to include a reference to block (B5). In accordance with the copy-on-write mechanism implemented by the file system, CR_c′ (in FIG. 5E) is overwritten with a modified copy of the root block (CR_c″), where the CR_c″ references both B1 and B5.

[0052] FIG. 6 shows a flow chart in accordance with an embodiment of the invention. More specifically, FIG. 6 shows a method for creating a snapshot in accordance with one embodiment of the invention.

[0053] Initially, the current root block of the HBT is copied (ST600). The copy of the current root block is subsequently associated with an administrator-chosen name for the snapshot (ST602). Said another way, the copy of the current root block is designated as the root block of the snapshot, where the snapshot is identified by the administrator-chosen name. The dead list associated with the HBT is subsequently associated with the snapshot (ST604), such that the dead list is no longer associated with the HBT. For example, referring to FIG. 5F, when clone (504) removes its reference to B2, then B2 is placed on the deadlist associated with clone (504).

[0054] The current root block is then overwritten with a new version of the root block to obtain a new HBT (ST606). The new HBT is subsequently associated with a new empty dead list (ST608). Finally, the snapshot (or more specifically the root block of the snapshot) is optionally linked to the new HBT (or more specifically the root block of the new HBT) (ST610). In one embodiment of the invention, the snapshot is linked to the HBT using a doubly-linked list.

[0055] In one embodiment of the invention, the clone of the snapshot is created using a method similar to one described for creating a snapshot in FIG. 6. However, instead of obtaining a copy of the current root block, the clone is created by obtaining a copy of the root block of the snapshot from which it was created. Further, unlike the dead list associated with the snapshot, the dead list associated with the clone is initially empty. Finally, the clone (or more specifically the root block of the clone) is linked to the snapshot from which it was created. However, unlike the link between the snapshot and the HBT, the link between the clone and the snapshot is an unidirectional link (typically a pointer) from the clone to the snapshot. Accordingly, one cannot traverse from the snapshot to the clone.

[0056] In one embodiment of the invention, when the clone is created, a reference count associated with the snapshot is incremented to reflect that a clone of the snapshot has been created. In one embodiment of the invention, the reference count associated with a snapshot is decremented each time a clone created from the snapshot is deleted. In one embodiment of the invention, the referenced count is used by the file system to determine whether the snapshot can be deleted. In one embodiment of the invention, the snapshot cannot be deleted if the reference count is greater than to a threshold value. In one embodiment of the invention, the threshold value is one.

[0057] As discussed above, each HBT, snapshot, and clone is associated with a dead list. In one embodiment of the invention, the contents of the dead list associated the HBT(s) and the contents of the dead list associated with the clone(s) may change over time, while the contents of the dead list associated with the snapshot(s) is static. The following discussion describes how the contents of the dead list associated the HBT(s) and the contents of the dead list associated with the clone(s) may change over time.

[0058] As discussed above, when the HBT is modified such that it no longer references a given block (e.g., the block is overwritten, or the object that contains it is freed), a determination must be made about whether the block can actually be freed (i.e., reclaimed for storing other data). A block can only be freed if and only if there are no other references to it (i.e., it is not referenced by any snapshot). In order to determine whether there are any references to the block, a comparison of the block's birth time with the birth time of the most recent snapshot (i.e., the most recently created snapshot of the HBT) is performed. In one embodiment of the invention, the most recent snapshot may be determined by traversing the linked list that links the root block of the HBT with the root blocks of its snapshots. The first snapshot encountered in the traversal corresponds to the most recent snapshot.

[0059] Returning to the discussion of how to determine whether there are any references to the block, if the birth time of the block is earlier than the birth time of the most recent snapshot, then, at a minimum, the most recent snapshot references the block and, thus, the block cannot be freed. If the block cannot be freed, then the block pointer associated with the block is placed on the dead list of the HBT. Alternatively, if the block's birth time is later than the birth time of the most recent snapshot, then none of the snapshots reference block and, thus, the block can be freed.

[0060] FIG. 7 shows an example of freeing blocks in accordance with an embodiment of the invention. As shown in FIG. 7, Block A (700) has a birth time that is earlier than the time the most recent snapshot (i.e., snapshot (704)) was created. Further, Block B (702) was born after the time the snapshot (706) was created. If the HBT (706) stops referencing Block A (700), Block A (700) cannot be freed because it was born before the snapshot (704) was created.

[0061] Accordingly, Block A is placed on the dead list associated with the HBT (700).

[0062] However, if the HBT (706) stops referencing Block B (702), then Block B (702) can be freed because it was born after the snapshot (704) was created and, thus, is not referenced by the snapshot (704).

[0063] In one embodiment of the invention, the file system includes functionality to delete any snapshot in the file system. Once a snapshot has been deleted (i.e., the user deletes the snapshot), a determination must be made about which blocks may be freed and which blocks must be maintained on a dead list prior to completing the deletion of the snapshot.

[0064] In one embodiment of the invention, in order to free a block that is referenced in the deleted snapshot, the following constraints must be met: (1) the block was born after the previous snapshot (i.e., the snapshot created immediately prior to the deleted snapshot), (2) the block was born before the deleted snapshot, (3) the block was placed on the dead list after the deleted snapshot was created, and (4) the block died (i.e., was placed on the dead list) before the next snapshot (i.e., the snapshot created immediately after the deleted snapshot) or the block was placed in the dead list associated with the HBT, if the next snapshot corresponds to the HBT. In one embodiment of the invention, if a given block satisfies all four of the aforementioned criteria, then the block is unique to the snapshot.

[0065] The blocks on the dead list associated with the next snapshot (or dead list associated with the HBT, if the next snapshot does not exist ) are those that meet constraints (2), (3) and (4) (i.e., the blocks live in the deleted snapshot, but are dead in the next snapshot).

[0066] FIG. 8 shows a flow chart in accordance with an embodiment of the invention. More specifically, FIG. 8 describes a method for determine which blocks of the deleted snapshot may be freed. Turning to FIG. 8, initially, the dead list associated with the next snapshot (or HBT) is obtained (ST800). A block pointer (BP) on the dead list is then selected (ST802). A determination is then made about whether the birth time of the block, referenced by the BP, is less than or equal to the birth time of the previous snapshot (ST804). In one embodiment of the invention, the birth time of the previous snapshot corresponds to the birth time of the root block of the previous snapshot.

[0067] If the birth time of the block, referenced by the BP, is less than or equal to the birth time of the previous snapshot, then the BP is added to the dead list associated with the deleted snapshot (ST806). If the birth time of the block referenced by the BP is greater than the birth time of the previous snapshot, then the block referenced by the BP is freed (i.e., the block referenced by the BP is now available to be overwritten by new data) (ST810). If there are any remaining BPs on the dead list to analyze then the method proceeds to ST802. Otherwise, the method proceeds to ST812. At ST812, the dead list associated with the next snapshot is deleted. Finally, the dead list associated with the deleted snapshot (which may have been modified in ST806) is associated with the next snapshot.

[0068] The method shown in FIG. 8 assumes that the dead list associated with the next snapshot includes at least one BP. However, if the dead list associated with the next snapshot does not include any BPs, then the method in FIG. 8 is not performed.

[0069] FIG. 9 shows an example of freeing blocks using the method described in FIG. 8, in accordance with an embodiment of the invention. In the example shown in FIG. 9, snapshot 2 (902) is deleted. Accordingly, prior to completing the deletion of snapshot 2 (902), the dead list (DL3) associated with the HBT (904) must be analyzed in accordance with the method described in FIG. 8.

[0070] Prior to analyzing DL3, the following discussion details which of the block pointers corresponding to Block A (906), Block B (908), Block C (910), and Block D (912) is included in DL3. With respect to Block A (906), Block A (906) was born before the snapshot 1 (900) and was deleted after snapshot 2 (902) was created. Thus, Block A (906) is included in DL3. With respect to Block B (908), Block B (908) was born after snapshot 1 (900) and was deleted after snapshot 2 (902) was created, thus, Block B (908) is also included in DL3.

[0071] With respect to Block C (912), Block C (912) was born before snapshot 1 (900) and was deleted after HBT (904) was created, thus, Block C (912) is included in DL3. Finally, with respect to Block D (914), Block D (914) was born before snapshot 1 (900) and was deleted before snapshot 2 (902) was created, thus, Block D is on the dead list (DL2) associated with snapshot 2 (902).

[0072] At this stage, DL3 includes Block A (906), Block B (908) and Block C (912). Using the method described in FIG. 8, Block A (906) and Block C (912) are placed on DL2 to obtain DL2′ (i.e., the result of modifying DL2 to include Block A (906) and Block C (912)) while Block B (908) is freed. The aforementioned results were obtained as follows. With respect to Block A (906), because Block A's birth time is earlier than snapshot 1's birth time, Block A (906) cannot be freed and, thus, is included in a DL2′. With respect to Block B (908), because Block B's birth time is later than snapshot 1's (900) birth time, Block B (908) can be freed. Finally, with respect to Block C (912), because Block C's birth time is earlier than snapshot 1 's birth time, Block C (912) cannot be freed and, thus, is also included in DL2′.

[0073] At this stage, the dead list (DL3) associated with HTB (904) is deleted and replaced with the dead list (DL2′) associated with HBT (904). Once HBT (904) is associated with DL2′, the file system may complete the deletion of snapshot 2 (902). Note that DL1 associated with Snapshot 1 (900) is not affected by the deletion of snapshot 2 (902).

[0074] In one embodiment of the invention, deleting a snapshot also includes removing the snapshot name from the file system and updating the links between the remaining snapshots and/or HBTs as appropriate.

[0075] In one embodiment of the invention, the file system supports “roll back” functionality. In one embodiment of the invention, roll back functionality allows a user to return the contents of the file system (i.e., the HBT) to the state corresponding to a selected snapshot. In one embodiment of the invention, the HBT is rolled back to a state corresponding to a selected snapshot by traversing the HBT and the appropriate snapshots (i.e., the snapshot created after the selected snapshot) and freeing the blocks that were born after the selected snapshot. In one embodiment of the invention, the blocks are freed using the method described above in FIG. 8.

[0076] In one embodiment of the invention, the file system implements a copy-on-write mechanism (as discussed above). As such, a block can only reference blocks that are the same age or older than it. Using this property, the aforementioned traversal of the HBT and appropriate snapshots may be optimized by not reading any blocks (or their associated braches) that have a birth time before the selected snapshot.

[0077] As discussed above, the clone is a HBT. Thus, the clone, like a HBT, may be associated with its own snapshots. However, when a clone is initially created, the previous snapshot of the clone (for the purpose of deleting the clone) corresponds to the snapshot from which the clone was created.

[0078] In one embodiment of the invention, in order to delete a clone, all the snapshots associated with the clone (i.e., the clone's snapshots) must be deleted. Once all the snapshots of the clone are deleted (using the snapshot deletion procedures described above), the clone itself is rolled back to the snapshot from which it was created. At this stage, there are no blocks that are unique to the clone and, thus, the clone can be removed from the file system.

[0079] While the above invention has been discussed with respect to a file system managing a single HBT with multiple snapshots and clones, the invention may be extended to include implementations in which there are multiple HBTs each of which is associated with multiple snapshots and clones.

[0080] The invention may be implemented on virtually any type of computer regardless of the platform being used. For example, as shown in FIG. 10 a networked computer system (1000) includes a processor (1002), associated memory (1004), a storage device (1006), and numerous other elements and functionalities typical of today's computers (not shown). The networked computer system (1000) may also include input means, such as a keyboard (1008) and a mouse (1010), and output means, such as a monitor (1012). The networked computer system (1000) is connected to a local area network (LAN) or a wide area network (e.g., the Internet) (not shown) via a network interface connection (not shown). Those skilled in the art will appreciate that these input and output means may take other forms. Further, those skilled in the art will appreciate that one or more elements of the aforementioned computer (1000) may be located at a remote location and connected to the other elements over a network. Further, the invention may be implemented on a distributed system having a plurality of nodes, where each portion of the invention (e.g., the storage pool, the SPA, the DMU, etc.) may be located on a different node within the distributed system. In one embodiment of the invention, the node corresponds to a computer system. Alternatively, the node may correspond to a processor with associated physical memory.

[0081] Further, software instructions to perform embodiments of the invention may be stored on a computer readable medium such as a compact disc (CD), a diskette, a tape, a file, or any other computer readable storage device.

[0082] While the invention has been described with respect to a limited number of embodiments, those skilled in the art, having benefit of this disclosure, will appreciate that other embodiments can be devised which do not depart from the scope of the invention as disclosed herein. Accordingly, the scope of the invention should be limited only by the attached claims.