Instant snapshot

• US 20020083037A1
• Filed: 08/17/2001
• Published: 06/27/2002
• Est. Priority Date: 08/18/2000
• Status: Active Grant

• Current Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Original Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Inventors: Edwards, John, Lewis, Blake, Viswanathan, Srinivasan
• Granted Patent: US 7,454,445 B2
• Time in Patent Office: Days
• US Class Current: 707/1
• CPC Class Codes: G06F 11/14 Error detection or correction of the data by redundancy in operation G06F11/16 takes precedence
• CPC Class Codes: G06F 11/1435 using file system or storage system metadata
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99956 File allocation

Abstract

The invention provides an improved method and apparatus for creating a snapshot of a file system. In a first aspect of the invention, a “copy-on-write” mechanism is used. An effective snapshot mechanism must be efficient both in its use of storage space and in the time needed to create it because file systems are often large. The snapshot uses the same blocks as the active file system until the active file system is modified. Whenever a modification occurs, the modified data is copied to a new block and the old data is saved (henceforth called “copy-on-write”). In this way, the snapshot only uses space where it differs from the active file system, and the amount of work required to create the snapshot is small. In a second aspect of the invention, a record of which blocks are being used by the snapshot is included in the snapshot itself, allowing effectively instantaneous snapshot creation and deletion. In a third aspect of the invention, the state of the active file system is described by a set of metafiles; in particular, a bitmap (henceforth the “active map”) describes which blocks are free and which are in use. The inode file describes which blocks are used by each file, including the metafiles. The inode file itself is described by a special root inode, also known as the “fsinfo block”. The system begins creating a new snapshot by making a copy of the root inode. This copy of the root inode becomes the root of the snapshot. The root inode captures all required states for creating the snapshot such as the location of all files and directories in the file system, it. During subsequent updates of the active file system, the system consults the bitmap included in the snapshot (the “snapmap”) to determine whether a block is free for reuse or belongs to the snapshot. This mechanism allows the active file system to keep track of which blocks each snapshot uses without recording any additional bookkeeping information in the file system. In a fourth aspect of the invention, a snapshot can also be deleted instantaneously simply by discarding its root inode. Further bookkeeping is not required, because the snapshot includes it'"'"'s own description. In a fifth aspect of the invention, the performance overhead associated with the search for free blocks is reduced by the inclusion of a summary file. The summary file identifies blocks that are used by at least one snapshot; it is the logical OR of all the snapmap files. The write allocation code decides whether a block is free by examining the active map and the summary file. The active map indicates whether the block is currently in use in the active file system. The summary file indicates whether the block is used by any snapshot. In a sixth aspect of the invention, the summary file is updated in the background after the creation or deletion of a snapshot. This occurs concurrently with other file system operations. Two bits are stored in the file system “fsinfo block” for each snapshot. These two bits indicate whether the summary file needs to be updated using the snapshot'"'"'s snapmap information as a consequence of its creation or deletion. When a block is freed in the active file system, the corresponding block of the summary file is updated with the snapmap from the most recently created snapshot, if this has not already been done. An in-core bit map records the completed updates to avoid repeating them unnecessarily. This ensures that the combination of the active bitmap and the summary file will consistently identify all blocks that are currently in use. Additionally, the summary file is updated to reflect the effect of any recent snapshot deletions when freeing a block in the active file system. This allows reuse of blocks that are now entirely free. After updating the summary file following a snapshot creation or deletion, the corresponding bit in the fsinfo block is adjusted. In a seventh aspect of the invention, the algorithm for deleting a snapshot involves examining the snapmaps of the deleted snapshot and the snapmaps of the next oldest and next youngest snapshot. A block that was used by the deleted snapshot but is not used by its neighbors can be marked free in the summary file, as no remaining snapshot is using it. However, these freed blocks cannot be reused immediately, as the snapmap of the deleted snapshot must be preserved until summary updating is complete. During a snapdelete, free blocks are found by using the logical OR of the active bitmap, the summary file, and the snapmaps of all snapshots for which post-deletion updating is in progress. In other words, the snapmap of the deleted snapshot protects the snapshot from reuse until it is no longer needed for updating. In the preferred embodiment, the invention is operative on WAFL file system. However, it is still possible for the invention to be applied to any computer data storage system such as a database system or a store and forward system such as cache or RAM if the data is kept for a limited period of time.

Claims

1. A method for capturing the contents of the files and directories in a file system, said file system comprising a set of storage blocks in a mass storage system including steps for

recording an active map in said file system of said storage blocks not available for writing data;

recording a consistency point in said file system including a consistent version of said file system at a previous time, said consistency point including a copy of said active map at said previous time; and

refraining from writing data to storage blocks in response to said active map, and at least one of said copy of said active map at said previous time.

2. A method as in claim 1, wherein said step for refraining includes determining a logical union of said storage blocks used by one or more of said copies of said active map at said previous time.

3. A method as in claim 1, wherein said step for refraining includes determining a subset of said storage blocks used by one or more of said copies of said active map at said previous time.

4. A method as in claim 1, wherein said file system is a WAFL file system.

5. A method as in claim 1, wherein said active map at said previous time is a snapmap.

6. A method as in claim 1 and 5, including removing a root inode of said snapmap using a snap delete.

7. A method as in claim 6, including steps for determining not to write to a block after said step, provided the previous or next snapmap uses said block.

8. A method as in claim 1, including a copy-on-write mechanism for copying modified data to a new block and saving old data in a current data block.

9. A method for capturing the contents of the files and directories in a file system, said file system comprising a set of storage blocks in a mass storage system including

recording a consistency point in said file system including a consistent version of said file system at a previous time, said consistency point including a copy of said active map at said previous time;

and

returning to said file system at a previous time using said consistent version of said file system following an unintended deletion or modification.

10. A method as in claim 9, wherein said consistent version includes a pointer to a previous root block of the inode file.

11. A method as in claim 9, wherein said file system is a WAFL file system.

12. A method as in claim 9, wherein said active map at said previous time is a snapmap.

13. A method as in claim 9 and 12, including a snapdelete method for removing a root inode of said snapmap.

14. A method as in claim 13, including steps for determining not to write to a block after said snapdelete method provided a previous or next snapmap uses said block.

15. A method as in claim 9, including a copy-on-write mechanism for copying modified data to a new block and saving old data in a current data block.

17. A method as in claim 16, including retrieving said file system at a previous time using a pointer.

18. A method as in claim 16, wherein said pointer corresponds to a root block of said file system at a previous time.

19. A method as in claim 16, wherein said file system is a WAFL file system.

20. A method as in claim 16, wherein said active map at said previous time is a snapmap.

21. A method as in claim 16 and 20, including a snapdelete method for removing a root inode of said snapmap.

22. A method as in claim 20, including not writing to a block after said snapdelete method provided a previous or next snapmap uses said block.

23. A method as in claim 16, including a copy-on-write mechanism for copying modified data to a new block and saving old data in a current data block.

26. A method as in claim 25, including making write allocation decisions in response to said summary map.

27. A method as in claim 25, wherein

said set of snapshots includes at least two said snapshots;

and

a result of said computing includes an indicator of a union of all blocks indicated by at least two said copies of earlier active maps included in said set of snapshots.

28. A method as in claim 25, wherein

said set of snapshots includes at least two said snapshots;

and

said computing includes performing a bitwise logical operation on at least two said copies of earlier active maps included in said set of snapshots.

29. A method as in claim 25, including

making write allocation decisions both in response to a current active map and in response to said summary map.

30. A method as in claim 25, including

computing a combination of a current active map and said summary map;

and

making write allocation decisions in response to a result of said computing.

31. A method as in claim 25, including, for a selected portion of said summary map

identifying a set of snapshots created since a recent update of said selected portion;

and

updating said selected portion in response to only a most recent one of said snapshots.

16. A method for saving previous versions of an active file system including the contents of the files and directories in a file system, said file system comprising a set of storage blocks in a mass storage system including steps for

writing modified files to unused data blocks;

keeping previous files in currently occupied blocks; and

recording a consistency point in said file system including a consistent version of said file system at a previous time, said consistency point including a copy of said active map at said previous time;

24. A method of operating a file system, said file system including an active map of information indicating in-use and free blocks, said file system maintaining a set of snapshots, each snapshot including a representation of said file system as it was at an earlier time, said method including

making write allocation decisions in response to a copy of an earlier active map included in at least one of said snapshots.

25. A method of operating a file system, said file system including an active map of information indicating in-use and free blocks, said file system maintaining a set of snapshots, each snapshot including a representation of said file system as it was at an earlier time, said method including

computing a summary map in response to at least one copy of an earlier active map included in at least one of said snapshots.

32. In a file system including an active map of information indicating in-use and free blocks, said file system maintaining a set of snapshots, each snapshot including a representation of said file system as it was at an earlier time, said file system maintaining a summary map in response to at least one copy of an earlier active map included in at least one of said snapshots, a method of updating said summary map, said method including

receiving a request to delete a selected snapshot;

for a block used by said selected snapshot, indicating said block is free in said summary map only in response to a snapshot just prior to said selected snapshot and in response to a snapshot just after said selected snapshot.

33. A method as in claim 32, wherein said indicating frees said block only when both

said block is unused by said snapshot just prior to said selected snapshot;

and

said block is unused by said snapshot just after said selected snapshot.

34. A method as in claim 32, wherein said snapshot just after said selected snapshot corresponds to an active file system.

39. A method as in claim 38, including

swapping said second copy with said first copy after said consistency point is completed.

35. In a file system including an active map of information indicating in-use and free blocks, said file system maintaining a set of snapshots, each snapshot including a representation of said file system as it was at an earlier time, said file system maintaining a summary map in response to at least one copy of an earlier active map included in at least one of said snapshots, a method of updating said summary map, said method including

selecting a set of blocks maintained by said file system for which to perform a write allocation operation;

updating only a portion of said summary map corresponding to said set of blocks, in response to said selecting; and

performing said write allocation operation in response to said updated summary map.

36. In a file system including an active map of information indicating in-use and free blocks, and said file system maintaining a set of snapshots, each snapshot including a representation of said file system as it was at an earlier time, said file system maintaining a summary map in response to at least one copy of an earlier active map included in at least one of said snapshots, a method of updating said summary map, said method including

while generating a consistency point, selecting a set of blocks maintained by said file system and updating only a portion of said summary map corresponding to said set of blocks.

37. In a file system including an active map of information indicating in-use and free blocks, and said file system maintaining a set of snapshots, each snapshot including a representation of said file system as it was at an earlier time, said file system maintaining a summary map in response to at least one copy of an earlier active map included in at least one of said snapshots, a method of updating said summary map, said method including

refraining from indicating a selected block as free in response to whether said selected block is included in said copy of an earlier active map.

38. In a file system including an active map of information indicating in-use and free blocks, a method of updating said active map, said method including

maintaining a plurality of copies of said active map, at least a first said copy being a substantially true representation of in-use and free blocks, and at least a second said copy being a representation of in-use and free blocks which reflects fewer free blocks than said first copy;

and

wherein said second copy refrains from indicating a selected block as free until after a next consistency point is completed.