Optimizing defragmentation operations in a differential snapshotter

• US 20040133602A1
• Filed: 10/14/2003
• Published: 07/08/2004
• Est. Priority Date: 10/16/2002
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zbikowski, Mark J., Leis, Benjamin A., Kusters, Norbert P.
• Granted Patent: US 7,664,771 B2
• Time in Patent Office: Days
• US Class Current: 707/104.1
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0617 in relation to availability
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

A method for establishing and maintaining a differential snapshot of a set of files stored on a volume is disclosed. The invention achieves processing time and disk space optimizations by avoiding copy-on-write operations for logically insignificant moves of blocks, such as the block rearrangements characteristic of defragmentation utilities. A file system enhancement enabling the passing of a block copy command from the file system to lower-level drivers, is used to inform the snapshotter that a block move operation is not logically meaningful. When the logically insignificant move is of a block whose data forms part of the data captured in the snapshot virtual volume, and when the move is to a block location that is functioning as logical free space, the snapshotter can simply modify its block bitmap and update translation table entries without needing to perform a copy-on-write.

Claims

1. A method for maintaining a differential snapshot of a volume, the volume comprising a plurality of blocks, the method comprising:

passing down, by a file system to a differential snapshotter, a block copy command for a block move from a location A on the volume to a location B on the volume.

2. The method of claim 1 wherein the block copy command is associated with a defragmentation operation.

3. The method of claim 1 wherein the snapshotter keeps a translation table.

4. The method of claim 3 wherein the snapshotter keeps a bitmap of the blocks in the volume, wherein, for a bit in the bitmap corresponding to a block in the volume, a first bit value indicates that the snapshotter does not need to take any action when the block is written, and a second bit value indicates that the snapshotter must protect the block with a copy-on-write before the block is written.

5. The method of claim 4, further comprising, if a bit in the bitmap corresponding to the location B has the second bit value:

performing a copy-on-write of the location B to a differential area location before the location B is written by the block move;

adding a table entry registering the copy-on-write of the location B to the differential area location; and

changing the bit corresponding to the location B to the first bit value.

6. The method of claim 4, further comprising, if a bit in the bitmap corresponding to the location B has the first bit value, and if a bit in the bitmap corresponding to the location A has the second bit value:

letting the block move happen;

changing the bit corresponding to the location A to the first bit value;

changing the bit corresponding to the location B to the second bit value; and

adding a table entry mapping the location A to the location B.

7. The method of claim 6, further comprising:

adding a table entry mapping the location B back to the location A.

8. The method of claim 6, further comprising, if, at a later time, a write of the location B is to occur:

performing a copy-on-write of the location B to a differential area location before the write occurs;

replacing the table entry mapping the location A to the location B with a table entry mapping the location A to the differential area location; and

changing the bit corresponding to the location B to the first bit value.

9. The method of claim 8, further comprising, if there is a table entry mapping the location B back to the location A, deleting the table entry.

10. The method of claim 6, further comprising, if a subsequent write of the location B has not yet occurred and a block move from the location B to a location C is initiated:

if a bit in the bitmap corresponding to the location C has the second bit value,

performing a copy-on-write of the location C to a differential area location before it is written by the block move;

adding a table entry registering the copy-on-write of the location C to the differential area location; and

changing the bit corresponding to the location C to the first bit value;

otherwise, if the bit corresponding to the location C has the first bit value, letting the block move happen;

changing the bit corresponding to the location B to the first bit value;

changing the bit corresponding to the location C to the second bit value;

replacing the table entry mapping the location A to the location B with a table entry mapping the location A to the location C; and

if there is a table entry mapping the location B back to the location A, replacing the table entry with a table entry mapping the location C back to the location A.

11. A method for moving a block from a location A to a location B, the method comprising:

passing down, by a file system, a block copy command to a lower level driver.

12. In a data storage system comprising a file system and one or more disk volumes, each volume comprising a plurality of files and a plurality of blocks, wherein each file is implemented by a set of one or more blocks, wherein blocks currently implementing a file are occupied-space blocks and all other blocks are free-space blocks, a method for maintaining a snapshot of an original volume, the method comprising:

taking a snapshot of the original volume;

monitoring moves of occupied-space blocks in the original volume, wherein moving an occupied-space block comprises transferring its contents to a second block, which is one of the free-space blocks, the second block thereby becoming an occupied-space block, and the first block thereby becoming a free-space block;

monitoring writes of blocks in the original volume; and

producing snapshot versions of blocks in response to read requests.

13. The method of claim 12 wherein monitoring moves includes intercepting a block copy command passed down by the file system.

14. The method of claim 12 wherein moves of blocks include moves that are associated with a defragmentation operation.

15. The method of claim 12 wherein taking a snapshot includes creating a bitmap comprising a plurality of bit spaces, wherein each bit space corresponds to a respective block in the original volume, wherein each bit space is set either to an ignore value or to a protect value, and wherein initially a bit space is set to the ignore value if its corresponding block is a free-space block when the snapshot is taken, and a bit space is set to the protect value if its corresponding block is an occupied-space block when the snapshot is taken.

16. The method of claim 15 wherein monitoring moves, monitoring writes and producing snapshot versions of blocks includes recording information regarding current actual locations of the snapshot versions of blocks in the original volume.

17. The method of claim 16 wherein monitoring a write of a block further comprises:

if the bit space in the bitmap corresponding to the block is set to the protect value,

copying the block to a location in a differential storage space;

setting the bit space to the ignore value;

if the block to be written is recorded as the current actual location of the snapshot version of a different block in the original volume, recording the location of the copy in the differential storage space as the new current actual location of the snapshot version of that different block, and otherwise recording the location of the copy in the differential storage space as the current actual location of the snapshot version of the block to be written; and

permitting the write to proceed; and

if the bit space in the bitmap corresponding to the block is set to the ignore value, permitting the write to proceed.

18. The method of claim 17 wherein a translation table is used to record information regarding current actual locations of the snapshot versions of blocks, the method further comprising, if the bit space in the bitmap corresponding to the block to be written is set to the protect value:

deleting each entry in the table that indicates that the block to be written is the current actual location of the snapshot version of a different block, and

recording in a new table entry the location of the copy in the differential storage space as the current actual location of the snapshot version of the block to be written.

19. The method of claim 16 wherein monitoring a move of a first block to a second block comprises:

if the bit space in the bitmap corresponding to the first block is set to the protect value, and the bit space in the bitmap corresponding to the second block is set to the ignore value,

permitting the move to proceed;

if the first block is recorded as the current actual location of the snapshot version of a third block in the original volume, recording the second block as the new current actual location of the snapshot version of the third block, and otherwise recording the second block as the current actual location of the snapshot version of the first block; and

exchanging the bits in the bit spaces in the bitmap corresponding to the first block and the second block, so that the bit space corresponding to the first block is set to the ignore value, and the bit space corresponding to the second block is set to the protect value;

otherwise, if the bit space corresponding to the second block is set to the protect value,

copying the second block to a location in a differential storage space;

setting the bit space corresponding to the second block to the ignore value;

if the second block is recorded as the current actual location of the snapshot version of a different block in the original volume, recording the location of the copy in the differential storage space as the current actual location of the snapshot version of that different block, and otherwise recording the location of the copy in the differential storage space as the current actual location of the snapshot version of the second block; and

permitting the move to proceed;

otherwise, if the bit space corresponding to the first block is set to the ignore value, permitting the move to proceed.

20. The method of claim 19 wherein a translation table is used to record information regarding current actual locations of the snapshot versions of blocks, the method further comprising, if the bit space corresponding to the first block is set to the protect value, if the bit space corresponding to the second block is set to the ignore value, and if the first block is recorded in the table as the current actual location of the snapshot version of a third block in the original volume:

if the second block and the third block are the same block, deleting each entry in the table that indicates that the first block is the current actual location of the snapshot version of the second block, and

if the second block and the third block are not the same block, recording in a new table entry the second block as the new current actual location of the snapshot version of the third block.

21. The method of claim 16 wherein producing the snapshot version of a block in response to a read request comprises directing the read to the current actual location of the snapshot version of the block.

22. The method of claim 21 wherein a translation table is used to record information regarding current actual locations of the snapshot versions of blocks, the method further comprising:

if the block to be read has a table entry indicating the current actual location of its snapshot version, redirecting the read to that location, and

otherwise, directing the read to the version of the block in the original volume.