System and method for determining changes in two snapshots and for transmitting changes to destination snapshot

• US 20030182313A1
• Filed: 03/19/2002
• Published: 09/25/2003
• Est. Priority Date: 03/19/2002
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Inventors: Manley, Stephen L., Kleiman, Steven R., Owara, Shane S., Federwisch, Michael L.
• Granted Patent: US 6,993,539 B2
• Time in Patent Office: Days
• US Class Current: 707/200
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/2066 Optimisation of the communication load
• CPC Class Codes: G06F 11/2074 Asynchronous techniques
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99954 Version management

Abstract

A system and method for remote asynchronous replication or mirroring of changes in a source file system snapshot in a destination replica file system using a scan (via a scanner) of the blocks that make up two versions of a snapshot of the source file system, which identifies changed blocks in the respective snapshot files based upon differences in volume block numbers identified in a scan of the logical file block index of each snapshot. Trees of blocks associated with the files are traversed, bypassing unchanged pointers between versions and walking down to identify the changes in the hierarchy of the tree. These changes are transmitted to the destination mirror or replicated snapshot. This technique allows regular files, directories, inodes and any other hierarchical structure to be efficiently scanned to determine differences between versions thereof. The changes in the files and directories are transmitted over the network for update of the replicated destination snapshot in an asynchronous (lazy write) manner. The changes are described in an extensible, system-independent data stream format layered under a network transport protocol. At the destination, source changes are used to update the destination snapshot. Any deleted or modified inodes already on the destination are moved to a temporary or “purgatory” directory and, if reused, are relinked to the rebuilt replicated snapshot directory. The source file system snapshots can be representative of a volume sub-organization, such as a qtree.

Claims

1. A system for generating a group of changes in a source file system snapshot pair for transmission to a replicated destination file system comprising:

a scanner that searches a respective logical block file index of each of a first snapshot and a second snapshot of the source file system according to a predetermined file index and that retrieves only blocks having volume block numbers at corresponding file index locations on each of the first snapshot and the second snapshot that have different volume block numbers; and

wherein the scanner is adapted to walk down a hierarchy of pointers associated with each respective logical block file index and retrieve only pointed-to blocks with changed volume block numbers relative to pointed-to blocks at corresponding file offsets while bypassing blocks having unchanged volume block numbers therebetween.

2. The system as set forth in claim 1 further comprising an inode picker that picks out inodes in the retrieved blocks having a predetermined association and that indicate changes between, respectively a first version and a second version of the inodes in the first snapshot and the second snapshot.

3. The system as set forth in claim 2 wherein the predetermined association comprises a sub-organization of a volume file system.

4. The system as set forth in claim 3 wherein the sub-organization comprises a qtree within the volume file system.

5. The system as set forth in claim 2 further comprising an inode worker that operates on queued blocks retrieved by the inode picker and that applies the scanner to derive changes between blocks in a hierarchy of the first version of each of the picked out inodes with respect to a hierarchy of the second version of each of the picked out inodes.

6. The system as set forth in claim 5 wherein the inode worker is adapted to collect the changes an forward the changes to a pipeline that packages the changes in a data stream for transmission to the destination file system.

7. The system as set forth in claim 6 further comprising an extensible and file system-independent format that transmits the changes between the source file system and the destination file system.

8. The system as set forth in claim 7 wherein the format comprises a plurality of standalone headers including directory information, including deleted files, and basic data file headers, following the standalone headers, each of the basic data headers being followed by a stream of file data.

9. The system as set forth in claim 6 wherein the destination file system includes an inode map for mapping inode numbers and associated file generation numbers provided by the pipeline to corresponding inode numbers and associated file generation numbers recognized by the destination file system.

10. The system as set forth in claim 9 further comprising, at the destination file system, a temporary directory, adapted to receive thereinto any directory entries from the destination file system for files indicated by the changes as modified and deleted files with respect to corresponding entries for the files on the inode map, the temporary directory being deleted at a conclusion an update of the destination file system with the changes, wherein any modified files and deleted files that remain associated with the destination file system remain linked to the destination file system.

11. The system as set forth in claim 5 wherein the inode worker is part of a plurality of like inode workers that each operate on queued blocks retrieved by the inode picker and that applie the scanner to derive changes between blocks in a hierarchy of the first version of each of the picked out inodes with respect to a hierarchy of the second version of each of the picked out inodes.

12. A method for generating a group of changes in a source file system snapshot pair for transmission to a replicated destination file system comprising:

searching, with a scanner, a respective logical block file index of each of a first snapshot and a second snapshot of the source file system according to a predetermined file index and retrieving only blocks having volume block numbers at corresponding file index locations on each of the first snapshot and the second snapshot that have different volume block numbers; and

with the scanner, walking down a hierarchy of pointers associated with each respective logical block file index and retrieve only pointed-to blocks with changed volume block numbers relative to pointed-to blocks at corresponding file offsets while bypassing blocks having unchanged volume block numbers therebetween.

13. The method as set forth in claim 12 further comprising picking out inodes, with an inode picker, in the retrieved blocks having a predetermined association and indicating changes between, respectively a first version and a second version of the inodes in the first snapshot and the second snapshot.

14. The method as set forth in claim 13 wherein the predetermined association comprises a sub-organization of a volume file system.

15. The method as set forth in claim 14 wherein the sub-organization comprises a qtree within the volume file system.

16. The method as set forth in claim 13 further comprising operating on queued blocks retrieved by the inode picker with an inode worker that applies the scanner to derive changes between blocks in a hierarchy of the first version of each of the picked out inodes with respect to a hierarchy of the second version of each of the picked out inodes.

17. A system for deriving changes in a base and incremental snapshot of a source file system and transferring the changes to update a replicated destination file system comprising:

a source scanning process that compares volume block numbers of inodes for the base and the incremental snapshots along respective logical file indexes therefor, and that returns changes in pointed-to blocks with respect to a predetermined association of the inodes;

a format that packages the changes in a form that provides directory information and file data information under separate headers; and

a destination directory process that builds a directory of the replicated destination file system by mapping, with an inode map, source inode numbers and associated file generation numbers to destination file system inode numbers and associated generation numbers.

18. The system as set forth in claim 17 further comprising a temporary directory of the destination file system that receives any modified and deleted files from the source with respect to existing files in the inode map and that is adapted to be deleted after an update of the destination file system is complete wherein any remaining files remain linked to the directory of the replicated destination file system.

19. The system as set forth in claim 17 wherein the predetermined association comprises a sub-organization of a volume.

20. The system as set forth in claim 19 wherein the sub-organization comprises a qtree.