[jira] [Commented] (FLINK-6359) Utilize Hierarchical Timing Wheels for performant timer

["Ted Yu (JIRA)" <ji...@apache.org>]

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

Ted Yu commented on FLINK-6359:
-------------------------------

[~StephanEwen] gave the following background on the mailing thread:

Here are the thoughts why I advocated to not expose the "delete" initially:

  (1) The original heap timer structure was not very sophisticated and could not support efficient timer deletion (as Gyula indicated). As a core rule in large scale systems: Never expose an operation you cannot do efficiently, hence there should be no delete operation until there is a better heap timer structure.

  (2) In general, we need timers to be able to go out-of core as well (there may be many many timers in certain cases). That's why we picked a RocksDB Timer Service for the large scale timers.

  (3) An additional challenge is that timers are per key and need to be stored in a key-partitioned fashion on checkpoint. Any implementation needs to handle that as well (so we probably need an extension of the classical time wheel structures)

If all this is solved and supports efficient deletes, then we can add that operation again, in my opinion.

> 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)