I'm working on an experimental patch to break up the BufMgrLock along
the lines we discussed a few days ago --- in particular, using a clock
sweep algorithm instead of LRU lists for the buffer replacement strategy.
I started by writing up some design notes, which are attached for
review in case anyone has better ideas.

One thing I realized quickly is that there is no natural way in a clock
algorithm to discourage VACUUM from blowing out the cache. I came up
with a slightly ugly idea that's described below. Can anyone do better?

regards, tom lane


Buffer manager's internal locking
---------------------------------

Before PostgreSQL 8.1, all operations of the shared buffer manager itself
were protected by a single system-wide lock, the BufMgrLock, which
unsurprisingly proved to be a source of contention. The new locking scheme
avoids grabbing system-wide exclusive locks in common code paths. It works
like this:

* There is a system-wide LWLock, the BufMappingLock, that notionally
protects the mapping from buffer tags (page identifiers) to buffers.
(Physically, it can be thought of as protecting the hash table maintained
by buf_table.c.) To look up whether a buffer exists for a tag, it is
sufficient to obtain share lock on the BufMappingLock. Note that one
must pin the found buffer, if any, before releasing the BufMappingLock.
To alter the page assignment of any buffer, one must hold exclusive lock
on the BufMappingLock. This lock must be held across adjusting the buffer's
header fields and changing the buf_table hash table. The only common
operation that needs exclusive lock is reading in a page that was not
in shared buffers already, which will require at least a kernel call
and usually a wait for I/O, so it will be slow anyway.

* A separate system-wide LWLock, the BufFreelistLock, provides mutual
exclusion for operations that access the buffer free list or select
buffers for replacement. This is always taken in exclusive mode since
there are no read-only operations on those data structures. The buffer
management policy is designed so that BufFreelistLock need not be taken
except in paths that will require I/O, and thus will be slow anyway.
(Details appear below.) It is never necessary to hold the BufMappingLock
and the BufFreelistLock at the same time.

* Each buffer header contains a spinlock that must be taken when examining
or changing fields of that buffer header. This allows operations such as
ReleaseBuffer to make local state changes without taking any system-wide
lock. We use a spinlock, not an LWLock, since there are no cases where
the lock needs to be held for more than a few instructions.

Note that a buffer header's spinlock does not control access to the data
held within the buffer. Each buffer header also contains an LWLock, the
"buffer context lock", that *does* represent the right to access the data
in the buffer. It is used per the rules above.

There is yet another set of per-buffer LWLocks, the io_in_progress locks,
that are used to wait for I/O on a buffer to complete. The process doing
a read or write takes exclusive lock for the duration, and processes that
need to wait for completion try to take shared locks (which they release
immediately upon obtaining). XXX on systems where an LWLock represents
nontrivial resources, it's fairly annoying to need so many locks. Possibly
we could use per-backend LWLocks instead (a buffer header would then contain
a field to show which backend is doing its I/O).


Buffer replacement strategy
---------------------------

There is a "free list" of buffers that are prime candidates for replacement.
In particular, buffers that are completely free (contain no valid page) are
always in this list. We may also throw buffers into this list if we
consider their pages unlikely to be needed soon. The list is singly-linked
using fields in the buffer headers; we maintain head and tail pointers in
global variables. (Note: although the list links are in the buffer headers,
they are considered to be protected by the BufFreelistLock, not the
buffer-header spinlocks.) To choose a victim buffer to recycle when there
are no free buffers available, we use a simple clock-sweep algorithm, which
avoids the need to take system-wide locks during common operations. It
works like this:

Each buffer header contains a "recently used" flag bit, which is set true
whenever the buffer is unpinned. (Setting this bit requires only the
buffer header spinlock, which would have to be taken anyway to decrement
the buffer reference count, so it's nearly free.)

The "clock hand" is a buffer index, NextVictimBuffer, that moves circularly
through all the available buffers. NextVictimBuffer is protected by the
BufFreelistLock.

The algorithm for a process that needs to obtain a victim buffer is:

1. Obtain BufFreelistLock.

2. If buffer free list is nonempty, remove its head buffer. If the buffer
is pinned or has its "recently used" bit set, it cannot be used; ignore
it and return to the start of step 2. Otherwise, pin the buffer,
release BufFreelistLock, and return the buffer.

3. Otherwise, select the buffer pointed to by NextVictimBuffer, and
circularly advance NextVictimBuffer for next time.

4. If the selected buffer is pinned or has its "recently used" bit set,
it cannot be used. Clear its "recently used" bit and return to step 3
to examine the next buffer.

5. Pin the selected buffer, release BufFreelistLock, and return the buffer.

(Note that if the selected buffer is dirty, we will have to write it out
before we recycle it; if someone else pins the buffer meanwhile we will
have to give up and try another buffer. This however is not a concern
of the basic select-a-victim-buffer algorithm.)

This scheme selects only victim buffers that have gone unused since they
were last passed over by the "clock hand".

A special provision is that while running VACUUM, a backend does not set the
"recently used" bit on buffers it accesses. In fact, if ReleaseBuffer sees
that it is dropping the pin count to zero and the "recently used" bit is not
set, then it appends the buffer to the tail of the free list. (This implies
that VACUUM, but only VACUUM, must take the BufFreelistLock during
ReleaseBuffer; this shouldn't create much of a contention problem.) This
provision encourages VACUUM to work in a relatively small number of buffers
rather than blowing out the entire buffer cache. It is reasonable since a
page that has been touched only by VACUUM is unlikely to be needed again
soon.

Since VACUUM usually requests many pages very fast, the effect of this is that
it will get back the very buffers it filled and possibly modified on the next
call and will therefore do its work in a few shared memory buffers, while
being able to use whatever it finds in the cache already. This also implies
that most of the write traffic caused by a VACUUM will be done by the VACUUM
itself and not pushed off onto other processes.

---------------------------(end of broadcast)---------------------------
TIP 1: subscribe and unsubscribe commands go to majordomo@postgresql.org

Tom Lane wrote:
> I'm working on an experimental patch to break up the BufMgrLock along
> the lines we discussed a few days ago --- in particular, using a clock
> sweep algorithm instead of LRU lists for the buffer replacement strategy.
> I started by writing up some design notes, which are attached for
> review in case anyone has better ideas.
>
> One thing I realized quickly is that there is no natural way in a clock
> algorithm to discourage VACUUM from blowing out the cache. I came up
> with a slightly ugly idea that's described below. Can anyone do better?

Uh, is the clock algorithm also sequential-scan proof? Is that
something that needs to be done too?

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

---------------------------(end of broadcast)---------------------------
TIP 5: Have you checked our extensive FAQ?

http://www.postgresql.org/docs/faq

Bruce Momjian <pgman@candle.pha.pa.us> writes:
> Tom Lane wrote:
>> One thing I realized quickly is that there is no natural way in a clock
>> algorithm to discourage VACUUM from blowing out the cache. I came up
>> with a slightly ugly idea that's described below. Can anyone do better?

> Uh, is the clock algorithm also sequential-scan proof? Is that
> something that needs to be done too?

If you can think of a way. I don't see any way to make the algorithm
itself scan-proof, but if we modified the bufmgr API to tell ReadBuffer
(or better ReleaseBuffer) that a request came from a seqscan, we could
do the same thing as for VACUUM. Whether that's good enough isn't
clear --- for one thing it would kick up the contention for the
BufFreelistLock, and for another it might mean *too* short a lifetime
for blocks fetched by seqscan.

regards, tom lane

---------------------------(end of broadcast)---------------------------
TIP 3: if posting/reading through Usenet, please send an appropriate
subscribe-nomail command to majordomo@postgresql.org so that your
message can get through to the mailing list cleanly

Bruce Momjian <pgman@candle.pha.pa.us> writes:

> Tom Lane wrote:
> >
> > One thing I realized quickly is that there is no natural way in a clock
> > algorithm to discourage VACUUM from blowing out the cache. I came up
> > with a slightly ugly idea that's described below. Can anyone do better?
>
> Uh, is the clock algorithm also sequential-scan proof? Is that
> something that needs to be done too?

I think the normal strategy is to make it *always* work the way you made
VACUUM work. That is, it should always enter newly loaded pages with the
"recently used" flag false.

It doesn't necessarily mean they get purged immediately on the next flush, any
other buffer that hasn't been accessed since it was loaded is also a
candidate, but if nothing else accesses it before the clock hand gets to it
then it a candidate.

The only thing that scares me about this is that running a vacuum or
sequential scan could have too much of an effect on non-sequential accesses
like index scans if it forced the hand around so fast that the index scan
didn't have a chance to reuse pages.

--
greg


---------------------------(end of broadcast)---------------------------
TIP 8: explain analyze is your friend

>>>>> "Tom" == Tom Lane <tgl@sss.pgh.pa.us> writes:

Tom> and changing the buf_table hash table. The only common
Tom> operation that needs exclusive lock is reading in a page that
Tom> was not in shared buffers already, which will require at
Tom> least a kernel call and usually a wait for I/O, so it will be
Tom> slow anyway.

Why not a separate lock per bucket chain in the hash table in addition
to the system-wide LWLock ? It's not so much that such an operation will be
slow anyway but that such a slow operation will unnecessarily block
other operations.

--
Pip-pip
Sailesh
http://www.cs.berkeley.edu/~sailesh



---------------------------(end of broadcast)---------------------------
TIP 7: don't forget to increase your free space map settings

On Sun, Feb 13, 2005 at 06:56:47PM -0500, Tom Lane wrote:
> Bruce Momjian <pgman@candle.pha.pa.us> writes:
> > Tom Lane wrote:
> >> One thing I realized quickly is that there is no natural way in a clock
> >> algorithm to discourage VACUUM from blowing out the cache. I came up
> >> with a slightly ugly idea that's described below. Can anyone do better?
>
> > Uh, is the clock algorithm also sequential-scan proof? Is that
> > something that needs to be done too?
>
> If you can think of a way. I don't see any way to make the algorithm
> itself scan-proof, but if we modified the bufmgr API to tell ReadBuffer
> (or better ReleaseBuffer) that a request came from a seqscan, we could
> do the same thing as for VACUUM. Whether that's good enough isn't
> clear --- for one thing it would kick up the contention for the
> BufFreelistLock, and for another it might mean *too* short a lifetime
> for blocks fetched by seqscan.

Is there anything (in the buffer headers?) that keeps track of buffer
access frequency? *BSD uses a mechanism to track roughly how often a page
in memory has been accessed, and uses that to determine what pages to
free. In 4.3BSD, a simple 2 hand clock sweep is used; the first hand
sets a not-used bit in each page, the second hand (which sweeps a fixed
distance behind the 1st hand) checks this bit and if it's still clear
moves the page either to the inactive list if it's dirty, or to the
cache list if it's clean. There is also a free list, which is generally
fed by the cache and inactive lists.

Postgresql has a big advantage over an OS though, in that it can
tolerate much more overhead in buffer access code than an OS can in it's
vm system. If I understand correctly, any use of a buffer at all means a
lock needs to be aquired on it's buffer header. As part of this access,
a counter could be incremented with very little additional cost. A
background process would then sweep through 'active' buffers,
decrementing this counter by some amount. Any buffer that was
decremented below 0 would be considered inactive, and a candidate for
being freed. The advantage of using a counter instead of a simple active
bit is that buffers that are (or have been) used heavily will be able to
go through several sweeps of the clock before being freed. Infrequently
used buffers (such as those from a vacuum or seq. scan), would get
marked as inactive the first time they were hit by the clock hand.
--
Jim C. Nasby, Database Consultant decibel@decibel.org
Give your computer some brain candy! www.distributed.net Team #1828

Windows: "Where do you want to go today?"
Linux: "Where do you want to go tomorrow?"
FreeBSD: "Are you guys coming, or what?"

---------------------------(end of broadcast)---------------------------
TIP 1: subscribe and unsubscribe commands go to majordomo@postgresql.org

On Wed, Feb 16, 2005 at 12:33:38PM -0500, Tom Lane wrote:
> "Jim C. Nasby" <decibel@decibel.org> writes:
> > The advantage of using a counter instead of a simple active
> > bit is that buffers that are (or have been) used heavily will be able to
> > go through several sweeps of the clock before being freed. Infrequently
> > used buffers (such as those from a vacuum or seq. scan), would get
> > marked as inactive the first time they were hit by the clock hand.
>
> Hmm. It would certainly be nearly as easy to adjust a counter as to
> manipulate the RECENTLY_USED flag bit that's in the patch now. (You
> could imagine the RECENTLY_USED flag bit as a counter with max value 1.)
>
> What I'm envisioning is that pinning (actually unpinning) a buffer
> increments the counter (up to some limit), and the clock sweep
> decrements it (down to zero), and only buffers with count zero are taken
> by the sweep for recycling. That could work well, but I think the limit
> needs to be relatively small, else we could have the clock sweep having
> to go around many times before it finally frees a buffer. Any thoughts
> about that? Anyone seen any papers about this sort of algorithm?
>
I have seen this algorithm described as a more generalized clock type
algorithm. As the size of the counter increases, up to the number of
buffers, the clock algorithm becomes LRU. One bit is the lightest
weight approximation. Increasing the number of bits or a count makes
the clock algorithm more closely approximate LRU. You need to balance
how long it takes to find a free buffer. That time increases as the
count size increases.

Ken

---------------------------(end of broadcast)---------------------------
TIP 7: don't forget to increase your free space map settings

"Jim C. Nasby" <decibel@decibel.org> writes:
> The advantage of using a counter instead of a simple active
> bit is that buffers that are (or have been) used heavily will be able to
> go through several sweeps of the clock before being freed. Infrequently
> used buffers (such as those from a vacuum or seq. scan), would get
> marked as inactive the first time they were hit by the clock hand.

Hmm. It would certainly be nearly as easy to adjust a counter as to
manipulate the RECENTLY_USED flag bit that's in the patch now. (You
could imagine the RECENTLY_USED flag bit as a counter with max value 1.)

What I'm envisioning is that pinning (actually unpinning) a buffer
increments the counter (up to some limit), and the clock sweep
decrements it (down to zero), and only buffers with count zero are taken
by the sweep for recycling. That could work well, but I think the limit
needs to be relatively small, else we could have the clock sweep having
to go around many times before it finally frees a buffer. Any thoughts
about that? Anyone seen any papers about this sort of algorithm?

regards, tom lane

---------------------------(end of broadcast)---------------------------
TIP 5: Have you checked our extensive FAQ?

http://www.postgresql.org/docs/faq

On Wed, Feb 16, 2005 at 11:42:11AM -0600, Kenneth Marshall wrote:
> I have seen this algorithm described as a more generalized clock type
> algorithm. As the size of the counter increases, up to the number of
> buffers, the clock algorithm becomes LRU. One bit is the lightest
> weight approximation. Increasing the number of bits or a count makes
> the clock algorithm more closely approximate LRU. You need to balance
> how long it takes to find a free buffer. That time increases as the
> count size increases.

Yeah, the trick to this seems to be how you tweak the rate at which
stuff 'falls out' of the active list. I can think of 3 ways to
accomplish this:

1) Change the maximum value to count to (or the value at which a buffer
is considered no longer in use).

This has the disadvantage of changing how effective the count is. In an
extreme situation, it would retuce back to a single bit. It also won't
affect buffers that already have higher counts, meaning older data is
more likely to stay in buffer than newer data.

2) Change the amount the counter is incremented by on each use (and/or
the amount it's decremented by).

An example of this might be having the clock decrement by 10. Under a
light to medium load, the system might increment by 10 on each use, but
if the system starts getting pressed for free buffers, that could be
reduced.

A downside of this would be that it potentially requires more space in
each header to store a larger value. An advatage is that it allows more
flexability than #1. For example, if the decrement value is increased in
order to speed up reclaiming of buffers, it won't create a difference in
how buffers are weighted based on when they were accessed like #1 will.

3) Change the speed of the clock.

This is what BSD effectively does. The OS periodically checks to see how
many pages are available on the free list, as well as how many were
removed since the last check. This information is used to decide how
many pages the clock algorithm should attempt to free in the next time
period (which can be 0).

If a two-hand algorithm is used, the distance between the two hands can
also be varied.

I think #3 probably means you'd need a seperate process to handle the
clock and moving buffers to a free list. Or perhaps this gets tied in
with the background writer. This might mean more overhead, but it could
improve contention if it means only one process needs to aquire some of
these locks.

So much for a simple design discussion. Fortunately, #1 and #2 should
be easy to test. #3 will certainly require more code, but it would
probably be simpler to implement than having multiple backends running
the clock algorithm (which I think is the current plan).

Something else I thought of; by using a counter instead of a bit, you
can also 'pre-seed' buffers based on why they were populated. For
example, pages brought in from an index might start with a value of 4;
heap pages 3, heap pages from a seqscan 2, and pages from vacuum, 1, or
maybe even 0.
--
Jim C. Nasby, Database Consultant decibel@decibel.org
Give your computer some brain candy! www.distributed.net Team #1828

Windows: "Where do you want to go today?"
Linux: "Where do you want to go tomorrow?"
FreeBSD: "Are you guys coming, or what?"

---------------------------(end of broadcast)---------------------------
TIP 4: Don't 'kill -9' the postmaster

Tom Lane wrote:
> "Jim C. Nasby" <decibel@decibel.org> writes:
>
>>The advantage of using a counter instead of a simple active
>>bit is that buffers that are (or have been) used heavily will be able to
>>go through several sweeps of the clock before being freed. Infrequently
>>used buffers (such as those from a vacuum or seq. scan), would get
>>marked as inactive the first time they were hit by the clock hand.

> What I'm envisioning is that pinning (actually unpinning) a buffer
> increments the counter (up to some limit), and the clock sweep
> decrements it (down to zero), and only buffers with count zero are taken
> by the sweep for recycling.

Would there be any value in incrementing by 2 for index accesses and 1
for seq-scans/vacuums? Actually, it should probably be a ratio based on
random_page_cost shouldn't it?

--
Richard Huxton
Archonet Ltd

---------------------------(end of broadcast)---------------------------
TIP 5: Have you checked our extensive FAQ?

http://www.postgresql.org/docs/faq