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)
