quickstep-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Harshad Deshmukh <hars...@cs.wisc.edu>
Subject Re: Eviction Policy Algorithm
Date Fri, 27 Apr 2018 19:21:31 GMT
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
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.



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:


Dylan Bacon
University of Wisconsin - Madison
Department of Computer Sciences

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