Method and apparatus for efficiently copying distributed data files

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.