Methods for combining access history and sequentiality for intelligent prefetching and devices thereof

Patent metadata

Field	Value
Publication number	US-9471497-B2
Application number	US-201414164077-A
Country	US
Kind code	B2
Filing date	Jan 24, 2014
Priority date	Jan 24, 2014
Publication date	Oct 18, 2016
Grant date	Oct 18, 2016

Abstract

A method, non-transitory computer readable medium, and device that prefetchs includes identifying a candidate data block from one of one or more immediate successor data blocks. The identified candidate data block has a historical access probability value from an initial accessed data block which is higher than a historical access probability value for each of the other immediate successor data blocks and is above a prefetch threshold value. The identifying is repeated until a next identified candidate data block has the historical access probability value below the prefetch threshold value. In the repeating, the identifying next immediate successor data blocks is from the previously identified candidate data block and the historical access probability value for each of the next immediate successor data blocks is determined from the originally accessed data block. The identified candidate data block with the historical access probability value above the prefetch threshold value is fetched.

First claim

What is claimed is:

1. A method comprising:
identifying, with a computing device, at least one candidate data block from one of one or more immediate successor data blocks that has a historical access probability value from an initially accessed data block which is higher than a historical access probability value for each of the other immediate successor data blocks and is above a prefetch threshold value that comprises a first static threshold value for a synchronous request for fetching associated with a current cache miss and a second static threshold value for an asynchronous request for fetching associated with a cache read;
repeating, with the computing device, the identifying until at least one next identified candidate data block has a historical access probability value below the prefetch threshold value, wherein each of the repeating of the identifying is performed with respect to one or more next immediate successor data blocks from the previously identified at least one candidate data block and with a historical access probability value for each of the next immediate successor data blocks that is determined from the initially accessed data block; and
fetching, with the computing device, the one or more identified candidate data blocks with the historical access probability value above the prefetch threshold value from one or more storage media for storage in cache.

2. The method as set forth in claim 1 , further comprising:
obtaining, with the computing device, historical access data between data blocks; and
determining, with the computing device, a probability of access value between the data blocks which are within a sequentially accessed semantic distance of each other.

3. The method as set forth in claim 1 , further comprising determining, with the computing device, when a prefetch trigger has occurred, wherein the identifying begins when the determining indicates an occurrence of the prefetch trigger.

4. The method as set forth in claim 3 , wherein the prefetch trigger comprises at least one of a cache miss or a cache read.

5. The method as set forth in claim 1 , further comprising:
determining, with the computing device, when to evict one or more of the prefetched candidate data blocks in the cache based on one or more replacement characteristics; and
evicting, with the computing device, the one or more of the prefetched candidate data blocks in response to said determining.

6. The method as set forth in claim 5 , wherein the one or more replacement characteristics comprise at least a replacement candidate prefetch gain value and an eviction loss value.

7. A computing device comprising:
at least one processor; and
at least one memory coupled to the processor configured to execute programmed instructions stored in the memory comprising:
identifying at least one candidate data block from one of one or more immediate successor data blocks that has a historical access probability value from an initially accessed data block which is higher than a historical access probability value for each of the other immediate successor data blocks and is above a prefetch threshold value that comprises a first static threshold value for a synchronous request for fetching associated with a current cache miss and a second static threshold value for an asynchronous request for fetching associated with a cache read;
repeating the identifying until at least one next identified candidate data block has a historical access probability value below the prefetch threshold value, wherein each of the repeating of the identifying is performed with respect to one or more next immediate successor data blocks from the previously identified at least one candidate data block and with a historical access probability value for each of the next immediate successor data blocks that is determined from the initially accessed data block; and

fetching the one or more identified candidate data blocks with the historical access probability value above the prefetch threshold value from one or more storage media for storage in cache.

8. The device as set forth in claim 7 , wherein the processor is further configured to execute programmed instructions stored in the memory further comprising:
obtaining historical access data between data blocks; and
determining a probability of access value between the data blocks which are within a sequentially accessed semantic distance of each other.

9. The device as set forth in claim 7 , the processor is further configured to execute programmed instructions stored in the memory further comprising determining when a prefetch trigger has occurred, wherein the identifying begins when the determining indicates an occurrence of the prefetch trigger.

10. The device as set forth in claim 9 wherein the prefetch trigger comprises at least one of a cache miss or a cache read.

11. The device as set forth in claim 7 , the processor is further configured to execute programmed instructions stored in the memory further comprising:
determining when to evict one or more of the prefetched candidate data blocks in the cache based on one or more replacement characteristics; and
evicting the one or more of the prefetched candidate data blocks in response to said determining has indicated.

12. The device as set forth in claim 11 , wherein the one or more replacement characteristics comprise at least a replacement candidate prefetch gain value and an eviction loss value.

13. A non-transitory computer readable medium having stored thereon instructions for managing fetching comprising executable code which when executed by a processor, causes the processor to perform steps comprising:
identifying at least one candidate data block from one of one or more immediate successor data blocks that has a historical access probability value from an initially accessed data block which is higher than a historical access probability value for each of the other immediate successor data blocks and is above a prefetch threshold value that comprises a first static threshold value for a synchronous request for fetching associated with a current cache miss and a second static threshold value for an asynchronous request for fetching associated with a cache read;
repeating the identifying until at least one next identified candidate data block has a historical access probability value below the prefetch threshold value, wherein each of the repeating of the identifying is performed with respect to one or more next immediate successor data blocks from the previously identified at least one candidate data block and with a historical access probability value for each of the next immediate successor data blocks that is determined from the initially accessed data block; and
fetching the one or more identified candidate data blocks with the historical access probability value above the prefetch threshold value from one or more storage media for storage in cache.

14. The medium as set forth in claim 13 , wherein the steps further comprise:
obtaining historical access data between data blocks; and
determining a probability of access value between the data blocks which are within a sequentially accessed semantic distance of each other.

15. The medium as set forth in claim 13 , wherein the steps further comprise determining when a prefetch trigger has occurred, wherein the identifying begins when the determining indicates an occurrence of the prefetch trigger.

16. The medium as set forth in claim 15 , wherein the prefetch trigger comprises at least one of a cache miss or a cache read.

17. The medium as set

Assignees

• Netapp Inc

Inventors

• Yang Suli
• Udayashankar Kishore Kasi
• Feng Jingxin
• Krishnan Swetha
• Srinivasan Kiran

Classifications

• G06F17/30132

  Physics · mapped topic

• G06F2212/314

  In storage network, e.g. network attached cache · CPC title

• H04L67/2852

  Electricity · mapped topic

• G06F12/0866

  for peripheral storage systems, e.g. disk cache · CPC title

• G06F2212/6024

  History based prefetching · CPC title