Simple analysis of the LRU buffer policy and its relationship to buffer warm-up transient

Abstract

In a database system, a buffer hit transient may occur after a load surge or a node failure. The buffer warm-up transient is the expected buffer hit probability as a function of the time, starting with an empty buffer until the buffer is full. It is only after the buffer becomes full that a buffer replacement policy kicks in. The buffer transient analysis presented in this paper has three main contributions. First, we present a simple approximation for the buffer warm-up transient, and show that it agrees very well with simulation estimates. This result can be used to estimate how long it takes for the buffer hit probability to get to any specified fraction of its steady state value, starting with an empty buffer, say after a failure. Secondly, we show that the analysis for the buffer warm-up transient leads to a simple and very accurate estimate of the steady state buffer hit probability for the LRU buffer replacement policy. Previous approximations to the LRU policy are comparatively more complicated, but we show that they result in estimates indistinguishable from the simple analysis we present. Thirdly, we generalize this method to estimate the transient behavior of the LRU policy starting with a non-empty buffer. This method can be used, for instance, to estimate the effect of a load surge on the buffer hit probability. We show that after a short load surge, it can take much longer than the surge duration for the buffer hit probability to return to its steady state value.