Optimizing multi-hit caching for long tail content

• US 8,639,780 B2
• Filed: 12/19/2012
• Issued: 01/28/2014
• Est. Priority Date: 01/10/2012
• Status: Active Grant

• Current Assignee: Edgio Incorporated
• Original Assignee: EdgeCast Networks (Verizon Communications Inc.)
• Inventors: Khakpour, Amir, Peters, Robert J.
• Primary Examiner(s): Avellino, Joseph E
• Assistant Examiner(s): CONAWAY, JAMES E
• Application Number:
  US13/720,859
• Publication Number:
  US 20130179529A1
• Time in Patent Office: 405 Days
• Field of Search: 709/203, 709/209, 709/213, 711/1, 711/100
• US Class Current: 709/219
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching

Abstract

Some embodiments provide an optimized multi-hit caching technique that minimizes the performance impact associated with caching of long-tail content while retaining much of the efficiency and minimal overhead associated with first hit caching in determining when to cache content. The optimized multi-hit caching utilizes a modified bloom filter implementation that performs flushing and state rolling to delete indices representing stale content from a bit array used to track hit counts without affecting identification of other content that may be represented with indices overlapping with those representing the stale content. Specifically, a copy of the bit array is stored prior to flushing the bit array so as to avoid losing track of previously requested and cached content when flushing the bit arras and the flushing is performed to remove the bit indices representing stale content from the bit array and to minimize the possibility of a false positive.

Claims

1. A computer-implemented method performed by a caching server for N hit caching of content by that caching server, wherein N is an integer value greater than one, the computer-implemented method comprising:

configuring the caching server with a first request counter and a second request counter for tracking request counts for a plurality of content received during different intervals to different sets of indices of the first and second request counters, wherein each set of the different sets of indices uniquely identifies a request count for different content of the plurality of content;

using the first request counter of the caching server to increment a request count for each content of a plurality of content that is requested during a first interval, wherein the first request counter tracks M requests received for a specific item of content of the plurality of content during the first interval to a particular set of indices, wherein M is an integer value that is less than N;

resetting the first request counter at the end of the first interval, said resetting comprising (i) copying the request count tracked to the particular set of indices of the first request counter to the second request counter and (ii) clearing request counts of the first request counter;

receiving at the caching server, a new request for the specific item of content during a second interval that immediately follows the first interval;

incrementing the particular set of indices of the first request counter to track the new request for the specific item of content that is received during the second interval;

determining a cumulative request count for the specific item of content based on the M requests from the first interval that were copied to the particular set of indices of the second request counter and at least the new request that is tracked to the particular set of indices of the first request counter during the second interval;

passing the specific item of content from an origin and caching it at the caching server when the cumulative request count for the specific item of content identifies N requests; and

passing the specific item of content from an origin without caching it at the caching server when the cumulative request count for the specific item of content identifies fewer than N requests.

2. The computer-implemented method of claim 1, wherein resetting the first request counter at the end of the first interval zeros request counts for any content that was requested in an interval immediately prior to the first interval but that was not requested during the first interval.

3. The computer-implemented method of claim 1, wherein the specific item of content is first content of the plurality of content, the particular set of indices is a first set of indices, and wherein the first request counter tracks X requests received for second content of the plurality of content during the first interval to a second set of indices, wherein X is an integer value.

4. The computer-implemented method of claim 3 further comprising resetting the first request counter at the end of the second interval by (i) copying request counts tracked to the first and second sets of indices of the first request counter to the second request counter and (ii) clearing the first request counter.

5. The computer-implemented method of claim 4 further comprising receiving a new request for the second content during a third interval that immediately follows the second interval.

6. The computer-implemented method of claim 5 further comprising incrementing the second set of indices of the first request counter to specify a first request for the second content based on zero requests tracked to the first and second request counters as a result of (i) not receiving a request for the second content during the second interval and (ii) resetting the first request counter at the end of the second interval.

7. The computer-implemented method of claim 1 further comprising querying cache of the caching server to determine whether the specific item of content is cached at the caching server.

8. The computer-implemented method of claim 7 further comprising passing the specific item of content from cache when the cumulative request count for the specific item of content identifies N+1 requests.

9. A computer-implemented method providing second hit content caching at a caching server comprising a processor and non-transitory computer-readable storage, the computer-implemented method comprising:

tracking by operation of the processor, requests for a first set of content received during a first interval as different sets of indices entered to a first array on the non-transitory computer-readable storage, wherein each set of indices of the different sets of indices uniquely identifies different content of the first set of content;

copying by operation of the processor, the different sets of indices entered to the first array to a second array on the non-transitory computer-readable storage at the end of the first interval;

clearing the first array at the end of the first interval by operation of the processor;

tracking by operation of the processor, requests for a second set of content received during a second interval that commences at the end of the first interval by entering a different set of indices uniquely identifying the second set of content to the first array;

receiving at the caching server, a request for particular content during the second interval;

serving the particular content from the non-transitory computer-readable storage of the caching server when the particular content is stored to the non-transitory computer-readable storage; and

serving the particular content from an origin server and caching the particular content to the non-transitory computer-readable storage when each index of the set of indices uniquely identifying the particular content is entered in at least one of the first array and the second array.

10. The computer-implemented method of claim 9 further comprising serving the particular content from an origin server without caching it at the caching server when at least one index of the set of indices uniquely identifying the particular content is not entered in the first array and the second array.

11. The computer-implemented method of claim 9 further comprising copying the sets of indices entered to the first array during the second interval to the second array and clearing the first array at the end of the second interval.

12. The computer-implemented method of claim 11 further comprising tracking requests for a third set of content received during a third interval as different sets of indices entered to the first array, wherein the third interval commences at the end of the second interval.

13. The computer-implemented method of claim 9 further comprising configuring the caching server with at least one hashing function that generates a set of indices uniquely identifying content based on a URL used to request that content.

14. The computer-implemented method of claim 9, wherein each set of indices uniquely identifying content comprises a fixed length array of indices with a specific combination of the indices to distinctly identify that content from other content having different combinations of indices set for the fixed length array.