Caution! That paper is from IBM. A lot of the caching algorithms developed there (including one <https://dl.acm.org/citation.cfm?id=2987553> I worked on, which handles the problem of blocks being of different sizes) come with patent restrictions.
> On Apr 27, 2018, at 2:21 PM, Harshad Deshmukh <hars...@cs.wisc.edu> wrote: > > Hi Dylan, > > > That's a good find! Thanks for sharing the paper. > > > I have dealt with the eviction policy code a little bit. Would you mind > describing the issues first? As far as I know, the referencing and > de-referencing of blocks is serial and sometimes causes performance > bottlenecks. We may need to analyze if the bottlenecks are due to the > eviction algorithm or synchronization involved in the eviction policy code. I > tried the following fix > https://github.com/hbdeshmukh/incubator-quickstep/commit/4b32336a1b89f70d1c17ffe7956ae6f78e691d7c > to make the synchronization a bit fine grained and it helped a bit. Please > feel free to adopt this fix. > > > As a separate discussion, we have a complicated buffer management problem for > following reasons. I am not sure if the current LRU-k eviction implementation > addresses these concerns: > > 1. Blocks could be of different sizes and have different lifetimes (stored > vs temporary). Therefore the consequences of evicting different blocks could > be different. > 2. We currently do not evict join hash tables. When memory is really > scarce, the buffer pool should evict hash tables. > > > How much attention should we pay to buffer management is more of a strategic > decision, considering that our focus is on in-memory settings. > > > Thanks, > > Harshad > > ________________________________ > From: Dylan Bacon <dba...@wisc.edu> > Sent: Friday, April 27, 2018 2:07:14 PM > To: dev@quickstep.incubator.apache.org > Subject: Eviction Policy Algorithm > > Attached screenshot of an algorithm that seems worthwhile to implement > in Quickstep for an eviction policy. The language and structure would > need to be adapted from cache pages to our database blocks, I'm not sure > how straightforward that would be. Sending this to the dev email for > broader discussion as I initially sent to individuals. Thoughts and > input are welcome. > > Source paper: > http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=C660AD720FD52C67A063B270F4B6DDF4?doi=10.1.1.105.6057&rep=rep1&type=pdf > > -- > Regards, > > Dylan Bacon > University of Wisconsin - Madison > Department of Computer Sciences > dba...@wisc.edu >
