Practical LFU Implementation for Web Caching

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.