Optimizing 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 method for performing optimized N-hit caching, wherein N is an integer value greater than 1, said method comprising:
tracking content requests for a plurality of content received during a first sub-interval of a recurring interval by entering a plurality of indices to a first bit array, wherein different sets of indices of the plurality of indices represent requests for different content of the plurality of content;
copying entries from the first bit array to a second bit array at the expiration of the first sub-interval to retain a copy of the content requests that were received during said first sub-interval after expiration of the first sub-interval;
flushing said first bit array after copying the entries to the second bit array;
tracking content requests received during a second sub-interval of the recurring interval to the first array whose entries were cleared at the expiration of the first sub-interval;
hashing a request for particular content received during the second sub-interval to produce a specific set of indices;
determining whether the particular content was previously requested during the first sub-interval by comparing the specific set of indices to entries of the second bit array;
determining whether the particular content was previously requested during the second sub-interval by comparing the specific set of indices to entries of the first bit array;
serving the particular content to an end user submitting the request for the particular content without caching the particular content when at least one index of the set of indices is not entered in the first bit array and the second bit array;
caching the particular content when said each index of the set of indices is entered in at least one of the first bit array and the second bit array.
2. The method of claim 1 , wherein each of said first and second bit arrays comprises a fixed sized array comprising a plurality of single-bit indices, wherein a request for content from the plurality of content is recorded in said first bit array by setting a set of the plurality of indices in the first bit array, and wherein the set of the plurality of indices uniquely identifies said content from other content of the plurality of content.
3. The method of claim 1 , wherein tracking the content requests comprises tracking content requests by encoding each content of the of content as a set of indices and storing said set of indices to the first bit array.
4. A content delivery network (CDN) comprising:
a plurality of distributed edge servers optimally serving content to a plurality of geographic regions, each edge server of the plurality of distributed edge servers comprising:
a communication interface for receiving requests identifying a plurality of content and for serving the plurality of content;
main memory configured with at least N−1 arrays, each array of the N−1 arrays tracking a specific number of times each content of the plurality of content is requested;
wherein the requests are received during a first sub-interval of a recurring interval and are entered into a plurality of indices of a first bit array of the N−1 arrays, wherein different sets of indices of the plurality of indices represent a request for different content of the plurality of content;
wherein the entries are copied from the first bit array to a second bit array at the expiration of the first sub-interval to retain a copy of the content requests that were received during said first sub-interval after expiration of the first sub-interval;
wherein said first bit array is flushed after copying the entries to the second bit array;
wherein content requests received during a second sub-interval of the recurring interval are tracked to the first array whose entries were cleared at the expiration of the first sub-interval;
wherein a request for particular content received during the second sub-interval is hashed to produce a specific set of indices;
wherein it is determined whether the particular content was previously requested during the first sub-interval by comparing the specific set of indices to entries of the second bit array;
wherein it is determined whether the particular content was previously requested during the second sub-interval by comparing the specific set of indices to entries of the first bit array;
wherein the particular content is served to an end user submitting the request for the particular content without caching the particular content when at least one index of the set of indices is not entered in the first bit array and the second bit array;
wherein the particular content is cached when said each index of the set of indices is entered in at least one of the first bit array and the second bit array.
5. The content delivery network of claim 4 further comprising a plurality of origin shield servers, each origin shield server of the plurality of origin shield servers (i) receiving a request from at least one edge sever of the plurality edge servers when content identified in the request is not cached at the edge server, (ii) caching the content identified in the request after a first request for the content, and (iii) serving the content to the edge server for subsequent delivery to an end user that originates the request.