University of Toronto

Huawei Technologies Canada Co., Ltd.

Huawei Cloud Computing Technologies Co., Ltd.

Ming Chen

Chung-Man Abelard Chow

Michael Stumm

Kia Shakiba

Albert Lee

Sari Sultan

The present disclosure provides a method and system for determining a cache size and allocating cache. A batch of requests for storing data in cache is received and associated with a set of counters configured to obtain respective estimated counts of unique hashed keys of requests associated therewith. Requests may be associated with respective counters in accordance with respective size of each request and a respective data block size associated with each counter. Estimated count of unique hashed keys of requests may be obtained at each counter for a selected expiry time based on Time to Live indicators of requests. Cache size to be allocated is computed by, for counters in the set, summing over a product of respective estimated count of hashed keys of requests at a counter with the data block size associated with the counter.

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

For a given application, increasing the size of a cache is beneficial up to a certain point and the number of hits does not increase significantly with a greater cache size. This disclosure provides a method to determine a miss ratio curve, for a cache having data blocks with a time-to-live. A hashed value of a data block's key address can be used to generate a 2D HLL counter for storing expiry times of the data blocks. The 2D HLL counter can be converted to a 1D array, from which a stack distance can be calculated. A frequency distribution of stack distances can then be converted into a miss ratio curve, from which an appropriate cache size can be selected.

Systems and methods to generate a cache miss ratio curve where cache data has a time-to-live

A method to obtain a cache miss ratio curve where a memory blocks of a cache have variable block sizes. By stacking sets of counters, each set being for a different block size, a stack distance for variable block sizes can be obtained and used to determine a miss ratio curve. Such curve can then be used to select a cache size that is appropriate for an application without requiring excessive memory. Methods can be used for batches of request, can apply limits to block sizes, and rounding for intermediary block sizes, they can be used with pruning, and their space complexity can be held constant.

Systems and methods to generate a miss ratio curve for a cache with variable-sized data blocks

Growing community of inventors

Kanata, Canada

Ming Chen