Effective buffer management replacement algorithm for parallel shared-nothing database systems

We introduce a new approach to database disk buffering, called the LFU-K method. The LFU-K page replacement algorithm is an improvement of the Least Frequently Used (LFU) algorithm. A probability-theoretical model for a formal description of the LFU-K algorithm is proposed. Using this model, we obtain some estimates for the LFU-K parameters. An implementation of LFU-2 policy (called LFU-2m algorithm) is discussed. As we demonstrate with trace-driven simulation experiments, the LFU-2m algorithm performs better than the conventional buffering algorithm for the shared-nothing database system workloads.