Disk drive with adaptively segmented cache

• US 5,966,726 A
• Filed: 06/25/1997
• Issued: 10/12/1999
• Est. Priority Date: 05/28/1997
• Status: Expired due to Term

• Current Assignee: Western Digital Corporation
• Original Assignee: Western Digital Corporation
• Inventors: Sokolov, Daniel John
• Primary Examiner(s): BRAGDON, REGINALD GLENWOOD
• Application Number:
  US08/881,518
• Time in Patent Office: 839 Days
• Field of Search: 711/113, 711/129, 711/133, 711/137, 711/170, 711/173
• 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 disk drive has an intelligent interface for communicating with a host, a magnetic disk, and a cache. The cache is divisible into a number of segments, with each segment having a cache access type. The number of segments may be varied in practice of a method for adaptively segmenting the cache. The method comprises the steps of: (a) calculating a plurality of caching factors while processing commands from the host; and (b) regularly determining whether to change the number of segments wherein an increase of the number of segments is effected based on a weighed weighing of the plurality of caching factors.

Claims

1. In a disk drive having an intelligent interface for communicating with a host, a magnetic disk, and a cache wherein the cache is divisible into a number of segments, wherein each segment has a cache access type, wherein the number of segments may be varied, a method for adaptively segmenting the cache comprising the steps of:

(a) calculating a plurality of caching factors while processing commands from the host; and

(b) regularly determining whether to change the number of segments wherein an increase of the number of segments is effected based on a weighed weighing of the plurality of caching factors, wherein commands from the host have a block count of a number of blocks of data to transfer and each segment contains a number of blocks per segment and wherein, while processing commands from the host, the disk drive counts the number of random cache accesses, and counts the segments that have sequential access as sequential cache hits, wherein the plurality of caching factors further comprises the number of random cache accesses, the number of sequential cache hits, the number of segments, the block count, and the number of blocks per segment.

2. The method of claim 1 wherein the host sends a request with a logical block address and each cache entry further comprises a prefetch range with a prefetch start logical block address and wherein the cache access type of a segment is defined as sequential when the logical block address of the request equals the prefetch start logical block address of the segment.

3. The method of claim 1 wherein the number of segments is adapted to at least one greater than the number of segments designated as a sequential cache access type.

4. The method of claim 1 wherein the number of segments is increased if commands received from the host are random, and there are no cache hits.

5. The method of claim 1 wherein the number of segments are determined after a predetermined number of seeks.

6. The method of claim 1 wherein the number of segments are changed while a seek completes.

7. In a disk drive having an intelligent interface for communicating with a host, a magnetic disk, and a cache wherein the cache is divisible into a number of segments wherein the number of segments may be varied, a method for adaptively segmenting the cache comprising the steps of:

(a) calculating a plurality of caching factors while processing commands from the host; and

(b) regularly determining whether to change the number of segments wherein a decrease of the number of segments is effected based on a weighed weighing of the plurality of caching factors, wherein each command from the host has a block count of data to be transferred, wherein the method further comprises the step of decreasing the number of segments if the block count is larger than half a number of blocks in a segment.

8. The method of claim 7, wherein commands from the host have a block count of a number of blocks of data to transfer, and each segment contains a number of blocks per segment, and wherein, while processing commands from the host, the disk drive counts the number of random cache accesses, and counts the segments that have sequential access as sequential cache hits, wherein the plurality of caching factors further comprises the number of random cache hits, the number of sequential cache hits, the number of segments, the block count and the number of blocks per segment.

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

10. The method of claim 7 wherein the number of segments are changed while waiting for a seek to complete.

11. In a disk drive having an intelligent interface for communicating with a host, a magnetic disk, 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 array, a method for adaptively segmenting the cache comprising the steps of:

(a) maintaining the cache array 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 effected when all of the segments are classified as sequential.

12. The method of claim 11 wherein the host sends a request with a logical block address and each cache array entry further comprises a prefetch range with a prefetch start logical block address and wherein the cache access type of a segment is defined as sequential when the logical block address of the request equals the prefetch start logical block address of the segment.

13. The method of claim 11 wherein the number of segments are changed while a seek completes.

14. The method of claim 11 wherein the number of segments are changed after a predetermined number of seeks.

15. In a disk drive having an intelligent interface for communicating with a host, a magnetic disk, 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 method for determining when to adaptively segment the cache comprising the steps of:

(a) receiving a first command from the host;

(b) receiving a second command from the host,

(c) checking if the disk drive is busy processing the first command;

(d) checking if a scan first flag has been set;

(e) if the disk drive is not busy processing the first command or the scan first flag is not set then starting a seek for the second command and adapting the number of segments in the cache.

16. The method of claim 15 further comprising the steps of:

(a) scanning the cache to assign the second command to a cache segment; and

(b) determining whether a seek is needed for the second command and, if a seek is needed, starting the seek.

17. The method of claim 15 further comprising the steps of:

(a) processing the first and second commands from the host;

(b) determining the number of cache hits while processing the first and second commands from the host;

(c) comparing the number of cache hits to the number of segments to determine the scan first flag.

18. In a disk drive having an intelligent interface for communicating with a host, a magnetic disk, 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 caching factors, and wherein the disk drive performs a number of seeks while processing commands from the host, a method for adaptively managing the cache comprising the steps of:

(a) computing caching factors while processing commands from the host until a predetermined number of seeks have occurred;

(b) checking whether a sequential stream is in process;

(c) stopping the sequential stream once if a sequential stream is in process; and

(d) changing the number of segments in the cache based on the commands processed.

19. The method of claim 18, wherein data is transferred in blocks and each block has a block boundary, wherein the step of stopping the sequential stream once further comprises the steps of stopping data transfer at a block boundary and restarting data transfer after reevaluating the number of segments.

20. The method of claim 18, wherein commands from the host have a block count of a number of blocks of data to transfer, and each segment contains a number of blocks per segment and wherein, while processing commands from the host, the disk drive counts the number of random cache accesses, and counts the segments that have sequential access as sequential cache hits, wherein the plurality of caching factors further comprises the number of random cache accesses, the number of sequential cache hits, the number of segments, the block count, and the number of blocks per segment.

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

22. In a disk drive having an intelligent interface for communicating with a host, a magnetic disk, 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, an upvote counter and a downvote counter, a block count of the number of blocks to transfer for a command from the host, a number of cache hits, a number of sequential cache hits, and a blocks per segment, a method for adaptively managing the number of segments in the cache comprising the steps of:

(a) initializing the upvote counter and the downvote counter;

(b) checking each segment of the cache to determine the number of cache hits and the number of sequential cache hits;

(c) computing an average block count;

(d) incrementing the upvote counter if there was a cache hit;

(e) incrementing the upvote counter if the number of sequential cache hits is greater than or equal to the number of segments divided by two;

(f) decrementing the upvote counter and incrementing the downvote counter if a number of sequential streams is greater than zero and the number of sequential streams is less than the number of segments divided by four;

(g) incrementing the downvote counter if the block count is greater than the blocks per segment divided by two;

(h) decrementing the upvote counter if the block count is less than the blocks per segment divided by two;

(i) incrementing the downvote counter if the block count is greater than the blocks per segment;

(j) halving the number of segments if the downvote counter is greater than the upvote counter; and

(k) doubling the number of segments if the upvote counter is greater than the downvote counter.

23. The method of claim 22 further comprising the step of doubling the number of segments until the number of segments are greater than the number of sequential streams.

24. The method of claim 22 further comprising the step of adjusting the number of segments by first aborting a current prefetch and finishing a sequential write before resegmenting the cache.