Miss behavior for caching with lease

Abstract

Caching with lease is to evict the data record from cache after its associated lease term expires. This policy differs from the traditional caching algorithms, e.g., LRU, by introducing a dimension of time to the data record stored in the cache. This model has recently attracted increasing interest not only from a theoretical perspective, but also in real system implementation. For the related theoretical studies, lease of each data record, also known as cache characteristic time and Time-To-Live (TTL), provides a convenient approximation that can simplify the complexity in analyzing popular caching algorithms such as LRU. This approach ignores the finite capacity of the cache size and assumes the lease term to be a known parameter that matches with the measurements. Recently, with new development in system engineering, caching with lease has been shown to be an efficient way to improve the performance of RDMA based key-value stores. This engineering practice imposes new challenges for designing caching algorithms based on lease. It calls for further theoretical investigation on the lease term in presence of a finite cache capacity. To this end, we derive the miss probabilities for caching with lease compared to LRU, when the frequency of requesting a data record is equal to the generalized Zipf's law. Based on the miss probability depending on the lease term, we also discuss adaptive algorithms that can optimally determine the lease term.