Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-11-09
2003-12-23
Choules, Jack M. (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
06668262
ABSTRACT:
BACKGROUND OF THE INVENTION
Historically, computer systems have stored data on a storage medium, such as in a file or database stored on a hard disk drive. However, such a storage medium is vulnerable to data loss due to a data corruption event, such as a physical failure of the hard disk or a power failure that suddenly shuts down the computer system. For example, such an event can corrupt the stored data by interrupting the writing of a block of data to a hard disk. Such a data corruption event can also cause a data file to be updated inconsistently, because a data change affecting different parts of the file is not applied to all of the parts of the file due to the event. Thus, some parts of the file are updated, and some parts that should be updated are not. In addition, a power surge due to a shutdown of the computer system, lightning strike, or problem in the external power source (e.g., electrical power utility) can cause an electrical signal or surge that results in data loss to different parts of the storage medium, such as a hard disk, resulting in a data file that is no longer valid.
Computer systems have mechanisms which guard against losing data. In one conventional approach, the computer system relies on a backup system to back up data files from the storage medium. Typically, the backups occur based on a predetermined time period or regular schedule, such as a daily backup. The backups can be a complete backup of all files on the storage medium, or can be an incremental backup. For example, an incremental backup system backs up only those data files that have changed within the time period.
In another conventional approach, an operating system provides for file system journaling for operations such as purging files or modifying directories, which is useful when there is an unexpected shutdown of the operating system or computer, or some other problem occurs that affects the state of the file system. In a further conventional approach, a computer system, an application executing on the computer system, or a database maintains a transaction log, which can be used to reinitiate the transactions interrupted or never initiated due to a data corruption event.
SUMMARY OF THE INVENTION
In the case of a failure, the conventional backup approach typically requires that a backup tape be located, often by a human operator, loaded on a tape drive, and read by the computer system to locate the files that have been corrupted. This approach can be time consuming and subject to failure if the backup tapes themselves fail for some reason, or human operators do not run the backup tapes reliably. The recovery process can be complicated when incremental backups are used, because, if a substantial number of files are lost, then several different incremental backup tapes may have to be located to recover all the files that were compromised.
In conventional approaches, such as those using a log or journal, there is typically no guarantee that the log or journal itself is not corrupt, or that a saved or retrieved version of a database is not also corrupted by the corruption event. Thus, in conventional approaches, a corrupt log or journal may be used to update a valid previous version of a database, leading to an invalid update to the database. Alternatively, in conventional approaches, a valid log or journal may be applied to a corrupt previous version of a database, also leading to an update to the database that is invalid.
The problem of recovering a corrupted database is more acute for computerized devices that may be shut down routinely by a power disconnection or other means. For example, this problem often applies to a network of devices, such as a router or other devices used in a content distribution network (CDN). Such network devices typically maintain a database (or hash table) including an identifier and configuration information for other similar devices on a network. The devices may be subject to sudden shutdowns because users expect to be able to disconnect the power cord, move or service the device, and reconnect the device as needed, without performing a backup procedure, or checking to see if a backup or journaling system is working properly. Such network devices typically are computers that do not provide such user-oriented input/output devices as graphic displays or keyboards for human users that would allow easy access to perform manual checking of backup or journaling systems. Thus, there is a need for a robust automatic recovery system designed to maintain such a database or hash table in such a device and enable rapid recovery of a valid version of the database if it is corrupted by a sudden shutdown or power surge.
In contrast, the invention is directed to techniques for modifying a database based on journals that include operations to be performed on the database. The journals enable verification of the validity of the operations prior to modifying the database in order to prevent corruption of the database due to the processing of an invalid operation. Furthermore, the journals enable recreation or recovery of the database using an older version of the database and archived journals.
In one arrangement, a database manager functions on a computerized device, such as a network device, to provide a robust recovery system for a database accessed by the computerized device. The database manager receives operations to be performed on the database, such as a write operation that enters a new data value or modifies an existing data value in the database, over a network or from some other source. The database manager enters the operations as operation records in a journal and generates an error detection value, such as a message digest, that can be used to check the validity of each operation record. The operation records are entered in the journal in the sequence to be used when applying the operation records to modify the database. After a predetermined number of entries have been made (or after a preset time period), the database manager copies the existing database to a new version of the database and modifies the copied database based on the operation entries from the journal. The database manager then generates an error detection number for the modified version of the database and clears the entries from the journal, so that a revised version of the journal can be started. The database manager then adds additional operation records to a revised version of the journal, makes a new copy of the modified database, and modifies the copy of the modified database with the additional operation records. The database manager then continues a process of clearing the journal, producing new versions of the journal with additional operation entries, and producing new modified versions of the database.
If there is a data corruption event, the database manager can check the validity of earlier versions of the database by using the error detection number for each database. The database manager can thus determine the most recent valid version of the database. Assuming, for example, that the current database is invalid, then the database manager checks the different versions of the journals and applies the versions of the journals to the most recent valid version of the database to produce a current, valid version of the database. The database manager checks the validity of each operation entry in each journal by checking the error detection number for each operation entry. Thus, the database manager uses the verified operation entries to revise the most recent valid version of the database until encountering an operation entry that is not valid, as indicated by the error detection number for that operation entry. The database manager can then generate an error signal indicating that the database has been partially recovered, and provides the signal to the computerized device or over the network to some destination, such as a network monitoring computer operated by a human operator. Then, for example, the monitoring computer or human operator can determine if the partial recovery
Chapin & Huang , L.L.C.
Choules Jack M.
Cisco Technology Inc.
Huang, Esq. David E.
LandOfFree
Methods and apparatus for modifying a database does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for modifying a database, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for modifying a database will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3131284