Re: Page replacement algorithm in buffer cache

On Thu, Mar 21, 2013 at 9:51 PM, Atri Sharma <atri(dot)jiit(at)gmail(dot)com> wrote:

> 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.
>

It is replaced when the usage_count is already found to be zero, not when
it is made zero.

> 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,

Well, it may be needed. But then again, it may not be needed. And that
old page, that also may be needed frequently in the future (which is far
more likely than a new page--after all an old page likely got old for a
reason). The best evidence that it will be needed again is that it
actually has been needed again.

I'm more convinced in the other direction, new pages should enter with 0
rather than with 1. I think that the argument that a new buffer needs to
be given more of an opportunity to get used again is mostly bogus. You
cannot bully the shared_buffers into being larger than it is. If all the
incoming buffers get "more opportunity", that just means the buffer-clock
ticks twice as fast, and really none of them has more opportunity when you
measure that opportunity against an outside standard (wall time, or
work-load accomplished). All of our children cannot be above average.

Cheers,

Jeff