Proof-of-concept ARC removal patches

Date: Thu, 03 Feb 2005 21:41:52 -0500
From: Tom Lane <tgl@sss.pgh.pa.us>
Subject: Proof-of-concept ARC removal patches

Re: subject -- shouldn't it be "replacement" and _not_ "removal" of ARC?

Attached are two different variants of a patch to remove the ARC
cache algorithm in favor of variants of the "2Q" algorithm.

...

In some desultory testing with pgbench, there was no significant
performance difference among the three algorithms, which leads me to
think that simplified 2Q might be the best bet (it certainly has the
smallest memory footprint). But it would be a good idea to do some
more measurements before believing that. I hope that Mark Wong can give
these a try on his setup soon.

...

Comments?

Wouldn't it been much more usable and fair to be able to "load" any of those
modules as I am, the user see fit? So, I could swap the algos on the fly
whichever better suits me? That will also lay down ground suitable for easier
performance testing between the modules should people write their own, new
ones.

I'd keep the ARC around and not remove as a proof-of-concept module as well.
Whatever the status of the IBM's ARC patent may become, the US customers will
simply not use the module. Researchers, however, will always be able to tell
that their modules are better or worse by comparing them to ARC (or 2Q or
whatever).

regards, tom lane

--
Serguei A. Mokhov | /~\ The ASCII
Computer Science Department | \ / Ribbon Campaign
Concordia University | X Against HTML
Montreal, Quebec, Canada | / \ Email!

Tom Lane wrote
Attached are two different variants of a patch to remove the ARC
cache algorithm in favor of variants of the "2Q" algorithm.

The first patch approximates the "full 2Q" algorithm described by
Johnson and Shasha, while the second approximates their
"simplified 2Q"
method. Full 2Q uses a list of pages that were recently in cache but
no longer are, while simplified 2Q does not; the first patch is
therefore a smaller change to the existing code.

"Full 2Q" is the right one, I think.

The patches are not exactly the J&S algorithms, in part because I kept
the special cases for VACUUM, and in part because I really
don't believe
their idea about not promoting from T1 into T2 until the page
has fallen
into B1. This helped to minimize the change from the
existing ARC code.

Agreed.

In some desultory testing with pgbench, there was no significant
performance difference among the three algorithms, which leads me to
think that simplified 2Q might be the best bet (it certainly has the
smallest memory footprint). But it would be a good idea to do some
more measurements before believing that. I hope that Mark
Wong can give
these a try on his setup soon.

Will give these a whirl...

Comments?

The use of 25% T1 and 75% T2 is probably the only thing to discuss, for
me.

Johnson & Sasha's results show that having a larger T1 makes the system
more responsive to changes, while a larger T2 gives a better longer term
hit rate. J&S's results show that higher T1/T2 ratios are better with
smaller caches. The CARS results show that keeping T1 above a certain
minimum size is better also.

From that, I'd suggest we choose a T1/T2 ratio that changes according to
how you start shared_buffers. If we had another GUC at all, it should be
one that isn't listed in the postgresql.conf file at all...since it
would be easy to misuse.

A default setting of something like T1 as % of total (just roughly)
= 50% when shared_buffers <= 1000
= 25% when shared_buffers = 5000
= 10% when shared_buffers = 20000
with smoothing...

Best Regards, Simon Riggs

Serguei Mokhov <mokhov@cs.concordia.ca> writes:

Re: subject -- shouldn't it be "replacement" and _not_ "removal" of ARC?

Sure.

Wouldn't it been much more usable and fair to be able to "load" any of those
modules as I am, the user see fit? So, I could swap the algos on the fly
whichever better suits me? That will also lay down ground suitable for easier
performance testing between the modules should people write their own, new
ones.

Fairness doesn't enter into it --- we have to get out from under the
upcoming patent, whether you think that's fair or not. As for the other
point, I already did the work needed to isolate this code into one file.
Anyone who wants to experiment can do so by inserting different versions
of freelist.c, which surely should be well within the ability of anyone
competent to do such experiments. I have no interest in setting up some
kind of hot-pluggable interface for this code: it doesn't look to me
like the development, testing, or maintenance burden would be repaid.
(As for on-the-fly changes, that's a complete non-starter because of the
differing demands for shared memory. So at best you'd be able to change
algorithms during postmaster restart, anyway.)

If someone is able to show, using these patches, that there is a really
significant difference between these algorithms, then I might reconsider
that position. But for now my answer is that it's not worth the trouble.

regards, tom lane

"Simon Riggs" <simon@2ndquadrant.com> writes:

The use of 25% T1 and 75% T2 is probably the only thing to discuss, for
me.

Hmm. I had been trying to avoid adding a GUC parameter for this ;-)

A default setting of something like T1 as % of total (just roughly)
= 50% when shared_buffers <= 1000
= 25% when shared_buffers = 5000
= 10% when shared_buffers = 20000
with smoothing...

Have you got anything to back up the need for such an adjustment?

BTW, now that I look at this code more closely, I'm feeling dissatisfied
with Jan's custom adjustments to the ARC algorithm, particularly the
rule that it takes touches from two different transactions to get a page
into T2. I preserved that logic in these proposed patches but I'm
thinking that we want to change it, independently of the ARC/2Q issue.
I'll start another thread in pghackers about that. I bring it up now
just because I think that it has an impact on the desirable size of T1.
It might be unwise to put too much emphasis on comparative benchmarks
taken before we change that rule.

regards, tom lane