Multi-layer multi-hit caching for long tail content

摘要

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.