Optimizing multi-hit caching for long tail content
First Claim
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.
6 Assignments
0 Petitions
Accused Products
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.
-
Citations
14 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
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. - View Dependent Claims (10, 11, 12, 13, 14)
-
Specification