Item-wise simulation in a block cache where data eviction places data into comparable score in comparable section in the block cache

• US 10,185,666 B2
• Filed: 12/15/2015
• Issued: 01/22/2019
• Est. Priority Date: 12/15/2015
• Status: Active Grant

• Current Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Original Assignee: Meta Platforms, Inc. (f/k/a Facebook, Inc.)
• Inventors: van Greunen, Jana, Zhou, Huapeng, Tang, Linpeng
• Primary Examiner(s): Lo, Ann J
• Assistant Examiner(s): Yew, Chie
• Application Number:
  US14/970,034
• Publication Number:
  US 20170168958A1
• Time in Patent Office: 1,134 Days
• CPC Class Codes: G06F 12/0873 Mapping of cache memory to specific storage devices or parts thereof
• CPC Class Codes: G06F 12/0875 with dedicated cache, e.g. instruction or stack
• CPC Class Codes: G06F 12/12 Replacement control
• CPC Class Codes: G06F 12/121 using replacement algorithms
• CPC Class Codes: G06F 12/127 using additional replacement algorithms
• 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 emulate item-wise storage and eviction in the block cache by maintaining, in the primary memory, sampling data items from the block cache. The sampled items can enable the cache appliance to represent a spectrum of retention priorities. When storing a pending data item into the block cache, a comparison of the pending data item with the sampled items can enable the cache appliance to identify where to insert a block containing the pending data item. When evicting a block from the block cache, a comparison of a data item in the block with at least one of the sampled items can enable the cache appliance to determine whether to recycle/retain the data item.

Claims

1. A computer-implemented method, comprising:

emulating item-wise caching for a block cache implemented in a secondary data storage of a caching system by;

selecting, as sample items, a subset of data items included in the block cache; and

maintaining the sample items in an ordered queue on a primary data storage of the caching system, wherein;

the sample items are ordered in the ordered queue based on a caching algorithm that computes a metric score for each of the sample items and determines an order for the sample items based on a comparison of the metric scores; and

each metric score is indicative of a retention priority;

identifying, from an item-wise cache implemented in the primary data storage, a pending data item for storage into the block cache;

determining a metric score, indicative of retention priority, of the pending data item;

comparing the metric score of the pending data item with the metric scores of the sample items in the ordered queue and identifying a comparable sample item from the sample items with a metric score that is closest to the metric score of the pending data item;

adding the pending data item into a block buffer that is stored in the primary data storage, wherein;

the block buffer corresponds to a memory section in the block cache implemented in the secondary data storage; and

the memory section in the block cache is associated with the comparable sample item; and

when adding the pending data item into the block buffer either results in the block buffer being full or a threshold percentage of being full, storing the block buffer, from the primary data storage, into the block cache, implemented in the secondary data storage, at the memory section that corresponds to the block buffer.

2. The computer-implemented method of claim 1, wherein the item-wise cache serves as a staging area for the block cache.

3. The computer-implemented method of claim 2, wherein identifying the pending data item for storage into the block cache comprises:

determining that the item-wise cache is full or a threshold percentage of being full; and

in response to determining that the item-wise cache is full or a threshold percentage of being full, identifying the pending data item as an eviction candidate from the item-wise cache.

4. The computer-implemented method of claim 1, wherein:

the block cache comprises a plurality of memory sections; and

each of the plurality of memory sections corresponds to (1) a priority range, and (2) at least one sample item, from the subset of data items selected as the sample items, that represents the priority range.

5. The computer-implemented method of claim 4, wherein each of the plurality of memory sections in the block cache includes an insertion pointer that indicates where to place, in that particular memory section of the plurality of the memory sections, a new or replacement block when the new or replacement block is to be written into the block cache.

6. A caching system, comprising:

a secondary data storage configured to implement a block cache that stores data in units of constant-sized block;

a primary data storage configured to implement an item-wise cache; and

a processor configured to;

emulate item-wise caching for a block cache implemented in a secondary data storage of a caching system by;

selecting, as sample items, a subset of data items included in the block cache; and

maintaining the sample items in an ordered queue on the primary data storage, wherein;

the sample items are ordered in the ordered queue based on a caching algorithm that computes a metric score for each of the sample items and determines an order for the sample items based on a comparison of the metric scores; and

each metric score is indicative of a retention priority;

identify, from the item-wise cache, a pending data item for storage into the block cache;

determine a metric score, indicative of retention priority, of the pending data item;

compare the metric score of the pending data item with the metric scores of the sample items to identify a comparable sample item from the sample items with a metric score that is closest to the metric score of the pending data item;

add the pending data item into a block buffer that is stored in the primary data storage, wherein;

the block buffer corresponds to a memory section in the block cache implemented in the secondary data storage; and

the memory section in the block cache is associated with the comparable sample item; and

when adding the pending data item into the block buffer either results in the block buffer being full or a threshold percentage of being full, store the block buffer, from the primary data storage, into the block cache, implemented in the secondary data storage, at the memory section that corresponds to the block buffer.

7. The caching system claim 6, wherein the caching algorithm comprises at least one of a multiple-queue caching algorithm, a segmented least recently used (SLRU) caching algorithm, a 2-way set associative least recently used caching (2LRU) algorithm, an adaptive replacement cache (ARC) algorithm, or a Greedy Dual Frequency Size (GDFS) algorithm.

8. The caching system of claim 6, wherein:

the primary data storage represents a random access memory (RAM);

the secondary data storage represents a solid state drive; and

the block cache in the solid state drive is adapted to be accessible only via block identifiers.

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

emulating item-wise caching for a block cache implemented in a secondary data storage of a caching system by;

selecting, as sample items, a subset of data items included in the block cache; and

maintaining the sample items in an ordered queue on a primary data storage of the caching system, wherein;

the sample items are ordered in the ordered queue based on a caching algorithm that computes a metric score for each of the sample items and determines an order for the sample items based on a comparison of the metric scores; and

each metric score is indicative of a retention priority;

identifying, from an item-wise cache implemented in the primary data storage, a pending data item for storage into the block cache;

determining a metric score, indicative of retention priority, of the pending data item;

comparing the metric score of the pending data item with the metric scores of the sample items in the ordered queue and identifying a comparable sample item from the sample items with a metric score that is closest to the metric score of the pending data item;

adding the pending data item into a block buffer that is stored in the primary data storage, wherein;

the block buffer corresponds to a memory section in the block cache implemented in the secondary data storage; and

the memory section in the block cache is associated with the comparable sample item; and

when adding the pending data item into the block buffer either results in the block buffer being full or a threshold percentage of being full, storing the block buffer, from the primary data storage, into the block cache, implemented in the secondary data storage, at the memory section that corresponds to the block buffer.

10. The non-transitory computer-readable data storage medium of claim 9, wherein the item-wise cache serves as a staging area for the block cache.

11. The non-transitory computer-readable data storage medium of claim 10, wherein identifying the pending data item for storage into the block cache comprises:

determining that the item-wise cache is full or a threshold percentage of being full; and

in response to determining that the item-wise cache is full or a threshold percentage of being full, identifying the pending data item as an eviction candidate from the item-wise cache.

12. The non-transitory computer-readable data storage medium of claim 9, wherein:

the block cache comprises a plurality of memory sections;

each of the plurality of memory sections corresponds to (1) a priority range, and (2) at least one sample item, from the subset of data items selected as the sample items, that represents the priority range.

13. The non-transitory computer-readable data storage medium of claim 12, wherein each of the plurality of memory sections in the block cache includes an insertion pointer that indicates where to place, in that particular memory section of the plurality of memory sections, a new or replacement block when the new or replacement block is to be written into the block cache.