Method and apparatus for computing file storage elements for backup and restore

Abstract

A method and apparatus for method for transferring files between a primary storage system and a backup and restore system is described. The system generates collapsed extents which are used to specify data to be backed up to a backup and restore system. The backup and restore system backs up data based on the collapsed extents but records all extents included in the collapsed extents to enable the system to facilitate restoration of the data at a later point in time.

Claims

1. A method of backing up and restoring data in a computer system, the method comprising:

defining a logical backup object;

specifying one or more collapsed extents; and

recording details of the collapsed extents.

2. The method of claim 1 further comprising:

starting data movement between a host and the backup and restore system; and

monitoring data movement.

3. The method of claim 2 further comprising:

receiving a completed signal; and

in response to the completed signal, halting the monitoring of the data movement.

4. The method of claim 2 further comprising repeatedly defining a logical backup object, specifying extents, starting data movement, recording details of the specified extents and monitoring data movement from a first storage unit to a second storage unit until all data is transferred to the second storage unit.

5. The method of claim 2 further comprising restoring data by:

creating empty objects to restore into;

discovering the extents of the empty objects;

reading the extents of the backup objects; and

specifying a mapping from backup extents to restore extents wherein at least one of the

extents corresponds to a collapsed extent.

6. A method of backing up data used in a computer system having a client, a primary storage system and a backup storage system, the method comprising:

discovering one or more actual extents on the primary storage system;

collapsing the extents; and

specifying the collapsed extents to the backup storage system.

7. The method of claim 6 wherein collapsing the extents comprises:

identifying a pattern in the actual extents discovered on the primary storage system; and

generating a representation of files specified by the actual extents which is more compact than the representation provided by the actual extents and defining the representation as a collapsed extent.

8. A method of restoring data from a backup and restore system to a host, the method comprising:

creating empty objects on host to restore into;

discovering the extents of the empty objects;

reading the extents of the backup objects; and

specifying a mapping from backup extents to restore extents wherein at least one of the extents corresponds to a collapsed extent.

9. The method of claim 8 wherein specifying a mapping comprises specifying pairs of extents which identify the backup extents and the restore extents.

10. The method of claim 8 further comprising:

monitoring data movement,

receiving a complete signal; and

in response to the completed signal halting the monitoring of the data movement.

11. A backup and restore system for backing up and restoring files to and from a primary storage system coupled to a client, the backup and restore system comprising:

a processor for defining a logical backup object;

a collapsed extent processor for specifying collapsed extents;

means for starting data movement; and

an extent recording processor for recording details of collapsed extents.

12. The system of claim 11 further comprising means for logically restoring a logical element from a segment of storage on the primary storage system.

13. The system of claim 11 further comprising a processor for specifying a mapping from backup extents to restore extents wherein at least one of the extents corresponds to a collapsed extent.

14. The system of claim 12, wherein said means for logically restoring comprises:

means for creating empty objects to restore into;

means for discovering the extents of the empty objects;

means for reading the extents of the backup objects; and

means for specifying a mapping from backup extents to restore extents wherein at least one of the extents corresponds to a collapsed extent.

15. The system of claim 12, wherein the means for logically restoring comprises means for specifying pairs of extents which identify the backup extents and the restore extents.

16. A method of restoring data from a backup and restore system to a host, the method comprising:

creating empty objects on host to restore into;

discovering the extents of the empty objects;

reading the extents of the backup objects; and

specifying a mapping from backup extents to restore extents wherein at least one of the

extents corresponds to a collapsed extent and wherein specifying a mapping comprises:

identifying whether both back up and restore extents are striped;

in response to both the back up and restore extents being striped, identifying whether both back up and restore extents have the same column width and column count;

in response to both the back up and restore extents being striped, identifying whether both back up and restore extents start at the beginning of a stripe element;

computing a number of repetitions; and

generating a single restore extent for the number of repetitions.

Description

CROSS-REFERENCE TO RELATED APPLICATIONS

Not applicable.

BRIEF DESCRIPTION OF THE DRAWINGS

The foregoing features of this invention, as well as the invention itself, may be more fully understood from the following description of the drawings in which:

FIG. 1 is a block diagram of a backup and restore system;

FIG. 1A is a diagrammatical view of extents striped on a pair of disks;

FIG. 2 is a flow diagram of the backup process;

FIG. 3 is a flow diagram of a technique for specifying collapsed extents to a backup and restore system;

FIG. 4 is a series of diagrammatical views of extents striped on a pair of disks;

FIG. 5 is a flow diagram of the restore process;

FIG. 6 is a flow diagram of the process for mapping backup exents to restore extents; and

FIG. 7 is a diagrammatical view of extents striped on a pair of disks.

DETAILED DESCRIPTION OF THE INVENTION

Before proceeding with a description of the present invention and the techniques associated therewith, some introductory concepts and terminology are explained.

An extent is a contiguous piece of data on a disk (i.e. a physical device) identified by a disk name, a starting offset and a length. These three parameters taken together uniquely identify an extent. As used herein, the term "extent" refers to the basic unit used to specify data.

As will be explained further below, in accordance with the present invention, multiple extents can sometimes be specified as though they are a single extent. The term "collapsed extent" is used herein to refer to any extent which itself is made up of more than one extent.

Reference is also sometimes made herein to storage systems (e.g. primary storage systems) having a disk array with a certain number of disks (e.g. two disks). It should be understood that any particular values mentioned herein are only exemplary and are not intended in any way to limit the scope of the invention. It should also be understood that the present invention applies to systems having any number of disks. The particular number of disks in a storage system in any particular application are chosen in accordance with a variety of factors particular to each application.

Reference is also sometimes made herein to particular primary storage systems and backup and restore systems such as the Symmetrix and Calyso systems available from EMC Corporation of Hopkinton. It should be understood that such references are not intended to be limiting but are merely made for ease of explanation and to facilitate the understanding of particular concepts and techniques described herein. It should thus be understood that the concepts and techniques described herein apply equally well to a broad range of primary storage systems and backup and restore systems.

Referring now to FIG. 1, a processing system 10 includes a computer or client 12 coupled via a path 14 to a primary storage system 16. Client 12 performs its operations using data stored in storage system 16. The storage system 16 is comprised of an array of disks 17a-17N. A connection 18 couples the storage device 16 to a backup and restore system 19.

The backup and restore system 19 includes a long term storage device 20 and a system 22 for placing data into the long term storage device 20 and recovering the data from the long term storage device 20. The storage device 20 is shown as tape storage system in FIG. 1. Those of ordinary skill in the art will appreciate, of course, that storage system 20 may alternatively include or be provided from disk drives or any other storage mechanism.

The client 12 may be any conventional computing system, such as a network client available from Sun Microsystems, and running the Solaris operating system (a version of Unix), an HP client running HP-UX (a Hewlett-Packard client, running a Hewlett-Packard version of the Unix operating system) or an IBM client running the AIX operating system (an IBM version of Unix) or any other system with an associated operating system such as the WINDOWS NT operating system. The storage system 16 may be any conventional storage system, including a Symmetrix storage system, as described above.

Those of ordinary skill in the art will appreciate that system 10 may include other components not shown in FIG. 1. For example, the system may also include a backup server which functions to monitor backup procedures and operations. Also, the client 12 may be coupled to many other devices not shown in FIG. 1.

Primary storage system 16 includes the plurality of disks 17a-17n so that the system 16 may, inter alia, provide redundant storage capacity. A variety of ways of storing data onto the disks 17a-17N in a manner which permits data stored on a disk to be recovered have been developed. A number of such methods are generally described in the RAIDbook, A Source Book For Disk Array Technology, published by the RAID Advisory Board, St. Peter, Minn. (5th Ed, February, 1996). These systems include "RAID" storage systems. RAID stands for Redundant Array of Independent Disks.

In the system shown in FIG. 1, the primary storage system 16 may be a system such as generally described in EMC Data Manager: Symmetrix Connect User Guide, P/N 200-113-591, Rev. C, December 1997, available from EMC Corporation of Hopkinton, Mass.

The connection 18 may be a high speed data channel, such as a SCSI cable or one or more fiber-channel cables. In this system, a user may be permitted to backup data from the primary storage system 16 over the connection 18 to the backup and restore system 19.

In general overview, client 12 determines which data should be backed up and represents the data utilizing so-called extents. It should be appreciated, of course that not every extent is transferred from the primary storage device 16 to the backup storage device 19. Thus there remains the problem of specifying the particular extents to be backed up. Typically the client 12 (or the primary storage device 16 or some other processor) provides the backup and restore system 19 with a list of extents. Each extent is specified by a disk name, a starting offset and a length. The host provides an ordered list of extents using this format.

The particular manner in which the extents to be backed up are specified to the system 19 will be described in detail below in conjunction with FIG. 2. Suffice it here to say that the client 12 determines the data which should be backed up and specifies one or more collapsed extents to the backup and restore system 19. While the data specified by the collapsed extents is being backed up from system 16 to system 19, the system 19 records the details of the specified collapsed extents. In this manner, relatively few extents are specified to the backup and restore system 19 but a relatively large number amount of data is transferred to the backup and restore system 19.

By specifying collapsed extents rather than actual extents to the backup and restore system 19, the number of extents specified to the backup and restore system 19 is less than the number of extents specified using the prior art approach for the same amount of data. Thus, more data can be backed up without reaching or exceeding the extent limit of the backup and restore system 19.

Also, by recording the details of the collapsed extents, the data can be properly restored in a restore operation.

Referring briefly to FIG. 1A, data is shown stored in a conventional stripe pattern where the striping is done across two disks 24, 25 denoted "Disk A", and "Disk B" respectively. It should be appreciated that in practice, the stripe technique is often utilized with more than two disks (i.e. the striping takes place across a relatively large number of disks) and that two disks are used in this example for ease of explanation. The stripe pattern 23 is made up of a first stripe 23a on Disk A and a second pattern 23b on Disk B. Stripe 23 is made of 200 extents (100 in stripe 23a and 100 on stripe 23b). It should be appreciated that the numbering of the extents (e.g. numbers 1, 3, 5, 7, . . . 199 in extent 23a and 2, 4, 6, 8, . . . 200 in extent 23b).

In a worst case scenario, to specify the extents to the backup and restore system 19 using conventional approaches, each extent must be individually specified to the system 19. Thus, in the case where 200 extents exist, each of the individual 200 extents must be specified to the backup and restore system 19. The extent list for Disk A and Disk B are shown in FIG. 1A.

As indicated in FIG. 1A, 200 total extents must be specified similarly, in the case where N+1 extents exist, one must specify each of the individual N+1 extents to the backup and restore system 19. Thus in the conventional prior art approach to specifying data to be backed up, one generates a logical backup object (LBO) and defines the LBO in terms of extents and then records the extents.

When it is time to restore data from the backup and restore system to the host, the host must define that the extents which have been backed up now have to go back to disk space specified by the host. Generally, this is not the same disk space from which the extent was moved during the backup process. That is, the host might specify that the original extent (which came from one contiguous disk space) must now go back into two different places on the disk. In this case data is restored to a different place from where the data was backed up. It is thus necessary to describe the data to be restored and where it goes.

FIGS. 2, 3, 5 and 6 are a series of flow diagrams showing the processing performed by portions of system 10 (FIG. 1) to backup and restore data. The rectangular elements (typified by element 26 in FIG. 2), are herein denoted "processing blocks" and represent computer software instructions or groups of instructions. The diamond shaped elements (typified by element 38 in FIG. 2), are herein denoted "decision blocks," represent computer software instructions, or groups of instructions which affect the execution of the computer software instructions represented by the processing blocks.

Alternatively, the processing and decision blocks represent steps performed by functionally equivalent circuits such as a digital signal processor circuit or an application specific integrated circuit (ASIC). The flow diagrams do not depict the syntax of any particular programming language. Rather, the flow diagrams illustrate the functional information one of ordinary skill in the art requires to fabricate circuits or to generate computer software to perform the processing required to perform backup and restore operations in accordance with the present invention. It should be noted that many routine program elements, such as initialization of loops and variables and the use of temporary variables are not shown. It will be appreciated by those of ordinary skill in the art that unless otherwise indicated herein, the particular sequence of steps described is illustrative only and can be varied without departing from the spirit of the invention. Thus, unless otherwise stated the steps described below are unordered meaning that, when possible, the steps can be performed in any convenient or desirable order.

Turning now to FIG. 2, the process of backing up data begins by initializing the backup and restore system as shown in step 26. Next as shown in step 28, tapes (or other storage devices) are mounted in the backup system (e.g. tape system 20 in FIG. 1). A logical backup object (LBO) is then defined as shown in step 30. A process for defining an LBO will be described in more detail below in conjunction with FIGS. 3 and 4. Generally, however, this process determines how to represent data to be backup using collapsed extents.

Processing then proceeds to step 32 in which data movement from a primary storage system (e.g. system 16 in FIG. 1) to a backup and restore system (e.g. system 19 in FIG. 1) is started. Next, the details of the collapsed extents which were specified in step 30 are recorded as shown in step 34. It should be appreciated that step 34 can be performed before or after step 32. Generally, the information can be conveyed by transmitting metadata information (i.e. the LBO metadata information) to the backup and restore system.

Next, as shown in step 36, data movement is monitored until the Fastrax system provides an indication that the data movement is complete.

Decision block 38 determines whether more files remain to be processed. If more files should be processed then, processing returns to step 28 and steps 28-36 are repeated until all of the data is moved. If no more files remain to be processed then processing ends.

Referring now to FIG. 3, the steps to define an LBO are shown. Processing begins by discovering the location of the extents to be backed up as shown in step 40 and then appropriately identifying any pattern in the extents to combine or collapse the extents as shown in step 42. It should also be appreciated that step 42 is important to providing an efficient representation of the extents.

The collapsing step makes the LBO definition work correctly in situations where there are a lot of extents or faster in a situation where the extents are relatively small and spread around multiple disks.

One particular technique for collapsing the extents as shown in step 42 is described in detail below in conjunction with FIG. 4. Generally, however, to collapse an extent it is first necessary to recognize a pattern in the stored data. The pattern is recognized by getting the logical volume manager mapping from the file mapping. In one approach described in U.S. patent application Ser. No. 09/777,977, filed on Feb. 5, 2001 and having named inventor Neil F. Schutzman and assigned to the assignee of the present invention, all of the extents are found and it is then determined whether there is a pattern to the extents. This approach allows the data to be represented compactly. After the patterns are recognized, the collapsed extents can be generated.

There are at least two techniques to obtain the extents. A first technique is to have the system provide a list of all extents. Then each extent can be examined in relation to other extents. For example, it could be recognized that extents 1 and 3 are on the same disk and are adjacent to each other and that extent 5 is on the same disk as extent 3 and is adjacent to extent 3. In this way one could recognize a stripe pattern for example.

A second technique is to have the system provide a layout of the logical volumes. Such a request would then identify, for example, that the system had two striped volumes. One could then have the system to provide a layout of the files within the logical volumes. This information would reveal patterns.

Once the collapsed extents have been provided, processing proceeds to step 44 in which the collapsed extents are specified to the backup and restore system (e.g. system 19 in FIG. 1). It should be appreciated that steps 40 and 44 are steps which those of ordinary skill in the art would recognize as being needed to define the LBO. It should be appreciated that once the extents are specified to the backup and restore system, the backup and restore system reads the extents from the disks of the primary storage system (e.g. system 16 in FIG. 1) and stores the extents on the storage system 20.

Referring now to FIG. 4, assume that an object being backed up looks as shown in FIG. 4. Thus the file is made up of a first extent 61 and two striped extents 62, 63. The conventional approach to specify the object/file to a backup and restore system is to list all of the extents. This means that 13 extents would have to be specified as shown in Table I below:

• Inventors
  Pillai, Ananthan K.; Mutalik, Madhav; Garber, Cara; Shekhar, Ajay;
• Assignee
  EMC Corporation (Hopkinton, MA)
• Published
  Jun-28-2005
• Current US Classes:
  707/205
  711/161
  711/162
  714/6
  714/7
• Application #
  822709
• International Classes
  G06F 012//00
• Field of Search
  711/161 711/162 707/205 714/6 714/7
• Examiner
  Padmanabhan; Mano
• Agent
  Daly, Crowley, Mofford & Durkee, LLP
• US Patent References:
  5819297
  5890165
  6029166
  6141773
  6161111
  6269381
  6360330
  6446175
  6578121
  6714952