[jira] [Created] (HIVE-13471) TinyLFU cache

["Ben Manes (JIRA)" <ji...@apache.org>]

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)