Re: our buffer replacement strategy is kind of lame

On Sat, Aug 13, 2011 at 4:40 PM, Greg Stark <stark@mit.edu> wrote:
> On Sat, Aug 13, 2011 at 8:52 PM, Robert Haas <robertmhaas@gmail.com> wrote:
>> and possibly we ought to put them all in a
>> linked list so that the next guy who needs a buffer can just pop one
>
> The whole point of the clock sweep algorithm is to approximate an LRU
> without needing to maintain a linked list. The problem with a linked
> list is that you need to serialize access to it so every time you
> reference a buffer you need to wait on a lock for the list so you can
> move that buffer around in the list.

Right, but the same doesn't apply to what I'm talking about.  You just
put each guy into the linked list when his reference count goes down
to 0.  When you want to allocate a buffer, you pop somebody off.  If
his reference count is still 0, you forget about him and pop the next
guy, and keep going until you find a suitable victim.

The problem with just running the clock sweep every time you need a
victim buffer is that you may have to pass over a large number of
unevictable buffers before you find someone you can actually kick out.That's work that should really be getting done in
thebackground, not
 
at the absolute last moment when we discover, hey, we need a buffer.

> It does kind of seem like your numbers indicate we're missing part of
> the picture though. The idea with the clock sweep algorithm is that
> you keep approximately 1/nth of the buffers with each of the n values.
> If we're allowing nearly all the buffers to reach a reference count of
> 5 then you're right that we've lost any information about which
> buffers have been referenced most recently.

It doesn't seem right to have 1/nth of the buffers at each of n values
because that might not match the actual workload.  For example, you
might have lightning-hot buffers that fill 50% of your available
cache.  Trying to artificially force some of those down to usage count
4 or 3 doesn't actually get you anywhere.  In fact, AFAICS, there's no
direct reason to care about about how many buffers have usage count 1
vs. usage count 5.  What IS important for performance is that there
are enough with usage count 0.  Any other distinction is only useful
to the extent that it allows us to make a better decision about which
buffers we should push down to 0 next.

> I wonder if we're suppoesd to be doing something like advancing the
> clock hand each time we increment a reference count as well?

That precise thing seems far too expensive, but I agree that
something's missing.  Right now we decrease usage counts when the
clock hand moves (which is driven by buffer allocation), and we
increase them when buffers are pinned (which is driven by access to
already-resident buffers).  I feel like that's comparing apples and
oranges.  If some subset of shared_buffers is very hot relative to the
uncached pages, then everything's going to converge to 5 (or whatever
arbitrary maximum we care to set in lieu of 5).

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company