Disk drive cache system using a dynamic priority sequential stream of data segments continuously adapted according to prefetched sequential random, and repeating types of accesses

• US 6,092,149 A
• Filed: 05/28/1997
• Issued: 07/18/2000
• Est. Priority Date: 05/28/1997
• Status: Expired due to Term

• Current Assignee: Western Digital Corporation
• Original Assignee: Western Digital Corporation
• Inventors: Swatosh, Timothy, Howe, Steven M., Williams, Jeffrey L., Hicken, Michael Scott, Sokolov, Daniel John
• Primary Examiner(s): Cabeca, John W.
• Assistant Examiner(s): BATAILLE, PIERRE MICHE
• Application Number:
  US08/864,525
• Time in Patent Office: 1,147 Days
• Field of Search: 711/113, 711/137, 711/118, 711/114, 711/129, 711/112, 395/673, 395/675
• 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/0871 Allocation or management of cache space
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
• CPC Class Codes: G06F 2212/601 Reconfiguration of cache memory
• CPC Class Codes: G06F 2212/6026 Prefetching based on access pattern detection, e.g. stride based prefetch
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0634 by changing the state or mode of one or more devices
• CPC Class Codes: G06F 3/0676 Magnetic disk device

Abstract

A magnetic disk drive with a caching system includes an intelligent interface to communicate with a host, a magnetic disk and a cache memory to buffer data transferred to and from the host. The caching system maximizes drive performance based on past access history. The caching system alters execution of commands by coalescing commands or executing internal commands in parallel. The caching system anticipates data requests by using a prefetch to store data that may be requested. The caching system divides the cache memory into segments to store multiple streams of data. The number of segments may be continuously adapted according to the types of access to maximize performance by maintaining a segment for each sequential stream of data. The caching system uses a dynamic priority list to determine segments to maintain and discard. Each segment is monitored to determine access types such as sequential, random, and repeating. The access type determines the amount of data to prefetch and to save, including a minimum and maximum prefetch. The caching system may prescan the cache memory during prefetch to alter the prefetch amount in response to a command request. The caching system may wait for a cache memory access that has not yet occurred. An initiator changes the caching parameters though a mode page.

Claims

1. In a disk drive having an intelligent interface for communicating with a host, a magnetic disk, host side programs, disk side programs, and a cache wherein the cache is divisible into a number of segments wherein the number of segments may be varied, wherein the cache employs a cache control structure including a cache entry table, a buffer counter, a host pointer and a disk pointer, a method for processing commands from the host comprising:

(a) receiving a plurality of commands from the host including a read command;

(b) selecting the read command from the plurality of commands;

(c) initializing a task control block data structure for the read command;

(d) deciding whether to scan the cache first or start a seek first;

(e) if scanning the cache first, performing a scan of the cache entry table to assign a cache segment to the read command to determine a full cache hit or a partial cache hit by checking whether data requested in the read command is in the cache, obtaining the disk pointer if there was not a full cache hit, starting a seek if there was no cache hit, computing a prefetch if there was not a full cache hit, setting the buffer counter and starting the disk side programs if there was not a full cache hit, setting the host pointer and starting the host side programs, and setting the cache control structure to a state that represents a condition the cache will be in after the read command has completed; and

(f) if starting a seek first, obtaining the disk pointer, starting a seek, adjusting a size of each segment and number of segments in the cache to adapt to commands being processed, performing a scan of the cache entry table to assign a cache segment to the read command to determine a full cache hit or a partial cache hit by checking whether data requested in the read command is in the cache, performing a seek if there was a partial cache hit, computing a prefetch for the read command if there was not a full cache hit, setting the buffer counter and starting a read of the magnetic disk if there was not a full cache hit, setting the host pointer and starting the host, and setting the cache control structure to a state that represents a condition the cache will be in after the read command has completed.

2. The method of claim 1, wherein the disk drive receives a first command and a second command, further comprising the steps of:

(a) determining a scan first state; and

(b) performing a scan to assign the second command to a segment if the scan first state is true and the disk drive is busy processing the first command.

3. The method of claim 1 further comprising the steps of:

(a) maintaining a cache array with a cache array entry wherein there is a cache array entry for each one of the number of segments, where each cache array entry classifies a segment by a cache access type, wherein the cache access type is selected from a plurality of cache access types including sequential and random; and

(b) regularly determining whether to change the number of segments wherein an increase of the number of segments is affected when all of the segments are classified as sequential.

4. The method of claim 1 further comprising the steps of:

(a) maintaining a cache array with a cache array entry wherein there is a cache array entry for each one of the number of segments, where each cache array entry classifies a segment by a cache access type, wherein the cache access type is selected from a plurality of cache access types including sequential and random; and

(b) regularly determining whether to change the number of segments wherein an increase of the number of segments is affected based on a weighed weighing of a plurality of caching factors.

5. The method of claim 1 further comprising the steps of:

(a) maintaining a cache array with a cache array entry wherein there is a cache array entry for each one of the number of segments, where each cache array entry classifies a segment by a cache access type, wherein the cache access type is selected from a plurality of access types including sequential and random; and

(b) regularly determining whether to change the number of segments wherein a decrease of the number of segments is affected based on a weighed weighing of a plurality of caching factors.

6. The method of claim 5 wherein the plurality of caching factors further comprises the number of random cache hits, number of sequential cache hits, number of segments, a block count and a blocks per segment.

7. The method of claim 5 wherein the number of segments are changed after a predetermined number of seeks.

8. The method of claim 1, wherein the disk drive receives a first command, further comprising the steps of:

(a) determining a scan first state;

(b) performing a scan to assign the first command to a segment if the scan first state is true and the disk drive is busy; and

(c) performing a seek if the scan first state is false and then adapting the number of segments in the cache and then performing a scan to assign the first command to a segment.

9. The method of claim 1, wherein the disk drive receives a first command and a second command, further comprising the steps of:

(a) in response to the first command initializing a read to provide a prefetch to be cached; and

(b) waiting for a cache hit in response to a second command whose requested data range is within the prefetch range and does not request a first logical block of the prefetch.

10. The method of claim 1, wherein the disk drive receives a first command and a second command, further comprising the steps of:

(a) performing a scan to assign the first command to a segment;

(b) compensating the cache parameters in response to the scan; and

(c) performing a scan to assign the second command to a segment prior to caching of data requested in the first command.

11. The method of claim 1, wherein the disk drive receives a first command and a second command, further comprising the steps of:

(a) performing a scan to assign the first command to a segment;

(b) initiating a read to prefetch data associated with the first command;

(c) compensating the cache parameters in response to the scan; and

(d) performing a scan to assign the second command to a segment prior to caching of prefetch data associated with the first command.

12. The method of claim 1, wherein the disk drive receives a first command, further comprising the steps of:

(a) performing a scan to assign the first command to a segment;

(b) maintaining a cache array with a cache array entry wherein there is a cache array entry for each one of the number of segments, where each cache array entry classifies a segment by a cache access type, wherein the cache access type is selected from a plurality of access types including sequential and random; and

(c) determining a minimum prefetch based on the cache access type for the first command and a cache environment variable.

13. The method of claim 1, wherein the disk drive receives a first command and a second command, further comprising the steps of:

(a) performing a scan to assign the first command to a segment;

(b) maintaining a cache array with a cache array entry wherein there is a cache array entry for each one of the number of segments, where each cache array entry classifies a segment by a cache access type, wherein the cache access type is selected from a plurality of access types including sequential and random;

(c) determining a minimum prefetch based on the cache access type for the first command and a cache environment variable;

(d) initiating a read for the first command; and

(e) determining if the second command requires a seek and aborting the prefetch only after at least a minimum prefetch has occurred.

14. The method of claim 1, wherein the disk drive receives a first command, further comprising the steps of:

(a) performing a scan to assign the first command to a segment;

(b) maintaining a cache array with a cache array entry wherein there is a cache array entry for each one of the number of segments, where each cache array entry classifies a segment by a cache access type, wherein the cache access type is selected from a plurality of access types including sequential and random; and

(c) determining a maximum prefetch based on the cache access type for the first command and a cache environment variable to preserve data already in the cache for a second command.

15. The method of claim 1, wherein the disk drive receives a first command, further comprising the steps of:

(a) processing a first command and caching only requested data from the disk drive; and

(b) processing a second command and caching prefetched data associated with the second command if the second command is determined to be sequential with the first command.

16. The method of claim 15 further comprising the step of determining the second command to be sequential with the first command by comparing a logical block address of the second command with a first logical block address of a prefetch for the first command to determine the second command to be sequential to the first command.

17. The method of claim 1 wherein each segment has a scan priority, further comprising the steps of:

(a) maintaining a cache array with a cache array entry wherein there is a cache array entry for each one of the number of segments, where each cache array entry classifies a segment by a cache access type, wherein the cache access type is selected from a plurality of access types including sequential and random; and

(b) determining whether to change the scan priority of each segment based on the cache access type.

18. The method of claim 17 wherein the scan priority is higher for sequential segments.

19. The method of claim 1, wherein the disk drive receives a first command and a second command, further comprising the steps of:

(a) determining the cache access type of the second command; and

(b) determining if the cache access type of the second command is a skip ahead sequential access and if the cache access type is skip ahead sequential access decrementing a buffer count and incrementing a host pointer to skip leading nonrequested data in the prefetch of the first command.

20. The method of claim 1, wherein the disk drive receives a first command and a second command, further comprising the steps of:

(a) determining the cache access type of the second command; and

(b) determining if the cache access type of the second command is semi-repeating access, and if the cache access type is semi-repeating access incrementing a buffer count and decrementing a host pointer to resend lagging requested data from the prefetch of the first command.