BLOCK CACHE STAGING IN CONTENT DELIVERY NETWORK CACHING SYSTEM

• US 20170168956A1
• 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: van Greunen, Jana, Zhou, Huapeng, Tang, Linpeng
• Application Number:
  US14/970,027
• Publication Number:
  US 20170168956A1
• Time in Patent Office: Days
• CPC Class Codes: G06F 12/0888 using selective caching, e.g. bypass
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching

Abstract

Several embodiments include a method of operating a cache appliance comprising a primary memory and a secondary memory. The primary memory can implement an item-wise cache and the secondary memory can implement a block cache. The cache appliance can record an access history of a data item in the item-wise cache. The cache appliance can determine, by evaluating the access history of the data item, whether to store the data item in the block cache.

Claims

1. A computer-implemented method, comprising:

recording an access history of a data item in a least recently used (LRU) cache implemented in a primary memory of a cache appliance;

computing a cache priority of the data item in the LRU cache by evaluating the access history of the data item;

determining, based on the computed cache priority, whether to store the data item in a block cache implemented by a secondary memory of the cache appliance;

storing the data item in one or more blocks in the block cache; and

storing, in an item index, an association that maps a data item identifier associated with the data item to the one or more blocks in the block cache.

2. The computer-implemented method of claim 1, wherein computing the cache priority of the data item based on an access count, an access frequency within a time window, a requestor diversity measure, size of the data item, item type of the data item, or any combination thereof.

3. The computer-implemented method of claim 1, wherein the data item is amongst one or more other data items in the LRU cache;

and wherein computing the cache priority includes computing the cache priority of the data item by evaluating the access history of the data item against at least an access history of another data item.

4. The computer-implemented method of claim 1, further comprising scheduling a minimum evaluation period for the data item to be in the LRU cache prior to storing the data item in the block cache.

5. The computer-implemented method of claim 1, wherein said determining whether to store the data item occurs when the LRU cache is full or substantially full.

6. The computer-implemented method of claim 1, wherein said determining whether to store the data item occurs when the data item is a least recently requested data item in the LRU cache.

7. A cache appliance, comprising:

a random access memory (RAM) configured to implement an item-wise cache;

a secondary storage drive configured to implement a block cache;

wherein the item-wise cache is configured to serve as a staging area for one or more data items to be stored in the block cache and to maintain an item index to identify one or more blocks of the block cache that store the data items;

a processor configured to;

update an access history of the data item in RAM, responsive to one or more repeated requests to access the data item while the data item is in the item-wise cache; and

determine whether to write the data item into the block cache based on the access history of the data item.

8. The cache appliance of claim 7, wherein the processor is configured to fetch the data item from an external host server when the data item is requested prior to either the item-wise cache or the block cache having stored the data item.

9. The cache appliance of claim 7, wherein the processor is configured to receive a data item request for the data item and, responsive to the data item request, to increment an access count associated with the data item, wherein the access history includes the access count.

10. The cache appliance of claim 7, wherein the item-wise cache is implemented as a least recently used (LRU) cache.

11. The cache appliance of claim 7, wherein the secondary storage drive is a solid state drive.

12. The cache appliance of claim 7, wherein the processor is configured to store the item index only in the RAM without backup to the secondary storage drive.

13. The cache appliance of claim 7, wherein the processor is configured to store the item-wise cache is a shared memory space of the RAM, wherein when a cache service application restarts, the restarted cache service application is capable of re-using the item-wise cache.

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

instructions for receiving a data item request for a data item at a cache appliance, wherein the cache appliance implements an item-wise cache in a random access memory (RAM) and a block cache in a secondary memory, wherein the item-wise cache is configured as a staging area for the block cache;

instructions for responding to the data item request by locating the data item in the item-wise cache;

instructions for responsive to the data item request, updating an access history of the data item in the RAM by incrementing an access count associated with the data item; and

instructions for determining whether to write the data item into the block cache of the cache appliance based on the access history of the data item.

15. The computer readable data storage memory of claim 14, wherein the cache appliance is part of a content delivery network that provides temporary data storage, for one or more frequently requested data items, in one or more edge point of presences in a wide area network.

16. The computer readable data storage memory of claim 14, wherein the instructions further comprises instructions for fetching the data item from a host server to store in the item-wise cache prior to receiving the data item request.

17. The computer readable data storage memory of claim 16, wherein said fetching is responsive to receiving a previous data item request for the data item when the data item yet is not stored in either the item-wise cache or the block cache.

18. The computer readable data storage memory of claim 14, wherein said determining whether to write the data item occurs when the RAM is beyond a threshold percentage of being full.

19. The computer readable data storage memory of claim 14, wherein the instructions further comprises:

instructions for, responsive to determining to write the data item into the block cache, storing the data item in a block buffer configured to be size of a single block in the block cache; and

instructions for, when the block buffer is full or substantially full, writing content of the block buffer into the block cache.

20. The computer-implemented method of claim 19, wherein the instructions further comprises:

instructions for maintaining multiple block buffers; and

instructions for, when the block buffers are full or substantially full, sequentially writing content of the block buffers into the block cache.