Abstract:
An outboard file cache system including file surge protection and an improved method for managing allocation of cache storage are disclosed. In an outboard cache, excessive writes to a file are detected by testing whether a segment belonging to a file specified by a nd, which logically precedes one of the segments specified in the command by a predetermined number of segments, is present in the outboard file cache, has been written, and has not been destaged. When a first surge-threshold is reached, a group of segments is selected and destaged. When a second surge-threshold is reached, the outboard cache inhibits allocation of further cache storage for the file for the purpose of writing until a selected group of segments is destaged.

Description:
COPENDING PATENT APPLICATIONS 
     This patent application is related to co-pending patent application Ser. No. 08/174,750, entitled &#34;Outboard File Cache System&#34; to Thomas P. Cooper and Robert E. Swenson, which was filed Dec. 23, 1993, is assigned to the assignee of the present invention, and is herein incorporated by reference. 
     BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     This invention is generally related to the area of storage hierarchies and more particularly to the management of cache storage in a storage hierarchy. 
     2. Description of the Prior Art 
     The performance of data processing systems has improved dramatically through the years. While new technology has brought performance improvements to all functional areas of data processing systems, the advances in some areas have outpaced the advances in other areas. For example, advancements in the rate at which computer instructions can be executed have far exceeded improvements in the rate at which data can be retrieved from storage devices and supplied to the instruction processor. Thus, applications that are input/output intensive, such as transaction processing systems, have been constrained in their performance enhancements by data retrieval and storage performance. 
     The relationship between the throughput rate of a data processing system, input/output (I/O) intensity, and data storage technology is discussed in &#34;Storage Hierarchies&#34; by E. I. Cohen, et al., IBM Systems Journal, 28 No. 1 (1989)62-76. The concept of the storage hierarchy, as discussed in the article, is used here in the discussion of the prior art. In general terms, the storage hierarchy consists of data storage components within a data processing system, ranging from the cache of the central processing unit at the highest level of the hierarchy, to direct access storage devices at the lowest level of the hierarchy I/O operations are required for access to data stored at the lowest level of the storage hierarchy. 
     Caching takes place at various levels of the storage hierarchy. An instruction processor cache caches data stored in main memory and main memory essentially caches data stored in secondary storage. A second level cache between an instruction processor cache and the main memory is used in the 2200/900 Series data processing system from Unisys Corporation. Secondary storage devices, such as disk subsystems, are also available with a cache between the electromechanical storage device and the main memory of data processing system. 
     Present caching techniques are typically implemented according to the physical characteristics of the level of the storage hierarchy being cached and without regard to the logical relationship of the data being cached. As a result, the cache system may be unable to provide the expected performance benefit in certain scenarios. 
     Present cache systems, such as that described in U.S. Pat. No. 4,394,733 entitled, &#34;Cache/Disk Subsystem&#34;, to Robert Swenson, are aware of the physical disk address of the data presently in cache, but are unaware as to which data in cache is logically related. For example, storage may be allocated to a file by the operating system in fixed units of storage called segments. The first segment of the file has a file relative segment offset of 0, the second segment of the file has a file relative segment offset of 1, and so on. Further consider that the physical segments of disk storage allocated to a file are not guaranteed to be contiguous. That is, it cannot be guaranteed that segment 0 of a file resides in the physical disk segment immediately preceding the physical disk segment allocated to segment 1 of the file. 
     The inability to recognize the logical relationship between physical disk segments in cache storage may adversely impact the performance benefits of the cache system in certain scenarios. For example, some applications cream very large files in the course of their processing. In particular, a merge-sort application combines the contents of two files and outputs a third sorted file. In the context of a cache disk system, the third file does not exist, so every write request results in a write-miss status from the cache disk. Because the sort-merge process is able to very quickly generate write requests, the available cache storage may be monopolized by the sort-merge application. To the extent that the sort-merge application is utilizing cache disk storage, other applications have less cache storage available for their use. For the purposes of this invention disclosure, this file behavior is referred to as &#34;surging&#34;. As a result of one file surging, the other applications seeking access to the disk will only have limited cache storage available, thereby causing a substantial decrease in their overall throughput rate. 
     In the Cache/Disk System of U.S. Pat. No. 4,394,733, a counter is maintained for the number of segments which have been written-to. When this counter reaches a predetermined threshold, further write requests are rejected until the number of written-to segments falls below the selected threshold. 
     The shortcoming of this is that a single application may effectively monopolize cache storage if it generates write requests too quickly. Other applications must wait for written-to segments from the single application to be destaged before they are allowed to write new segments to cache storage. Thus, all applications are being adversely impacted because of the rate at which a single application is writing dam to a file. 
     It would be desirable to identify when a file is surging, limit further writing to the single file until segments can be destaged, and eliminate the adverse impact on the performance of other applications when a single file is surging. 
     SUMMARY OF THE INVENTION 
     It is an object of the invention to prevent a single file which is undergoing sequential write operations from using excessive cache storage. 
     Another object is to selectively take preemptive measures for a file undergoing sequential writes, wherein the measures taken vary according to the rate at which sequential write operations are being performed on the file. 
     A further object of the invention is to destage segments of a file upon detecting a first level of sequential writes to the file. 
     Still another object of the invention is to destage segments of a file and prevent further allocation of segments in cache storage for the purpose of writing segments to the file until the destage is complete upon detecting a second level of sequential writes to the file, wherein the second level is greater than the first level. 
     According to the present invention, the foregoing and other objects and advantages are attained by establishing a surge-threshold. If sequential write operations are performed on a file at a rate which exceeds the surge-threshold, the file is surging. Upon receiving a command to process, an outboard file cache searches for the segments of a file identified by the command. If the segments are present in the cache storage, the function specified by the command is performed. Otherwise, if the function is a write and the segments are not present in cache storage, a test is performed to determine whether the file is surging. If the file has exceeded the surge-threshold, then segments in cache storage which belong to the surging file are destaged. Segments are then allocated and the write function is performed. 
     In accordance with another aspect of the invention, if a file has exceeded the surge-threshold and a write function is requested on segments not present in cache storage, then segments belonging to the surging file are identified for destaging, and allocation of segments in cache storage for the purpose of writing further segments to the file is denied until the identified segments are destaged. 
     A further object of the invention is to establish first and second surge-thresholds. The first surge-threshold is used to identify a first level of sequential writing to a file and the second surge-threshold is used to identify a second greater level of sequential writing to a file. When sequential writing to a file exceeds the first surge-threshold, segments of the file in cache storage are selected and destaged. Two actions are taken when the second surge-threshold is exceeded. First, segments of the surging file are selected and destaged. Second, the write function is not performed and additional segments in cache storage are not allocated for the purpose of writing until the segments of the surging file are destaged. 
     Still other objects and advantages of the present invention will become readily apparent to those skilled in the art from the following detailed description, wherein only the preferred embodiment of the invention is shown, simply by way of illustration of 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 invention. Accordingly, the drawings and description are to be regarded as illustrative in nature, and not as restrictive. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 illustrates the exemplary storage hierarchy in which the present invention is embodied; 
     FIG. 2 shows the logical layout of segments in a file; 
     FIG. 3 contains a flowchart of the general processing steps for providing surge protection. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENT 
     FIG. 1 illustrates the exemplary storage hierarchy in which the present invention is embodied. A plurality of Control Units 104a-b are coupled to Host 10 via IOPs 38 and 38b for providing access to Disks 106a, 106b, 106c, 106d, 106e, and 106f. Application and system software executing on Host 10 reads data from and writes dam to Files 108a-h. While Files 108a-h are depicted as blocks it should be understood that the data is not necessarily stored contiguously in Disks 106a-f. 
     The exemplary Host 10 is a 2200/900 Series data processing system which is commercially available from the Unisys Corporation. The Host 10 includes Instruction Processors (IPs) which are the basic instruction execution units of the system. Each IP includes a first level cache (not shown) having a section for instructions and a section for operands. The IPs are functional to call instructions from memory, execute the instructions and store the results, and in general, perform data manipulation. The Host further includes Storage Controllers (SCs) directly coupled to the for providing access to Main Storage Units (MSUs). 
     Each of the SCs also provide interfaces for multiple Input/Output Processors (IOPs) 38a and 38b. The IOPs read data from the MSUs for writing to perpheral devices 106a-f, and read data from peripheral devices for writing to the MSUs. Peripheral devices may include printers, tape drives, disk drives, network communication processors, etc. For the purposes of the present invention, the peripheral devices provide a backing store for long term storage of data and are simply referenced as Disks 106a-f. 
     The IOPs 38a and 38b are microprocessor controlled units that control the initiation, data transfer, and termination sequences associated with software generated I/O channel programs. Initiation and termination sequences are executed by the microprocessor and data transfer is controlled by hard-wired logic. 
     Outboard File Cache 102 provides cache storage for Files 108a-h with resiliency against data loss which is comparable to Disks 106-f. A Data Mover 110 is coupled to the Input/Output Bus 40 in the Host and provides a functionality which is similar to the IOPs 38a and 38b. The Data Mover provides a Fiber Optic Link 112 to the Outboard File Cache. All or part of Files 108 may be stored in the Outboard File Cache 102 depending upon the storage capacity of the Outboard File Cache 102, and the size and number of Files 108 selected to be cached. 
     The portion of Files 108a-h that are stored in the Outboard File Cache 102 are shown as blocks 114a -h. The cached portion of Files 108 are labeled File-A&#39;, File-B&#39;, . . . , File-H&#39; for discussion purposes. File-A&#39; 114a is the portion of File-A that is stored in Outboard File Cache 102, File-B&#39; 114b is the portion of File-B that is stored in Outboard File Cache 102, etc. The Outboard File Cache at this level of the storage hierarchy allows references to cached files to be immediately directed to the Outboard File Cache 102 for processing, in contrast with a non-cached file where an I/O channel program must be constructed to access the proper disk and the request and data must flow through a possibly lengthy data path. 
     The Outboard File Cache 102 includes a Host Interface Adapter (HIA) 214, Index Processor (IXP) 236 and Cache Storage 220. The HIA provides the functionality for transferring data between the Cache Storage 220 and the Data Mover 110 on the Host 10. The IXP includes the logic for managing Cache Storage 220, processing commands sent from the Host, and initiating and preparing for data transfer. The File Descriptor Table 506 is stored in Cache Storage and is used and maintained by the IXP in allocating storage for Files 114a-h. The copending application which has been incorporated by reference may be consulted for details on the File Descriptor Table 506 and aspects of the overall operation. 
     FIG. 2 shows the logical layout of segments in File A&#39; 114a. The invention may be understood with reference to the File A&#39; as it is written to Cache Storage 220. File A&#39; should be viewed as a snapshot of the state of the file at some time after 256 segments have been written to Cache Storage. 
     The segments of the file are identified by their offset relative to the first segment of the file. Thus, the first segment is numbered segment 0, the second segment is numbered segment 1, and so on. The invention may be understood by tracing the processing steps of FIG. 3 with reference to File A&#39; of FIG. 2 and examining how the creation of File A&#39; in Cache Storage was affected. 
     FIG. 3 contains a flowchart of the general processing steps for providing surge protection. Step 11 establishes surge-thresholds. A surge-threshold is used in detecting when a file is surging. In the preferred embodiment two surge-thresholds are implemented. When the number of segments which have been sequentially written in Cache Storage 220 surpasses one of the surge-thresholds, special processing is performed. Those skilled in the art will recognize that one or both surge-thresholds may be used without departing from the spirit of the invention. 
     The first and second surge-thresholds are used to indicate two levels of surging. The impact on cache storage is more critical when a file exceeds the second surge-threshold than when a file exceeds the first surge-threshold. Therefore, the remedial actions taken vary according to the level of file surging. The nature of the surge-thresholds will become apparent in the processing steps which follow. 
     Step 13 obtains a command to process. Commands are sent from the Host 10 to the Outboard File Cache 102 for manipulating Files 114a-h. The commands in the exemplary embodiment include a function code, file-identifier, and a file-relative-segment-offset. The function code identifies the operation to be performed on the file (such as read or write), the file-identifier indicates the logical file upon which the operation is to be performed (for example, File A&#39;), and the file-relative-segment-offset specifies the offset from the first segment of the file at which the operation is to be performed. A command may reference one or more segments of a file. 
     Processing proceeds to Step 15 which searches the File Descriptor Table 506 for the one or more segments specified in the command. Decision Step 17 tests whether Step 15 was successful in locating the desired segments. If the requested segments are present in Cache Storage, control is directed to Step 19 to finish processing the command. Otherwise, control is directed to Step 21. 
     Step 21 tests whether the function specified in the command is write. The surge condition is not tested when a command other than write (such as read) is issued to the Outboard File Cache 102 because other commands do not result in a segment in Cache Storage 220 which must be destaged. Therefore, for non-write commands control is directed to Step 19 to finish processing the command. Step 19 will proceed to allocate the necessary segments in Cache Storage. 
     Control is directed to decision Step 23 when a write command is encountered for segments which are not in Cache Storage 220. Decision Step 23 tests whether a file is surging by testing whether either of the surge-thresholds have been exceeded. While not shown in FIG. 3, it should be understood that the write operation is permitted for the first 32 (file-relative-segment-offsets 0-31) segments of a file without testing whether either the first or second surge-thresholds has been exceeded. Thereafter, the test for whether a file has exceeded the first surge-threshold is performed when a write is attempted for a segment whose file-relative-segment-offset is a multiple of 8. Thus, the test for a file exceeding the first surge-threshold will be performed when a write is attempted for segment 32, when a write to segment 40 is attempted, and so on. The test for whether a file has exceeded the second surge-threshold is not performed until a write operations is attempted on the segment whose file-relative-segment-offset is 256. Thereafter, the test for whether a file has exceeded the second surge-threshold is performed when a segment whose file-relative-segment-offset is a multiple of 8 is referenced. Thus, the test for a file exceeding the second surge-threshold will be performed when a write to segment 256 is attempted, when a write to segment 264 is attempted, and so on. 
     Those skilled in the art will recognize that the particular first and second surge thresholds disclosed in this application may not be suitable for all applications. Optimal values for the surge thresholds could be determined by operational analysis or heuristics. 
     By way of example, the tests for whether a file has exceeded either the first or second surge-threshold is discussed next. If a command seeks to write to segment 32, and segment 0 (the file-relative-segment-offset of the referenced segment - the first surge-threshold) is in Cache Storage 220, is written, and not destaged (the cache segment has not been saved to one of Disks 106a-h), Test 23 will detect that the first surge-threshold has been exceeded and the file is therefore surging. If segment 0 is not in cache or it has not been written, then decision Step 23 directs control to Step 19 as described above. 
     If a command seeks to write to segment 256, and segment 0 (the file-relative-segment-offset of the referenced segment --the second surge-threshold) is in Cache Storage 220, is written, and not destaged (the cache segment has not been saved to one of Disks 106a-f), test 23 will detect that the second surge-threshold has been exceeded and therefore the file is surging beyond that which is desirable. If segment 0 is not in cache or it has not been written, then decision Step 23 directs control to Step 19 as described above. 
     In the preferred embodiment, the test for a surging file is not performed for each segment accessed. Rather the test is performed upon writing and allocation of segment 32, segment 40, segment 48, segment 56, segment 64, etc. It will be recognized that the test could be performed at different intervals depending upon the particular system in which the invention is implemented. 
     Step 25 selects segments to destage for the file which is found to be surging. If the first surge-threshold is exceeded upon an attempt to write segment 32, then a group of up to 8 segments between segments 0 and 7 is selected for destaging; if the first surge-threshold is exceeded upon an attempt to write segment 48, then a group of up to 8 segments between segments 8 and 15 is selected for destaging and so on. 
     If the second-surge threshold is exceeded upon an attempt to write segment 256, then a group of up to 8 segments between segments 0 and 7 are selected for destaging; if the second surge-threshold is exceeded upon an attempt to write segment 264, then a group of up to 8 segments between segments 8 and 14 are selected for destaging, and so on. 
     Step 27 inhibits further processing of the command until the selected segments are destaged if the second surge-threshold is surpassed. This step is performed when a file exceeds the second surge-threshold but not when the a file exceeds only the first surge-threshold because when the second surge-threshold is surpassed the situation calls for more more serious restrictions on the surging file. In addition to selecting segments to destage (the same as the first surge-threshold), the operation as specified by the function in the command is not performed when the second surge-threshold is surpassed. In contrast, when a file has only exceeded the first surge-threshold, additional segments are identified for destaging and the function specified by the command is performed. Note that the Host 10 may resend the command when a file has exceeded the second surge-threshold and the Outboard File Cache 102 will not fully process the command until the file no longer exceeds the second surge-threshold. Therefore, Step 19 performs the operation specified by the function in the command only if the second surge-threshold is not surpassed, and any segments selected for destaging are destaged. 
     Having described the preferred embodiment of the invention in the drawings and accompanying description, those skilled in the art will recognize that various modifications to the exemplary embodiment could be made without departing from the scope and spirit of the claims set forth below: