Method of determining a cache size using an estimation of a number of requests for cache memory and a size of the requests

A system for allocating a cache, comprising:

• at least one processor;
• and
• machine readable memory storing machine readable instructions, which when executed by the at least one processor, configures the system to:
• receive a plurality of requests, each request of the plurality of requests including a request for storing respective data to a caching memory, each request having a respective request size, each respective data being associated with a respective key;
• associate the plurality of requests to a set of counters, each counter of the set of counters being associated with a respective data block size that is different than the data block size associated with any other counter of the set of counters, by, for each request of the plurality of requests:
• determining which counter of the set of counters has a smallest associated respective data block size that is at least as large as the request size of the request;
• and
• associating a hash of the key associated with the respective data of the request with the determined counter, the hash of the key being a hashed key;
• determine a cache size based on:
• a number of unique hashed keys associated with each respective counter of the set of counters;
• and
• the respective data block size of each counter of the set of counters;
• and
• allocate the cache by reserving, for caching, a portion of the caching memory, the portion of the caching memory having a size at least equal to the cache size.

A method to allocate a cache in a memory, comprising:

• receiving a plurality of requests, each request of the plurality of requests including a request for storing respective data to the cache, each request having a respective request size, each respective data being associated with a respective key, at least one request of the plurality of requests having a respective Time to Live (TTL) indicator;
• associating the plurality of requests to a set of sliding HyperLogLog (HLL) counters, each sliding HLL counter of the set of HLL counters being associated with a respective data block size, the associating of the plurality of requests to the set of sliding HLL counters including:
• for each request:
• determining which sliding HLL counter of the set of sliding HLL counters has a smallest associated respective data block size that is at least as large as the respective request size of the request;
• and
• associating a hash of the key associated with the respective data of the request with the determined counter, the hash of the key being a respective hashed key;
• determining a cache size of the cache, for a selected expiry time, based on:
• a number of unique hashed keys associated with each respective sliding HLL counter of the set of sliding HLL counters;
• and
• the respective data block size of each sliding HLL counter of the set of sliding HLL counters;
• and
• allocating the cache by reserving, for caching, a portion of the memory, the portion of the memory having a size at least equal to the cache size.