Cascading pre-filter to improve caching efficiency

1. A computer-implemented method comprising:

receiving, from a requestor, a request for data associated with a key;

determining that the data is not in a cache;

identifying the key in a first pre-filter in a set of cascading pre-filters associated with the cache, wherein subsequent pre-filters in the set of cascading pre-filters correspond to greater request frequency counts than previous pre-filters in the set of cascading pre-filters; and

storing, in response to the key being in the first pre-filter, the key in a second pre-filter in the set of cascading pre-filters, wherein a second request frequency count, that corresponds to the second pre-filter, is greater than a first request frequency count, that corresponds to the first pre-filter.

2. The computer-implemented method of claim 1 , further comprising determining the key for the data by performing a hash function on an identifier of the data.

3. The computer-implemented method of claim 2 , wherein the identifier of the data is at least one of a uniform resource locator (URL) of the data, a logical address for the data, or a physical address for the data.

4. The computer-implemented method of claim 1 , wherein each pre-filter in the set of cascading pre-filters comprises an ordered set of bloom filters.

5. The computer-implemented method of claim 4 , further comprising:

determining that each bloom filter in the ordered set of bloom filters for the second pre-filter is full;

resetting a first bloom filter in the ordered set of bloom filters for the second pre-filter; and

storing the key in the first bloom filter.

6. The computer-implemented method of claim 1 , further comprising:

receiving a second request for the data;

identifying the key in the second pre-filter in the set of cascading pre-filters, wherein the second pre-filter is a final pre-filter in the set of cascading pre-filters; and

storing, in response to the key being in the second pre-filter, the data in a first entry in the cache.

7. The computer-implemented method of claim 6 , further comprising evicting a second entry in the cache based on a location of a corresponding entry in at least one pre-filter in the set of cascading pre-filters.

8. The computer-implemented method of claim 1 , further comprising:

determining that the key is not in any pre-filter in the set of cascading pre-filters; and

storing the key in a pre-filter, in the set of cascading pre-filters, that corresponds to a request frequency count of 1.

9. The computer-implemented method of claim 1 , wherein the requestor is a client device and the request for data is received over a network.

10. The computer-implemented method of claim 1 , wherein the requestor is a processor.

11. The computer-implemented method of claim 1 , further comprising;

retrieving the data from a data store; and

providing the data to the requestor.

12. The computer-implemented method of claim 11 , wherein the data store is a network server.

13. A non-transitory computer-readable medium having computer readable instructions that, upon being executed by a processor, cause the processor to:

receive a request for data associated with a key, wherein the data is not in a cache;

identify the key in a first pre-filter in a set of cascading pre-filters associated with the cache, wherein subsequent pre-filters in the set of cascading pre-filters correspond to greater request frequency counts than previous pre-filters in the set of cascading pre-filters; and

store, in response to the key being in the first pre-filter, the key in a second pre-filter in the set of cascading pre-filters, wherein a second request frequency count, that corresponds to the second pre-filter, is greater than a first request frequency count, that corresponds to the first pre-filter.

14. The non-transitory computer-readable medium of claim 13 , wherein the instructions further cause the processor to:

receive a second request for the data;

identify the key in the second pre-filter in the set of cascading pre-filters, wherein the second pre-filter is a final pre-filter in the set of cascading pre-filters; and

store, in response to the key being in the second pre-filter, the data in a first entry in the cache.

15. A system comprising:

a processor;

a cache memory;

a set of cascading pre-filters associated with the cache memory, wherein subsequent pre-filters in the set of cascading pre-filters correspond to greater request frequency counts than previous pre-filters in the set of cascading pre-filters; and

operational memory including instructions that, upon being executed by the processor, cause the system to:

receive, from a requestor, a request for data associated with a key, wherein the data is not in the cache memory;

identify the key in a first pre-filter in the set of cascading pre-filters; and

store, in response to the key being in the first pre-filter, the key in a second pre-filter in the set of cascading pre-filters, wherein a second request frequency count, that corresponds to the second pre-filter, is greater than a first request frequency count, that corresponds to the first pre-filter.

16. The system of claim 15 , wherein each pre-filter in the set of cascading pre-filters comprises an ordered set of bloom filters.

17. The system of claim 15 , wherein the operational memory comprises further instructions that, upon being executed by the processor, further cause the system to:

retrieve the data from a data store; and

provide the data to the requestor.

18. The system of claim 17 , wherein the data store is a network server and the requestor is a client device.

19. The system of claim 16 , wherein the operational memory comprises further instructions that, upon being executed by the processor, further cause the system to:

determine that each bloom filter in the ordered set of bloom filters for the second pre-filter is full;

reset a first bloom filter in the ordered set of bloom filters for the second pre-filter; and

store the key in the first bloom filter.

20. The system of claim 15 , wherein the operational memory comprises further instructions that, upon being executed by the processor, further cause the system to:

receive a second request for the data;

identify the key in the second pre-filter in the set of cascading pre-filters, wherein the second pre-filter is a final pre-filter in the set of cascading pre-filters;

store, in response to the key being in the second pre-filter, the data in a first entry in the cache memory; and

evict a second entry in the cache memory based on a location of a corresponding entry in at least one pre-filter in the set of cascading pre-filters.