
\documentstyle[11pt]{article}




\textwidth = 38.0pc
\textheight = 50.0pc
\oddsidemargin = 0pc
\evensidemargin = 0pc

%%%%%  Definitions file




\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}

\newtheorem{definition}{Definition}[section]
\newtheorem{assumption}[definition]{Assumption}
\newtheorem{remark}[definition]{Remark}
\newtheorem{example}[definition]{Example}

\newcommand{\blackslug}{\penalty 1000\hbox{
    \vrule height 8pt width .4pt\hskip -.4pt
    \vbox{\hrule width 8pt height .4pt\vskip -.4pt
          \vskip 8pt
          \vskip -.4pt\hrule width 8pt height .4pt}
    \hskip -3.9pt
    \vrule height 8pt width .4pt}}
\newenvironment{proof}{\noindent {\sc proof.}\newline}{\noindent\blackslug}

\newenvironment{claim}
 {\noindent {\bf Claim}}{}
\newenvironment{claimproof}
                {\noindent {\bf proof of claim.}\newline}{\noindent
                                             {\bf end of proof of claim}}


\def\mybox#1#2{\begin{center}
        \fbox{\begin{minipage}{#1}#2\end{minipage}}
        \end{center}}
\newenvironment{zboxp}[1]{\mybox{0.95\textwidth}{#1}}{}
\newenvironment{zprog}[1]{
		\begin{tabbing}
                mmm\=mm\=mm\=m\=m\=m\=m\=m\=m\=mmm\=mm\=mm  \kill
                #1 \end{tabbing}
                }{}
\newenvironment{zplainprog}[1]{
                \begin{center}
                \begin{minipage}{0.95\textwidth}{
                \begin{zprog}{#1
                }\end{zprog}
                }\end{minipage}
                \end{center}
                }{}
\newenvironment{zboxprog}[1]{
                \begin{zboxp}{
                \begin{zprog}{#1
                }\end{zprog}
                }\end{zboxp}
                }{}


%% Commands for printing (or non printing of parts)
\newcommand{\skipportion}[1]{
 #1
}
%% Put a single '%' at beginning of next line if these portions are
%% wanted
%\renewcommand{\skipportion}[1]{}

%% Commands for printing (or non printing of parts)
\newcommand{\oldversion}[1]{#1}
%% Put a single '%' at beginning of next line if these portions are
%% wanted
\renewcommand{\oldversion}[1]{}

\newcommand{\e}{\mbox{$\epsilon$}}
%%%%%%%%%%%%%%%%%%%startpoint %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\title{2Q: a low overhead 
high performance buffer management replacement algorithm
	 \footnote{
                Supported by
                U.S. Office of Naval Research \#N00014-91-J-1472 and
                \#N00014-92-J-1719,
                U.S. National Science Foundation grants
                \#CCR-9103953 and IRI-9224601,
		and USRA \#5555-19.
		Part of this work was performed while Theodore
		Johnson was a 1993 ASEE Summer Faculty Fellow
		at the National Space Science Data Center
		of NASA Goddard Space Flight Center.  \newline
		$\mbox{\ }\;\;\;{}^{\dag}$ 
		Authors' e-mail addresses : 
		ted@squall.cis.ufl.edu and
                 shasha@cs.nyu.edu
}}


%\author{ Theodore\ Johnson \quad\quad\quad\quad Dennis\ Shasha \\
%\\
%	Courant Institute, New York University \\
%	New York, NY 10012.}

\author{
\begin{tabular}{ccc}
Theodore\ Johnson & & Dennis\ Shasha \\
University of Florida & & Courant Institute, New York University\\
Gainesville, FL 32611 & & New York, NY 10012 \\
& & and \\
& & Novell, Inc.\\
& & Summit, NJ 07901\\
\end{tabular}
}



\date{{\today}}



\maketitle
\begin{abstract}
\sl



In a path-breaking paper last year 
Pat and Betty O'Neil and Gerhard Weikum proposed a self-tuning
improvement to the Least Recently Used (LRU) buffer management
algorithm\cite{OOW-93}.
Their improvement is called LRU/k and advocates giving priority\footnote{
Throughout this paper,
if page p has more priority than page p'
then p will be replaced after p'.
}
to buffer pages based on the kth most recent access.
(The standard LRU algorithm is denoted LRU/1 according to this 
terminology.)
If P1's kth most recent access is more more
recent than P2's, then P1 will be replaced after P2.
Intuitively, LRU/k for k $>$ 1 is a good strategy, because 
it gives low priority
to pages that have been scanned or to pages that  belong
to a big randomly accessed file (e.g., the account file in TPC/A).
They found that LRU/2 achieves most of the advantage of their method.

The one problem of LRU/2 is the processor overhead
to implement it.
In contrast to LRU, each page access requires log N work to a priority
queue where N is the number of pages in
the buffer.

Question: is there an easier way (constant overhead per access
as in LRU) with similar performance to LRU/2?

Answer: Yes. 

Our ``Two Queue'' algorithm (hereafter 2Q)
has constant time overhead, performs as well
as LRU/2, and requires no tuning.
These results hold for real (DB2 commercial) traces
as well as simulated ones.
Based on these experiments, we estimate that 2Q
will provide a 5-10\% improvement for most 
applications and more for some.
We give some analytic reasons for this result.

\end{abstract}

\section{Background}


Fetching data from disk requires at least a factor of 1000 more time
than fetching data from a RAM buffer.
For this reason, good use of the buffer can significantly
improve the throughput and response time of any data-intensive system.


Until the early 80's, the least recently used buffer replacement
algorithm (replace the page that was least
recently accessed or used) 
was the algorithm of choice in nearly all cases.
Indeed, the theoretical community blessed it by showing that LRU
never replaces more than a factor $f$
as many elements as an optimal
clairvoyant algorithm (where $f$ is the size of the buffer)
\cite{ST-85}.
\footnote{A companion result is that LRU on a buffer
of size B will never
page more than twice as much as a clairvoyant algorithm
on a buffer of size B/2.}

Factors this large can heavily influence the behavior of a database
system, however, as Stonebraker's 
classic article pointed out in 1981\cite{S-81}.
Since that article,
commercial database systems have adopted hybrid buffer
management schemes --- based on LRU, but not pure LRU.
For example, most commercial database 
systems discard a page resulting from a file scan as soon as the
scan accesses the next page.
Following Stonebraker, they observe that there is no point
in keeping a recently accessed scanned page, since the
scan won't use it again.
(LRU by contrast would give high priority to the
most recently scanned page.)
%Dennis, can you add some citations to these algorithms?
% Ted, no I can't because I have this information mostly
% from word-of-mouth.

The trouble with such hybrid schemes is that they
partition the buffer into smaller buffers
(e.g. for sorts, for compiled queries, and possibly for scans)
reducing the effective available space, say, when one buffer is
not fully utilized.
Also, they don't capture all cases.
For example, 
LRU will give high priority to 
recently accessed random data pages accessed via an index
(e.g. account file pages in TPC/A) even though these pages too
are unlikely to be accessed again.

The O'Neil-Weikum paper provided
a welcome alternative to buffer partitioning.
They suggested a more-or-less self-tuning full buffer
variant of LRU with many of the same properties as the
hybrid schemes.
The essence of their scheme is that a page should
not obtain buffer privileges merely because it is accessed once.
What's important is whether it has been popular over time.
The version they advocate --- called LRU/2 --- replaces
the page whose {\bf penultimate} (second-to-last) access
is least recent among all penultimate accesses.

In order to be able to find that page quickly, they organize pointers to 
the buffer pages in a priority queue based
on penultimate access time.
The operations are deletemin
to get the page to replace and a promotion scheme to move a page
that has been accessed to a new place in the queue.
Priority queue operations 
entail a time complexity that grows
with the log of the size of the buffer.

They examine (i) a synthetic workload with references
to two pools of pages one for an index and one for data pages;
(ii) a synthetic workload with random references based on a Zipfian
distribution of reference frequencies obeying
the 80-20 rule on 1000 possible pages; and (iii) a commercial
on-line transaction processing workload derived from a Swiss bank.
In every case, they show a significant improvement over LRU,
sometimes as high as 40\%.

One delicate aspect of their algorithm is that there are two
tuning parameters.
The first is the {\em Correlated Reference Period.}
This is an amount of time during which a page is retained
in the buffer once it has been accessed.
In this way close-in-time subsequent accesses
from the same process (so-called ``correlated''
accesses that arise for example
in a scan) find the page in the buffer.
At the same time, multiple accesses within a correlation period
count only as a single access from the point of view of replacement priority.
The net effect is that if a page is referenced several times within
a correlated reference period and then isn't accessed for a while,
it will have low buffer priority.

The second tuning parameter is the {\em Retained Information Period}
which is the length of time a page's access history is remembered
after it is ejected from the buffer.
The authors recommend 200 seconds though higher values don't hurt.

Since we spend a lot of time with operating system people,
whose favorite data structure is a linked list with constant
time operations, we have looked for and found a variant of LRU/2
having comparable performance results, 
constant time overhead (implementable on a list), and 
requiring no tuning (because the algorithm delivers good performance
with a fixed setting of the parameters over a range
of applications).


\section{2Q Algorithm Description}

LRU works well because it tends to remove cold pages from the buffer
to make space for the faulted page.  If the faulting page is cold, however,
then LRU may displace a warmer page to make space for the cold one.
Furthermore, the cold page will reside in the buffer for a considerable
amount of time.  LRU/2 improves on LRU by using a more aggressive
exit rule, thereby quickly removing cold pages from the buffer.
Implementing the exit rule requires priority queue
manipulations.

The ways in which 2Q and LRU/2 improve upon LRU are 
in some sense complementary.
Instead of cleaning cold pages from the LRU buffer,
2Q admits only hot pages to the LRU buffer.
As with LRU/2, 2Q tests pages for their second reference time.
Simplifying slightly,
on the first reference to a page, 2Q places it in a special buffer,
the A1 queue, which is managed as a FIFO queue.
If the page is re-referenced during its A1 residency, then it is probably
a hot page.
So, if a page in A1 is referenced, the page is moved to the Am queue,
which is managed as an LRU queue.
If a page is not referenced while on A1, it is probably
a cold page, so 2Q removes it from the buffer.


{\bf Simplified 2Q}

\begin{zplainprog}{
\rule{15cm}{0.5pt}
\\
if p is on the Am queue
\\
then
\\
\> put p on the front of the Am queue
\\
\> /* Am is managed as an LRU queue*/
\\
else if p is on the A1 queue
\\
then
\\
\> remove p from the A1 queue 
\\
\> put p on the front of the Am queue
\\
else /* first access we know about concerning p */ 
\\
\> /* find a free page slot for p */ 
\\
\> if there are free page slots available
\\
\> then
\\
\>\> put p in a free page slot 
\\
\> else if A1's size is above a certain tunable threshold then
\\
\>\> delete from the tail of A1
\\
\>\> put p in the freed page slot
\\
\> else 
\\
\>\> delete from the tail of Am
\\
\>\> put p in the freed page slot
\\
\> end if
\\
\> put p on the front of the A1 queue
\\
end if
}\end{zplainprog}

When we experimented with the above algorithm, we found that tuning
it was difficult.
If the maximum size of A1 is set too small,
the test for hotness is too strong and the buffer will take too long
to load in the hot data items.
If the maximum size of A1 is set too large, then A1 steals page slots
from Am, and performance degrades because the buffer for the
hot pages is small.

A solution to the tuning problems is to store pointers to the pages
in A1 instead of the pages themselves.
This solution lets A1 remember enough past references to be responsive
to moderately hot pages, yet preserve all page slots for the LRU buffer.
We found that this solution works well for traces generated from
stationary distributions, but performs poorly for actual traces.
In real access patterns, the locality of reference can change
very quickly.  A common occurrence is for a page to receive many references
for a short period of time (i.e., correlated references),
then no references for a long time.
When a new page is accessed, it should be retained for a period
of time to satisfy the correlated references, then ejected
from the buffer
if it does not receive any further references


{\bf 2Q, Full Version} 

To resolve the above problems we
partition A1 into A1in and A1out.
The most recent first accesses will be in the memory (up to a certain
threshold), but then older first accesses will be thrown out
of memory but remembered in A1out.
(Remembering a page address requires only a few bytes (fewer than 10).)
Given a buffer size B,
one divides it into Am, A1in (of maximum size Kin 
and minimum size 1), and A1out (of maximum size Kout).
Fixing these parameters is one goal of this paper
though our current best estimates
(for reasons we discuss later) are: Kin should be 25\% of the page slots
and Kout should hold identifiers for as many pages as would
fit on 50\% of the buffer.


\begin{zplainprog}{
\rule{15cm}{0.5pt}
\\
// If there is space, we give it to X.
\\
// If there is no space, we free a page slot to make room for page X.
\\
reclaimfor(page X) 
\\
begin
\\
\> if there are free page slots then
\\
\>\> put X into a free page slot
\\
\> else if($|$A1in$|>$Kin)
\\
\>\> page out the tail of A1in, call it Y
\\
\>\> add identifier of Y to the head of A1out
\\
\>\> if($|$A1out$|>$Kout)
\\
\>\>\> remove  identifier of Z from the tail of A1out
\\
\>\> end if
\\
\>\> put X into the reclaimed page slot
\\
\> else
\\
\>\> page out the tail of Am, call it Y
\\
\>\> // do not put it on A1out; it hasn't been accessed for a while
\\
\>\> put X into the reclaimed page slot
\\
\> end if
\\
end
\\
}\end{zplainprog}


\begin{zplainprog}{
\rule{15cm}{0.5pt}
\\
On accessing a page X : 
\\
begin
\\
\> if X is in Am then
\\
\>\> move X to the head of Am
\\
%\> else if (X is in A1in) then
%\\
%\>\> remove X from A1in
%\\
%\>\> add X to the head of Am
%\\
\> else if (X is in A1out) then
\\
\>\> reclaimfor(X)
\\
\>\> add X to the head of Am
\\
\> else if (X is in A1in) // do nothing, don't even promote it
\\
\> else // X is in no queue
\\
\>\> reclaimfor(X)
\\
\>\> add X to the head of A1in
\\
\> end if
\\
end
\\
}\end{zplainprog}


This algorithm solves the correlated reference problem by retaining
newly referenced pages in A1in to satisfy repeated requests.
If a page in A1in is accessed, it isn't promoted to Am, because
the second access may simply be a correlated reference.
The A1out buffer, by contrast,
 is used to detect pages that have high long-term access
rates.  

\section{Experimental Results}

In this section, we show that 2Q is better than LRU and is comparable
to LRU/2.
In all our experiments, we tried to represent LRU/2 as fairly as possible,
but it was difficult to model the tunables of that algorithm exactly.
The LRU/2 algorithm keeps a page in the buffer for a grace period
(the Correlated Reference Period)
and considers a second access to be a legitimate second access
only if it arrived after that period.
It also remembers pages that have been ejected for 200 seconds.


To implement the LRU/2 algorithm with a correlated reference period,
we used the A1in queue.
On its first access, a page is added to the A1in queue.
The page it displaces is inserted into the LRU/2 
priority queue, and a deletemin operation (on the penultimate
access time)
is run to determine a page to eject from the buffer (perhaps the
one just inserted from the A1in queue).
References to a page in the A1in queue are not counted.
We adjusted the size of the A1in queue to obtain the best performance
for the LRU/2 algorithm.


\subsection{Simulation Experiments}

The experiments in this subsection are from artificially generated traces.
They give some intuition about the behavior of LRU, LRU/2, and 2Q,
but do not necessarily represent a  real application's behavior.

{\bf Zipf Distributions}

These two figures compare the performance of LRU, LRU/2, and 2Q on a 
Zipfian input distribution with parameter $\alpha=0.5$ and $\alpha=0.86$
respectively.
A setting of $\alpha=0.86$ gives an 80/20 distribution,
while a setting of $\alpha=.5$ give a less skewed distribution
(about 45/20).
These obey the independent reference model\cite{ACK-87}, 
i.e., each
page has a single stationary probability to be accessed at any point in time.
We set Kin to 1 (since there are no
correlated references) and Kout to
50\% of the number of page slots in the buffer.
We run the simulator for one million references, and report
the number of hits divided by one million.
We explicitly include the effects of the startup transient to
provide a fair comparison, since both 2Q and LRU/2 sacrifice
responsiveness to achieve a higher long-term hit rate.
We simulated a database of 50,000 pages and buffer sizes
ranging from 2,500 page slots to 20,000 page slots.

As a reference point, we included the hit rate of the A0  algorithm
(A0 always replaces the page whose probability of access is lowest)
which is known to be optimal for stable probability distributions\cite{CD-73}.
These charts show that 2Q provides a substantial improvement over LRU,
and has performance comparable to that of LRU/2.
The performance improvement is highest when the number of page slots is small.

\begin{figure}
\vspace{3.2in}
\special{psfile=zalgcp5.eps  hscale=60 vscale=60 hoffset=40, voffset=-210}
\caption{Zipf input comparison with parameter 0.5}
\label{fig1}
\end{figure}

\begin{figure}
\vspace{3.2in}
\special{psfile=zalgcp8.eps  hscale=60 vscale=60 hoffset=40, voffset=-210}
\caption{Zipf input comparison with parameter 0.8}
\label{fig2}
\end{figure}


{\bf Mixed Zipf/Scans}

Both the LRU/2 and the 2Q algorithms are designed to give
low priority
to scanned pages.
We modified the Zipf simulator so that it would occasionally start
a scan.  When simulating a scan, no page in the scan is repeated.
We adjusted the probability of starting a scan so that one
third of the references generated are due to scans.

We ran two experiments, each of which had a database size of 50,000.
In the first experiment, we used a Zipf distribution with parameter
$\alpha=.86$ and 5,000 page slots.  In the second experiment we used
$\alpha=.5$ and 10,000 page slots.
In both experiments we varied the scan length and reported the hit
rates of LRU, LRU/2, and 2Q (with $|$A1in$|$=1 and $|$A1out$|$=50\%
of the number of page slots).

The experiments show that 2Q and LRU/2 have a considerably higher
hit rate than LRU.
The hit rates are lower than in the no-scan case, however.
This is to be expected because there is little hope of getting a hit
on a scan.
However, we notice that the the hit rate of 2Q suffers less than the
hit rate of LRU.  The hit rate of 2Q is about 70\% of its no-scan hit rate,
while the hit rate of LRU is about 60\% of its no-scan hit rate.
Thus, 2Q provides a kind of ``scan resistance.''


\begin{figure}
\vspace{3.2in}
\special{psfile=scan20_5.eps  hscale=60 vscale=60 hoffset=40, voffset=-210}
\caption{1/3 Scan Input Mixed with Zipf Input Having Parameter 0.5 }
\label{fig3}
\end{figure}

\begin{figure}
\vspace{3.2in}
\special{psfile=scan10_8.eps  hscale=60 vscale=60 hoffset=40, voffset=-210}
\caption{1/3 Scan Input Mixed with Zipf Input Having Parameter 0.8 }
\label{fig4}
\end{figure}



{\bf Online Transaction Processing-style Index Accesses}

A nice observation of the LRU/2 paper is that randomly accessed
data pages get an excessively high priority under LRU.
The authors posited an example where there are 100 index pages
and 10,000 data pages.  References come in pairs, one page
selected uniformly at random
from the set of index pages and one selected uniformly at random
from the set of data pages.
The number of available page slots varies from
less than 100 to greater than 100.
They showed that LRU/2 gives priority to the index pages
as it should, since their hit rate with 100 page slots is almost 1/2.
We ran a simulation with identical parameters, and we found
that 2Q also gives preference to index pages.

\begin{figure}
\vspace{3.2in}
\special{psfile=twopool.eps  hscale=60 vscale=60 hoffset=40, voffset=-210}
\caption{Behavior of Algorithms on Index Accesses to Data Pages}
\label{fig5}
\end{figure}


\subsection{Experiments on Real Data}

Colleagues at IBM and Novell (UNIX Systems Group)
kindly supplied traces of a commercial DB2 database application and of hits
on program text for a windowing graphics
application, respectively.\footnote{
We attempted to obtain the Swiss Bank traces used in the LRU/2 paper,
but Gerhard Weikum informed us that the bank considers these to be secret.}
We ran experiments using the same parameters for these two
(very different) applications.
2Q performed well on both.

For these experiments we set Kout to 50\% of the total number of page slots
(we arrived at  this setting based on our simulation studies,
described in the next section).
We set Kin to 20\% and 30\% of the total number of page slots
to test the sensitivity of the 2Q algorithm to the Kout parameter.
Since the differences among the various algorithms sometimes fall
below 5\% we represent these results with tables.

{\bf Trace Data from a DB2 Commercial Application}

The DB2 trace data came from a commercial installation of DB2.
We received a trace file containing 500,000 references to 75514 unique pages.
The file was fed to our buffer management simulators.
The results show that both 2Q and LRU/2 provide a significantly higher hit
rate than LRU. 

The best performance is obtained when the size of Kin is matched
to the amount of correlated reference activity, though the
sensitivity is slight enough to be ignored.


\begin{table}
\begin{center}
\begin{tabular}{|c| c c c c|}
\hline
Number of page slots &	LRU/2 &	LRU	 & 2Q	& 2Q \\
                     &        &          & Kin=30\% & Kin=20\% \\ \hline
50       &          .345  & .317    &   .349 &  .349 \\ \hline
100      &          .432  & .413    &   .444 &  .430 \\ \hline
200      &          .516  & .512    &   .521 &  .510 \\ \hline
500      &          .610  & .606    &   .624 &  .611 \\ \hline
700      &          .639  & .630    &   .658 &  .648 \\ \hline
1000     &          .665  & .654    &   .686 &  .681 \\ \hline
1200     &          .678  & .667    &   .698 &  .695 \\ \hline
1500     &          .693  & .683    &   .711 &  .712 \\ \hline
1700     &          .702  & .691    &   .719 &  .720 \\ \hline
2000     &          .712  & .704    &   .729 &  .730 \\ \hline
2500     &          .727  & .718    &   .742 &  .744 \\ \hline
3000     &          .738  & .730    &   .750 &  .753 \\ \hline
3500     &          .747  & .740    &   .759 &  .760 \\ \hline
4000     &          .755  & .748    &   .767 &  .766 \\ \hline
5000     &          .768  & .762    &   .778 &  .777 \\ \hline
6000     &          .778  & .773    &   .785 &  .786 \\ \hline
7000     &          .786  & .781    &   .791 &  .791 \\ \hline
8000     &          .792  & .789    &   .795 &  .795 \\ \hline
9000     &          .798  & .795    &   .798 &  .799 \\ \hline
10000    &          .802  & .801    &   .801 &  .801 \\ \hline
\end{tabular}
\caption{DB2 trace hit rate comparison of LRU, LRU/2, and 2Q.}
\end{center}
\end{table}


{\bf Trace Data from Program Text Accesses of a Windowing Application}

Colleagues at the UNIX Systems Group of Novell supplied us with a trace
of program references made on a windowing application.
We received a trace file containing 427,618 references to 290 
256 byte pages.
%\footnote{We used smaller pages than those suggested, in order
%to obtain a more active set of references.}.
The results show again that both LRU/2 and 2Q 
provide a significantly higher hit
rate than LRU. 

{\bf Rerunning the Synthetic Experiments with Default Tuning Parameters}

Since 2Q with a single set
of parameters works so well with trace files from  very different sources
and with very different characteristics,
we conjectured that our suggested parameter settings are almost
always good and 2Q needs little tuning.
To confirm our conjecture, we ran the simulations with a Zipf distribution
with Kin set to 25\% of the page slots and Kout set to 50\% of the page slots.
For a fair comparison, we used an A1in queue for the LRU/2 algorithm.
In spite of the fact that there are no correlated references
in the reference string, both 2Q and LRU/2 show a substantial improvement
over LRU.


\begin{table}
\begin{center}
\begin{tabular}{|c| c c c c|}
\hline
Number of page slots &	LRU/2 &	LRU	 & 2Q	& 2Q \\
                     &        &          & Kin=30\% & Kin=20\% \\ \hline
4          &  .443   &   .428  &      .457   &     .457 \\ \hline
6          &  .504   &   .479  &      .533   &     .532 \\ \hline
8          &  .551   &   .536  &      .598   &     .598 \\ \hline
10         &  .602   &   .578  &      .662   &     .661 \\ \hline
12         &  .678   &   .655  &      .722   &     .721 \\ \hline
14         &  .740   &   .713  &      .762   &     .765 \\ \hline
16         &  .762   &   .730  &      .785   &     .792 \\ \hline
18         &  .790   &   .759  &      .815   &     .816 \\ \hline
20         &  .809   &   .772  &      .832   &     .836 \\ \hline
22         &  .825   &   .795  &      .836   &     .844 \\ \hline
24         &  .852   &   .825  &      .845   &     .849 \\ \hline
26         &  .866   &   .839  &      .858   &     .866 \\ \hline
28         &  .877   &   .849  &      .876   &     .879 \\ \hline
30         &  .883   &   .861  &      .894   &     .896 \\ \hline
32         &  .893   &   .876  &      .911   &     .913 \\ \hline
34         &  .917   &   .909  &      .923   &     .926 \\ \hline
36         &  .930   &   .925  &      .932   &     .934 \\ \hline
38         &  .937   &   .935  &      .940   &     .941 \\ \hline
40         &  .943   &   .946  &      .946   &     .946 \\ \hline
\end{tabular}
\caption{Windowing code trace hit rate comparison of LRU, LRU/2, and 2Q.}
\end{center}
\end{table}



\begin{table}
\begin{center}
\begin{tabular}{|c| c c c|}
\hline
Number of page slots &	LRU/2 &	LRU	 & 2Q \\
\hline
\multicolumn{4}{|c|}{$\alpha=.5$}  \\
\hline
5\%  & .141 & .105 & .162 \\
\hline
10\% & .222 & .183 & .238 \\
\hline
20\% & .347 & .313 & .356 \\
\hline
40\% & .544 & .529 & .535 \\
\hline \hline
\multicolumn{4}{|c|}{$\alpha=.86$}  \\
\hline
5\%  & .584 & .528 & .595 \\
\hline
10\% & .661 & .618 & .667 \\
\hline
20\% & .745 & .718 & .744 \\
\hline
40\% & .838 & .826 & .827 \\
\hline
\end{tabular}
\caption{Independent Zipf hit rate comparison of LRU, LRU/2, and 2Q.}
\end{center}
\end{table}





\section{Setting the Parameters}

Recall that the 2Q algorithm has a queue called Am for pages hit
at least two and possibly more times, a queue A1in that stores pages
that have been hit only once (in recent memory), 
and a queue A1out that stores pointers
of pages that have been hit only once. 
To gain intuition about these schemes, we performed the following 
experiments.

{\bf The Size of A1out}

When we developed the Simplified 2Q algorithm, we ran experiments to determine
if the pages in A1 should be stored, or if only the tags should
be stored.
If A1 holds pages, then
a page in A1 will not cause a page fault if it is re-referenced,
but will steal pages from Am.
We ran experiments to see which approach (pages or tags) was better.
A Zipf distribution on 50,000 data items was given to the 2Q algorithm.
In the first experiment, the parameter of the Zipf distribution
is set to $\alpha=.86$ and 10,000 page slots are used.
In the second experiment, $\alpha=.5$ and 5,000 page slots are used.
In both experiments, we made all A1 entries store either pages  or
tags.
We found that the storing the A1 tags is 
is considerably better than that storing the A1 pages.
Further, the performance of 2Q
algorithm is not sensitive to the size of A1 when A1 stores tags,
while the algorithm is highly sensitive when A1 stores pages. 

For this reason, the Full 2Q algorithm uses tags (i.e., A1out) to filter
the pages that are admitted to Am.
The A1in queue is used to handle correlated references only.



\begin{figure}
\vspace{3.2in}
\special{psfile=zcmp.eps  hscale=60 vscale=60 hoffset=40, voffset=-210}
\caption{The Effect of the Size of A1in on the Hit Rate, assuming Zipf 0.5}
\label{fig6}
\end{figure}

%\begin{figure}
%\vspace{3.2in}
%\special{psfile=irlg8-2q.eps  hscale=60 vscale=60 hoffset=40, voffset=-210}
%\caption{The Effect of the Size of A1in on the Hit Rate, assuming Zipf 0.8}
%\label{fig7}
%\end{figure}

{\bf Responsiveness}

The chart in the previous experiment suggests that the best setting
of the size of A1out is about 5\% of the number of page slots in Am.
However, we found that such a small A1out queue did not give good performance
on real input.
The problem with using such a small A1out queue is that it 
admits pages too selectively into the Am queue, and cannot respond to changes
in locality.

To investigate the responsiveness of this algorithm
to changes in locality, we ran the algorithms for
1,000,000 Zipf references, then made a random permutation of the
probabilities assigned to the items (thus affecting a change in locality).
This chart shows hit rates as a function of time after the permutation.
The LRU algorithm recovers very quickly from a change in locality
(which makes LRU harder to beat in practice than in theory).
The LRU/2 algorithm algorithm recovers quickly, but not as fast as LRU.
Thus, LRU/2 has sacrificed some responsiveness for a greater
long-term hit rate.
When the 2Q algorithm uses a small A1out (5\% of the Am page slots),
the responsiveness is very poor, and the hit rate still has not recovered
after 1,000,000 references\footnote{
This counter-intuitive phenomena occurs because we tuned the 2Q algorithm
to quickly fill up when empty.  Flushing cold pages takes longer.}
When a moderately large A1out is used (50\% of the number of 
page slots in A1in),
2Q is almost as responsive as LRU/2.
Since the long-term performance suffers little when the size
of A1out is increased from 5\% to 50\% but the responsiveness
is greatly increased, we have used an A1out size of 50\%
in our performance comparisons.




\begin{figure}
\vspace{3.8in}
\special{psfile=lc5_20.eps  hscale=40 vscale=40 hoffset=110, voffset=-30}
\caption{Responsiveness and the Size of A1, with Zipf 0.5}
\label{fig8}
\end{figure}

\begin{figure}
\vspace{3.8in}
\special{psfile=lc8_20.eps  hscale=40 vscale=40 hoffset=110, voffset=-30}
\caption{Responsiveness and the Size of A1, with Zipf 0.8}
\label{fig9}
\end{figure}

\subsection{Theoretical Setting for 2Q Parameters}

On a static reference stream, the A0 algorithm \cite{CD-73} is optimal.
That algorithm effectively locks the B-1 data items with the 
highest access probability into memory, and use the last page slot
to service page faults.
LRU works well because it tends to keep hot items near the front of
the queue, removing the cold ones.
However, LRU is too trusting.  
It will admit a cold item into the
buffer on the first hit
and kick out a hotter item to make room.
LRU/2 tries to avoid this problem by preferentially
cleaning cold pages from the buffer.
We would like to filter the items that are admitted to the buffer,
to ensure that we make room only for new hot pages.

To do this, we could in principle look at the inter-reference times
(coming from different threads of execution).
If a data item has a short 
inter-reference time, we can
feel confident that it is a hot item, and thus feel confident that
we will not remove a hot page from the buffer to make room for
a cold page.


In the Simplified 2Q algorithm, the A1 queue acts as a filter,
as does the A1out queue in the Full 2Q algorithm.
An item will be admitted to the
LRU queue (Am) only if it receives a second reference before being
removed from the A1out queue.
Suppose that the miss rate (the fraction of references that are misses)
is $m$, and there are $f$ spaces
%Ted: Is this the miss rate you get assuming A0?
%If so, you should say so.
available in the A1out area.
We have observed that the A1out queue is usually full
(the miss rate is much greater than the A1out hit rate).
Thus, an item is admitted to the LRU buffer if it receives
a second reference within $f/m$ references.
%Ted: Here is one problem. This is not true if a page receives
%a second reference within the first |A1in| references.
%Suggested fix: I think you can just say that it is the f/m references once
%the page falls into the A1out queue from the A1in one.
Let us call this probability $p_{accept}$.
Suppose that item $i$ is referenced with probability $p_{i}$.
The probability that item $i$ gains admission to the LRU buffer
on the $k^{\rm th}$ reference after entering A1in is 
$p_{i}(1-p_{i})^{k-1}$.
%Ted: same problem as above. Same solution.
Therefore,
\begin{eqnarray*}
p_{accept}=&\sum_{k=1}^{f/m}p_{i}(1-p_{i})^{k-1}
=&1-(1-p_{i})^{f/m}
\end{eqnarray*}


The probability of admission is close to one for large values
of $p_{i}$, then drops off rapidly to zero when $p_{i}$ becomes small.
Thus, the A1out queue does indeed act as a filter, admitting hot
items into the queue and ejecting cold items.

We can define the A1out filter's cutoff hotness as the reference probability,
$p_{cutoff}$,
at which $p_{accept}=1/2$.  The derivative of $p_{accept}$ is large at this
%Ted: I don't understand why this is important.
%Ted: What we want is to calculate the percentage of hits as a function
%of the probabilities of page access and of the size of A1in, A1out etc.
point, and an item with reference probability $p_{cutoff}$ will be admitted
to Am after three references instead of two.

So, we solve
\begin{eqnarray*}
1-(1-p_{i})^{f/m}=1/2
\end{eqnarray*}
for the value of interest.  Given $f$ and $m$, we can ask for the
access probability of the coldest item which has a 50\% chance of being
admitted to the LRU buffer.  Then
\begin{eqnarray*}
p_{cutoff} =&1-(1/2)^{m/f} \\
\approx & m \ln(2)/f
\end{eqnarray*}
(The approximation is by taking a Taylor series.)
%Ted: When m=f, the first expression is 1/2 and the second is ln(2).
%if ln(2) = 1/2 that means that e^{1/2} = 2, but that surely doesn't work.

We note that the A1out filter is somewhat self-adjusting.
When the miss rate is high, $p_{cutoff}$ is relatively high,
so the queue will admit only the hottest items.
When the miss rate is low, $p_{cutoff}$ is relatively small,
so that only the moderately hot items that should be admitted
to the queue have a chance of gaining admission.

Next, given $p$ and $m$, we can ask what $f=f_{crit}$ gives
%Ted: What is p? Is that the same as p_accept
%Do you mean to say that we are now trying to find the f value that
%gives an entrance probability of .5 for a page with access probability p?
$p_{accept}=.5$.
We find that
\begin{eqnarray*}
f_{crit}=&-\frac{m\ln(2)}{\ln(1-p)} \\
&\approx m\ln(2)/p
\end{eqnarray*}

The approximation follows because $\ln(1-p) \approx -p$.
If we know the access probability of the coldest item that
should be in the buffer, we can solve for $f$.
However, we typically do not know the access probabilities ahead of
time (otherwise we'd use the $A0$ algorithm).
For a rough estimate of $f$, let us find $f_{crit}$ that will
admit an item of average hotness to the buffer 50\% of the time.
If the miss rate is $m$ and there are $B$ page slots,
%Ted: B is the number of page slots in Am right?
%If so, please say so.
the average access probability for an item in the buffer
is $(1-m)/B$.  Substituting for $p$ in the formula for $f_{crit}$,
we find that
\begin{eqnarray*}
f_{approx}=\frac{\ln(2) m B} {1-m}
\end{eqnarray*}
%Ted: Let's just look at the sensitivity to m. If m is 0 or close to it,
%then the buffer should be empty.
%If m is .5 then the buffer should be ln(2) B.
%These are not small sensitivities.

Since this formula requires an a priori estimate of the miss rate,
it is of little use in practical tuning.
However, it suggests that
the size of A1out should be a fixed
fraction of the size of the buffer, $B$.
Our simulation experiments indicate that this fraction should be about 1/2.
%Ted: The problem is that if this prediction is correct,
%then we should get very different results for different values of m.
%Do the experiments bear this out?


The number of page slots is usually a small fraction of the database size.
Let $D$ be the number of data items, and let $B=rD$.
Then:
\[
p_{cutoff}=2m\ln(2)/(rD)
\]
The average reference probability
of a cold data item is $m/(1-r)D$.  If we let $X=m/D$, then we
find that 
the average cold data item has a reference probability of
$\frac{1}{1-r}X$, and that:
\[
p_{cutoff}=\frac{2\ln(2)}{r}X
\]
Since $r$ is small, $\frac{2\ln(2)}{r} \gg \frac{1}{(1-r)}$.
Thus, setting $f=B/2$ filters out the average cold data item
as long as $r$ is small.
Furthermore, $f_{approx}/B= 1/2$ when $m=1/(1+2\ln(2)) \approx .419$.
The value of $f_{approx}$ does not vary rapidly with $m$ as long as
$m$ is not large (if $m$ is large, little can be done).
We conclude that the performance of the algorithm is not sensitive to
the exact setting of $f$, 
and that $f=B/2$ is almost always a good choice.





\section{Conclusion}

2Q is a good buffering algorithm (giving a 5-10\% improvement in hit rate
over LRU for a wide variety of applications
and buffer sizes), having constant time  overhead,
and requiring little or no tuning.
It works well for the same intuitive reason that LRU/2 works well:
it bases buffer priority on sustained popularity rather than on a  single
access.

2Q seems to behave as well as LRU/2 
in our tests (slightly better usually, in fact)
can be implemented in constant time using conventional list operations,
and both analysis and experiment suggest it requires little or no tuning.

\section{Acknowledgments}

Many thanks to
Ted Messinger of IBM and Steve Pendergrast of Novell
for supplying us with real data.
Thanks also to Gerhard Weikum, Pat and Betty O'Neil for friendly
discussions and program code --- would that all algorithmic
competitions were so civil.



\newcommand{\etalchar}[1]{$^{#1}$}
\bibliographystyle{alpha}
\begin{thebibliography}{110}

\bibitem{CD-73}
{\sc E.G. Coffman and P.J. Denning}
\newblock{\bf Operating System Theory}
\newblock{\em Prentice-Hall}, 1973

\bibitem{OOW-93}
{\sc Elizabeth J. O'Neil, Patrick E. O'Neil, and Gerhard Weikum}
\newblock{The LRU-K Page Replacement Algorithm for Database Disk Buffering}
\newblock{Proceedings of the 1993 ACM Sigmod International Conference
on Management of Data, June 1993 pp. 297-306}

\bibitem{ST-85}
{\sc Daniel D. Sleator and Rober T. Tarjan}
\newblock{Amortized Efficiency of List Update and Paging Rules}
\newblock{\em Communications of the ACM}, Feb. 1985, vol. 28, no. 2, pp. 202-208

\bibitem{S-81}
{\sc Michael Stonebraker} 
\newblock{Operating System Support for Database Management}
\newblock{\em Communications of the ACM}, vo. 24, no. 7, July 1981, pp. 412-418.

\bibitem{ACK-87}
{\sc O.I. Aven, E.G. Coffman, and Y.A. Kogan}
\newblock{\bf Stochastic Analysis of Computer Storage}
\newblock{\em D. Reidel}, 1987

\end{thebibliography}


\end{document}






