Method to throttle rate of data caching for improved I/O performance

• US 9,189,422 B2
• Filed: 02/07/2013
• Issued: 11/17/2015
• Est. Priority Date: 02/07/2013
• Status: Active Grant

• Current Assignee: Avago Technologies International Sales Pte Limited (Broadcom, Inc.)
• Original Assignee: Avago Technologies General IP PTE Limited (Broadcom, Inc.)
• Inventors: Shivashankaraiah, Vinay Bangalore, Gopinath, Netra
• Primary Examiner(s): Bragdon, Reginald
• Assistant Examiner(s): Wang, Edward
• Application Number:
  US13/761,397
• Publication Number:
  US 20140223106A1
• Time in Patent Office: 1,013 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 12/122 of the least frequently used [LFU] type, e.g. with individual count value
• 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 12/126 with special data handling, e.g. priority of data or instructions, handling errors or pinning

Abstract

A cache device for the caching of data and specifically for the identification of stale data or a thrashing event within the cache device is described. Further a cache device for the prioritization of cached data in the cache device during a thrashing event as well as stale cached data in the cache device are described. Methods associated with the use of the caching device for the caching of data and for the identification of data in a thrashing event or the identification of stale cached data are also described.

Claims

1. A method of storing data onto a cache device when the amount of hot data exceeds the cache device'"'"'s storage capacity comprising:

monitoring references to data stored in one or more physical cache windows in a cache device by utilizing a least recently used queue block;

prioritizing said data stored in said one or more physical cache windows to a least recently used queue in said least recently used queue block;

promoting said one or more physical cache windows to a higher priority least recently used queue in said least recently used queue block based on the number of said references to said data in said one or more physical cache windows during a certain time period;

demoting said one or more physical cache windows to a lower priority least recently used queue in said least recently used queue block when said data is not accessed during a certain time period;

monitoring the number of demoted physical cache windows in said cache device using one or more counters in said least recently used queue block;

searching a hash table in communication with said least recently used queue;

identifying said cache device is thrashing when the total number of said demoted physical cache windows is equal to zero and a total number of free physical cache windows is equal to zero; and

increasing the number of said references required to store said data in said one or more demoted physical cache windows,

wherein said increasing in said number of said references is greater than three references.

2. The method claim 1, further comprising:

identifying that no free physical cache windows are available in said cache device;

replacing data from said one or more demoted physical cache windows in said lowest priority least recently used queue;

storing new data to said one or more demoted physical cache windows; and

tracking references to said new data stored in said one or more demoted physical cache windows utilizing said least recently used queue block.

3. The method of claim 2, further comprising:

tracking data in a host using a virtual cache window;

monitoring the number of references to said data in said host using said virtual cache window; and

storing said data from said host onto said cache device represented by said one or more physical cache windows based upon said data from said host receiving a number of said references during a certain time period.

4. The method of claim 1, further comprising:

identifying said cache device has stale data when the total number of said one or more demoted physical cache windows is greater than zero and the total number of said free physical cache windows is equal to zero.

5. The method of claim 1, further comprising

identifying when said cache device has free physical cache windows when the total number of said one or more demoted cache windows is equal to zero and the total number of said free cache windows is greater than zero.

6. A cache device for the caching of data comprising:

at least one virtual cache window;

at least one physical cache window;

a least recently used queue block in communication with said at least one physical cache window, wherein said least recently used queue block comprises at least two least recently used queues, at least two counters and one global counter; and

a hash table in communication with said least recently used queue block,

wherein said at least one physical cache window is prioritized to said at least two least recently used queues in said least recently used queue block based on the number of references to data stored in said at least one physical cache window,

wherein said hash table maintains a list of the location of said data stored in said at least one physical cache window as well as the location of said at least one physical cache window,

wherein said least recently used queue block monitors the number of references to said data stored in said at least one physical cache window,

wherein said at least two counters and one global counter monitor demotion of said at least one physical cache window in communication with said least recently used queue block.

7. The cache device of claim 6, wherein said at least one physical cache window further comprise at least one cache block for storage of said data.