[
https://issues.apache.org/jira/browse/FLINK-6359?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=15981740#comment-15981740
]
Ben Manes commented on FLINK-6359:
----------------------------------
Kafka also has a very nice
[implementation|https://github.com/apache/kafka/blob/trunk/core/src/main/scala/kafka/utils/timer/TimingWheel.scala]
written Scala. That shows a more generic abstraction which might offer some
inspiration.
A major difference between most implementations and Caffeine's is an
optimization around the time spans that the wheels operate in. Most use human
time units which requires using multiplication, division, and modulus
operations. Those are expensive arithmetic operations so data structures like
HashMap exploit power-of-two sizes to perform those same operations using
shifts and AND masks. Caffeine's will be used for expiration so every cache
entry is a timer, so there is care to avoid new per-entry fields. These are
perhaps micro-optimizations that Flink may be less as concerned about.
I think a port could use the power-of-two tricks for a very clean algorithm and
wrapped in a more generic API like Kafka's.
> Utilize Hierarchical Timing Wheels for performant timer
> -------------------------------------------------------
>
> Key: FLINK-6359
> URL: https://issues.apache.org/jira/browse/FLINK-6359
> Project: Flink
> Issue Type: Improvement
> Reporter: Ted Yu
>
> In this thread on mailing list:
> http://search-hadoop.com/m/Flink/VkLeQPmRa31hd5cw
> Gyula Fóra mentioned that timer deletion becomes performance bottleneck due
> to the usage of priority queue.
> Benjamin has an implementation for Hierarchical Timing Wheels (Apache
> License) :
> https://github.com/ben-manes/caffeine/blob/master/caffeine/src/main/java/com/github/benmanes/caffeine/cache/TimerWheel.java
> {code}
> * A hierarchical timer wheel to add, remove, and fire expiration events in
> amortized O(1) time. The
> * expiration events are deferred until the timer is advanced, which is
> performed as part of the
> * cache's maintenance cycle.
> {code}
> We should consider porting the above over to facilitate performant timer.
--
This message was sent by Atlassian JIRA
(v6.3.15#6346)
