Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-02-09
2004-05-04
Channavajjala, Srirama (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C714S015000, C714S016000, C711S119000, C711S120000, C711S142000, C711S152000, C711S161000, C711S162000
Reexamination Certificate
active
06732124
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a data processing system with capabilities to recover its file systems, and also to a computer-readable medium storing a program designed therefor. More particularly, the present invention relates to a data processing system which can recover from system failures by using log records to restore the consistency of its file system structure, as well as to a computer-readable medium storing-a program providing such failure recovery functions.
2. Description of the Related Art
A computer system fails for various reasons, often introducing some inconsistencies in its file system structure. In the event of an abnormal shutdown, the computer system has to be rebooted, and the file system is entirely scanned to test whether any inconsistent entry has been produced. If any problem is found in this test, the computer system applies an appropriate modification to the file system in question, thereby restoring its consistency.
Scanning an entire file system, however, takes a long time, hampering a prompt failure recovery of the computer system. To reduce the down time, many of the modern computer operating systems (OS), such as UNIX OS, employ a certain mechanism to restore the file systems by using transaction logs. That is, any modifications or updates made to data in a computer file system are recorded in a log (or journal) file, and in case of a system failure, the file system would be restored through the process of scanning the log file and reapplying recorded updates to their destinations. The use of such a transaction logging mechanism reduces the system's down time theoretically, but at the same time, it poses several technical challenges as described below.
(1) Supporting Multi-volume Secondary Storage
Besides handling files themselves, the file systems have to manage what is called “metadata.” The term “metadata,” denoting “data about data” literally, refers herein to such data that describes the location, size, and other information about each file stored in a computer's secondary storage unit. While metadata objects are also stored in a prescribed portion of a secondary storage unit, they are normally read out to the main memory of the computer system for the purpose of faster access and manipulation. In other words, metadata is cached on the computer's main memory. Updated metadata objects are written back to the secondary storage unit at predetermined intervals, so that every modification made to the cached metadata will be reflected in their original entities in the secondary storage unit some time later. To ensure the successful recovery of file systems, it is mandatory for the logging system to save all recent records of such metadata modifications into its dedicated secondary storage subsystem before the cache contents are copied back to the secondary storage unit.
Some systems have a plurality of secondary storage units to provide for larger file systems. In such systems, a single file system operation may manipulate metadata objects managing multiple secondary storage units. To log this file system operation, conventional logging systems record every modification made on the metadata cache memory. However, the log records collected in this way would not serve satisfactorily, because it would take much time for the computer system to search the log records for relevant metadata objects stored in different secondary storage units. This means that the conventional logging systems are not effective in reducing the down time in such environments where metadata objects are distributed in multiple secondary storage units.
(2) Time for Scanning of Log Records
Another factor that delays the file system recovery is the time required for searching the entire log storage to find the oldest log record. This issue will be discussed below.
The logging system interacts with individual transactions which constitute a file system operation, and it collects records solely for such transactions that have committed, or successfully finished. To ensure this scheme, most file systems with a logging mechanism are configured to assign a sequence number to each transaction. When restoring such file systems, the logging system attempts to identify the oldest transaction on the basis of sequence numbers affixed to the stored log records. The logging system then starts a log replay from the identified point.
Log records should be saved in a dedicated secondary storage device, in preparation for possible system failures. While log records are produced endlessly, the storage for them is limited in size. This suggests that the logging system must reuse the limited storage resource in a cyclical manner, and to do so, it has to overwrite old records with new ones. In actuality, many of the stored log records are obsolete (i.e., not to be used to restore the file system), while the others are essential for file system recovery. Scanning the entire log storage to identify the oldest transaction means reading and testing many obsolete log records. This is obviously inefficient.
(3) Sequence Number Overflow
When searching for the oldest transaction, the system presupposes that the sequence numbers increase monotonously; they will never overflow or return to zero during logging operations. Typical logging systems prevent the sequence number from overflowing or wrapping around by reinitializing the log storage to zeros, when a file system restoration process is completed, or when it is detected that the sequence number will soon overflow. Such logging systems then resume their operation, restarting the sequence number from zero. However, it takes a long time to reinitialize the entire log storage, during which the computer systems are unable to provide their services. If they are working as servers, the interrupt of services would pose intolerable stress to their clients.
While the above three problems (1) to (3) relate to the restoration of a file system, the introduction of a logging system can even cause adverse effects to normal operations of the target computer systems. More specifically, there are several known techniques to realize high-speed access to secondary storage devices for logging purposes, which include log spooling on memory and sequential access optimized for specific disk structures. However, with those techniques alone, usable file recovery systems cannot be realized. Rather, to make such systems truly practical, it is necessary to develop more enhanced log collection and storage methodologies. Otherwise, computer systems would suffer from considerable penalties in throughput and storage efficiencies. The following will enumerate several specific issues that must be addressed.
(4) Increased Secondary Storage Traffic
It is often seen that a single transaction updates the same data object a number of times. The system may produce a log record each time an update occurs, but this log collection practice consumes more memory resources, as well as raises input/output traffic from/to the secondary storage unit for logging.
(5) Logging of Concurrent Transactions
The logging system collects information on what updates have been made by individual transactions and records a set of such updates each time one transaction is completed, because the log must preserve the correct order of transaction executions. This generally means that no transactions can update a specific data object if it is being manipulated by another ongoing transaction. It may be relatively easy to implement this rule in the case of handling individual files; a plurality of transactions can proceed concurrently, while maintaining exclusive access to each file. However, the concurrent execution of transactions can be a challenge, when a plurality of transactions manipulate data controlling multiple files, such as a resource allocation map used to assign a storage space, etc.
Suppose, for example, that one transaction A was freeing up its allocated space, while another transaction B needed a free space, and as a result, the spa
Hamanaka Seishiro
Koseki Michihiko
Sumi Masashi
Taniwaki Sadayoshi
Yamaguchi Satoru
Channavajjala Srirama
Fujitsu Limited
Greer Burns & Crain Ltd.
LandOfFree
Data processing system with mechanism for restoring file... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Data processing system with mechanism for restoring file..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Data processing system with mechanism for restoring file... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3254439