Practical LFU Implementation for Web Caching
Report ID: TR-622-00Author: Serpanos, D. N. / Karakostas, George
Date: 2000-06-00
Pages: 12
Download Formats: |PDF| |Postscript|
Abstract:
Web caches can achieve high hit rates through exploitation of the properties of object access distribution, which is governed by Zipf's law, in general. Web caches need to store the most popular objects and typically employ the Least Frequently Used (LFU) replacement policy, which achieves high cache hit rates, and often the highest hit rate. Correct implementation of LFU requires that replacement decisions are made based on frequency access information (popularity), for all the objects accessed since the beginning of a cache's operation. The immensely large number of such objects renders the implementation of LFU impractical in many environments.
In this paper, we introduce an alternative implementation of LFU, the Window-LFU policy, which makes replacement decisions based on access frequency measurements in a recent past, called time-window. Window-LFU achieves cache hit rates equivalent to those of LFU, but with access information from a shorter history, leading to high performance at a low cost (significantly lower than that of LFU). We provide analytical results which enable one to estimate the appropriate window size, in order to achieve the target cache hit rate of LFU. Furthermore, we present simulation results using actual traces, which indicate that the proposed Window-LFU policy behaves as expected and in some configurations it leads to better results than theoretically expected, due to dependencies between successive Web objects requests in real environments. Our theoretical and simulation results demonstrate that Window-LFU provides an efficient solution for effective Web caches at a low cost, due to its shorter history measurements.