Write allocation based on storage system map and snapshot

• US 7,454,445 B2
• Filed: 08/17/2001
• Issued: 11/18/2008
• Est. Priority Date: 08/18/2000
• Status: Expired due to Term

• Current Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Original Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Inventors: Edwards, John, Lewis, Blake, Viswanathan, Srinivasan
• Primary Examiner(s): Le; Miranda
• Application Number:
  US09/932,578
• Publication Number:
  US 20020083037A1
• Time in Patent Office: 2,650 Days
• Field of Search: 707 1- 10, 707100-102, 707/104.1, 707200-206, 711100-1014, 711161-162, 711111-112, 711/114, 711/170, 709/203, 709/218
• US Class Current: 1/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. A “copy-on-write” mechanism is used. 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. 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. A record of which blocks are being used by the snapshot is included in the snapshot itself, allowing effectively instantaneous snapshot creation and deletion. A snapshot can also be deleted instantaneously simply by discarding its root inode.

Claims

1. A method comprising:

maintaining an active map of information indicating in-use blocks and free blocks of an active file system in a storage system;

maintaining a set of snapshots in the storage system, each snapshot representing a state of said active file system at a particular point in time, each snapshot having a corresponding active map indicating in-use blocks and free blocks of the active file system for a point in time at which said snapshot was generated;

computing a summary map as a logical OR of the active maps of at least two of said snapshots, wherein said computing includes performing a bitwise logical operation on at least two copies of earlier active maps included in said set of snapshots;

identifying a set of snapshots created since a recent update of a selected portion of the summary map;

updating said selected portion of the summary map based on only a most recent one of said identified snapshots, and

using the summary map to make write allocation decisions in the storage system based on both a current active map of the active file system and said summary map, including using the summary map to avoid overwriting blocks used by a snapshot.

2. A method as in claim 1, wherein said summary map is computed using an inclusive OR operation.

3. A method as in claim 1, wherein using the summary map to make write allocation decisions in the storage system comprises:

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

making write allocation decisions based on a result of said computing.

4. A method comprising:

maintaining an active map of information indicating in-use blocks and free blocks of an active file system;

maintaining a set of snapshots, each snapshot representing a state of said active file system at a particular point in time, each snapshot having a corresponding active map indicating in-use blocks and free blocks of the active file system for a point in time at which said snapshot was generated;

maintaining a summary map computed as a logical OR on active maps included in at least two of said snapshots, wherein said maintaining includes performing a bitwise logical operation on at least two copies of earlier active maps included in said set of snapshots;

identifying a set of snapshots created since a recent update of a selected portion of the summary map;

updating said selected portion of the summary map based on only a most recent one of said identified snapshots,

making a write allocation decision based on both a current active map of the active file system and the summary map, including using the summary map to avoid overwriting blocks used by a snapshot;

receiving a request to delete a particular snapshot; and

deleting said particular snapshot, wherein said deleting involves, for a block used by said particular snapshot, indicating said block is free in said summary map depending on a snapshot just prior to said particular snapshot and a snapshot just after said particular snapshot.

5. A method as in claim 4, wherein said indicating frees said block only when both

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

and

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

6. A method as in claim 4, wherein said snapshot just after said particular snapshot corresponds to an active file system.

7. A method comprising:

maintaining an active map of information indicating in-use and free blocks associated with a file system;

maintaining a set of snapshots, each snapshot representing a state of said file system at a particular point in time;

maintaining a summary map computed as a logical OR of active maps included in at least two of said snapshots, wherein said maintaining includes performing a bitwise logical operation on at least two copies of earlier active maps included in said set of snapshots;

selecting a set of blocks maintained by said file system for which to perform a write allocation operation based on both a current active map of the file system and the summary map, including using the summary map to avoid overwriting blocks used by a snapshot;

identifying a set of snapshots created since a recent update of a selected portion of the summary map;

updating said selected 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.

8. A method as in claim 7, wherein said summary map is computed using an inclusive OR operation.

9. A method as in claim 7, wherein said logical union is an inclusive OR operation.

10. A method comprising:

maintaining a plurality of persistent point-in-time images of a file system, each persistent point-in-time image representing a state of said file system at a particular point in time, each persistent point-in-time image having associated therewith a separate map indicating in-use blocks and free blocks of the file system at the corresponding point in time;

generating a summary map as a logical OR on at least two of said maps associated with the plurality of said persistent point-in-time images, wherein said generating includes performing a bitwise logical operation on at least two copies of said earlier maps associated with the plurality of persistent point in time images;

identifying a set of snapshots created since a recent update of a selected portion of the summary map;

updating said selected portion of the summary map based on only a most recent one of said identified snapshots; and

making write allocation decisions based on said summary map and a map indicating in-use blocks and free blocks associated with a current state of the file system, including using the summary map to avoid overwriting blocks used by a snapshot.

11. A method as in claim 10, wherein said summary map is computed using an inclusive OR operation.

12. A method comprising:

maintaining a plurality of snapshots of a structured set of data in a data storage system, each snapshot representing a state of said structured set of data at a particular point in time, each snapshot having associated therewith a separate active map indicating in-use blocks and free blocks of the structured set of data at the corresponding point in time;

generating a summary map which represents a summary of at least two of said active maps for different points in time, by using a logical OR of said at least two of said active maps, wherein said generating comprises performing a bitwise logical operation on at least two copies of said earlier maps included in said plurality of snapshot;

identifying a set of snapshots created since a recent update of a selected portion of the summary map;

updating said selected portion of the summary map based on only a most recent one of said identified snapshots; and

making write allocation decisions relating to the structured set of data in the data storage system, based on the summary map and an active map indicating in-use blocks and free blocks associated with a current state of the structured set of data, including using the summary map to avoid overwriting blocks used by a snapshot.

13. A method as in claim 12, wherein the data storage system comprises a file server and the structured set of data is a file system.

14. A method as in claim 12, wherein the logical OR is an inclusive OR operation.