Performing data backups with a stochastic scheduler in a distributed computing environment

[0002] The present invention relates in general to data backups and, in particular, to system and method for performing data backups with a stochastic scheduler in a distributed computing environment.

[0003] Maintaining complete and accurate data backups are an important part of modem information technology practices. Data backups must be performed on a regular basis to be most effective in ensuring that critical,data is not lost. Historically, data backups were performed predominantly using removable forms of storage media, such as streaming tapes, removable drum and disk drives, floppy diskettes, and similar forms of recordable media. Although data backups are still performed using these types of media, contemporary enterprise, workgroup and mobile computing practices present a broader set of needs than can be met by these traditional backup methodologies alone.

[0004] A typical workgroup computing environment contains individual client systems interconnected over a local area network or “intranetwork” located in a departmental setting. An enterprise computing environment generally contains individual intranetworks interconnected over a wide area network or “internetwork” located in a company wide setting. Often, the internetworks includes geographically distributed resources which, when taken as a whole, comprise a unified set of loosely associated computers. The Internet is an example of a widely used public internetwork that can form part of an enterprise computing environment.

[0005] Data backups in these environments are generally directed to a centralized server that requests or polls individual clients for data backups on a regularly scheduled basis. However, backup schedules must be coordinated to occur during periods of inactivity for each client without causing client-against-client contention and differences between individual systems, such as hardware configurations and operating systems, must be addressed.

[0006] By comparison, mobile computing environments generally consist of conventional notebook and portable computers, but has increasingly included thin clients (diskless workstations), handheld personal data assistants, and other forms of portable and highly portable computing devices. Unlike non-mobile client systems, devices operating in a mobile computing environment, by definition, often function in isolation from other systems. Consequently, data backups must often be deferred until a connection with a data backup server is established.

[0007] Independent of computing environment, successfully performing and managing data backups can be difficult and time-consuming. For instance, contention between competing clients concurrently vying to perform data backups must be reconciled. As well, any client-installed software must be consistently configured and kept up-to-date. Furthermore, in the event of corruption, configuration parameters must be readily recoverable without requiring manual reinstallation at each client.

[0008] Several prior art data backup applications attempt to provide solutions to these concerns, including Net Backup, licensed by Veritas, Mountain View, Calif.; Networker, licensed by Legato, Sunnyvale, Calif.; and Quick Backup, licensed by McAfee, Santa Clara, Calif. To varying degrees, these solutions fail to satisfactorily address the data backup needs for enterprise, workgroup and mobile computing environments. For instance, the Net Backup application does not allow for automated backup of Registry-files. The Legato and Quick Backup applications are primarily directed to performing data backups in non-mobile computing environments. All of these solutions offer limited customizability, particularly in terms of offering flexible feature sets and in their ability to scale between different environments.

[0009] Therefore, there is a need for an approach to performing data backups in enterprise, workgroup and mobile computing environments that avoids conflicts in backup schedules, yet can accommodate the needs of infrequently connected clients. Preferably, such an approach offers a client-based solution that “pushes” data sets to a backup server.

[0010] There is a further need for a data backup approach that encapsulates configuration parameters in a monolithic application package, thereby facilitating self-configuration and updates.

[0011] The present invention provides a backup session application that includes a stochastic scheduler for generating a random start time. A data set including individual files with tracked file attributes is regularly copied into a backup data set stored on a centralized server. A data backup session only commences upon a successful connection and failed data backup sessions can be later resumed without duplication of previous file copying. Configuration parameters are encapsulated within the backup session application. Deleted files are maintained on the centralized server until a waiting period has expired.

[0012] An embodiment of the present invention is a system and method for performing a data backup with a stochastic scheduler in a distributed computing environment. A data set on a client is tracked. The data set is to be maintained with a backup data set on a centralized server within the distributed computing environment. A time period during which to initiate a data backup session for the tracked data set is selected. An instance of a backup session application on the client is periodically executed. The client attempts to initiate a connection with the centralized server beginning at a random start time during the selected time period. The client regularly reattempts the connection initiation following each failed connection initiation attempt. The tracked data set is selectively copied into the backup data set upon a successful connection initiation. Upon each successful data backup session for the tracked data set, a new random start time within the selected time slice for a next data backup session is generated.

[0013] Still other embodiments of the present invention will become readily apparent to those skilled in the art from the following detailed description, wherein is described embodiments of the invention by way of illustrating the best mode contemplated for carrying out the invention. As will be realized, the invention is capable of other and different embodiments and its several details are capable of modifications in various obvious respects, all without departing from the spirit and the scope of the present invention. Accordingly, the drawings and detailed description are to be regarded as illustrative in nature and not as restrictive.

[0014] FIG. 1 is a block diagram showing a distributed computing environment, including a system for performing data backups with a stochastic scheduler, in accordance with the present invention;

[0015] FIG. 2 is a detail block diagram showing a client and server pairing of the system of FIG. 1;

[0016] FIG. 3 is a block diagram showing the functional software modules of the backup session application of FIG. 2;

[0017] FIG. 4 is a table diagram showing, by way of example, an index file;

[0018] FIG. 5 is a table diagram showing, by way of example, a log file;

[0019] FIG. 6 is a flow diagram showing a method for performing data backups with a stochastic scheduler in accordance with the present invention in accordance with the present invention;

[0020] FIG. 7 is a flow diagram showing a routine for performing a backup session for use in the method of FIG. 6;

[0021] FIG. 8 is a flow diagram showing a routine for performing a self-update for use in the method of FIG. 7;

[0022] FIG. 9 is a flow diagram showing a routine for performing a reconfiguration for use in the method of FIG. 7;

[0023] FIG. 10 is a flow diagram showing a routine for performing a data backup for use in the method of FIG. 7; and

[0024] FIG. 11 is a flow diagram showing a routine for determining a next backup session scheduling for use in the method of FIG. 6.

[0025] FIG. 1 is a block diagram showing a distributed computing environment 10, including a system for performing data backups with a stochastic scheduler, in accordance with the present invention. The distributed computing environment 10 consists of a plurality of individual clients 11 interconnected with a centralized server 12 via an intranetwork 13. In turn, the clients 11 and centralized server 12 are connected to an internetwork 15, such as the Internet, through a router 14. Mobile clients 16 and other remote clients 17 can access the intranetwork 13 via the internetwork 15. Other network topologies and configurations of machines and network resources are feasible.

[0026] Each of the clients, including intranetwork clients 11, mobile clients 16 and remote clients 17, execute a backup session application 18 (BSA) to periodically perform a data backup to the centralized server 12. The backup session application 18 provides client-based “push” data backups and employs a stochastic scheduler to avoid contention between clients simultaneously competing for access to the centralized server 12.

[0027] The individual computer systems, including intranetwork clients 11, mobile clients 16, remote clients 17, and centralized server 12, are general purpose, programmed digital computing devices consisting of a central processing unit (CPU), random access memory (RAM), non-volatile secondary storage, such as a hard drive or CD ROM drive, network interfaces, and peripheral devices, including user interfacing means, such as a keyboard and display. Program code, including software programs, and data are loaded into the RAM for execution and processing by the CPU and results are generated for display, output, transmittal, or storage.

[0028] FIG. 2 is a detail block diagram showing a client and server pairing 20 of the system of FIG. 1. The client 21 could be a fixed machine, either local or remote, or mobile. Both the client 21 and backup server 22 are interconnected through some means of connection 31, such as a serial, intranetwork, internetwork, telephonic, infrared, or similar interface or combination thereof. In addition, the client 21 and backup server 22 both include a storage device 23, 24, respectively, providing persistent data storage.

[0029] The client 21 executes a backup session application 25 providing the necessary functionality for performing data backups on the backup server 22. The backup session application 25 is self-contained and encapsulates an initial configuration. The backup session application 25 maintains a set of support files 26, including a local configuration file, on the storage device 23. As a backup, however, the backup session application 25 also stores a remote configuration file 29 on the storage device 24.

[0030] The backup server 22 does not execute any backup applications. Rather, the client 21 “pushes” backups of a data set 27 maintained on the storage device 23 to the backup server 22 on a regular, stochastically scheduled basis. The backup server 22 includes some form of storage manager 28, such as a file or database manager, with which the backup session application 25 interfaces to effect storage of a backup data set 30 on the storage device 24.

[0031] FIG. 3 is a block diagram showing the functional software modules of the backup session application 25 of FIG. 2. Each module is a computer program written as source code in a conventional programming language, such as the C++ programming language, and is presented for execution by the CPU as object or byte code, as is known in the art. The various implementations of the source code and object and byte codes can be held on a computer-readable storage medium or embodied on a transmission medium in a carrier wave.

[0032] The backup session application 25 consists of eight modules: configuration generator 41, installer 42, uninstaller 43, simple version 44, enterprise version 45, stochastic scheduler 46, self-updater 47, and manual backup 48. The backup session application 25 maintains support files 26 locally in the storage device 23, including a .ini file 49, an index file 50, and a log file 51, and maintains a configuration file 29, including a backup .ini file 53, remotely in the storage device 24. The individual files 52 in the data set 27 are the primary inputs of the backup session application 25 which copies select files 52 as copied files 54 into the backup data set 30. The backup session application 25 operates in accordance with a sequence of process steps, as further described below beginning with reference to FIG. 6.

[0033] Functionally, the configuration generator 41 encapsulates configuration parameters within the backup session application 25 itself. These configuration parameters determine, in part, the default timing, feature set and version of the backup session application 25. The configuration generator 41 maintains a persistent configuration file, call a “.ini” file 49, as well as a backup .ini file 53, on the client 21 and server 22, respectively. In the event of corruption of the .ini files, the local .ini file 49 will override a corrupt backup .ini file 53 and the encapsulated configuration parameters will override both corrupt .ini files. Thus, the encapsulated configuration parameters ensure that the operation of the backup session application 25 can be recovered without requiring manual reinstallation. In addition, the encapsulated configuration parameters allow dynamic self-updating and reconfiguration.

[0034] In the described embodiment, the backup session application 25 can be configured as a “simple” version 44 with a minimal feature set or as an “enterprise” version 45 with an extended feature set. Internally, the backup session application 25 is identical irrespective of the configured version. However, the user interface is tailored to reflect the available features under the premise that an enterprise installation might require further local customization of configuration parameters than a smaller-scale installation.

[0035] The installer 42 module performs installation of the backup session application 25 on a new machine, including creating the necessary persistent copies of the .ini file 49 and backup .ini file 53. Conversely, the uninstaller 43 module uninstalls the backup session application 25 and any related components and support files. In the described embodiment, the installer 42 and uninstaller 43 modules conform to the standard installation/deinstallation guidelines for Microsoft Windows-compliant applications.

[0036] The stochastic scheduler 46 generates a random start time for a backup session. The user selects a time slice defining a data backup session time period. The stochastic scheduler 46 chooses a unique random start time within this time slice. Since each client 21 is similarly running a stochastic scheduler 46, contention between competing backup sessions is significantly reduced or eliminated by the start time randomness factor.

[0037] The self-updater 47 allows the backup session application 25 to be dynamically updated. At the start of every data backup session, the self-updater 47 determines whether a new version of the backup session application 25 is available on the backup server 22. If so, the new version is downloaded and the executing backup session application 25 is dynamically replaced with an instance of the new backup session application 25.

[0038] The manual backup 48 module allows a user to override the stochastically scheduled start time for the next data backup session. Thus, a user can force a full or incremental data backup on demand.

[0039] FIG. 4 is a table diagram 60 showing, by way of example, an index file 50. The index file 50 contains a plurality of entries 61, one entry 61 per file 52 in the data set 27. Each entry 61 contains three columns of information. The backup date 62 column stores the last date upon which the file 52 was successfully backed up. The file date 63 column stores, as file attributes, the date and time of the last modification to the file 52. Finally, the file path 64 column stores the physical machine location of the file 52. For instance, the example entry indicates a successful backup of the file “\\client 5\C\data\foo” occurred on Jun. 5, 2000 and that this file was last modified on Jun. 7, 2000 at precisely 2:30 pm. Other forms of table and data organization are feasible.

[0040] FIG. 5 is a table diagram 70 showing, by way of example, a log file 51. The log file 51 contains a plurality of entries 71, one entry 71 per data backup session. Each entry 71 contains three columns of information. The backup type 72 column stores an indication of the outcome of the data backup session, that is, “full,” “incremental” or “failed.” The date 73 column stores the date of the data backup session. Finally, the number of files 74 column stores the number of files backed up. For instance, the example entry indicates an incremental backup (“I”) of 258 files occurred on Jun. 5, 2000. Other forms of table and data organization are feasible.

[0041] FIG. 6 is a flow diagram showing a method for performing data backups with a stochastic scheduler 80 in accordance with the present invention. The method performs continuously as a background process on the client 21 (shown in FIG. 2). However, if the client 21 is mobile and not connected to a backup server 22 at the time that a backup session is attempted, the data set backup is deferred until at least the next backup session.

[0042] Between backup sessions, the data set 27 is tracked (block 81) for addition, modifications and deletions. Generally, the data set 27 is tracked indirectly by the operating system, which automatically places a date and time stamp on the individual files 52 (shown in FIG. 3) in the data set 27 upon creation or modification. At the stochastically scheduled time, as explained further below with reference to FIG. 11, the backup session application 25 wakes up (block 82), that is, is activated to attempt a data backup session. If the client 21 busy processing other tasks (block 83), the backup session application 25 waits (block 84) for a predetermined time period. A default time period of ten minutes is used in the described embodiment.

[0043] Otherwise, if the client 21 is idle (block 83), the backup session application 25 determines whether a suitable connection 31 to the backup server 22 is present (block 85). For instance, if the client 21 is mobile, a connection 31 might only be available when the client 21 is physically attached to the backup server 22. Similarly, a low speed connection might be the only means of connecting, but would otherwise be unsuitable for performing a backup session due to low bandwidth. The backup session is stochastically rescheduled (block 92), as further described below with reference to FIG. 11, if there is no suitable connection.

[0044] If a suitable connection 31 is present (block 85), the backup session application 25 next determines whether the backup server 22 is available (block 86). “Available” means that the backup server 22 has the necessary capacity to host a backup session in terms of available bandwidth and storage.

[0045] Finally, if the backup server 22 is available (block 86), the backup session is performed (block 87), as further described below with reference to FIG. 7. If the backup session fails (block 88), a backup failure entry 71 (shown in FIG. 5) is recorded in the log file 51 (block 89). Otherwise, a success backup entry 71 is recorded in the log file 51 (block 90).

[0046] If the backup session application 25 remains live (block 91), the next backup session is stochastically rescheduled (block 92), as further described below with reference to FIG. 11, and the backup session application 25 goes to sleep (block 93), that is, sleeps, until the time for the next backup session attempt. Otherwise, if the backup session application 25 has been terminated (block 91), the method exits.

[0047] FIG. 7 is a flow diagram showing a routine for performing a backup session 100 for use in the method of FIG. 6. The purpose of this routine is to process any updates and configuration changes and to backup, or resume a failed backup of, the data set 27 on a file-by-file basis. Thus, if, upon establishing a connection to the backup server 22, a new update of the backup session application 25 is found (block 101), the update is processed (block 102), as further described below with reference to FIG. 8. In the described embodiment, the backup session application 25 compares the size of the currently executing version to any new version found on the backup server 22. Similarly, if a new configuration for the backup session application 25 is found (block 103), the reconfiguration is processed (block 104), as further described below with reference to FIG. 9.

[0048] The backup session application 25 can resume a failed backup session using the log file 51 (shown in FIG. 3). If last entry 71 (shown in FIG. 5) in the log file 51 indicates a failed backup (block 105), the name of the last successful file 52 to be backed up is determined from the index file 50 (block 106). The backup session then begins with the next file 52.

[0049] Finally, the actual data backup executes (block 107), as further described below with reference to FIG. 10. The files 52 (shown in FIG. 3) in the data set 27 are backed up on a file-by-file basis. The routine then returns.

[0050] FIG. 8 is a flow diagram showing a routine for performing a self-update 110 for use in the method of FIG. 7. The purpose of this routine is to dynamically replace an executing backup session application 25 with an updated version. The self-update is only performed over a connection 31 having sufficient bandwidth. In the described embodiment, network connections are favored and dial-up connections are considered unsuitable for self-updates.

[0051] Thus, if the connection has low bandwidth (block 111), the self-update is skipped and the routine returns. Otherwise, the new backup session application 25 is copied from the backup server 22 (block 112). If the copy fails (block 113), the self-update is skipped and the routine returns. Otherwise, the currently executing backup session application 25 is swapped with an executing instance of the new backup session application 25 (block 114).

[0052] In the described embodiment, the copied backup session application 25 is executed as an interim process using a temporary process name. The interim process terminates the currently executing backup session application 25 and starts a third instance of the backup session application 25 using the same process name as the original backup session application 25. Other techniques for swapping an executing process instance are feasible.

[0053] FIG. 9 is a flow diagram showing a routine for performing a reconfiguration 120 for use in the method of FIG. 7. The purpose of this routine is to dynamically reconfigure an executing backup session application 25.

[0054] This routine is similar to the routine for performing a self-update 110. However, the new backup session application 25 is self-generated and contains revised, encapsulated configuration parameters. In the described embodiment, the backup session application 25 includes a reserved memory space of approximately 500 bytes for storing the configuration parameters. The first time the backup session application 25 executes, these configuration parameters are written out as a .ini file 49 (shown in FIG. 3) and copied as a backup .ini file 53. The encapsulated configuration parameters represent default values for the execution of the backup session application 25, thereby ensuring that the backup session application 25 is at minimum self-configuring in the event of the loss of both the .ini file 49 and backup .ini file 53.

[0055] Thus, a new instance of the backup session application 25 is created with encapsulated configuration parameters (block 121). The currently executing backup session application 25 is then swapped with an executing instance of the new backup session application 25 (block 122).

[0056] In the described embodiment, the reconfigured backup session application 25 is executed as an interim process using a temporary process name. The interim process terminates the currently executing backup session application 25 and starts a third instance of the backup session application 25 using the same process name as the original backup session application 25. Other techniques for swapping an executing process instance are feasible.

[0057] FIG. 10 is a flow diagram showing a routine for performing a data backup for use in the method of FIG. 7. The purpose of this routine is to perform a file-by-file backup and to process a deferred deletion of files. The routine proceeds in two iterative processing loops for backing up individual files 52 (blocks 131-139) and deleting expired files (blocks 140-144).

[0058] During the first processing loop (blocks 131-139), each file 52 is retrieved (block 132) and, if present in the index file 50 (block 133), checked for changed file attributes (block 135). If the file attributes have changed (block 135), the file 52 is copied into the backup data set (block 136). Otherwise, the file 52 is skipped. In the described embodiment, changed file attributes are detected by comparing the date and time of the file 52 against the file date 63 stored in corresponding entry 61 in the index file 50. Other techniques for detecting changed file attributes are feasible. If the retrieved file 52 is not in the index file 50 (block 133), a new entry 61 is made in the index file 50 (block 134) and the file 52 is copied (block 136).

[0059] If the file copying is successful (block 137), the backup date 62 in the corresponding entry 61 in the index file 50 is updated (block 138) and iterative processing continues with the next file 52. Otherwise, if the file copying was unsuccessful (block 137), the routine returns.

[0060] During the second processing loop (blocks 140-144), each file 52 is checked for a marking for deletion. Any file 52 not marked for deletion is skipped (block 141). Similarly, any file 52 marked for deletion but not older than 30 days is skipped (block 142). Thus, only those files 52 which are both marked for deletion and older than 30 days are deleted from the backup data set 30 (block 143). Iterative processing continues with the next file 52. The routine returns after the last file 52 has been processed.

[0061] FIG. 11 is a flow diagram showing a routine for determining a next backup session scheduling 150 for use in the method of FIG. 6. The purpose of this routine is to generate a stochastically scheduled backup session. A time slice specified by a desired start time and end time is selected (block 151). A start time for the next data backup session falling within the time slice is randomly chosen (block 152). If the chosen start time was previously used (block 153), a new random start time is generated (block 152). The routine returns upon the successful generation of a start time.

[0062] In the described embodiment, the time slice is expressed as a percentage of a day beginning at midnight. Thus, for example, 25% would indicate a time slice starting at midnight and ending at 6:00 am, that is, falling within the first quarter of the day. A start time is randomly chosen within the time slice using a random number generation function, such as rand( ). Other random number functions or techniques could be used, as would be recognized by one skilled in the art.

[0063] While the invention has been particularly shown and described as referenced to the embodiments thereof, those skilled in the art will understand that the foregoing and other changes in form and detail may be made therein without departing from the spirit and scope of the invention.