Multi-layer multi-hit caching for long tail content
View Patent ↗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 arrays 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.
1. A computer-implemented method with which a caching server performs N hit caching of content, wherein N is an integer value greater than one, the computer-implemented method comprising:
configuring the caching server with a first array and a second array, each array comprising a plurality of indices;
for each of a plurality of requests requesting content from the caching server, identifying from the plurality of indices, a different set of indices that uniquely identifies each unique item of content;
incrementing indices of the first array that correspond to different sets of indices identifying content requested from the caching server during a first interval;
incrementing indices of the second array that correspond to different sets of indices identifying content requested from the caching server during a second interval immediately following the first interval; and
obtaining at least a first count from a particular set of indices of the first array and at least a second count from the particular set of indices of the second array in response to a request for particular content, wherein the particular content is uniquely identified by the particular set of indices, and wherein the first count and the second count are different integer values greater than zero;
caching the particular content in a non-transitory storage medium of the caching server in response to a sum of the first count and the second count being at least N; and
serving the particular content to the user.
2. The computer-implemented method of claim 1 further comprising retrieving to the caching server, the particular content from an origin server and serving the particular content from the caching server to a requesting end user in response to the sum of the first count and the second count equaling N.
3. The computer-implemented method of claim 1 further comprising serving the particular content without caching the particular content at the caching server in response to the sum of the first count and the second count equaling a total value less than N.
4. The computer-implemented method of claim 1 , wherein the first array is a first counting bloom filter and the second array is a second counting bloom filter and wherein each index of the plurality of indices for each array comprises multiple bits for counting up to at least N−1.
5. The computer-implemented method of claim 1 further comprising overwriting the first array by copying values from the plurality of indices of the second array to the plurality of indices of the first array at expiration of the second interval.
6. The computer-implemented method of claim 5 further comprising resetting values for the plurality of indices of the second array at the expiration of the second interval.
7. The computer-implemented method of claim 1 further comprising resetting values of the second array and preserving values of the first array at expiration of the second interval.
8. The computer-implemented method of claim 7 further comprising switching roles of the first array and second array by using the second array to track requests received during a third interval immediately following the second interval.
9. A caching server comprising:
memory configured with (i) a first array tracking request counts for content requested during a current interval having a designated time span and (ii) a second array tracking request counts for content requested during a previous interval immediately preceding the current interval;
wherein the memory is configured to, for each of a plurality of requests requesting content from the caching server, identify from a plurality of indices in the first and second arrays, a different set of indices that uniquely identifies each unique item of content;
a first non-transitory storage medium caching content requested at least N times based on a sum total of request counts tracked to the first array during the current interval and request counts tracked to the second array during the previous interval; and
a second non-transitory storage medium caching content requested at least M times based on a sum total of request counts tracked to the first array during the current interval and request counts tracked to the second array during the previous interval, wherein N is an integer value that is greater than M and the second non-transitory storage medium is slower than the first non-transitory storage medium.
10. The caching server of claim 9 , wherein the first array is a first counting bloom filter and the second array is a second counting bloom filter, each counting bloom filter comprising at least a plurality of indices with different sets of the plurality of indices uniquely identifying different content.
11. The caching server of claim 9 , wherein the first array comprises a first plurality of multi-bit indices, wherein the first array tracks content request counts by incrementing different sets of the first plurality of multi-bit indices corresponding to different sets of indices that uniquely identify different instances of content that are requested during the current interval, wherein the second array comprises a second plurality of multi-bit indices, and wherein the second array tracks content request counts by incrementing different sets of the second plurality of multi-bit indices corresponding to different sets of indices that uniquely identify different instances of content that are requested during the previous interval.
12. The caching server of claim 11 further comprising a processor (i) determining a request count for particular content during the current interval by identifying a minimum value for each index of the first plurality of indices that corresponds to an index of the particular set of indices uniquely identifying the particular content and (ii) determining a request count for the particular content during the previous interval by identifying a minimum value for each index of the second plurality of indices that corresponds to an index of the particular set of indices uniquely identifying the particular content.
13. The caching server of claim 11 further comprising a processor determining M requests for particular content when a minimum value for a set of indices from the first plurality of indices that correspond to a particular set of indices uniquely identifying the particular content summed with a minimum value for a set of indices from the second plurality of indices that correspond to the particular set of indices uniquely identifying the particular content equals at least M−1.
14. The caching server of claim 9 further comprising a networked interface forwarding content to a requesting end user in response to a request from the end user, wherein the networked interface (i) forwards the content from the first non-transitory storage medium when the content was previously requested N times during the current interval and the previous interval, (ii) forwards the content from the second non-transitory storage medium when the content was previously requested M times during the current interval and the previous interval, (iii) forwards the content from an origin server when the content was previously requested less than M times.
15. The caching server of claim 9 further comprising a routine overwriting request counts of the second array with the request counts of the first array and erasing the request counts of the first array when restarting the current interval at expiration of the designated time span.
16. The caching server of claim 9 further comprising a mapping table identifying the first non-transitory storage medium as caching content that is requested more than N times and identifying the second non-transitory storage medium as caching content that is requested between M and N−1 times.