System and method for prioritizing data in a cache

Abstract

Implementations described and claimed herein provide a system and methods for prioritizing data in a cache. In one implementation, a priority level, such as critical, high, and normal, is assigned to cached data. The priority level dictates how long the data is cached and consequently, the order in which the data is evicted from the cache memory. Data assigned a priority level of critical will be resident in cache memory unless heavy memory pressure causes the system to reclaim memory and all data assigned a priority state of high or normal has been evicted. High priority data is cached longer than normal priority data, with normal priority data being evicted first. Accordingly, important data assigned a priority level of critical, such as a deduplication table, is kept resident in cache memory at the expense of other data, regardless of the frequency or recency of use of the data.

What is claimed is: 
     
         1 . A method comprising:
 receiving a write request to write data to a cache having one or more states;   assigning a priority level to the data using at least one processor, the priority level and a cache replacement policy dictating an order in which the data is evicted from the cache; and   writing the data to the one or more states in the cache based on the assigned priority level.   
     
     
         2 . The method of  claim 1 , wherein the one or more states includes a first state, a second state, and a third state, and data assigned a first priority level is stored in the first state, data assigned a second priority level is stored in the second state, and data assigned a third priority level is stored in the third state. 
     
     
         3 . The method of  claim 2 , wherein the first priority level is critical, the second priority level is high, and the third priority level is normal. 
     
     
         4 . The method of  claim 2 , wherein the data assigned the first priority level is evicted from the first state only after both the data assigned the second priority level and the data assigned the third priority level is evicted. 
     
     
         5 . The method of  claim 4 , wherein a deduplication table is assigned the first priority level to ensure that the deduplication table is accessible from the cache. 
     
     
         6 . The method of  claim 2 , wherein data assigned the second priority level is evicted from the second state after data assigned the first priority level is evicted from the first state. 
     
     
         7 . The method of  claim 2 , wherein the cache replacement policy comprises maintaining a first list in the second state and a second list in the third state, the first list being a most recently used list having a most recently used position and a least recently used position and the second list being a most frequently used list having a most frequently used position and a least frequently used position, data in the least recently used position being evicted when there is no available space in the cache and data is added to the most recently used position and data in the least frequently used position being evicted when there is no available space in the cache and data is added to the most frequently used position. 
     
     
         8 . The method of  claim 2 , wherein a size of the first state continues to grow without evicting data assigned the first priority level until a maximum size of the first state is reached. 
     
     
         9 . The method of  claim 8 , wherein the maximum size is greater than an upper limit of cache allocated to a deduplication table and less than a maximum capacity of the cache. 
     
     
         10 . One or more tangible computer-readable storage media storing computer-executable instructions for performing a computer process on a computing system, the computer process comprising:
 receiving a write request to write data to a cache having one or more states;   assigning a priority level to the data, the priority level and a cache replacement policy dictating an order in which the data is evicted from the cache; and   writing the data to the one or more states in the cache based on the assigned priority level.   
     
     
         11 . The one or more tangible computer-readable storage media of  claim 10 , wherein the one or more states includes a first state, a second state, and a third state, and data assigned a first priority level is stored in the first state, data assigned a second priority level is stored in the second state, and data assigned a third priority level is stored in the third state. 
     
     
         12 . The one or more tangible computer-readable storage media of  claim 11 , wherein the first priority level is critical, the second priority level is high, and the third priority level is normal. 
     
     
         13 . The one or more tangible computer-readable storage media of  claim 11 , wherein the data assigned the first priority level is evicted from the first state only after both the data assigned the second priority level and the data assigned the third priority level is evicted. 
     
     
         14 . The one or more tangible computer-readable storage media of  claim 13 , wherein a deduplication table is assigned the first priority level to ensure that the deduplication table is accessible from the cache. 
     
     
         15 . A system comprising:
 a cache having one or more states storing data based on a priority level assigned to the data, the priority level and a cache replacement policy dictating an order in which the data is evicted from the cache.   
     
     
         16 . The system of  claim 15 , wherein the one or more states includes a first state, a second state, and a third state, and data assigned a first priority level is stored in the first state, data assigned a second priority level is stored in the second state, and data assigned a third priority level is stored in the third state. 
     
     
         17 . The system of  claim 16 , wherein the first priority level is critical, the second priority level is high, and the third priority level is normal. 
     
     
         18 . The system of  claim 16 , wherein the data assigned the first priority level is evicted from the first state only after both the data assigned the second priority level and the data assigned the third priority level is evicted. 
     
     
         19 . The system of  claim 16 , wherein a size of the first state continues to grow without evicting data assigned the first priority level until a maximum size of the first state is reached. 
     
     
         20 . The system of  claim 19 , wherein the maximum size is greater than an upper limit of cache allocated to a deduplication table and less than a maximum capacity of the cache.