MEMORY-EFFICIENT CACHING METHODS AND SYSTEMS

• US 20130173853A1
• Filed: 09/26/2012
• Published: 07/04/2013
• Est. Priority Date: 09/26/2011
• Status: Abandoned Application

• Current Assignee: NEC Laboratories America Inc (NEC Corporation)
• Original Assignee: NEC Laboratories America Inc (NEC Corporation)
• Inventors: Ungureanu, Cristian, Rago, Stephen, Aranya, Akshat, Debnath, Biplob Kumar
• Application Number:
  US13/627,489
• Publication Number:
  US 20130173853A1
• Time in Patent Office: Days
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0871 Allocation or management of cache space
• CPC Class Codes: G06F 12/0891 using clearing, invalidating or resetting means
• CPC Class Codes: G06F 12/122 of the least frequently used [LFU] type, e.g. with individual count value
• CPC Class Codes: G06F 12/124 being minimized, e.g. non MRU
• CPC Class Codes: G06F 2212/222 Non-volatile memory

Abstract

Caching systems and methods for managing a cache are disclosed. One method includes determining whether a cache eviction condition is satisfied. In response to determining that the cache eviction condition is satisfied, at least one Bloom filter registering keys denoting objects in the cache is referenced to identify a particular object in the cache to evict. Further, the identified object is evicted from the cache. In accordance with an alternative scheme, a bit array is employed to store recency information in a memory element that is configured to store metadata for data objects stored in a separate cache memory element. This separate cache memory element stores keys denoting the data objects in the cache and further includes bit offset information for each of the keys denoting different slots in the bit array to enable access to the recency information.

Claims

1. A method for managing a cache comprising:

determining whether a cache eviction condition is satisfied;

in response to determining that the cache eviction condition is satisfied, referencing at least one Bloom filter registering keys denoting objects in the cache to identify a particular object in the cache to evict; and

evicting the particular object from the cache.

2. The method of claim 1, further comprising:

in response to determining that the cache eviction condition is satisfied, iteratively modifying the at least one Bloom filter by deregistering at least one of the keys until determining that a given key for one of the objects in the cache is not registered in the at least one Bloom filter.

3. The method of claim 2, wherein the identifying comprises identifying the object denoted by the given key as the particular object in the cache to evict.

4. The method of claim 1, wherein the at least one Bloom filter includes a current Bloom filter and a previous Bloom filter.

5. The method of claim 4, wherein the method further comprises:

modifying the previous Bloom filter and the current Bloom filter by setting values of the previous Bloom filter to values in the current Bloom filter and emptying the current Bloom filter.

6. The method of claim 5, wherein the modifying is performed in response to determining that a threshold has been reached during said referencing.

7. The method of claim 1, further comprising:

registering a key denoting a requested object in the at least one Bloom filter in response to determining that the requested object is in the cache.

8. A caching system comprising:

a main storage element configured to store data;

a cache configured to store data objects and metadata for the data objects that includes at least one Bloom filter; and

a processor configured to reference the at least one Bloom filter registering keys denoting the data objects in the cache to identify which of the data objects in the cache to evict in response to determining that a cache eviction condition is satisfied.

9. The system of claim 8, wherein the metadata is stored on at least one first memory element that is separate from at least one second memory element on which said data objects are stored.

10. The system of claim 9, wherein the at least one first memory element comprises random access memory, wherein the at least one second memory element comprises flash memory, and wherein the main storage element comprises at least one storage disk.

11. The system of claim 8, wherein the processor is configured to, in response to determining that the cache eviction condition is satisfied, iteratively modify the at least one Bloom filter by deregistering at least one of the keys until determining that a given key for one of the objects in the cache is not registered in the at least one Bloom filter.

12. The system of claim 11, wherein the processor is further configured to evict the object denoted by the given key.

13. The system of claim 8, wherein the at least one Bloom filter includes a current Bloom filter and a previous Bloom filter and wherein the processor is further configured to set values of the previous Bloom filter to values in the current Bloom filter and to empty the current Bloom filter.

14. The system of claim 13, wherein the processor is further configured to set the values of the previous Bloom filter to the values in the current Bloom filter and to empty the current Bloom filter in response to determining that a threshold has been reached while referencing the previous and current Bloom filters to identify which of the data objects in the cache to evict.

15. A caching system comprising:

a main storage element configured to store data;

a cache including at least one first element configured to store metadata for data objects that includes a bit array and at least one second element configured to store the data objects, wherein the at least one second element includes keys denoting the data objects in the cache and includes bit offset information for each of the keys denoting different slots in the bit array; and

a processor configured to identify, in response to determining that a cache eviction condition is satisfied, a particular data object in the cache to evict by deter Wining whether the slot in the bit array corresponding to the particular data object indicates that the particular data object was recently used.

16. The system of claim 15, wherein the at least one first element comprises random access memory, wherein the at least one second element comprises flash memory, and wherein the main storage element comprises at least one storage disk.

17. The system of claim 15, wherein each of the slots of the bit array denote one of a set state, reset state or free state.

18. The system of claim 17, wherein the processor is further configured to evict the particular data object from the cache in response to determining that the slot in the bit array corresponding to the particular data object is in a reset state and wherein the processor is further configured to set the slot in the bit array corresponding to the particular data object to a free state.

19. The system of claim 17, wherein the processor is further configured to receive a request for a given data object and to

set the slot corresponding to the given data object to a set state if the given data object is in the cache, and

add the given data object to the cache and associate any free state slot in the bit array with the given data object in bit offset information for the given data object if the given data object is not in the cache.

20. The system of claim 17, wherein the processor is further configured to, in response to determining that the cache eviction condition is satisfied, reset at least one of the slots of the hit array from a set state to a reset state prior to identifying the particular data object.