Method for operating a cache memory system using a recycled register for identifying a reuse status of a corresponding cache entry

Description Submit all comments and votes

INTRODUCTION

1. Field of Invention

This invention relates to a high performance computer data storage device including a combination of solid state storage and a rotating magnetic disk device.

2. Description of Prior Art

A number of computer data storage systems exist which make some use of solid state memory devices as a caching controller for placement between a computer host device and rotating magnetic disk devices. A typical caching system uses a single solid state memory unit as a holding area for data stored on a string of magnetic disks, thereby allowing certain information to be stored in a high speed cache memory, thereby increasing speed of performance as compared to the use solely of relatively lower speed disk memories, i.e. the percentage of times a desired piece of data is contained in the high speed cache memory, thereby allowing faster access as compared with when that data is only stored in a disk drive. A block diagram of such a system is shown in FIG. 1. Host computer 101 communicates with the entire string 102 of disks 102-1 through 102-N via cache unit 103 via Host interface 104, such as Small computer Systems Interface (SCSI). All data going to or from disk strip 102 passes through the cache-to-disk data path consisting of host interface 104, cache unit 103, and disk interface 105. Cache unit 103 manages the caching of data and services requests from host computer 101. Major components of cache unit 103 include microprocessor 103-1, cache management hardware 103-2, cache management firmware 103-3, address lookup table 103-4, and solid state cache memory 103-5.

The prior art cache system of FIG. 1 is intended to hold frequently accessed data in a solid state memory area so as to give more rapid access to that data than would be achieved if the same data were accessed from the disk media. Typically, such cache systems are quite effective when attached to certain host computers and under certain workloads. However, there exist some drawbacks and, under certain conditions, such cache systems exhibit a performance level less than that achieved by similar, but uncached, devices. Some of the factors contributing to the less than desirable performance of prior art cached disk devices are now described.

The single cache memory 103-5 is used in conjunction with all disks in disk string 102. Data from any of the disks may reside in cache memory 103-5 at any given time. The currently accessed data is given precedence for caching regardless of the disk drive on which it resides. When fulfilling a host command, the determination of whether or not the data is in cache memory 103-5, and the location of that data in cache memory 103-5, is usually via hashing schemes and table search operations. Hashing schemes and table searches can introduce time delays of their own which can defeat the purpose of the cache unit itself.

Performance is very sensitive to cache-hit rates. Due to caching overhead and queuing times, a low hit rate in a typical string oriented cache system can result in overall performance that is poorer than that of configured uncached string of disks.

The size of cache memory 103-5 relative to the capacity of disk drives 102 is generally low. An apparently obvious technique to remedy a low hit rate is to increase the cache memory 103-5 size. However, it has been found that there is an upper limit to the size of cache memory 103-5 above which adding more capacity has limited benefits. With limited cache memory 103-5 capacity, a multitude of requests over a variety of data segments exhausts the capability of the cache system to retain the desirable data in cache memory 103-5. Often, data that would be reused in the near future is decached prematurely to make room in cache memory 103-5 for handling new requests from the host computer 101. The result is a reduced cache hit rate. A reduced hit rate increases the number of disk accesses; increased disk accesses increases the contention on the data path. A self-defeating cycle is instituted.

"Background" cache-ahead operations are limited since the data transferred during such activities travels over the same data path as, and often conflicts with, the data transferred to service direct requests from the host computer 101. The data path between cache unit 103 and disk string 102 can easily be overloaded. All data to and from any of the disks in disk string 102, whether for satisfying requests from host computer 101 or for cache management purposes, travels across the cache-to-disk path. This creates a bottleneck if a large amount of prefetching of data from disk string 102 to cache memory 103-5 occurs. Each attempt to prefetch data from disk string 102 into cache memory 103-5 potentially creates contention for the path with data being communicated between any of the disk drives of disk string 102 and host computer 101. As a result, prefetching of data into cache memory 103-5 must be judiciously limited; increasing the size of the cache memory 103-5 beyond a certain limit does not produce corresponding improvements in the performance of the cache system. This initiates a string of related phenomena. Cache-ahead management is often limited to fetching an extra succeeding track of data from disk wherever a read command from the host cannot be fulfilled from the cached data. This technique helps to minimize the tendency of cache-ahead to increase the queuing of requests waiting for the path between cache memory 103-5 and disk string 102. However, one of the concepts on which caching is based is that data accesses tend to be concentrated within a given locality within a reasonably short time frame. For example, data segments are often accessed in sequential fashion. Limiting the cache-ahead operations to being a function of read misses can have the negative effect of lowering the cache hit rate since such limitation may prevent or degrade the exploitation of the locality of data accesses.

A variety of algorithms and configurations have been devised in attempts to optimize the performance of string caches. A nearly universally accepted concept involves the retention and replacement of cached data segments based on least-recently used (LRU) measurements. The decaching of data to make room for new data is managed by a table which gives, for each cached block of data, its relative time since it was last accessed. Depending on the algorithm used, this process can also result in some form of table search with a potential measurable time delay.

Cache memory 103-5 is generally volatile; the data is lost if power to the unit is removed. This characteristic, coupled with the possibility of unexpected power outages, has generally imposed a write-through design for handling data transferred from host computer 103 to the cached string. In such a design, all writes from host computer 103 are written directly to disk; handled at disk speed, these operations are subject to all the inherent time delays of seek, latency, and lower transfer rates commonly associated with disk operations.

Cache unit 103 communicates with the string of disk drives 102 through disk interface 105.

SUMMARY OF THE INVENTION

Computer operations and throughput are often limited by the time required to write data to, or read data from, a peripheral data storage device. A solid state storage device has high-speed response, but at a relatively high cost per megabyte of storage. A rotating magnetic disk, optical disk, or other mass media provides high storage capacity at a relatively low cost per megabyte, but with a low-speed response. The teachings of this invention provide a hybrid solid state and mass storage device which gives near solid state speed at a cost per megabyte approaching that of the mass storage device.

For the purposes of this discussion, embodiments will be described with regard to magnetic disk media. However, it is to be understood that the teachings of this invention are equally applicable to other types of mass storage devices, including optical disk devices, and the like.

This invention is based on a combination of hardware and firmware features.

The hardware features include: one or more rotating magnetic disk media, an ample solid state storage capacity; private channels between the disks and the solid state storage device; and high speed microprocessors to gather the intelligence, make data management decisions, and carry out the various data management asks.

The firmware features include the logic for gathering the historical data, making management decisions, and instructing the hardware to carry out the various data management operations. Important aspects of the firmware include making the decisions regarding the retention of data in the solid state memory based on usage history gathered during the device's work load experience.

The present invention includes a unique methodology for retaining, or recycling, of certain cached data which normally would be decached. While it would be normal to decache that data which is least recently used, this invention adds the further feature of utilizing a simple, but effective method of determining the probability of reuse of the least recently used data. This recycling methodology determines which data, although currently the least recently used, should still be retained in cache based on its higher potential reuse; and which least recently used data has a lessor probability of being reused, and thus, should be decached to make space in cache for other data which is or may be of current need.

The hybrid storage media of this invention performs at near solid state speeds for many types of computer workloads while practically never performing at less than normal magnetic disk speeds for any workload.

A rotating magnetic disk media is used to give the device a large capacity; the solid state storage is used to give the device a high-speed response capability. By associating the solid state media directly with a single magnetic disk device, a private data communication line is established which avoids contention between normal data transfers between the host and the device and transfers between the solid state memory and the disk. This private data channel permits virtually unlimited conversation between the two storage media. Utilization of ample solid state memory permits efficient maintenance of data for multiple, simultaneously active data streams. Management of the storage is via one or more microprocessors which utilize historical and projected data accesses to perform intelligent placement of data. No table searches are employed in the time-critical path. Host accesses to data stored in the solid state memory are at solid state speeds; host accesses to data stored on the magnetic disk are at disk device speeds. Under most conditions, all data sent from the host to the device is handled at solid state speeds.

BRIEF DESCRIPTIONS OF THE DRAWINGS

FIG. 1 is a block diagram of a typical prior art cached disk computer data storage system;

FIG. 2 is a block diagram depicting one embodiment of a cached disk computer data storage device constructed in accordance with the teachings of this invention;

FIG. 3 is a block diagram depicting one embodiment of a hardware controller for implementing the described invention;

FIG. 4 is a flow chart depicting the operation of one embodiment of this invention;

FIG. 5 is a flow chart depicting a more detailed description of the operation of the host command step of FIG. 4;

FIG. 6 is a flow chart depicting the operation of one embodiment of the analyze host I/O command operation of FIG. 5;

FIG. 7 is a flow chart depicting in more detail the operation of the setup track address list operation of FIG. 6;

FIG. 8 is a flow chart depicting in more detail the address translation of FIG. 7;

FIG. 9 is a flow chart depicting the cache read hit operation depicted in FIG. 5;

FIG. 10 is a flow chart depicting in more detail the cache read miss/operation depicted in FIG. 5;

FIG. 11 is a flow chart depicting the cache write hit operation of FIG. 5;

FIG. 12 is a flow chart depicting the cache write miss operation of FIG. 5;

FIG. 13 is a flow chart depicting the seek cache miss operation of FIG. 5;

FIG. 14 is a flow chart depicting the decache LRU operation of FIGS. 6, 13 and 15;

FIG. 15 is a flow chart depicting the cache ahead operation of FIG. 4;

FIG. 16 is a flow chart depicting the operation of the cache ahead determination operation of FIG. 15;

FIG. 17 is a flow chart depicting the operation of the initiate background sweep operation of FIG. 4;

FIG. 18 is a flow chart depicting the step of background sweep initiation at host I/O completion depicted in FIG. 4;

FIG. 19 is a flow chart depicting the generate background event operations depicted in FIGS. 17, 18, and 20;

FIG. 20 is a flow chart depicting the operation of the continued background sweep step of FIG. 4;

FIG. 21 is a flow chart depicting the power down control operations; and

FIG. 22 is a flow chart depicting the final background sweep operation depicted in FIG. 21.

DESCRIPTION OF THE TABLES

Tables F-1 through F-4 describe the organization of Tables T-1 through T-4, respectively;

Table T-0 depicts a sample of I/O commands extracted from computer system operations during normal usage. These I/O commands, and the intervening commands, were the basis for the sample predicted LRU and ADT tables as shown in Tables T-1 through T-3.

Table T-1 depicts an example of values in the address translation (ADT) table prior to the handling of the first I/O operation from the host CPU;

Table T-2 depicts an example of values in the Least-Recently-Used (LRU) table prior to the handling of the first I/O operation from the host CPU; and

Table 3 is formed of Tables T-3a through T-3e, which depict the ADT table after various numbers of I/O operations.

DETAILED DESCRIPTION OF THE INVENTION

Glossary of Terms

ADDRESS TRANSLATION:

The conversion of a sector address into a track address and sector offset within the trac