Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1999-02-19
2001-05-08
Kulik, Paul V. (Department: 2177)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S118000, C711S154000
Reexamination Certificate
active
06230243
ABSTRACT:
TECHNICAL FIELD
This invention relates, in general, to the managing of changed data stored in a coupling facility cache structure, and in particular, to efficiently identifying the oldest changed data within castout classes of the cache structure.
BACKGROUND ART
A cache structure is a high-speed cache shared by one or more independently-operating computing units of a computing environment. In particular, cache structures are located within a remote facility, referred to as a coupling facility, that is coupled to the one or more independently-operating computing units. The computing units store and retrieve data from the cache structures.
Coupling facility cache structures can be configured in several different modes of operation, one of which is a store-in mode. Store-in mode caches are used, for example, by the DB2 database management facility of International Business Machines Corporation. A key attribute of the store-in mode is that changed data may be stored into the non-volatile memory of the coupling facility using the high performance coupling facility links. This avoids the delay in the execution of database transactions that result when the data is written to secondary storage (e.g., direct access storage devices (DASD)) using normal input/output (I/O) operations, and is an advantage of the coupling facility cache.
The store-in mode requires, however, that the database program provide background tasks, called castout processes, to periodically write the changed data, using batched I/O operations to the database locations on DASD. In order to enhance the performance of the I/O operations, the changed data are grouped by physical DASD volume into castout classes.
The castout processes provide two key functions: First, they ensure that the cache does not become full of changed data, and thus, keeps the percentage of changed versus unchanged data in the cache at or below certain thresholds. Second, the castout processes ensure that the amount of time a database page can reside in the cache in the changed state is bounded by some predetermined value. This bound is critical in those cases in which the coupling facility fails and database logs are needed to recover the lost data. The bounding of the amount of time a page can remain changed in the cache, bounds how far back in time the logs must be processed, and thus, bounds the amount of time needed to perform the recovery operation. Bounding this recovery time is critical in meeting the availability goals of the database.
In order to satisfy the bounds, it is important for the castout processes to be able to efficiently determine the age of the oldest changed page in the cache. This determination cannot be based solely on the arrival pattern of the requests, since the timestamps associated with the transactions and stored in the database log do not correspond to the arrival of the data at the coupling facility. They occur at different times. Also, the coupling facility services numerous coupling facility links in parallel, and so the sequence at which requests arrive at the facility does not correspond to the sequence in which they are executed. Thus, more information is required. This additional information is provided in an object associated with each changed page written to the coupling facility, called the user data field (UDF). The UDF object contains the timestamp that the database associates with the changed page. The UDF object is stored in a directory entry associated with the changed page and can be retrieved by issuing a read directory command.
Conventionally, the castout processes determine the oldest timestamp value in the directory by scanning the entire directory each time a castout process executes. This requires issuing numerous read directory commands to retrieve all of the UDF values in the cache, so that the oldest changed page can be identified. Since, the directory for a large cache may contain several million directory entries, significant overhead is realized in the coupling facility when the directory scan is executed. Further, a castout process needs to execute every few minutes, and thus, the overhead is exacerbated. It has even been necessary to purchase additional central processing unit (CPU) engines for the coupling facility to satisfy the scan.
Based on the foregoing, a need exists for a capability that enables the efficient determination of the age of the oldest changed page in a cache structure without requiring the need to scan the entire cache directory. A further need exists for a capability that manages changed data in a cache structure in a manner that does not degrade system performance. A yet further need exists for a capability that manages the changed data in a manner that enhances castout processing.
SUMMARY OF THE INVENTION
The shortcomings of the prior art are overcome and additional advantages are provided through the provision of a method of managing changed data of castout classes. In one embodiment, the method includes attempting to place, within a predefined amount of time, an entry for a changed datum in a first data structure associated with a castout class. The method further includes placing the entry in a second data structure associated with the castout class, when the predefined amount of time to place the entry in the first data structure elapses.
In one example, the attempting to place the entry in the first data structure includes determining whether a timestamp of the entry is larger than the timestamp located at one end of the first data structure; determining, when the timstamp is not larger, whether the timestamp of the entry is smaller than a timestamp located at another end of the first data structure; and searching the first data structure for the predefined amount of time, when the timestamp of the entry is not larger than the timestamp at the one end or smaller than the timestamp at the other end, for a proper location to place the entry.
In a further example, the placing of the entry on the second data structure includes inserting the entry at one end of a first portion of the second data structure, when a timestamp of the entry is smaller than a timestamp located at the one end; inserting the entry at another end of the first portion of the second data structure, when the timestamp of the entry is larger than a timestamp located at the another end; and inserting the entry in a second portion of the second data structure, when the entry is not inserted at the one end or the another end.
In a further embodiment of the present invention, the method includes determining which entry of the first data structure or the second data structure represents an oldest changed datum of the castout class.
In yet a further embodiment of the invention, at least a portion of the second data structure is unordered, and the method includes ordering, using at least one background task, the at least a portion of the second data structure.
In another aspect of the present invention, a system of managing changed data of castout classes is provided. The system includes, for instance, means for attempting to place, within a predefined amount of time, an entry for a changed datum in a first data structure associated with the castout class; and means for placing the entry in a second data structure associated with the castout class, when the predefined amount of time to place the entry in the first data structure elapses.
In yet a further aspect of the present invention, a system of managing changed data of castout classes is provided. The system includes, for example, a processor adapted to attempt to place, within a predefined amount of time, an entry for a changed datum in a first data structure associated with a castout class. The processor is further adapted to place the entry in a second data structure associated with the castout class, when the predefined amount of time to place the entry in the first data structure elapses.
In yet a further aspect of the present invention, an article of manufacture including at least one computer usable medium having computer readable pro
Elko David Arlen
Josten Jeffrey W.
Nick Jeffrey M.
Surman David H.
Wilkinson Wendell W.
Heslin & Rothenberg, P.C.
International Business Machines - Corporation
Kinnaman, Jr. Esq. William A.
Kulik Paul V.
LandOfFree
Method, system and program products for managing changed... 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, system and program products for managing changed..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method, system and program products for managing changed... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2478099