Method and apparatus for transferring archival data among an arbitrarily large number of computer devices in a networked computer environment

• US 5,751,997 A
• Filed: 01/19/1996
• Issued: 05/12/1998
• Est. Priority Date: 01/21/1993
• Status: Expired due to Term

• Current Assignee: Apple Computer Incorporated (Apple Inc.)
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Titus, Diane J., Spirakis, Charles S., Kullick, Steven E.
• Primary Examiner(s): Kim, Matthew M.
• Application Number:
  US08/588,830
• Time in Patent Office: 844 Days
• Field of Search: 395/600, 395/488, 395/489, 395/200.08, 395/182.02, 395/182.04, 395/474, 395/439-441, 395/415-419, 395/444, 395/180, 395/182.18, 395/182.03
• US Class Current: 711/162
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1456 Hardware arrangements for backup
• CPC Class Codes: G06F 11/1464 for networked environments

Abstract

A method and apparatus for storing on centralized mass storage devices archival data from multiple computers in a networked environment. In a networked computer system having a communication network interconnecting one or more computers and a storage unit, parallel processes are created to perform repeated backup operations for disks on computer devices on the communication network. The backup operations for a disk include a backup initialization which occurs when a primary storage device does not have a full index or a backup data file for a disk but a secondary storage device does. During a backup initialization, data from the files and directories on that disk along with an index entry for each file or directory are passed to the primary storage device which directly passes that information directly through to the secondary storage device. The index entries are incorporated into a full index and the data is incorporated into a backup data file. During a backup cycle, the computer device is incrementally backed up to a primary storage device such that the primary storage device contains a full index with an entry for each file and directory on the disk and a backup data file for the disk with data for the files and directories which have been changed or created since the last backup to the secondary storage device occurred. When a specified, predetermined time or event occurs or the transfer is otherwise indicated, the primary storage device transfers the full index and the backup data file to the secondary storage device.

Claims

1. In a networked computer system having a communication network interconnecting one or more primary storage devices, one or more secondary storage devices and a plurality of computer devices, each computer device having one or more disks, a method for storing data from one or more computer devices, said method comprising the steps of:

indicating when a transfer of data from a primary storage device to a secondary storage device should occur;

transferring data from the primary storage device to the secondary storage device in response to such indicating, the data including for a particular disk a corresponding full index and a backup data file, the data being merged, respectively, with any full index and backup data file for the disk currently stored on the secondary storage device, the merged any full index and backup data file corresponding to the particular disk, the data being merged in such a way so that if an index entry in the full index from a computer indicates that data corresponding to that index entry has been changed or created, the corresponding data in a resulting backup data file is the corresponding data from the backup data file from the primary storage device and if an index entry in the full index from the computer indicates that data corresponding to that index entry has been changed or created, the corresponding data in the resulting backup data file is the corresponding data from a previously-stored backup data file;

checking whether the primary storage device has a full index corresponding to a disk of a computer device and, if the primary storage device has such a corresponding full index, then sending the corresponding full index, or a portion thereof, to the primary storage device and, if the primary storage device does not have such a corresponding full index, then checking to see if the secondary storage device has such a full index corresponding to the disk and, if the secondary storage device does have such a corresponding full index, sending directly or indirectly that corresponding full index to the computer device and if the secondary storage device does not have a copy of such corresponding full index, copying data and corresponding information from the disk to the secondary storage device, storing the data in a backup data file on the secondary storage device or external storage devices connected thereto, creating a corresponding full index for accessing the data in the backup data file on the secondary storage device and storing that corresponding full index on the secondary storage device;

determining which data on the disk of the computer device has been changed or created since the last time the corresponding full index for that disk was modified;

creating an index entry for each file or directory on the disk;

sending index entries and a copy of the determined data to the primary storage device; and

forming on the primary storage device a new corresponding full index and new corresponding backup data file for the disk from the index entries and data received from the computer device and the corresponding full index and backup data file, if any, on the primary storage device.

2. The method as defined in claim 1 further comprising a step of creating two or more parallel processes to perform steps defined in claim 1.

3. The method as defined in claim 1 further comprising the steps of:

assigning a responsible primary storage device to a disk such that the primary storage device receives data from the disk;

checking that the primary storage device sending data related to a disk to the secondary storage device in response to the indicating of a data transfer is the responsible primary storage device; and

discarding the data if the primary storage device is not the responsible primary storage device assigned to the disk.

4. The method as defined in claim 1 further comprising the steps of:

checking for a specific condition at each attempt to perform a backup operation for a disk; and

performing the attempted backup operation only if the specific condition has occurred.

5. The method as defined in claim 1 further comprising the steps of:

setting a minimum time between backups for a disk on a computer device;

recording when a computer device sends index entries and data for a disk to a primary storage device;

accessing a current date and time;

checking at each attempt to perform a transfer of data for a disk whether the minimum time between backups for a disk elapsed since the computer device last sent index entries and data for a disk to a primary storage device; and

performing the attempted data transfer only if the minimum time has elapsed.

6. In a networked computer system having a communication network interconnecting one or more primary storage devices, one or more secondary storage devices and a plurality of computer devices, each computer device having one or more disks, a method for storing data from one or more computer devices, said method comprising the steps of:

indicating when a transfer of data from a primary storage device to a secondary storage device should occur; and

for each disk,

creating index entries for data on a computer device, each index entry specifying a corresponding portion of the data,

sending a copy of data and associated index entries from the computer device to the secondary storage device using the primary storage device without storing the data or index entries on the primary storage device,

storing the data in a backup data file on the secondary storage device, the backup data file corresponding to the disk from which the data was transferred,

forming an index from the index entries such that each index entry specifies a location within the backup data file where data associated with that index entry is located, the index corresponding to the disk from which the data was transferred,

storing the index for a disk on the secondary storage device,

sending an index for the disk from the secondary storage device to the primary storage device and storing the index on the primary storage device,

indicating to the computer device which files on the disk are identified in the index on the primary storage device and when those files were last modified,

determining which files on the disk have been changed or created since the last modified dates of the files indicated by primary storage device,

sending an index entry for each file on the disk from the computer device to the primary storage device, each index entry indicating the location of the data corresponding to said each index entry,

sending data for the files which have been changed or created from the computer device to the primary storage device,

if there is not an index and a backup data file corresponding to the disk on the primary storage device, forming an index containing the index entries from the computer device and forming a backup data file containing the data from the computer device, the formed index and backup data file corresponding to the disk,

if there is an index and a backup data file corresponding to the disk, then forming a new index containing the index entries from the computer device, forming a new backup data file, checking each index entry in the new index to see if the data associated with that entry has been changed and, if it has, then incorporating the associated data in the backup data file received from the computer device into the new backup data file, and if it has not been changed, then incorporating the associated data in the backup data file on the primary storage device into the new backup data file, and

transferring in response to said indicating step one or more backup data files and index corresponding to the disk from the primary storage device to the secondary storage device, replacing the index on the secondary storage device with the index received from the primary storage device, forming a new backup data file, checking each index entry in the new index to see if the data corresponding to that entry has been changed and, if it has, then incorporating the corresponding data in the backup data file received from the primary storage device into the formed new backup data file, and if it has not been changed, then incorporating the corresponding data in the backup data file on the secondary storage device into the formed new backup data file.

7. The method as defined in claim 6 further comprising a step of creating two or more-parallel processes to perform steps defined in claim 6.

8. The method as defined in claim 6 further comprising the steps of:

assigning a responsible primary storage device to a disk such that the primary storage device receives data from the disk;

checking that the primary storage device sending data related to a disk to the secondary storage device in response to the indicating of a data transfer-is the responsible-primary storage device; and

discarding the data if the primary storage device is not the responsible primary storage device assigned to the disk.

9. The method as defined in claim 6 further comprising the steps of:

checking for a specific condition at each attempt to perform a backup operation for a disk; and

performing the attempted backup operation only if the specific condition has occurred.

10. The method as defined in claim 6 further comprising the steps of:

setting a minimum time between backups for a disk on a computer device;

recording when a computer device sends index entries and data for a disk to a primary storage device;

accessing a current date and time;

checking at each attempt to perform a backup operation for a disk whether the minimum time between backups for a disk elapsed since the computer device last sent index entries and data for a disk to a primary storage device; and

performing the attempted backup operation only if the minimum time has elapsed.

11. An apparatus for storing archival data from one or more computer devices, each computer device having at least one disk, said apparatus comprising:

a primary storage device;

a secondary storage device;

means for interconnecting said primary storage device, said secondary storage device and the computer devices;

transfer indicating-means for indicating a transfer from said primary storage device to said secondary storage device;

a full index having a plurality of index entries, each index entry specifying corresponding data;

a backup initialization having

means for sending a copy of data and corresponding index entries for a disk from the computer device to the primary storage device,

means for passing the data and corresponding index entries through the primary storage device to the secondary storage device without storing the data or index entries on the primary storage device,

means for storing the data in a backup data file on the secondary storage device,

means for forming an index from the index entries such that each index entry specifies a location within the backup data file where data associated with that index entry is located; and

a backup cycle having

a first state having

means for sending an index from the secondary storage device to the primary storage device,

computer device indicating-means for indicating to the computer device which files are identified in the full index on the primary storage device and the last modified date specified in the index entry for each file,

means for determining which files on the computer device have been changed or created since the last modified date indicated in the index entry for that file in the full index on the primary device,

file change indicating means for indicating that the file has been changed or created,

means for sending an index entry for each file on the disk and data for the files which have changed from the computer device to the primary storage device,

means for discarding the full index on the primary storage device,

means for forming a new index containing the index entries from the computer device, and

means for forming a backup data file containing the data,

a second state having

computer device indicating means for indicating to the computer device which files are identified in the full index on the primary storage device and the last modified date specified in the index entry for each file,

means for determining which files on the computer device have been changed or created since the last modified date indicated in the index entry for that file in the full index on the primary device,

file change indicating means for indicating that the file has been changed or created,

means for sending an index entry for each file on the disk and data for the files which have changed from the computer device to the primary storage device,

means for forming a new index containing the index entries from the computer device and a new backup data file by checking each index entry received from the computer device to see if the data associated with that entry has been changed and, if it has, then incorporating the associated data in the backup data file received from the computer device into the new backup data file, and if it has not been changed, then incorporating the associated data in the backup data file on the primary storage device into the new backup data file; and

a third state having

means for responding to said indicating means by transferring one or more backup data files and index associated with the disk from the primary storage device to the secondary storage device,

means for replacing the index on the secondary storage device with the index received from the primary storage device, and

means for forming a new backup data file by checking each index entry in the new index to see if the data associated with that entry has been changed and, if it has, then incorporating the associated data in the backup data file received from the primary storage device into a new backup data file, and if it has not been changed, then incorporating the associated data in the backup data file on the secondary storage device into a new backup data file.

12. The apparatus as defined in claim 11 wherein said interconnecting means is a communication network.

13. The apparatus as defined in claim 11 further including means for creating parallel processes to perform the backup initialization and the backup cycle.

14. The apparatus as defined in claim 11 wherein an index entry comprises:

a first field identifying a file;

a second field specifying a location of the file on a disk on the computer device;

a third field specifying a location of data associated with the file in a backup data file;

a fourth field specifying a length of the file identified by said first field; and

a fifth field indicating when the file was last modified.

15. In a networked computer system having a communication network interconnecting one or more primary storage devices, one or more secondary storage devices and a plurality of computer devices, each computer device having one or more storage resources, a method for transferring data from one or more of the storage resources, said method comprising the steps of:

initiating and controlling two or more concurrent processes by each active primary storage device, wherein each process initiates a connection between a computer device and a secondary storage device;

indicating when a transfer of data from the primary storage device to the secondary storage device should occur;

transferring data from the primary storage device to the secondary storage device in response to such indicating;

forming for a storage resource of a computer device a new index and a corresponding data file on a secondary storage device by comparing and merging data from a primary storage device index and data files with previously-existing index and data file corresponding to the storage resource, said previously-existing index and data file being stored on the secondary storage device;

checking whether the primary storage device has an index that defines the data from the storage resource;

if the primary storage device does not have the index, checking to see if the secondary storage device has such an index;

if the secondary storage device has a version of the index,

sending a copy of the secondary storage device version of the index to the computer device via the primary storage device,

if the secondary storage device does not have such an index,

copying data and corresponding information from the storage resource of the computer device to the secondary storage device,

storing the data in a data file on the secondary storage device or external storage devices connected to the secondary storage device, creating an index for accessing the data in the backup data file, and

storing a copy of the index from the computer device on the secondary storage device;

determining which data on the storage resource to update;

creating an index entry for the determined data;

sending index entries and a copy of the determined data to the primary storage device; and

forming a new index and a new corresponding data file on the primary storage device by comparing and merging newly-acquired determined data from the computer device contained in the most recent index and data files with the previously existing index and data files already stored on the primary storage device.

16. In a networked computer system having a communication network interconnecting a plurality of devices, the devices including one or more primary storage devices, one or more secondary storage devices and a plurality of computer devices, each computer device having one or more storage resources, a method for transferring among the devices data from the storage resources, said plurality of devices capable of creating a plurality of parallel processes, said method comprising the steps of:

assigning a secondary storage device to a storage resource;

performing a backup initialization operation for the storage resource from which data is being transferred, the backup initialization operation forming a first full index and a first backup data file for each storage resource being stored on a secondary storage device;

repeatedly performing backup cycles for the storage resource from which data is being transferred, during each backup cycle,

determining from which files and directories on the storage resource data should be transferred;

transferring from the computer device of the storage resource a second full index for the storage resource, the second full index having an entry for each file and directory on the storage resource, and a second backup data file for the storage resource, the second backup data file including data for the determined storage resource'"'"'s files and directories, and

storing the second full index and the second backup data file on the primary storage device, incorporating the second full index and the second backup data file with a previously-stored second full index and a previously-stored second backup data file, if any exist, on the primary storage device, the backup cycles being repeatedly performed until a transfer of data from the primary storage device is indicated;

indicating when a transfer of data from the primary storage device to a secondary storage device should occur;

transferring data from the primary storage device to the secondary storage device in response to such indicating, the data comprising with respect to a particular storage resource, the second full index and the second backup data file stored on the primary storage device;

incorporating the data transferred from the primary storage device into the first full index and the first backup data file stored on the secondary storage device to produce a new first full index having an index entry for each file and directory on the storage resource and a new first backup data file having data for each file and directory, the data for a particular index entry being from the second backup data file if the second backup data file contains data for that particular index entry and being from the first backup data file if the second backup data file does not contain data for that particular index entry; and

storing the new first full index and the new first backup data file on the secondary storage device.

17. The method of claim 16 further comprising the step of creating parallel processes to repeatedly perform the steps of claim 16 for multiple storage resources.

18. The method of claim 16 wherein the determination as to which data to transfer for a storage resource is based on which files and directories have been changed or created since a last transfer of data from the primary storage device to the assigned secondary storage device of the storage resource, such that the data of those files and directories are determined as the data to be transferred.

19. The method of claim 16 wherein the step of indicating a transfer from the primary storage device to the secondary storage device occurs at specified time intervals.