Re: Page replacement algorithm in buffer cache - Mailing list pgsql-hackers

Perhaps this isn't the help you were looking for, but I spent a long time looking into this a few years ago.  Then I stopped and decided to work on other things.  I would recommend you do so too.

If I have to struggle to come up with an artificial test case that shows that there is a problem, then why should I believe that there actually is a problem?  If you take a well-known problem (like, say, bad performance at shared_buffers > 8GB (or even lower, on Windows)) and create an artificial test case to exercise and investigate that, that is one thing.  But why invent pathological test cases with no known correspondence to reality?  There are plenty of real problems to work on, and some of them are just as intellectually interesting as the artificial problems are.

My conclusions were:

1) If everything fits in shared_buffers, then the replacement policy doesn't matter.

2) If shared_buffers is much smaller than RAM (the most common case, I believe), then what mostly matters is your OS's replacement policy, not pgsql's.  Not much a pgsql hacker can do about this, other than turn into a kernel hacker.

3) If little of the highly-used data fits in RAM. then any non-absurd replacement policy is about as good as any other non-absurd one.

4) If most, but not quite all, of the highly-used data fits shared_buffers and shared_buffers takes most of RAM (or at least, most of RAM not already needed for other things like work_mem and executables), then the replacement policy matters a lot.  But different policies suit different work-loads, and there is little reason to think we can come up with a way to choose between them.  (Also, in these conditions, performance is very chaotic.  You can run the same algorithm for a long time, and it can suddenly switch from good to bad or the other way around, and then stay in that new mode for a long time).  Also, even if you come up with a good algorithm, if you make the data set 20% smaller or 20% larger, it is no longer a good algorithm.

5) Having buffers enter with usage_count=0 rather than 1 would probably be slightly better most of the time under conditions described in 4, but there is no way get enough evidence of this over enough conditions to justify making a change.  And besides, how often do people run with shared_buffers being most of RAM, and the hot data just barely not fitting in it?

If you want some known problems that are in this general area, we have:

1) If all data fits in RAM but not shared_buffers, and you have a very large number of CPUs and a read-only or read-mostly workload, then BufFreelistLock can be a major bottle neck.  (But, on a Amazon high-CPU instance, I did not see this very much.  I suspect the degree of problem depends a lot on whether you have a lot of sockets with a few CPUs each, versus one chip with many CPUs).  This is very easy to come up with model cases for, pgbench -S -c8 -j8, for example, can often show it.

2) A major reason that people run with shared_buffers much lower than RAM is that performance seems to suffer with shared_buffers > 8GB under write-heavy workloads, even with spread-out checkpoints.  This is frequently reported as a real world problem, but as far as I know has never been reduced to a simple reproducible test case. (Although there was a recent thread, maybe "High CPU usage / load average after upgrading to Ubuntu 12.04", that I thought might be relevant to this.  I haven't had the time to seriously study the thread, or the hardware to investigate it myself)

Cheers,

Jeff