Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Method for Improving Least Recently Used Buffer Performance Using Multiple Stack Insertion Points Based on Data Types

IP.com Disclosure Number: IPCOM000105612D
Original Publication Date: 1993-Aug-01
Included in the Prior Art Database: 2005-Mar-20
Document File: 2 page(s) / 111K

Publishing Venue

IBM

Related People

Dan, A: AUTHOR [+2]

Abstract

A method is disclosed for improving the performance of the Least Recently Used (LRU) buffer replacement policy under a workload that satisfies the Independent Reference Model (IRM) wherein there are multiple disjoint data sets and where the relative frequency of access of the data sets is unknown. This is achieved by dynamically adjusting the insertion points in the LRU stack for different data sets.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 46% of the total text.

Method for Improving Least Recently Used Buffer Performance Using Multiple Stack Insertion Points Based on Data Types

      A method is disclosed for improving the performance of the
Least Recently Used (LRU) buffer replacement policy under a workload
that satisfies the Independent Reference Model (IRM) wherein there
are multiple disjoint data sets and where the relative frequency of
access of the data sets is unknown.  This is achieved by dynamically
adjusting the insertion points in the LRU stack for different data
sets.

      The IRM (Independent Reference Model) applies to several
database transaction processing workloads, such as the TPC-A
benchmark [1,2] In such workloads, there are multiple types of data,
that are accessed with different frequencies, but uniformly within
each data type.  It has been shown in [3]  that with knowledge of the
access frequencies an optimal allocation policy can be devised which
performs significantly better than the LRU policy.  Again assuming
knowledge of access frequencies, it has been shown [4]  that the
generalized clock buffer replacement policy can also outperform the
LRU policy and approach the performance of the optimal buffer
allocation policy.

      Therefore, one objective of the method disclosed here is to
improve the performance of the LRU buffer replacement policy under
IRM, without any knowledge of access frequencies for different data
types.

      In the basic LRU policy, when a data granule is not found in
the LRU stack, it is brought in and inserted at the top of the stack.
The basic problem with this approach is that infrequently accessed
data (cold data) are also inserted at the top of the LRU stack,
pushing down all other data granules including hot data.  This is the
cause for degradation of performance of the LRU policy as compared to
that of optimal buffer allocation.  Therefore, a method is disclosed
to improve performance of the LRU policy by inserting colder data at
a lower point in the LRU stack as compared to the insertion points of
hot data types.  However, since in general the frequency of access of
different data types is unknown, both the relative ordering of the
insertion points and their locations in the stack are unknown.

      The method disclosed solves both these problems by dynamically
adjusting the point of insertion of different data types in the LRU
stack.  There are several possible implementations of the basic idea
of dynamically adjusting the insertion pointer based on data types.
Below a preferred embodiment is described.

      Assume that the workload consists of K data types.  (For
example, in TPC-A the data types consist of ACCOUNT, BRANCH, TELLER
and INDEX.)  The proposed method keeps K pointers corresponding to
the point of insertion of each data type.  Initially all of these
pointers point to the top of the stack, which is the same as the
basic LRU policy.  The resulting buffer hit ratios of the different
data t...