Re: [HACKERS] Clock with Adaptive Replacement
Jim Nasby writes: > On 2/12/16 9:55 AM, Robert Haas wrote: >> I think it's important to spend time and energy figuring out exactly >> what the problems with our current algorithm are. We know in general >> terms that usage counts tend to converge to either 5 or 0 and >> therefore sometimes evict buffers both at great cost and almost > Has anyone done testing on the best cap to usage count? IIRC 5 was > pulled out of thin air. My recollection is that there was some testing behind it ... but that was back around 2005 so it seems safe to assume that that testing is no longer terribly relevant. In particular, I'm sure it was tested with shared_buffer counts far smaller than what we now consider sane. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Clock with Adaptive Replacement
On 2/12/16 9:55 AM, Robert Haas wrote: I think it's important to spend time and energy figuring out exactly what the problems with our current algorithm are. We know in general terms that usage counts tend to converge to either 5 or 0 and therefore sometimes evict buffers both at great cost and almost Has anyone done testing on the best cap to usage count? IIRC 5 was pulled out of thin air. Actually, I don't recall ever seeing a clock sweep that supported more than a single bit, though often there are multiple 'pools' a buffer could be in (ie: active vs inactive in most unix VMs). If you have a reasonable amount of 1 or 0 count buffers then this probably doesn't matter too much, but if your working set is significantly higher than shared buffers then you're probably doing a LOT of full sweeps to try and get something decremented down to 0. randomly. But what's a lot less clear is how much that actually hurts us given that we are relying on the OS cache anyway. It may be that we need to fix some other things before or after improving the buffer eviction algorithm before we actually get a performance benefit. I suspect, for example, that a lot of the problems with large shared_buffers settings have to do with the bgwriter and checkpointer behavior rather than with the buffer eviction algorithm; and that others have to do with cache duplication between PostgreSQL and the operating system. So, I would suggest (although of course it's up to It would be nice if there was at least an option to instrument how long an OS read request took, so that you could guage how many requests were coming from the OS vs disk. (Obviously direct knowledge from the OS is even better, but I don't think those APIs exist.) you) that you might want to focus on experiments that will help you understand where the problems are before you plunge into writing code to fix them. +1 -- Jim Nasby, Data Architect, Blue Treble Consulting, Austin TX Experts in Analytics, Data Architecture and PostgreSQL Data in Trouble? Get it in Treble! http://BlueTreble.com -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Clock with Adaptive Replacement
Thank you very much for response. I am not sure that CART can significantly improve PostgreSQL performance - I just want to know opinion of community about CAR/CART and other possible alternative to GCLOCK algorithm. Looks like it CAR really provides better cache hit ratio and so at some workloads should increase Postgres performance. But now amount of memory at servers is large enough to completely keep most of typical databases in cache. So time of locating buffer in cache is more critical then time of buffer eviction. And here CART doesn't provide any benefits comparing with GCLOCK algorithm. One of the problems with GCLOCK algorithm from my point of view is that for large caches, containing larger number of pages locating victim page can take substantial amount of time, because we have to perform several turnovers before some count becomes zero. In theory CART can address this problem because there are not counters - justs single bit per page. On 12.02.2016 18:55, Robert Haas wrote: On Thu, Feb 11, 2016 at 4:02 PM, Konstantin Knizhnik wrote: What do you think about improving cache replacement clock-sweep algorithm in PostgreSQL with adaptive version proposed in this article: http://www-cs.stanford.edu/~sbansal/pubs/fast04.pdf Are there some well known drawbacks of this approach or it will be interesting to adopt this algorithm to PostgreSQL and measure it impact om performance under different workloads? I find this ten years old thread: http://www.postgresql.org/message-id/flat/d2jkde$6bg$1...@sea.gmane.org#d2jkde$6bg$1...@sea.gmane.org but it mostly discus possible patent issues with another algorithm ARC (CAR is inspired by ARC, but it is different algorithm). As far as I know there are several problems with current clock-sweep algorithm in PostgreSQL, especially for very large caches. May be CAR can address some of them? Maybe, but the proof of the pudding is in the eating. Just because an algorithm is smarter, newer, and better in general than our current algorithm - and really, it wouldn't be hard - doesn't mean that it will actually solve the problems we care about. A few of my EnterpriseDB colleagues spent a lot of time benchmarking various tweaks to our current algorithm last year and were unable to construct a test case where it sped anything up. If they tried the same tweaks against the 9.4 source base, they could get a speedup. But 9.5 had locking improvements around buffer eviction, and with those improvements committed there was no longer any measurable benefit to improving the quality of buffer eviction decisions. That's a surprising result, to me anyway, and somebody else might well find a test case where a benefit can be shown - but our research was not successful. I think it's important to spend time and energy figuring out exactly what the problems with our current algorithm are. We know in general terms that usage counts tend to converge to either 5 or 0 and therefore sometimes evict buffers both at great cost and almost randomly. But what's a lot less clear is how much that actually hurts us given that we are relying on the OS cache anyway. It may be that we need to fix some other things before or after improving the buffer eviction algorithm before we actually get a performance benefit. I suspect, for example, that a lot of the problems with large shared_buffers settings have to do with the bgwriter and checkpointer behavior rather than with the buffer eviction algorithm; and that others have to do with cache duplication between PostgreSQL and the operating system. So, I would suggest (although of course it's up to you) that you might want to focus on experiments that will help you understand where the problems are before you plunge into writing code to fix them. -- Konstantin Knizhnik Postgres Professional: http://www.postgrespro.com The Russian Postgres Company -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Clock with Adaptive Replacement
On Thu, Feb 11, 2016 at 4:02 PM, Konstantin Knizhnik wrote: > What do you think about improving cache replacement clock-sweep algorithm in > PostgreSQL with adaptive version proposed in this article: > > http://www-cs.stanford.edu/~sbansal/pubs/fast04.pdf > > Are there some well known drawbacks of this approach or it will be > interesting to adopt this algorithm to PostgreSQL and measure it impact om > performance under different workloads? > I find this ten years old thread: > > http://www.postgresql.org/message-id/flat/d2jkde$6bg$1...@sea.gmane.org#d2jkde$6bg$1...@sea.gmane.org > > but it mostly discus possible patent issues with another algorithm ARC (CAR > is inspired by ARC, but it is different algorithm). > As far as I know there are several problems with current clock-sweep > algorithm in PostgreSQL, especially for very large caches. > May be CAR can address some of them? Maybe, but the proof of the pudding is in the eating. Just because an algorithm is smarter, newer, and better in general than our current algorithm - and really, it wouldn't be hard - doesn't mean that it will actually solve the problems we care about. A few of my EnterpriseDB colleagues spent a lot of time benchmarking various tweaks to our current algorithm last year and were unable to construct a test case where it sped anything up. If they tried the same tweaks against the 9.4 source base, they could get a speedup. But 9.5 had locking improvements around buffer eviction, and with those improvements committed there was no longer any measurable benefit to improving the quality of buffer eviction decisions. That's a surprising result, to me anyway, and somebody else might well find a test case where a benefit can be shown - but our research was not successful. I think it's important to spend time and energy figuring out exactly what the problems with our current algorithm are. We know in general terms that usage counts tend to converge to either 5 or 0 and therefore sometimes evict buffers both at great cost and almost randomly. But what's a lot less clear is how much that actually hurts us given that we are relying on the OS cache anyway. It may be that we need to fix some other things before or after improving the buffer eviction algorithm before we actually get a performance benefit. I suspect, for example, that a lot of the problems with large shared_buffers settings have to do with the bgwriter and checkpointer behavior rather than with the buffer eviction algorithm; and that others have to do with cache duplication between PostgreSQL and the operating system. So, I would suggest (although of course it's up to you) that you might want to focus on experiments that will help you understand where the problems are before you plunge into writing code to fix them. -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
[HACKERS] Clock with Adaptive Replacement
Hi hackers, What do you think about improving cache replacement clock-sweep algorithm in PostgreSQL with adaptive version proposed in this article: http://www-cs.stanford.edu/~sbansal/pubs/fast04.pdf Are there some well known drawbacks of this approach or it will be interesting to adopt this algorithm to PostgreSQL and measure it impact om performance under different workloads? I find this ten years old thread: http://www.postgresql.org/message-id/flat/d2jkde$6bg$1...@sea.gmane.org#d2jkde$6bg$1...@sea.gmane.org but it mostly discus possible patent issues with another algorithm ARC (CAR is inspired by ARC, but it is different algorithm). As far as I know there are several problems with current clock-sweep algorithm in PostgreSQL, especially for very large caches. May be CAR can address some of them? -- Konstantin Knizhnik Postgres Professional: http://www.postgrespro.com The Russian Postgres Company -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers