Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-11-13
2001-02-20
Kulik, Paul V. (Department: 2777)
Data processing: database and file management or data structures
Database design
Data structure types
C702S010000
Reexamination Certificate
active
06192376
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to data processing systems which utilize hierarchically arranged file systems to facilitate data access and, more particularly, to a method and apparatus for assuring an ability to recover in the event of an error during update of an index to a hierarchical file system.
BACKGROUND OF THE INVENTION
A hierarchical file system (HFS) is utilized by many computational systems to enable ready-access to individual files within a large file system. Such systems may include thousands to tens of thousands of files and the search time for any file may become quite large if a linear search technique is utilized through respective addresses. By using a hierarchical index, the search procedure is greatly speeded, allowing rapid access to a desired file.
FIG. 1
illustrates the logical structure of an HFS index array which provides a means for moving from an anchor point
10
, through a root page
12
and down through various levels of index pages
14
,
16
,
18
to a desired record
20
. An HFS has between two and many indexes. Each index can be logically viewed as a data structure, commonly called a B-tree. In such a tree, there is one root node
12
that may change in the course of normal updates. Root node
12
may be an only page in the index or may point to other pages, as is most often the case. Any page that points to another page (or pages) is hereafter called an “index” page. Any page that does not point to another page is hereafter called a “sequence” page. A sequence page (e.g.,
20
) resides at the “end” of a series of pointers within the index and contains the actual data being sought.
During operation of an application program, index updates are required on a continuing basis. An HFS index must be atomically updated to preserve its integrity. Further, if a cancel or other interruption occurs during the course of an update or between two update requests, the system must preserve any prior changes that have been made. Normally, in current implementations of shadowed index operations, each individual update results in a corresponding input/output operation to “harden” the new index data. This avoids the complications of providing code to recover in the case of an error. However, because of the large number of updates which occur during operation of an application program, writes to disk of index changes are often delayed until a period of time has passed, during which a number of updates to the index can occur. At such time, all updates are then written to disk. Until that time, the changed index values/control blocks are maintained in virtual storage.
By delaying the hardening of such index updates to disk, system performance is substantially improved as a result of the decrease in number of time-consuming disk input/output actions that are required. However, by maintaining such changed index records in volatile memory, controls must be implemented to assure a system/data recovery capability in the event of an error or cancel action.
As will be hereafter understood, an index is a key-ordered file of unique index records. The B-tree which is utilized to implement an HFS is divided into two entities, an index set and a sequence set. As shown in
FIG. 1
, the pages at the lowest level of a B-tree are collectively called the sequence set and contain the actual index records. The higher levels are collectively called the index set and consist of routing nodes (or “pages”). A routing node is a special kind of index record which contains an index key and a pointer to an index page in a next lower level of the same B-tree, i.e., a “down-pointer”.
Each index includes a set of attributes which a caller provides when the index is created. These attributes are used to manage the index for the caller. The attributes identify the index and describe the characteristics of the index. A name directory includes pointers to metadata in the attribute data. Metadata is information which identifies a file size, where to find the file, and other characteristics of the file that are required for its access.
To search a hierarchical index, an anchor point
10
indicates the initial point of entry which is root page
12
. The root page contains a down pointer to a next lower level index page. The down pointers are followed until the sequence set is reached, at which point, the actual index data can be found. The index manager maintains the integrity of the index throughout the update operation, until the shadow copy is hardened to disk.
In order to enable recovery of data in the event of error or interrupt, the prior art has utilized a method of making mirrored or shadowed copies of user data files. Such a system is disclosed in U.S. Pat. No. 5,638,509 to Dunphy et al. wherein an index of all data file activity on a computer system is maintained and copies of data files are made so as to enable a user to recreate the state of the computer system at any selected point in time. A data file monitor intercepts all communications between an application and the file system to obtain data file status and activity information. This information is used to identify data files which are transmitted to backup media for storage, along with directory information to be used to later locate and retrieve such data files. Such systems require continued accesses to the back-up media which inhibits system throughput capabilities.
U.S. Pat. 5,664,186 to Bennett et al. describes a file management and backup system, wherein a copy of a file or file system is logically frozen in time while a backup is made. The central idea described in Bennett et al. patent is that a backup copy is made, either to disk or tape, while allowing continued access and updates to the object being backed up. U.S. Pat. No. 5,706,510 to Burgoon describes a system for management of files in a shared file system. During an update of a file, a user obtains a writable copy of a file. When an edited file is entered into a history of the managed file system, a read-only copy of the file remains on the user's disk. When the user updates the file system, the read-only file copy may be replaced with a link which enables access to a current version of the shared file. Rather than viewing a current version of a shared file, the user may wish to maintain a tatic file version by maintaining a link thereto.
It is an object of this invention to provide an improved method and apparatus for enabling a deferral of writing of index data to disk so as to reduce the number of disk I/O's.
It is another object of this invention to provide a method and apparatus for updating index data, while deferring its writing-to-disk, and at the same time, enabling error recovery and cancel protection for any index update that is in process.
SUMMARY OF THE INVENTION
The method of the invention updates a tree arranged index for an hierarchical file system (HFS) The index includes at least one index value, i.e., an index page, that is logically positioned between an index anchor value and a sequence page. The sequence page includes actual index data. Logical positioning of the index page is determined by one or more pointers. The method initially responds to an index update request by making an update “shadow” copy of (i) a sequence page and (ii) any other index pages, up to and including a root page, that are to be updated in accord with the update request. Thereafter, an index manager updates the shadow copy of the sequence page in accord with the update request. The index manager further updates the root page and each shadowed index page that is present in a path to the updated sequence page to indicate that the path has been updated and includes the most current data. If a cancel or error indication occurs prior to updating of the index path, the shadowed copies of the sequence page, index page and root page are released, enabling the system to return to the non-updated pages. Otherwise, the index manager updates the index anchor value to point to the updated root page, thereby indicating that the index update has been successfu
Kincaid W. James
Levish David
Mahon Thomas A.
International Business Machines - Corporation
Kulik Paul V.
Ohlandt Greeley Ruggiero & Perle L.L.P.
LandOfFree
Method and apparatus for shadowing a hierarchical 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 Method and apparatus for shadowing a hierarchical file..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for shadowing a hierarchical file... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2561972