lru cache replacement

On Tue, 24 Jun 2003 xoror@infuse.org wrote:

I was researching on cache replacement strategy as well. 2Q has one
disadvantage see this exellent paper:
http://www.almaden.ibm.com/cs/people/dmodha/#ARC see the paper
"ARC: A Self-Tuning, Low Overhead Replacement Cache" for theory and "One
Up on LRU" for implementation details. ARC requires no tuning and can
switch fast between chaging patterns. Best of all is it is resistant to a
"sequential scan" pattern. and i think it's even easier to implement then
2q :)

does pgbench test with relatively large sequential scans?

BTW, i'm also willing to implement ARC for pgsql if you guys also think
it's a better algoritm. We will no longer have to tweak parameters like
Kin, Kout. ARC also uses 2 buffers like 2q.

xoror,

On Tue, 24 Jun 2003 12:13:51 +0200 (MEST)
xoror@infuse.org wrote:

I was researching on cache replacement strategy as well. 2Q has one
disadvantage see this exellent paper:
http://www.almaden.ibm.com/cs/people/dmodha/#ARC see the paper
"ARC: A Self-Tuning, Low Overhead Replacement Cache" for theory and "One
Up on LRU" for implementation details. ARC requires no tuning and can
switch fast between chaging patterns. Best of all is it is resistant to a
"sequential scan" pattern. and i think it's even easier to implement then
2q :)

Thanks for your information. I check the paper and implement it by Java for
testing.

does pgbench test with relatively large sequential scans?

Probably no.

--
Yutaka tanida <yutaka@nonsensecorner.com>
http://www.nonsensecorner.com/

Yutaka tanida <yutaka@nonsensecorner.com> writes:

xoror@infuse.org wrote:

does pgbench test with relatively large sequential scans?

Probably no.

pgbench tries to avoid any seqscans at all, I believe, so it wouldn't be
very useful for testing a method that's mainly intended to prevent
seqscans from blowing out the cache.

I tried to implement LRU-2 awhile ago, and got discouraged when I
couldn't see any performance improvement. But I was using pgbench as
the test case, and failed to think about its lack of seqscans.

We could probably resurrect that code for comparison to 2Q, if anyone
can devise more interesting benchmark cases to test.

BTW, when you were running your test case, what shared_buffers did you
use?

regards, tom lane

Yutaka tanida <yutaka@nonsensecorner.com> writes:

xoror@infuse.org wrote:

does pgbench test with relatively large sequential scans?

Probably no.

pgbench tries to avoid any seqscans at all, I believe, so it wouldn't be
very useful for testing a method that's mainly intended to prevent
seqscans from blowing out the cache.

I tried to implement LRU-2 awhile ago, and got discouraged when I
couldn't see any performance improvement. But I was using pgbench as
the test case, and failed to think about its lack of seqscans.

We could probably resurrect that code for comparison to 2Q, if anyone
can devise more interesting benchmark cases to test.

BTW, when you were running your test case, what shared_buffers did you
use?

It's very easy to test sequencial scans using pgbench: just drop the
index from account table. I am using this technique to generate heavy
loads.
--
Tatsuo Ishii

On Tue, 24 Jun 2003, Tom Lane wrote:

Yutaka tanida <yutaka@nonsensecorner.com> writes:

xoror@infuse.org wrote:

does pgbench test with relatively large sequential scans?

Probably no.

pgbench tries to avoid any seqscans at all, I believe, so it wouldn't be
very useful for testing a method that's mainly intended to prevent
seqscans from blowing out the cache.

I tried to implement LRU-2 awhile ago, and got discouraged when I
couldn't see any performance improvement. But I was using pgbench as
the test case, and failed to think about its lack of seqscans.

Yes , lru-2 will behave like LRU under 'normal' load. it will detect
sequential scans and adapt to it. I think that was why you didn't
see any substantial gain in cache hits. though I think ARC does a better
job. LRU-2 also has logaritmic complexity overhead.

The ARC guys have tested with real traces from a Db of a large insurrance
company and the results were quite encouraging. (a lot of other traces
where examined as well)

We could probably resurrect that code for comparison to 2Q, if anyone
can devise more interesting benchmark cases to test.

As i stated before, i'm willing to implement ARC and to see how they all
compare.

On Tue, 24 Jun 2003 10:27:09 -0400
Tom Lane <tgl@sss.pgh.pa.us> wrote:

I tried to implement LRU-2 awhile ago, and got discouraged when I
couldn't see any performance improvement. But I was using pgbench as
the test case, and failed to think about its lack of seqscans.

How about cache hit rate?

BTW, when you were running your test case, what shared_buffers did you
use?

I use 16,64,256 and 4096.

---
Yutaka tanida<yutaka@hi-net.zaq.ne.jp>

On Tue, 24 Jun 2003 10:27:09 -0400
Tom Lane <tgl@sss.pgh.pa.us> wrote:

I tried to implement LRU-2 awhile ago, and got discouraged when I
couldn't see any performance improvement. But I was using pgbench as
the test case, and failed to think about its lack of seqscans.

How about cache hit rate?

BTW, when you were running your test case, what shared_buffers did you
use?

I use 16,64,256 and 4096.

---
Yutaka tanida<yutaka@hi-net.zaq.ne.jp>

On Wed, 25 Jun 2003 00:43:56 +0900
Yutaka tanida <yutaka@nonsensecorner.com> wrote:

BTW, when you were running your test case, what shared_buffers did you
use?

I use 16,64,256 and 4096.

I missed. My shown result(+4% cache hit rate) is shared_buffers=64.

---
Yutaka tanida<yutaka@hi-net.zaq.ne.jp>
謎のWebsite http://www.nonsensecorner.com/

xoror@infuse.org wrote:

I tried to implement LRU-2 awhile ago, and got discouraged when I
couldn't see any performance improvement. But I was using pgbench as
the test case, and failed to think about its lack of seqscans.

Yes , lru-2 will behave like LRU under 'normal' load. it will detect
sequential scans and adapt to it. I think that was why you didn't
see any substantial gain in cache hits. though I think ARC does a better
job. LRU-2 also has logaritmic complexity overhead.

The ARC guys have tested with real traces from a Db of a large insurrance
company and the results were quite encouraging. (a lot of other traces
where examined as well)

We could probably resurrect that code for comparison to 2Q, if anyone
can devise more interesting benchmark cases to test.

As i stated before, i'm willing to implement ARC and to see how they all
compare.

Great.

-- 
  Bruce Momjian                        |  http://candle.pha.pa.us
  pgman@candle.pha.pa.us               |  (610) 359-1001
  +  If your life is a hard drive,     |  13 Roberts Road
  +  Christ can be your backup.        |  Newtown Square, Pennsylvania 19073