Thread: Re: [PATCHES] update i386 spinlock for hyperthreading
Bruce Momjian <pgman@candle.pha.pa.us> writes:
> Manfred Spraul wrote:
>> I remember there were patches that tried other algorithms instead of the
>> simple LRU for the buffer manager. Has anyone tried to change the
>> locking of the buffer manager?
> CVS HEAD already has an Adaptive Replacement Cache (ARC) for buffer
> replacement.
That's irrelevant to the problem, though. Unless the ARC code uses data
structures that are more amenable to localized locking than the old
global buffer freelist. (Jan?)
regards, tom lane
Tom Lane wrote: >Bruce Momjian <pgman@candle.pha.pa.us> writes: > > >>Manfred Spraul wrote: >> >> >>>I remember there were patches that tried other algorithms instead of the >>>simple LRU for the buffer manager. Has anyone tried to change the >>>locking of the buffer manager? >>> >>> > > > >>CVS HEAD already has an Adaptive Replacement Cache (ARC) for buffer >>replacement. >> >> > >That's irrelevant to the problem, though. Unless the ARC code uses data >structures that are more amenable to localized locking than the old >global buffer freelist. (Jan?) > > regards, tom lane > > Not that I know of. The new strategy uses one shared hash table like the old, and one buffer pool as well. It grabs the same old Bufmgr lock during the lookup+replacement decision process, gives it up during eventual IO, grabs it again when done with the IO. As a matter of fact, the strategy itself does no locking at all. Like the old LRU code it simply assumes that the buffer manager holds the lock during calls. Jan -- #======================================================================# # It's easier to get forgiveness for being wrong than for being right. # # Let's break this rule - forgive me. # #================================================== JanWieck@Yahoo.com #
Jan Wieck <JanWieck@Yahoo.com> writes:
>> That's irrelevant to the problem, though. Unless the ARC code uses data
>> structures that are more amenable to localized locking than the old
>> global buffer freelist. (Jan?)
> the strategy itself does no locking at all. Like the old LRU code it
> simply assumes that the buffer manager holds the lock during calls.
Okay, I suspected as much but wasn't sure.
Manfred's numbers definitely say that we need to find a way to break
down the BufMgrLock into multiple finer-grain locks. We already have
all those per-buffer LWLocks, but I don't see how to apply those to
the problem of managing the global lookup and replacement datastructures.
Anyone see an attack path here?
regards, tom lane
Tom Lane wrote: > Jan Wieck <JanWieck@Yahoo.com> writes: > >> That's irrelevant to the problem, though. Unless the ARC code uses data > >> structures that are more amenable to localized locking than the old > >> global buffer freelist. (Jan?) > > > the strategy itself does no locking at all. Like the old LRU code it > > simply assumes that the buffer manager holds the lock during calls. > > Okay, I suspected as much but wasn't sure. > > Manfred's numbers definitely say that we need to find a way to break > down the BufMgrLock into multiple finer-grain locks. We already have > all those per-buffer LWLocks, but I don't see how to apply those to > the problem of managing the global lookup and replacement datastructures. > > Anyone see an attack path here? Should we have one lock per hash bucket rather than one for the entire hash? -- 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, Pennsylvania19073
Bruce Momjian wrote: >>Anyone see an attack path here? >> >> > >Should we have one lock per hash bucket rather than one for the entire >hash? > > That's the simple part. The problem is the aging strategy: we need a strategy that doesn't rely on a global list that's updated after every lookup. If I understand the ARC code correctly, there is a STRAT_MRU_INSERT(cdb, STRAT_LIST_T2) that happen in every lookup. -- Manfred
Manfred Spraul wrote: > Bruce Momjian wrote: > >>>Anyone see an attack path here? >>> >>> >> >>Should we have one lock per hash bucket rather than one for the entire >>hash? >> >> > That's the simple part. The problem is the aging strategy: we need a > strategy that doesn't rely on a global list that's updated after every > lookup. If I understand the ARC code correctly, there is a > STRAT_MRU_INSERT(cdb, STRAT_LIST_T2) that happen in every lookup. Moving the Cache Directory Block (cdb) on a hit to the MRU position of the appropriate queue "is the bookkeeping" of this strategy. The whole algorithm is based on it, and I don't see yet how to avoid that without opening a huge can of worms that look like deadlocks. But I'll think about it for a while. Jan -- #======================================================================# # It's easier to get forgiveness for being wrong than for being right. # # Let's break this rule - forgive me. # #================================================== JanWieck@Yahoo.com #
Jan Wieck wrote: > Manfred Spraul wrote: > > Bruce Momjian wrote: > > > >>>Anyone see an attack path here? > >>> > >>> > >> > >>Should we have one lock per hash bucket rather than one for the entire > >>hash? > >> > >> > > That's the simple part. The problem is the aging strategy: we need a > > strategy that doesn't rely on a global list that's updated after every > > lookup. If I understand the ARC code correctly, there is a > > STRAT_MRU_INSERT(cdb, STRAT_LIST_T2) that happen in every lookup. > > Moving the Cache Directory Block (cdb) on a hit to the MRU position of > the appropriate queue "is the bookkeeping" of this strategy. The whole > algorithm is based on it, and I don't see yet how to avoid that without > opening a huge can of worms that look like deadlocks. But I'll think > about it for a while. If we can't eliminate the global lock, and we reduce its duration? -- 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, Pennsylvania19073
Jan Wieck wrote: >Moving the Cache Directory Block (cdb) on a hit to the MRU position of >the appropriate queue "is the bookkeeping" of this strategy. The whole >algorithm is based on it, and I don't see yet how to avoid that without >opening a huge can of worms that look like deadlocks. But I'll think >about it for a while. > I feared that. Are there strategies that do not rely on a global lock? The Linux kernel uses a lazy LRU with referenced bits: on access, the referenced bit is set. The freespace logic takes pages from the end of a linked list, and checks that bit: if it's set, then the page is moved back to the top of the list. Otherwise it's a candidate for replacement. Pages start at the head of that pseudo-lru list, with the reference bit clear: that way a page that is accessed only once has a lower priority than a frequently accessed page. At least that's how I understand the algorithm. -- Manfred
Bruce Momjian <pgman@candle.pha.pa.us> writes:
> If we can't eliminate the global lock, and we reduce its duration?
It'd be a big win even if we could just arrange that ReadBuffer and
ReleaseBuffer don't *both* grab the same global lock.
Can we logically separate the buffer lookup hashtable from the freelist
maintenance code? I am wondering about having two locks, one for each
of those areas. In principle I think a fast-path ReadBuffer (one that
doesn't need to do I/O because the desired page is in a buffer already)
would need to get only a share lock on the lookup table, and never lock
the freelist structure at all. ReleaseBuffer would need a write lock
on the freelist, but need not touch the lookup table. Only in the case
where ReadBuffer has to do I/O, and therefore needs to acquire a free
buffer to read the page into, do you need locks on both structures ---
and with sufficient care, you might not need to lock them both at the
same time, even in that path.
To make this work, we would have to recognize that the "freelist" might
be out of date --- that is, a page that had been in the freelist because
it has zero pins would be left in the freelist by ReadBuffer, and anyone
trying to remove it from the freelist for reuse would have to notice
that it has positive pin count and realize that it's not really free.
But that should be pretty simple.
Beyond that we could think about locking just parts of each of these
structures (for instance, doesn't ARC really use multiple freelists?)
but I think we ought to focus first on that basic division.
regards, tom lane
Manfred Spraul <manfred@colorfullife.com> writes:
> Are there strategies that do not rely on a global lock? The Linux kernel
> uses a lazy LRU with referenced bits: on access, the referenced bit is
> set. The freespace logic takes pages from the end of a linked list, and
> checks that bit: if it's set, then the page is moved back to the top of
> the list. Otherwise it's a candidate for replacement.
I think this is the same idea as what I was just suggesting: add an
extra check when looking for a free page, and thereby avoid having to
lock/update the global datastructure during ReadBuffer.
regards, tom lane
Tom Lane wrote: > Manfred Spraul <manfred@colorfullife.com> writes: >> Are there strategies that do not rely on a global lock? The Linux kernel >> uses a lazy LRU with referenced bits: on access, the referenced bit is >> set. The freespace logic takes pages from the end of a linked list, and >> checks that bit: if it's set, then the page is moved back to the top of >> the list. Otherwise it's a candidate for replacement. > > I think this is the same idea as what I was just suggesting: add an > extra check when looking for a free page, and thereby avoid having to > lock/update the global datastructure during ReadBuffer. Hmmmm ... speaking without having done in depth thought on this one: If there would be an easy way to determine the approximate position of a CDB inside the queue, one could just forget about moving it to the MRU position if it's in the upper 3rd or so anyway. The theory of the whole ARC strategy (which is nothing more than four LRU's with a twist) is that the access frequency of blocks is reverse proportional to their numbers (a few are high frequency used, some are medium often requested, the vast majority rather seldom). That means, that the buffers in the upper third or quarter of the T1 queue (and that's the critical one) are basically circling around each other with frequent visitors from the lower regions or other queues. So if there would be a way to make a good guess on that relative queue position, that expensive CDB shuffeling can be avoided often. Jan -- #======================================================================# # It's easier to get forgiveness for being wrong than for being right. # # Let's break this rule - forgive me. # #================================================== JanWieck@Yahoo.com #
>Tom Lane > Manfred's numbers definitely say that we need to find a way to break > down the BufMgrLock into multiple finer-grain locks. We already have > all those per-buffer LWLocks, but I don't see how to apply those to > the problem of managing the global lookup and replacement datastructures. > > Anyone see an attack path here? Not specifically, but some ideas that might lead to something useful... Taking a leaf from somebody else's book is always the best way - much as has been done with the ARC algorithm itself. 1. Scaling Oracle8iT: Building Highly Scalable OLTP System Architectures James Morle ISBN: 0-201-32574-8 ...seems like an interesting purchase in this regard (I have no connection with the author) - but I can't vouch for usefulness of it. http://www.aw-bc.com/catalog/academic/product/0,4096,0201325748-TOC,00.h tml This is nothing to do with OPS or RAC, which I definitely do not advocate as an approach to the current challenges. 2. DB2 has long offered multiple BUFFERPOOLS. Why not explicitly define multiple pools and then assign specific database objects to them - each would have its own MRU list. ...that spurs some further off-the-wall ideas that follow the more usual PostgreSQL line "design for automated operation" - how to make use of multiple buffer pools without the need to manually assign database objects to them??? First a question: am I right in thinking that the problem is proportional to the number of independent actors (i.e. CPUs), but not dependant at all on the actual size of the cache? 3. Split the T1 list into 2 (maybe more?) pieces, completely independent of one another - T1a and T1b. When a T2, T1a, or T1b hit occurs, we *somehow* pick one of the T1 lists, in a pseudo random fashion and move it to the top of that list. This would clearly not be the best that ARC can achieve, but if the buffer (and therefore the list) is big enough, then the skew between the two lists might well be less than the loss of performance from having a hot single MRU list. This might be regarded as vertical partitioning. >Jan Wieck writes: >The theory of the whole ARC strategy (which is nothing more than four >LRU's with a twist) is that the access frequency of blocks is reverse >proportional to their numbers (a few are high frequency used, some are >medium often requested, the vast majority rather seldom). That means, >that the buffers in the upper third or quarter of the T1 queue (and >that's the critical one) are basically circling around each other with >frequent visitors from the lower regions or other queues. 4. Taking the analogy from (3) differently: partition T1 horizontally, like the floors of a building, or the league divisions in Football (Major/Minor? in the US, or 1st, 2nd, 3rd etc in the UK). The ARC algorithm is identical, but T1 effectively has multiple MRU points, or put another way, multiple lists all chained together. Say we give it 3 levels - T1.1 thru T1.3. When a block is first promoted from T2, it goes to the MRU of T1.3. When a hit occurs when it is in T1.3 it gets punted to the MRU of T1.2, and when a hit occurs when in T1.2 it would get promoted to T1.1 MRU. On the way down, blocks falling off of T1.1 would go to T1.2 then T1.3. The T1.1 MRU would still be hotter than the rest. The way I am thinking about this now is that the MRU points are evenly spaced, so the ARC algorithm doesn't dynamically resize them as it does with T1/T2, but that could change also. Doing things this way might mean that ARC doesn't have to remember which transaction id added it - a specific ARC tailoring feature added for PostgreSQL, since even if an UPDATE/DELETE touches it twice, it won't move very far up the list. Would that save time on the list reordering code? 4a) Perhaps MRU points should be spaced as 1/6, 1/3, 1/2 of the list, or someother fairly simple but non-linear way in an attempt to balance the hit frequency of the MRU points. Perhaps use four levels, then split 1/16, 2/16, 4/16, 8/16 (so last level if 9/16ths of list). 4b) Combine this with idea (3) above to split that list into two or more equal sized lists, T1.1a and T1.1b. 4c) Promote blocks differently, according to their content type? Put index non-leaf blocks (from fastroot down) & the rightmost leaf block that are in T1 straight into T2.1, put permanent table heap blocks & index leaf blocks into T2.2 and put temporary objects into T2.3. Would require tasting the block or enquiring details about its parent object rather than handling it blind - without regard to its contents, as ARC does now - that sounds expensive. Hope some of that helps.. Best Regards, Simon Riggs