Sequentially processing data in a cached data storage system

• US 4,956,803 A
• Filed: 09/14/1989
• Issued: 09/11/1990
• Est. Priority Date: 07/02/1987
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Wagner, Robert E., Tayler, Gerald E.
• Primary Examiner(s): Shaw, Gareth D.
• Assistant Examiner(s): Mills, John G.
• Application Number:
  US07/407,077
• Time in Patent Office: 362 Days
• Field of Search: 364/200 MS File, 364/900 MS File
• US Class Current: 711/113
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 12/0888 using selective caching, e.g. bypass
• CPC Class Codes: G06F 2212/312 In storage controller
• CPC Class Codes: G06F 2212/6026 Prefetching based on access pattern detection, e.g. stride based prefetch

Abstract

The disclosure relates to sequential performance of a cached data storage subsystem with a minimal control signal processing. Sequential access is first detected by monitoring and examining the quantity of data accessed per unit of data storage (track) across a set of contiguously addressable tracks. Since the occupancy of the data in the cache is usually time limited, this examination provides an indication of the rate of sequential processing for a data set, i.e., a data set is being processed usually in contiguously addressable data storage units of a data storage system. Based upon the examination of a group of the tracks in a cache, the amount of data to be promoted to the cache from a backing store in anticipation of future host processor references is optimized. A promotion factor is calculated by combining the access extents monitored in the individual data storage areas and is expressed in a number of tracks units to be promoted. The examination of the group of tracks units and the implementation of the data promotion and demotion (early cast-out) is synchronized which results in a synergistic effect for increasing throughput of the cache for sequentially-processed data. A limit of promotion is determined to create a window of sequential data processing.

Claims

1. Data processing apparatus including a cache store operatively connected between a host processor and a backing store, the backing store having addressable data storage tracks, both stores storing data addressable by the addresses of the backing store data storage tracks, each track being capable of storing an amount of data equal to a given number of data bits, the host processor accessing, or primarily accessing, the cache store for writing and reading data to and from both stores, and a cache controller determining the promotion and demotion of data between the cache and the backing store and arranged, in operation, to switch between promotion and demotion protocols in dependence on the result of a running analysis of the proportion of data in the currently accessed track and its connected previously accessed tracks actually referenced in relation to predetermined thresholds, the controller, for each access to the cache store by the host processor, measuring the amount of data in that track that is referenced by the access as an indication of locality of reference and separately storing the measured amount as an access extent for that track or incorporating such there into and means for comparing the predetermined thresholds with the stored access extents for yielding a given result, and the controller having means responsive to the given result to control said promotion and demotion of data.

2. Apparatus as claimed in claim 1, wherein the host processor is arranged to send chains of access commands, each of which include a track address, to the cache controller for accesses invoked by any one such chain of commands, the controller compares the access extent for the addressed track with a first threshold value and, if it exceeds such first threshold value, reads all of the other access extents for tracks in the cache with backing store addresses numerically adjacent the addressed track address and which identify tracks accessed or, under hashing, that reasonably bound have been accessed by the host processor in the chain before accessing the given track, separately compares all such with the first threshold value and if a predetermined number of such also exceeds the first threshold value, sets a sequential indicator for the current track, the controller observing a "by track" protocol if the sequential indicator is not set and a prefetching protocol if the sequential indicator is set.

3. Apparatus as claimed 2, wherein the controller, on setting the sequential indicator for the current track, combines the access extents involved to produce a combined access extent value and compares it with a preset combined threshold value, the controller, if the combined access extent value is not greater than the combined threshold value, generating an integral number proportional to the combined access extent to be representative of a sensed rate of I/O and promotes that number of prefetched tracks and sets the sequential indicator for each of them.

4. Apparatus as claimed in claim 3, wherein there is a cache bypass and the controller is arranged, if the combined access extent is greater than the combined access threshold, to reset the sequential indicator for the current track and causing all subsequent accesses in the chain to bypass the cache for directly accessing the backing store.

5. Apparatus as claimed in claim 4, wherein track promotion and demotion takes place effectively concurrently with data transfers between a host processor and the cache and, if the controller is observing the prefetch protocol and a host processor supplied access command is invoked relating to a track in the prefetch group being promoted which is not already in the cache, the actual data involved is sent via the bypass directly to the host processor, the amount of the data transferred being recorded, and is also promoted with the rest of the track or tracks, in due order, prior to re-analysis of the access statistics for promotion and demotion protocol determination.

6. Apparatus as claimed in claim 5, wherein the combined access extent is generated by suming an integral number of predetermined ones of the read access extents and multiplying the sum by a look-ahead constant value which is a number not greater than ten.

7. Apparatus as claimed in claim 6, wherein the predetermined access extents are all access extents such that were any one of such to be less than the first threshold value, the sequential indicator would be prevented from being set.

8. Apparatus as claimed in claim 5, wherein cache space for prefetched tracks is generated by demoting the data contents of tracks from the cache having backing store addresses contiguous but increasingly less than the backing store address of the given track and demoting the integral number of further tracks minus one from the cache store to the backing store beginning with a track having two backing store addresses less than the given track backing store address and proceeding to a track having an address equal to the address of the given track minus the integral number of tracks to be prefetched.

9. Apparatus as claimed in claim 8, wherein the host processor is adapted to send and the controller is adapted to receive and respond to a host processor supplied command defining an extent of host processor current permitted access to contiguous backing store tracks beginning with a first backing store address and ending with a second backing store address the promotion of prefetched tracks and demotion of lower addressed tracks being restricted to lie within the permitted access extent.

10. In a data storage system having attachment means for attaching the data storing system to a host processor whereby data may be transferred between the host processor and the data storing system for storage and retrieval;

data transfer means intercoupling the attachment means, the cache store and the backing store so that data may be transferred directly between either of the stores and the attachment means or between the two stores;

a programmed control connected to the attachment means, the data transfer means and the two stores for sending control signals thereto and receiving command and status signals therefrom such that the programmed control controls the operations of the data storing system;

the programmed control including a control store for storing computer program indicia for sensing same and responding to the sensed indicia to send out the control signals and to sense the analyze the received command and status signals;

the stores each having addressable data storing tracks of equal data storage capacity;

means in the programmed control stored computer program indicia to cause the programmed control to allocate predetermined ones of the cache tracks to store data addressably stored for predetermined respective ones of the backing store tracks;

means in the cache store for addressing the allocated cache tracks using the addresses of the predetermined respective ones of the tracks in the backing store;

monitoring program indicia in the control store for being sensed by the programmed control for executing computer programming contained in such indicia for causing the programmed control for operating the system to monitor the data transfers between the attachment means and the cache store addressed ones of the allocated cache tracks for measuring the length of data in each such transfer and storing the measured data lengths, then summing the measured data lengths for all data transfers between the attachment means and the respective cache tracks to create a stored access extent for each of the cache tracks allocated to store data;

threshold indicia in the control store for indicating a threshold value and being sensible by the programmed control for obtaining the threshold value;

indicator means in the data transfer means for indicating a completion of a last data transfer between the cache store and the attachment means and the backing store address for the cache track used in the data transfer;

comparison program indicia in the control store for being sensed by the programmed control for executing computer programming contained is such indicia causing the programmed control to operate the system for sensing the completion indicator and responding thereto sensing the stored access extents for the cache track used in the last data transfer and for "K" cache tracks respectively addressable by backing store addresses contiguous with the backing store address for the last access cache track, then the programmed control processing the sensed stored access extents using predetermined calculations to create an intermediate value is greater than the threshold value, indicating the sequential mode of operation for data transfers in the last accessed cache track, wherein "K" is an integer; and

data promotion program indicia in the control store for being sensed by the programmed control for executing computer programming contained in such indicia for causing the programmed control to operate the system for sensing the sequential indicator, if the sequential indicator is set, then causing the programmed control to operate the system for promoting data from next backing store tracks to cache store tracks with the tracks having backing store address contiguous with and greater than the backing store address of the last accessed cache track, calculating the number of tracks to be promoted by sensing the intermediate value and changing the intermediate value by predetermined calculations, then activating the data transfer means for promoting the data stored in the next baking store tracks.

11. In a peripheral data storing system for being attached to a host processor and having interconnected cache and backing stores, transfer means in the system coupled to said stores for accessing same using the addresses of the backing store and for transferring data with an attached host processor and between the two stores and indicating when the host processor is accessing the cache store for either recording or reading data therein or therefrom, each of the stores having addressable data storing tracks of a given data storing capacity;

the improvement including, in combination;

short data means coupled to the transfer means and to the stores for controlling inter-store data transfers when the host processor is accessing data stored therein in a random accessing mode and including cache control means coupled to the cache store for activating the transfer means to transfer data between the stores to encourage data to be read by the host processor to be resident in the cache store and data to be written into the system to be written directly to the backing store;

sequential data means coupled to the cache store and to said transfer means for activating the transfer means to maintain in said cache store data residing in a number of said cache store tracks located within a locality of references, local means in said sequential means for indicating to the sequential means which of said backing store tracks reside within a locality of references for each of the cache store tracks currently being accessed for data transfer with the host processor;

long data means coupled to the cache and backing stores and to said transfer means for encouraging all data transfers to be directly between the host processor and the backing store; and

mode control means coupled to said transfer means and to all of said data means for monitoring the lengths of individual ones of the data transfers between the host processor and the cache store and responding to the monitored data transfer lengths in groups of cache store tracks accessible by contiguous ones of the backing store addresses to establish said localities of references and to actuate a respective one of the data means to control data transfers between said cache and backing stores of backing store tracks bearing addresses within and adjacent to localities of references by respective ones of the data means such that the short data means controls the inter-store data transfers for short individual host processor to system data transfers, the sequential data means controls the inter-store data transfers for individual host processor to system data transfers which appear to be sequential and the long data means limits and controls the inter-store data transfers for individually long host processor to system data transfers.

12. In a data storage system having attachment means for attaching the system to a host processor whereby data may be transferred between the host processor and the system for storage and retrieval;

a cache store in the system;

a backing store in the system, data transfer means intercoupling the attachment means, the cache store and the backing store so that data may be transferred directly between either of the stores and the attachment means or between the two stores;

a programmed control connected to said attachment means, the data transfer means and the two stores for sending control signals thereto and receiving command and status signals therefrom such that the programmed control controls the operation of the system;

the programmed control having a control store for storing computer program indicia;

the programmed control sensing the program indicia and responding to the sensed indicia to operate the system in accordance with the control indicia, the command signals and the status signals;

the stores having addressable data storing tracks of equal data storage capacity;

means in the programmed control to allocate predetermined ones of the cache tracks to store data addressed for predetermined ones of the backing store tracks;

means in the cache store for addressing the allocated cache tracks using the addresses of said predetermined respective ones of the tracks in the backing store, respectively;

the improvement including, in combination;

measuring program indicia in the control store for being sensed by the programmed control for causing the programmed control to monitor the data transfers between the attachment means and the cache store including measuring the length of each data transfer and storing the measured lengths including summing all measured lengths to create a stored access extent relating to each of the allocated ones of the cache tracks;

threshold indicia in the control store for being sensed by the programmed control for indicating to the programmed control threshold values respectively for first thresholds of access extents in the respective cache tracks for indicating a possible sequential mode of operation and a second threshold greater than the first threshold for indicating data transfers exceeding a need for a sequential mode of operation in the system;

access detection indicia in the control store for being sensed by the programmed control for causing the programmed control to respond to an attachment means explicit attempted access to each given cache track for instituting a comparison of the stored measured length sums with said thresholds;

comparison indicia in the control store for being sensed by the programmed control for causing the programmed control to respond to said instituted comparison to compare the stored measured length sum for said given cache track with said first threshold, if said comparison indicates that the given cache track has a stored access extent sum less than or equal to the first threshold, then no sequential mode is needed, else if said comparison indicates that the given cache track has a stored access extent sum greater than said first threshold, then setting an indicator that a sequential mode is possible for data transfers related to said given cache track and other predetermined cache tracks accessible by addresses contiguous and less than the address of the given cache track;

combining indicia in the control store for being sensed by the programmed control for causing the programmed control to respond to said indicator being set to compare the stored access extent sums for said other predetermined cache tracks, respectively, and individually with said first threshold, if not all of said other predetermined cache tracks are allocated to backing store tracks of if any one of said other predetermined cache tracks have stored access extent sums not greater than the first threshold, then causing the programmed control not to institute a sequential mode, else if all said other predetermined cache tracks are allocated to respective backing store tracks and all have stored access extent sums greater than the first threshold, causing the programmed control to indicate that a sequential mode is to be set for the data transfers between the attachment means which include data transfers with said given cache track; and

data promotion indicia in the control store for being sensed by the programmed control for causing the programmed control to sense and respond to the sequential mode indication for summing the stored access extent sums for said given and other predetermined cache tracks for calculating a number of cache tracks that should be allocated to certain backing store tracks for storing data therefrom wherein the certain backing store tracks have backing store addresses contiguous and increasing with respect to the given track address and the number of certain backing store tracks being said calculated number of tracks and then causing the programmed control to actuate the data transfer means to transfer the data from said backing store to said cache store for the cache tracks allocated for said certain backing store tracks whenever such tracks are either not allocated or do not contain the data of the certain backing store tracks.

13. In a data storing system having attachment means for attaching the data storing system to a host processor whereby data may be transferred between the host processor and the data storing system for storage and retrieval;

a random access cache store in the data storing system;

a rotating disk data storing device in a backing store in the data storing system;

data transfer means intercoupling the attachment means, the cache store and the backing store so that data may be transferred directly between either of the stores and the attachment means or between the two stores;

a programmed, control connected to said attachment means, the data transfer means and the two stores for sending control signals thereto and receiving command and status signals therefrom such that the programmed control controls the operations of the data storing system;

the programmed control including a control store for storing computer program indicia for sensing same and responding to the sensed indicia to send out said control signals and to sense and analyze said received command and status signals;

the stores each having addressable data storing tracks of equal data-storage capacity;

means in the programmed control stored computer program indicia to cause said programmed control to allocate predetermined ones of the cache tracks to store data addressably stored for predetermined respective ones of the backing store tracks;

means in the cache store for addressing the allocated cache tracks using the addresses of said predetermined respective ones of the tracks in the backing store;

the improvement including, in combination;

monitoring program indicia in the control store for being sensed by the programmed control for executing computer programming contained in such indicia for causing the programmed control for operating the system to monitor said data transfers between the attachment means and the cache store addressed ones of the allocated cache tracks for measuring the length of data in each such transfer and storing the measured data lengths, then summing the measured data lengths for all data transfers between the attachment means and the respective cache tracks to create a stored access extent for each of the cache tracks allocated to store data;

threshold indicia in the control store for indicating a threshold value and being sensible by the programmed control for obtaining said threshold value;

indicator means in the data transfer means for indicating a completion of a last data transfer between the cache store and the attachment means and the backing store address for the cache track used in the data transfer;

comparison program indicia in the control store for being sensed by the programmed control for executing computer programming contained is such indicia causing the programmed control to operate the system for sensing said completion indicator and responding thereto sensing the stored access extents for the cache track used in the last data transfer and for "K" cache tracks respectively addressable by backing store addresses contiguous with the backing store address for the last access cache track, then the programmed control processing the sensed stored access extents using predetermined calculations to create an intermediate value is greater than the threshold value, indicating a sequential mode of operation for data transfers in said last accessed cache track, wherein "K" is an integer; and

data promotion program indicia in the control store for being sensed by the programmed control for executing computer programming contained in such indicia for causing the programmed control to operate the system for sensing the sequential indicator, if the sequential indicator is set, then causing the programmed control to operate the system for promoting data from next backing store tracks to cache store tracks with the tracks having backing store address contiguous with and greater than the backing store address of said last accessed cache track, calculating the number of tracks to be promoted by sensing the intermediate value and changing the intermediate value by predetermined calculations, then activating the data transfer means for promoting the data stored in said next backing store tracks.