Method and apparatus for efficiently copying distributed data files

• US 7,194,492 B2
• Filed: 06/02/2003
• Issued: 03/20/2007
• Est. Priority Date: 10/29/2001
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Seidenberg, Thomas, Bopardikar, Raju C.
• Primary Examiner(s): Vo; Tim
• Assistant Examiner(s): LY, CHEYNE D
• Application Number:
  US10/452,688
• Publication Number:
  US 20040098424A1
• Time in Patent Office: 1,387 Days
• Field of Search: 707/200, 707/203, 707/204, 707/202, 707/205
• US Class Current: 1/1
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99955 Archiving or backup

Abstract

Metadata that relates logical block addresses of data used by a file system with the physical block addresses at which the data is stored is maintained in nodes that are arranged into a hierarchical volume map tree that extends from a root node to a plurality of leaf nodes. A copy of the volume map tree root node is maintained in a data structure called a delta that represents the data in the covolume and the modifications to that volume map tree copy represent all additions, changes or deletions made to the volume. A copy of the data, or a new covolume, can be made by creating a new delta containing a new copy of the volume map tree root node as it existed at the time the new covolume was created. The deltas are arranged into a tree structure that represents the data in a covolume and whether the data is unchanged from a previous covolume or changed in that covolume. The delta tree structure can be used to determine whether a delta is not shared so that its covolume can be deleted. Deltas may also be arranged in local delta trees that represent changes to a particular logical is location. The local delta tree can be used to quickly locate unused locations in order to free these locations.

Claims

1. A method for efficiently copying a distributed data file consisting of a source covolume having a plurality of data blocks, each data block being located at a physical block address in a storage system, the method comprising:

(a) creating a hierarchical volume map tree having a root node corresponding to the source covolume, a plurality of intermediate nodes and a plurality of leaf nodes, each leaf node corresponding to one of the plurality of data blocks, the volume map tree mapping logical block addresses to physical block addresses;

(b) adding a path to the tree when a write operation in the source covolume writes data with a logical block address to a physical block address;

(c) creating a new covolume that is a copy of the source covolume by copying the root node of the volume map tree to the new covolume wherein the new covolume has a different root node, but shares all of the intermediate nodes and the leaf nodes with the source covolume; and

(d) adding a new path to the tree when a write operation in the new covolume writes data at a logical block address already written by a write operation in the source covolume wherein the new covolume shares all of the intermediate nodes and the leaf nodes with the source covolume except for intermediate nodes and leaf nodes corresponding to data which has been changed.

2. The method of claim 1 wherein the volume map tree root node and the data in the source covolume are collectively called a delta and the method further comprises:

(e) arranging deltas corresponding to a plurality of covolumes into a delta tree structure indicating from which covolume another covolume was created.

3. The method of claim 2 further comprising:

(f) walking the delta tree to determine whether a delta corresponding to a particular covolume is shared by two or more deltas corresponding to covolumes that have been copied from the particular covolume; and

(g) deleting the particular delta when it is not shared and a source covolume that is part of the particular delta is deleted.

4. The method of claim 3 further comprising:

(h) combining the shared delta with its parent delta when a covolume corresponding to the parent delta is deleted.

5. The method of claim 3 further comprising:

(i) combining a delta with a single child delta that depends from the delta when a covolume that corresponds to the delta is deleted.

6. The method of claim 2 wherein the delta tree has a root delta and a plurality of natural deltas wherein each natural delta corresponds to a covolume in which the latest changes are made and wherein the method further comprises the steps of walking the delta tree starting at a particular natural delta to search the data in a covolume corresponding to the particular natural delta.

7. The method of claim 2 further comprising:

(j) arranging the deltas into a least one local delta tree structure corresponding to a particular logical block address, which local delta tree structure indicates which deltas modified the logical block address.

8. The method of claim 7 further comprising:

(k) using the local delta tree structure to determine which data blocks are no longer referenced by a covolume; and

(l) freeing the data blocks determined in step (k).

9. The method of claim 1 wherein step (b) comprises marking each intermediate node and each leaf node in the path as owned by the source covolume.

10. The method of claim 9 wherein step (d) comprises, during a write operation in the new covolume, mapping a logical block address to a physical block address and adding a new path to the volume map tree when the mapping requires modification of a node owned by the source covolume.

11. Apparatus for efficiently copying a distributed data file consisting of a source covolume having a plurality of data blocks, each data block being located at a physical block address in a storage system, the apparatus comprising:

a hierarchical volume map tree having a root node corresponding to the source covolume, a plurality of intermediate nodes and a plurality of leaf nodes, each leaf node corresponding to one of the plurality of data blocks, the volume map tree mapping logical block addresses to physical block addresses;

a mechanism that adds a path to the tree when a write operation in the source covolume writes data with a logical block address to a physical block address;

a mechanism for creating a new covolume that is a copy of the source covolume by copying the root node of the volume map tree to the new covolume wherein the new covolume has a different root node, but shares all of the intermediate nodes and the leaf nodes with the source covolume; and

a mechanism that adds a new path to the tree when a write operation in the new covolume writes data at a logical block address already written by a write operation in the source covolume wherein the new covolume shares all of the intermediate nodes and the leaf nodes with the source covolume except for intermediate and leaf nodes corresponding to data which has been changed.

12. The apparatus of claim 11 wherein the volume map tree root node and the data in the source covolume are stored in a delta structure and the apparatus further comprises a mechanism that arranges delta structures corresponding to a plurality of covolumes into a delta tree structure indicating from which covolume another covolume was created.

13. The apparatus of claim 12 further comprising a mechanism that walks the delta tree to determine whether a delta corresponding to a particular covolume is shared by two or more deltas corresponding to covolumes that have been copied from the particular covolume and a mechanism that deletes the particular delta when it is not shared and a source covolume that is part of the particular delta is deleted.

14. The apparatus of claim 13 further comprising a mechanism that combines the shared delta with its parent delta when a covolume corresponding to the parent delta is deleted.

15. The apparatus of claim 13 further comprising a mechanism that combines a delta with a single child delta that depends from the delta when a covolume that corresponds to the delta is deleted.

16. The apparatus of claim 12 wherein the delta tree has a root delta and a plurality of natural deltas wherein each natural delta corresponds to a covolume in which the latest changes are made and wherein the apparatus further comprises a mechanism that walks the delta tree starting at a particular natural delta to search the data in a covolume corresponding to the particular natural delta.

17. The apparatus of claim 12 further comprising a mechanism that arranges deltas in a further local delta tree structure corresponding to a particular logical block address, which local delta tree indicates which deltas modified the logical block address.

18. The apparatus of claim 17 further comprising a mechanism that uses the local delta tree structure to determine which data blocks are no longer referenced by a covolume;

and a mechanism that frees the data blocks that are no longer referenced by a covolume.

19. The apparatus of claim 11 wherein the mechanism that adds a path to the tree comprises a mechanism that marks each intermediate node and each leaf node in the path as owned by the source covolume.

20. The apparatus of claim 19 wherein the mechanism that adds a new path to the tree comprises a mechanism that is operable during a write operation in the new covolume that maps a logical block address to a physical block address, and adds a new path to the volume map tree when the mapping requires modification of a node owned by the source covolume.

21. A computer program product for efficiently copying a distributed data file consisting of a source covolume having a plurality of data blocks, each data block being located at a physical block address in a storage system, the computer program product comprising a computer usable medium having computer readable program code thereon embedded in memory, including:

program code for creating a hierarchical volume map tree having a root node corresponding to the source covolume, a plurality of intermediate nodes and a plurality of leaf nodes, each leaf node corresponding to one of the plurality of data blocks, the volume map tree mapping logical block addresses to physical block addresses;

program code for adding a path to the tree when a write operation in the source covolume writes data with a logical block address to a physical block address;

program code for creating a new covolume that is a copy of the source covolume by copying the root node of the volume map tree to the new covolume wherein the new covolume has a different root node, but shares all of the intermediate nodes and the leaf nodes with the source covolume; and

program code for adding a new path to the tree when a write operation in the new covolume writes data at a logical block address already written by a write operation in the source covolume wherein the new covolume shares all of the intermediate nodes and the leaf nodes with the source covolume except for intermediate nodes and leaf nodes corresponding to data which has been changed.

22. The computer program product of claim 21 wherein the volume map tree root node and the data in the source covolume are collectively called a delta and the computer program product further comprises program code for arranging deltas corresponding to a plurality of covolumes into a delta tree structure indicating from which covolume another covolume was created.

23. The computer program product of claim 22 further comprising program code for walking the delta tree to determine whether a delta corresponding to a particular covolume is shared by two or more deltas corresponding to covolumes that have been copied from the particular covolume and program code for deleting the particular delta when it is not shared and a source covolume that is part of the particular delta is deleted.

24. The computer program product of claim 23 further comprising program code for combining the shared delta with its parent delta when a covolume corresponding to the parent delta is deleted.

25. The computer program product of claim 23 further comprising program code for combining a delta with a single child delta that depends from the delta when a covolume that corresponds to the delta is deleted.

26. The computer program product of claim 22 wherein the delta tree has a root delta and a plurality of natural deltas wherein each natural delta corresponds to a covolume in which the latest changes are made and wherein the computer program product further comprises program code for walking the delta tree starting at a particular natural delta to search the data in a covolume corresponding to the particular natural delta.

27. The computer program product of claim 22 further comprising program code for arranging the deltas into a least one local delta tree structure corresponding to a particular logical block address, which local delta tree structure indicates which deltas modified the logical block address.

28. The computer program product of claim 27 further comprising program code for using the local delta tree structure to determine which data blocks are no longer referenced by a covolume and program code for freeing the data blocks which are no longer referenced by a covolume.