Method and apparatus for cache replacement using a catalog

• US 8,732,401 B2
• Filed: 10/07/2011
• Issued: 05/20/2014
• Est. Priority Date: 07/07/2011
• Status: Active Grant

• Current Assignee: Atlantis Computing, Inc. (hiveIO, Inc.)
• Original Assignee: Atlantis Computing, Inc. (hiveIO, Inc.)
• Inventors: Venkatesh, Chetan, Dixit, Sagar Shyam
• Primary Examiner(s): LANE, JOHN A
• Application Number:
  US13/269,503
• Publication Number:
  US 20130013844A1
• Time in Patent Office: 956 Days
• Field of Search: 711/133, 711/144
• US Class Current: 711/133
• CPC Class Codes: G06F 12/0808 with cache invalidating means G06F12/0815 takes precedence
• CPC Class Codes: G06F 12/126 with special data handling, e.g. priority of data or instructions, handling errors or pinning
• CPC Class Codes: G06F 12/128 adapted to multidimensional cache systems, e.g. set-associative, multicache, multiset or multilevel
• CPC Class Codes: G06F 16/172 Caching, prefetching or hoarding of files
• CPC Class Codes: G06F 9/45533 Hypervisors; Virtual machine monitors

Abstract

Methods and systems to intelligently cache content in a virtualization environment using virtualization software such as VMWare ESX or Citrix XenServer or Microsoft HyperV or Redhat KVM or their variants are disclosed. Storage IO operations (reads from and writes to disk) are analyzed (or characterized) for their overall value and pinned to cache if their value exceeds a certain defined threshold based on criteria specific to the New Technology File System (NTFS) file-system. Analysis/characterization of NTFS file systems for intelligent dynamic caching include analyzing storage block data associated with a Virtual Machine of interest in accordance with a pre-determined data model to determine the value of the block under analysis for long term or short term caching. Integer values assigned to different types of NTFS objects in a white list data structure called a catalog that can be used to analyze the storage block data.

Claims

1. A method, comprising:

using an assigned value from a catalog to determine which slot to evict from a set in a cache, the assigned value is an integer;

evaluating a slot from the set in the cache using an intelligent content aware caching application running on a virtual machine (VM) hypervisor, the intelligent content aware caching application configured to read contents of the catalog to determine whether or not to evict the slot being evaluated;

determining when metadata for the slot being evaluated has an assigned value of three and foregoing eviction of the slot being evaluated when its metadata has the assigned value of three;

(a) evaluating all slots in the set having an assigned value of zero and evicting a slot having an oldest time stamp and having the assigned value of zero in its metadata;

(b) evaluating all slots in the set having an assigned value of two and evicting a slot having an oldest time stamp and having the assigned value of two in its metadata;

(c) evaluating all slots in the set having an assigned value of one and evicting a slot having an oldest time stamp and having the assigned value of one in its metadata; and

evaluating slots in a second set in the cache after at least one slot in the set that was found to have an assigned value of zero, two, or one in its metadata has been evicted, or when no slots in the set were found that have assigned values of zero, two, or one in their metadata.

2. The method of claim 1, wherein the evaluating of all slots occurs in an order and the order is (a) followed by (b), and (b) followed by (c).

3. The method of claim 1 and further comprising:

evaluating the next slot in the set.

4. The method of claim 1 and further comprising:

going to another set in the cache and evaluating slots in the another set.

5. A non-transitory computer readable storage medium including instructions that, when executed on a computer system cause the computer system to perform a method comprising:

using an assigned value from a catalog to determine which slot to evict from a set in a cache, the assigned value is an integer;

evaluating a slot from the set in the cache using an intelligent content aware caching application running on a virtual machine (VM) hypervisor, the intelligent content aware caching application configured to read contents of the catalog to determine whether or not to evict the slot being evaluated;

determining when metadata for the slot being evaluated has an assigned value of three and foregoing eviction of the slot being evaluated when its metadata has the assigned value of three;

(a) evaluating all slots in the set having an assigned value of zero and evicting a slot having an oldest time stamp and having the assigned value of zero in its metadata;

(b) evaluating all slots in the set having an assigned value of two and evicting a slot having an oldest time stamp and having the assigned value of two in its metadata;

(c) evaluating all slots in the set having an assigned value of one and evicting a slot having an oldest time stamp and having the assigned value of one in its metadata; and

evaluating slots in a second set in the cache after at least one slot in the set that was found to have an assigned value of zero, two, or one in its metadata has been evicted, or when no slots in the set were found that have assigned values of zero, two, or one in their metadata.

6. The non-transitory computer readable storage medium of claim 5, wherein all slots are executed in an order and the order is (a) followed by (b), and (b) followed by (c).

7. The non-transitory computer readable storage medium of claim 5 further comprises:

evaluating the next slot in the set.

8. The non-transitory computer readable storage medium of claim 5 further comprises:

going to another set in the cache and evaluating slots in the another set.

9. A system, comprising:

a memory to store a catalog; and

a processor coupled with the memory to execute an intelligent content aware caching application to

use an assigned value from a catalog to determine which slot to evict from a set in a cache, the assigned value is an integer,

evaluate a slot from the set in the cache using an intelligent content aware caching application running on a virtual machine (VM) hypervisor, the intelligent content aware caching application configured to read contents of the catalog to determine whether or not to evict the slot being evaluated,

determine when metadata for the slot being evaluated has an assigned value of three and foregoing eviction of the slot being evaluated when its metadata has the assigned value of three

(a) evaluate all slots in the set having an assigned value of zero and evicting a slot having an oldest time stamp and having the assigned value of zero in its metadata;

(b) evaluate all slots in the set having an assigned value of two and evicting a slot having an oldest time stamp and having the assigned value of two in its metadata;

(c) evaluate all slots in the set having an assigned value of one and evicting a slot having an oldest time stamp and having the assigned value of one in its metadata; and

evaluate slots in a second set in the cache after at least one slot in the set that was found to have an assigned value of zero, two, or one in its metadata has been evicted, or when no slots in the set were found that have assigned values of zero, two, or one in their metadata.

10. The system of claim 9, wherein all slots are executed in an order and the order is (a) followed by (b), and (b) followed by (c).

11. The system of claim 9, further comprises the processor to evaluate the next slot in the set.

12. The system of claim 9, further comprises the processor to go to another set in the cache and evaluate slots in the another set.