BLOCK CACHE EVICTION

• US 20170168944A1
• Filed: 12/15/2015
• Published: 06/15/2017
• Est. Priority Date: 12/15/2015
• Status: Abandoned Application

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: Zhou, Huapeng, Tang, Linpeng, van Greunen, Jana
• Application Number:
  US14/970,041
• Publication Number:
  US 20170168944A1
• Time in Patent Office: Days
• CPC Class Codes: G06F 12/12 Replacement control
• CPC Class Codes: G06F 12/122 of the least frequently used [LFU] type, e.g. with individual count value
• CPC Class Codes: G06F 12/128 adapted to multidimensional cache systems, e.g. set-associative, multicache, multiset or multilevel
• CPC Class Codes: G06F 2212/1021 Hit rate improvement

Abstract

Several embodiments include a method of operating a cache appliance comprising a primary memory implementing an item-wise cache and a secondary memory implementing a block cache. The cache appliance can track at least a block-specific access statistic associated a target block in the block cache. The block-specific access statistic can be stored in the primary memory. The cache appliance can detect an eviction condition that triggers the caching system to evict at least one block from the block cache; and selecting an eviction candidate block to evict by comparing the block-specific access statistic of the target block against one or more block-specific access statistics of one or more other blocks.

Claims

1. A computer-implemented method, comprising:

storing a data item in a target block of a block cache implemented in a secondary data storage of a caching system;

tracking a block-specific access statistic associated the target block in a primary data storage of the caching system;

detecting an eviction condition that triggers the caching system to evict at least one block from the block cache; and

selecting the target block as an eviction candidate block to evict by comparing the block-specific access statistic of the eviction candidate block against one or more block-specific access statistics of one or more other blocks.

2. The computer-implemented method of claim 1, wherein selecting the target block as the eviction candidate block to evict occurs without accessing data items within the eviction candidate block.

3. The computer-implemented method of claim 1, further comprising maintaining an item-wise cache in the primary data storage as a staging area for the block cache.

4. The computer-implemented method of claim 1, further comprising sorting blocks in the block cache based on access statistics of the blocks to generate an ordered queue of blocks to evict.

5. The computer-implemented method of claim 4, wherein sorting the blocks includes sorting based on metadata associated with the blocks.

6. The computer-implemented method of claim 5, wherein the metadata associated with the blocks includes number of data items in each of the blocks.

7. The computer-implemented method of claim 1, further comprising:

implementing a first caching algorithm to determine which block to evict from the block cache; and

implementing a second caching algorithm to determine which data item, in the block to evict, to retain.

8. The computer-implemented method of claim 7, further comprising:

retaining the data item by copying the data item into a block buffer; and

scheduling to save content of the block buffer into the block cache when the block buffer is full or substantially full.

9. The computer-implemented method of claim 1, wherein selecting the target block as the eviction candidate block includes selecting the target block based on a segmented least recently used (SLRU) caching algorithm on most popular item in each block.

10. The computer-implemented method of claim 1, wherein selecting the target block as the eviction candidate block includes selecting the target block with lowest number of accesses as the eviction candidate block.

11. The computer-implemented method of claim 1, further comprising:

maintaining, in a primary data storage of the caching system, an item index of top-N data items in each block of the block cache; and

wherein selecting the target block includes selecting the target block as the eviction candidate block based on access statistics of the top-N data items.

12. The computer-implemented method of claim 11, wherein maintaining the item index of the top-N data items includes tracking access statistics of a subset of the data items in the block cache that are most frequently accessed.

13. The computer-implemented method of claim 1, wherein the block-specific access statistic includes number of access, number of access within a time window, most recent access time, an aggregate of recent access times, or any combination thereof.

14. The computer-implemented method of claim 1, wherein the block-specific access statistic includes an average of a fixed number of recent access times.

15. The computer-implemented method of claim 14, further comprising tracking the recent access times, wherein when the target block is accessed for less than the fixed number of times, filling in a pre-determined number in place of missing access times.

16. A computer-readable data storage medium storing computer-executable instructions that, when executed, cause a computer system to perform a computer-implemented method, the instructions comprising:

instructions for tracking, in a primary data storage of a caching system, block-specific statistics for blocks in a block cache implemented in a secondary data storage of the caching system;

instructions for maintaining a block eviction queue that is ordered based on the block-specific statistics;

instructions for selecting an eviction block candidate from the block eviction queue; and

instructions for discarding the eviction block candidate from the block cache.

17. The computer-readable data storage medium of claim 16, wherein discarding the eviction block candidate includes marking the eviction candidate block as being available for replacement.

18. The computer-readable data storage medium of claim 16, wherein discarding the eviction candidate block includes writing over content of the eviction candidate block.

19. The computer-readable data storage medium of claim 16 wherein the instructions further comprises instructions for instructions for detecting that the block cache is full or substantially full;

and wherein selecting the eviction block candidate is responsive to detecting that the block cache is full or substantially full.

20. A cache appliance, comprising:

a solid state storage drive configured to implement a block cache;

a random access memory (RAM) configured to implement an item-wise cache and an item index that maps one or more data items to one or more blocks in the block cache;

a processor configured to;

track, in a primary data storage of a caching system, block-specific statistics for blocks in a block cache implemented in a secondary data storage of the caching system;

maintain a block eviction queue that is ordered based on the block-specific statistics;

select an eviction block candidate from the block eviction queue; and

discard the eviction block candidate from the block cache.