For adaptive caching

• US 20050144394A1
• Filed: 12/24/2003
• Published: 06/30/2005
• Est. Priority Date: 12/24/2003
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Zimmer, Vincent J., Komarla, Eshwari P.
• Granted Patent: US 7,353,339 B2
• Time in Patent Office: Days
• US Class Current: 711/137
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 2212/502 using adaptive policy

Abstract

Provided are techniques for cache management. An incoming request to access a first data block is received. A probability of how likely a second data block may be accessed based on the access of the first data block is determined. Whether the probability exceeds a read ahead threshold is determined. The second data block is prefetched in response to determining that the probability exceeds the read ahead threshold.

Claims

1. A method for cache management, comprising:

receiving an incoming request to access a first data block;

determining a probability of how likely a second data block may be accessed based on the access of the first data block;

determining whether the probability exceeds a read ahead threshold; and

prefetching the second data block in response to determining that the probability exceeds the read ahead threshold.

2. The method of claim 1, further comprising:

determining whether a hop count associated with the first data block is greater than a hop count threshold; and

promoting the read request to a different position in a request data structure in response to determining that the hop count is greater than the hop count threshold.

3. The method of claim 1, further comprising:

updating a probability that the first data block may be accessed.

4. The method of claim 1, further comprising:

updating a prefetch counter when prefetching the second data block.

5. The method of claim 1, wherein the incoming request is a write request and further comprising:

caching the first data block;

committing the write request to a storage device; and

sending acknowledgement that the write request has been committed.

6. The method of claim 5, further comprising:

writing the first data block to the storage device after committing the write request.

7. The method of claim 1, further comprising:

determining that a data block is to be evicted from cache;

determining whether data blocks currently in the cache have been accessed within a predetermined interval;

evicting a data block in the cache that is held for a nearest computing device in response to determining that the data blocks have been accessed within the predetermined interval; and

evicting a data block in cache that has least recently been accessed in response to determining that at least one data block has not been accessed within the predetermined interval.

8. The method of claim 7, wherein the determination of which computing device is a nearest computing device is based on a hop count associated with a request from that computing device.

9. The method of claim 1, wherein the incoming request is a read request further comprising:

determining whether the first data block is in cache;

determining whether the first data block was previously prefetched in response to determining that the first data block is in cache; and

incrementing a prefetch success counter in response to determining that the first data block was previously prefetched.

10. The method of claim 1, further comprising:

determining whether a percentage of times a prefetched data block was accessed exceeds a success threshold;

updating the read ahead threshold in response to determining that the percentage does not exceed the success threshold.

11. The method of claim 1, further comprising:

updating a hop count threshold based on access statistics.

12. The method of claim 1, wherein the probability is determined using a Bayesian networks technique.

13. A system in communication with data storage, comprising:

a computing device with an Input/Output (I/O) processor;

a storage controller capable of managing Input/Output (I/O) access to the data storage, wherein the data storage controller is coupled to the computing device; and

a cache management agent at the computing device, wherein the cache management agent is capable of receiving an incoming request to access a first data block, determining a probability of how likely a second data block may be accessed based on the access of the first data block, determining whether the probability exceeds a read ahead threshold, and prefetching the second data block in response to determining that the probability exceeds the read ahead threshold.

14. The system of claim 13, wherein the cache management agent is capable of determining whether a hop count associated with the first data block is greater than a hop count threshold and promoting the read request to a different position in a request data structure in response to determining that the hop count is greater than the hop count threshold.

15. The system of claim 13, wherein the cache management agent is capable of updating a probability that the first data block may be accessed.

16. The system of claim 13, wherein the cache management agent is capable of updating a prefetch counter when prefetching the second data block.

17. The system of claim 13, wherein the incoming request is a write request and wherein the cache management agent is capable of caching the first data block, committing the write request to a storage device, and sending acknowledgement that the write request has been committed.

18. The system of claim 17, wherein the cache management agent is capable of writing the first data block to the storage device after committing the write request.

19. The system of claim 13, wherein the cache management agent is capable of determining that a data block is to be evicted from cache, determining whether data blocks currently in the cache have been accessed within a predetermined interval, evicting a data block in the cache that is held for a nearest computing device in response to determining that the data blocks have been accessed within the predetermined interval, and evicting a data block in cache that has least recently been accessed in response to determining that at least one data block has not been accessed within the predetermined interval.

20. The system of claim 19, wherein the determination of which computing device is a nearest computing device is based on a hop count associated with a request from that computing device.

21. The system of claim 13, wherein the incoming request is a read request and wherein the cache management agent is capable of determining whether the first data block is in cache, determining whether the first data block was previously prefetched in response to determining that the first data block is in cache, and incrementing a prefetch success counter in response to determining that the first data block was previously prefetched.

22. The system of claim 13, wherein the cache management agent is capable of determining whether a percentage of times a prefetched data block was accessed exceeds a success threshold and updating the read ahead threshold in response to determining that the percentage does not exceed the success threshold.

23. The system of claim 13, wherein the cache management agent is capable of updating a hop count threshold based on access statistics.

24. The system of claim 13, wherein the probability is determined using a Bayesian networks technique.

25. An article of manufacture, comprising a storage medium having stored therein instructions that when executed by a computing device results in the following:

receiving an incoming request to access a first data block;

determining a probability of how likely a second data block may be accessed based on the access of the first data block;

determining whether the probability exceeds a read ahead threshold; and

prefetching the second data block in response to determining that the probability exceeds the read ahead threshold.

26. The article of manufacture of claim 25, wherein the instructions when executed further result in the following:

determining whether a hop count associated with the first data block is greater than a hop count threshold; and

promoting the read request to a different position in a request data structure in response to determining that the hop count is greater than the hop count threshold.

27. The article of manufacture of claim 25, wherein the instructions when executed further result in the following:

updating a probability that the first data block may be accessed.

28. The article of manufacture of claim 25, wherein the instructions when executed further result in the following:

updating a prefetch counter when prefetching the second data block.

29. The article of manufacture of claim 25, wherein the incoming request is a write request and wherein the instructions when executed further result in the following:

caching the first data block;

committing the write request to a storage device; and

sending acknowledgement that the write request has been committed.

30. The article of manufacture of claim 29, wherein the instructions when executed further result in the following:

writing the first data block to the storage device after committing the write request.

31. The article of manufacture of claim 25, wherein the instructions when executed further result in the following:

determining that a data block is to be evicted from cache;

determining whether data blocks currently in the cache have been accessed within a predetermined interval;

evicting a data block in the cache that is held for a nearest computing device in response to determining that the data blocks have been accessed within the predetermined interval; and

evicting a data block in cache that has least recently been accessed in response to determining that at least one data block has not been accessed within the predetermined interval.

32. The article of manufacture of claim 31, wherein the determination of which computing device is a nearest computing device is based on a hop count associated with a request from that computing device.

33. The article of manufacture of claim 25, wherein the incoming request is a read request and wherein the instructions when executed further result in the following:

determining whether the first data block is in cache;

determining whether the first data block was previously prefetched in response to determining that the first data block is in cache; and

incrementing a prefetch success counter in response to determining that the first data block was previously prefetched.

34. The article of manufacture of claim 25, wherein the instructions when executed further result in the following:

determining whether a percentage of times a prefetched data block was accessed exceeds a success threshold;

updating the read ahead threshold in response to determining that the percentage does not exceed the success threshold.

35. The article of manufacture of claim 25, wherein the instructions when executed further result in the following:

updating a hop count threshold based on access statistics.

36. The article of manufacture of claim 25, wherein the probability is determined using a Bayesian networks technique.