quickstep-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Navneet Potti <nav...@gmail.com>
Subject Re: Eviction Policy Algorithm
Date Fri, 27 Apr 2018 19:39:44 GMT
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 <harshad@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 <dbacon@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
> dbacon@wisc.edu
> 


Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message