Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1998-02-03
2001-02-20
Cabeca, John W. (Department: 2752)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S133000, C711S136000, C711S160000
Reexamination Certificate
active
06192450
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to destage of data from a write cache to a storage device, and methods for managing destage to improve efficiency thereof.
BACKGROUND OF THE INVENTION
In a data processing system, instructions and associated data are transferred from storage devices to one or more processors for processing, and then resulting data generated by the processor is returned to storage devices. Thus, typical processing operations involve frequent and repetitive reading and writing from/to storage devices. As a result, storage access delays are often a primary limitation in the performance of a data processing system. Preferably, therefore, storage access speed should be maximized to maximize performance. However, often cost and other constraints require that the storage devices be comprised of relatively long access time circuitry, e.g., hard disk rives. To overcome the resulting performance rawbacks, caches are typically used.
A cache typically includes a relatively small, but relatively high speed, bank of memory, that can be more rapidly accessed by the processor(s) than the storage device that the cache services. A write cache is used to temporarily store data being written by the processor to a storage device. The processor writes data into the write cache, and thereafter the data is transferred or destaged from the write cache to the appropriate storage device. A read cache duplicates memory locations in the storage device, so that when a particular storage location being accessed by the processor is duplicated in the read cache, the processor may rapidly access the read cache instead of waiting for access to the storage device.
Typically, a cache is associated with a cache directory, which stores an indication of those memory locations currently stored in the cache. Thus, when a processor requests access to a particular memory location, the cache directory is accessed to determine whether that memory location is in the cache. If so, the requested memory location may be accessed in the cache, if appropriate. If the memory location is not in the cache, the accessed memory location may be established in the cache, if appropriate.
Typically, sequential locations on a storage device can be read or written rapidly. For example, a disk drive may be arranged into tracks and sectors, so that sequential data in sequential tracks and sectors can be rapidly read or written. However, it is also typical to incur long access delays when reading or writing data at disparate locations. For example, a disk drive typically incurs a substantial delay to transfer from one track and sector to another, non-adjacent track and sector.
In light of the rapid access that can be made to sequential locations on a storage device, caches are typically organized into “lines”, which are relatively long sequences of sequential storage locations. Typically, when storage locations are written into a write cache, the data written into the cache is arranged into cache lines, and then sequential locations from one or more sequential cache lines are destaged to the storage device at one time. Similarly, when memory locations are duplicated into a read cache, typically the needed memory location as well as neighboring memory locations, are brought into a line of the cache.
Data is typically destaged from a write cache in the order in which it is written to the cache, i.e., first-in, first-out. This approach, however, can lead to various difficulties.
For example, while sequential storage locations are often written sequentially in time, this is not always the case. Consider, for example, a processing thread that writes to sequential storage locations in a first range of storage location on a storage device, and then writes to sequential storage locations in a second range of storage locations which is adjacent to the first range. If the second range is located at higher storage addresses than the first range of storage locations, then the first range should be destaged before the second range, and in this case a destage algorithm which destages memory locations in the order in which they were written to the cache, can operate efficiently. However, if the second range of storage locations is at lower storage addresses than the first range, then the second range should be destaged before the first range, and in this case a destage algorithm which destages memory locations in the order in which they were written in the cache will operate inefficiently, because the first range will be destaged first.
As a further example, when an exceptionally large amount of data is written to the cache in one operation, a sizeable percentage of the cache will be consumed. A large block of data of this kind should be destaged as soon as possible to free space in the cache. Unfortunately, if a first-in, first-out strategy is used in destaging the data, this large percentage of the cache will remain consumed until all previously written data has been destaged. The resulting delay can cause the cache to become full, preventing additional write operations and delaying processing.
SUMMARY OF THE INVENTION
The invention addresses these and other difficulties inherent in destage of data on a first-in, first-out basis, by coalescing as much data together as possible prior to each destage operation. This results in higher performance by destaging a large quantity of data from the cache with each destage operation.
Specifically, in one aspect of the present invention, a working set of data items stored in a write cache is coalesced for destage to a storage device, by locating the least recently accessed data in the cache that will be destaged to the storage device, and then selecting a root item of data at a lower storage address than the least recently accessed data. The working set is then completed by identifying additional data in the cache that will be destaged to locations in the storage device substantially adjacent to the root item of data.
In another aspect, a working set of data items stored in a write cache is coalesced for destage to a storage device, by identifying a larger than average group of data items that were stored together into the cache, and selecting one of the data items in the group, e.g., the first item in the group, as a root item of data to be included in the working set. The working set is then completed by identifying additional data in the cache that will be destaged to locations in the storage device substantially adjacent to the root item of data.
In the particular disclosed embodiment described below, if the cache does not include a larger than average group of data items, the root data item is identified by initially selecting the least recently accessed destagable data item in the cache. Then, a search is conducted for a destagable data item at a lower storage device address that is within a predetermined range of storage locations of the currently selected data item. If such a data item is found, then this data item becomes the currently selected data item, and the search is repeated. When the search fails to find a data item at a lower storage device address within a predetermined range of the currently selected item, the process terminates and the currently selected data item becomes the root data item. This approach ensures that adjacent, later-written data items at lower storage device addresses, such as the second address range described in the preceding example, will be included in the destage operation.
In the disclosed embodiment, data items are included in the working set only if those data items are within a predetermined range of storage locations that includes the root item. Data items outside of this range are not adjacent to the root item of data and not included in the working set.
In the disclosed embodiment, data written into the cache is entered at the head of an LRU queue, the least recently accessed data being located at the tail of the LRU queue. Once the root item of data or any other item of data is included in the working set, then a data item substantially
Bauman Ellen Marie
Galbraith Robert Edward
Johnson Mark A.
Cabeca John W.
International Business Machines - Corporation
Tzeng Fred F.
Wood Herron & Evans LLP
LandOfFree
Destage of data for write cache does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Destage of data for write cache, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Destage of data for write cache will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2583747