Dynamic resizing of probabilistic data structures for use in cache admission policies

A method for use with a tiered data storage system that includes a cache memory managed by a cache admission policy, the method comprising:

• maintaining and running multiple counting bloom filters each having a different size;
• admitting and evicting data items from the cache on a least frequently used (LFU) basis, where LFU estimation is provided by a current counting bloom filter selected from the multiple counting bloom filters;
• determining an LFU estimation efficiency over a plurality of data requests;
• selecting an updated counting bloom filter from the multiple counting bloom filters responsive to determining the LFU estimation efficiency;
• and
• replacing the current counting bloom filter with the updated counting bloom filter.

A tiered data storage system configured to service data requests under a workload, the tiered data storage system comprising:

• a low performance storage tier;
• and
• a high performance storage tier that includes a cache memory managed by a cache admission policy, the cache admission policy configured to:
• arbitrate between a new data item and a selected cache victim for admission to and eviction from the cache, the arbitration based on a least frequently used (LFU) estimation provided by a probabilistic data structure having a current size;
• and
• adjust the current size of the probabilistic data structure based on characteristics of the workload over a plurality of data requests.