Skip site navigation (1) Skip section navigation (2)

Page replacement algorithm in buffer cache

From: Atri Sharma <atri(dot)jiit(at)gmail(dot)com>
To: Pg Hackers <pgsql-hackers(at)postgresql(dot)org>
Subject: Page replacement algorithm in buffer cache
Date: 2013-03-22 04:51:59
Message-ID: CAOeZVic4HikhmzVD=ZP4JY9g8PgpyiQQOXOELWP=kR+=H1Frgg@mail.gmail.com (view raw or flat)
Thread:
Lists: pgsql-hackers
Hello all,

Sorry if this is a naive question.

I was going through Greg Smith's slides on buffer
cache(http://www.westnet.com/~gsmith/content/postgresql/InsideBufferCache.pdf).
When going through the page replacement algorithm that we use i.e.
clocksweep algorithm, I felt a potential problem in our current
system.

Specifically, when a new entry is allocated in the buffer, it's
USAGE_COUNT is set to 1. On each sweep of the algorithm, the
USAGE_COUNT is decremented and an entry whose  USAGE_COUNT becomes
zero is replaced.

I feel that this could lead to a bias towards replacement of
relatively younger pages in the  cache over older pages. An entry
which has just entered the cache with USAGE_COUNT=1 could be replaced
soon, but it may be needed frequently in the near future, which would
result in it being repeatedly brought into the cache, leading to
replacement overheads.

I think this is the well known face off between LRU and MRU algorithms.

How do we work around this problem?

Regards,

Atri

--
Regards,

Atri
l'apprenant


Responses

pgsql-hackers by date

Next:From: Tom LaneDate: 2013-03-22 04:58:05
Subject: Re: Proposal for Allow postgresql.conf values to be changed via SQL [review]
Previous:From: Amit KapilaDate: 2013-03-22 04:47:10
Subject: Re: Proposal for Allow postgresql.conf values to be changed via SQL [review]

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group