[jira] [Commented] (IMPALA-8690) Better eviction algorithm for data cache

["ASF subversion and git services (Jira)" <ji...@apache.org>]

    [ https://issues.apache.org/jira/browse/IMPALA-8690?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17071979#comment-17071979 ] 

ASF subversion and git services commented on IMPALA-8690:
---------------------------------------------------------

Commit 01691b998a96fd29575a3c3912377bd18fdd712f in impala's branch refs/heads/master from Joe McDonnell
[ https://gitbox.apache.org/repos/asf?p=impala.git;h=01691b9 ]

IMPALA-8690: Add LIRS cache eviction algorithm

One concern for the data cache is that the LRU eviction
algorithm is suceptible to being flushed by large
scans of low priority data. This implements the LIRS algorithm
described in "LIRS: An Efficient Low Inter-reference Recency
Set Replacement Policy to Improve Buffer Cache Performance"
by Song Jiang / Xiaodon Xhang 2002. LIRS is a scan-resistent
eviction algorithm with low performance penalty to LRU.

This introduces the startup flag data_cache_eviction_policy to
control which eviction policy to use. The only two options are
LRU and LIRS, with the default continuing to be LRU.

To accomodate the new algorithm and associated tests, some
code moved around:
1. The RLCacheShard implementation moved from util/cache/cache.cc
   to util/cache/rl-cache.cc.
2. The backend cache tests were split into multiple files.
   util/cache/cache-test.h contains shared cache testing code.
   util/cache/cache-test.cc contains generic tests that should
   work for any algorithm.
   util/cache/rl-cache-test.cc are RLCacheShard specific tests
   util/cache/lirs-cache-test.cc are LIRS specific tests
3. To make it easy for clients of the cache code to customize
   the cache eviction algorithm, the public interface changed
   from using a template to taking the policy as an argument.
4. Cache::MemoryType is removed.
5. Cache adds an Init() method to verify the validity of
   startup flags

Testing:
 - Added LIRS specific backend cache tests (lirs-cache-test)
 - Ran TPC-DS with a very small cache and concurrency to test
   corner cases with the LIRS eviction policy
 - Parameterized data-cache-test to run for both LRU and LIRS
 - Added LIRS equivalents for tests in custom_cluster/test_data_cache.py
 - Ran cache-bench with LRU and LIRS. The results are:
   Test case           | Algorithm | Lookups / sec | Hit rate
   ZIPFIAN ratio=1.00x | LRU       | 11.31M        | 99.9%
   ZIPFIAN ratio=1.00x | LIRS      | 10.09M        | 99.8%
   ZIPFIAN ratio=3.00x | LRU       | 11.36M        | 95.9%
   ZIPFIAN ratio=3.00x | LIRS      |  9.27M        | 96.4%
   UNIFORM ratio=1.00x | LRU       |  7.46M        | 99.8%
   UNIFORM ratio=1.00x | LIRS      |  6.93M        | 99.8%
   UNIFORM ratio=3.00x | LRU       |  5.63M        | 33.3%
   UNIFORM ratio=3.00x | LIRS      |  3.24M        | 33.3%
   The takeaway is that LIRS is a bit slower on lookups and
   quite a bit slower on inserts. However, they both are still
   doing millions of operations per second, so it should not
   be a bottleneck for the data cache.

Change-Id: I670fa4b2b7c93998130dc4e8b2546bb93e9a84f8
Reviewed-on: http://gerrit.cloudera.org:8080/15306
Reviewed-by: Joe McDonnell <jo...@cloudera.com>
Tested-by: Impala Public Jenkins <im...@cloudera.com>


> Better eviction algorithm for data cache
> ----------------------------------------
>
>                 Key: IMPALA-8690
>                 URL: https://issues.apache.org/jira/browse/IMPALA-8690
>             Project: IMPALA
>          Issue Type: Improvement
>          Components: Backend
>    Affects Versions: Impala 3.3.0
>            Reporter: Michael Ho
>            Assignee: Joe McDonnell
>            Priority: Major
>
> With the current implementation of data cache, all data access will be cached regardless of the access pattern. The current LRU eviction algorithm is not resistant to scan traffic so in case some users scan a big fact table, a lot of the heavily accessed items will be evicted inevitably. We should adopt better eviction algorithm (e.g. LRFU or some other well known ones in the literature). Would be nice to evaluate it against some users' traces now that IMPALA-8542 is fixed.
> In the short run, we probably need some workaround (e.g. query hints to disable caching for certain tables). Will file a separate jira for it.



--
This message was sent by Atlassian Jira
(v8.3.4#803005)

---------------------------------------------------------------------
To unsubscribe, e-mail: issues-all-unsubscribe@impala.apache.org
For additional commands, e-mail: issues-all-help@impala.apache.org