hive-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Ben Manes (JIRA)" <j...@apache.org>
Subject [jira] [Created] (HIVE-13471) TinyLFU cache
Date Sun, 10 Apr 2016 04:56:25 GMT
Ben Manes created HIVE-13471:
--------------------------------

             Summary: TinyLFU cache
                 Key: HIVE-13471
                 URL: https://issues.apache.org/jira/browse/HIVE-13471
             Project: Hive
          Issue Type: Improvement
          Components: llap
            Reporter: Ben Manes


Hive currently uses either the [FIFO|https://github.com/apache/hive/blob/master/llap-server/src/java/org/apache/hadoop/hive/llap/cache/LowLevelFifoCachePolicy.java]
or [LRFU|https://github.com/apache/hive/blob/master/llap-server/src/java/org/apache/hadoop/hive/llap/cache/LowLevelLrfuCachePolicy.java]
caching algorithms. My understanding is that LRFU is O(lg n) and makes predictions based on
the current working set.

A more modern alternative is [TinyLFU|http://arxiv.org/pdf/1512.00727.pdf] which is O(1) by
capturing the frequency in a sketch and recency through LRU queues. This allows it to [outperforms|https://github.com/ben-manes/caffeine/wiki/Efficiency]
ARC and LIRS, two of the best policies to date.

[Caffeine|https://github.com/ben-manes/caffeine] provides a concurrent implementation by using
the write-ahead log approach to record & replay updates (see [HighScalability article|http://highscalability.com/blog/2016/1/25/design-of-a-modern-cache.html]).
It is currently being migrated to in [HBASE-15560|https://issues.apache.org/jira/browse/HBASE-15560]
and [ACCUMULO-4177|https://issues.apache.org/jira/browse/ACCUMULO-4177] for their on-heap
caches.

If there is interest let me know if I can be of help.



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)

Mime
View raw message