[FLINK-6359] Utilize Hierarchical Timing Wheels for performant timer

• Type: Improvement
• Status: Closed
• Priority: Major
• Resolution: Won't Do
• Component/s: API / DataStream, Runtime / Task
• Labels: perfomance
• Assignee: Unassigned
• Reporter: Ted Yu
• Created: 22/Apr/17 14:42
• Updated: 17/Jan/20 13:25
• Resolved: 17/Jan/20 13:25

Description

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

 * 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.

We should consider porting the above over to facilitate performant timer.