[FLINK-9423] Implement efficient deletes for heap based timer service

• Type: Improvement
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Affects Version/s: 1.5.0
• Fix Version/s: 1.6.0
• Assignee: Stefan Richter
• Reporter: Stefan Richter
• Created: 23/May/18 13:00
• Updated: 28/Feb/19 11:14
• Resolved: 31/May/18 07:59

Description

The current data structures in the `HeapInternalTimerService` are not able to support efficient timer deletes, the complexity is currently O(n), where n is the number of registered timers.

 

We can keep track of timer's positions in the priority queue and (in combination with the already existing set/map) have a more efficient algorithm for deletes.

Issue Links

• is depended upon by: FLINK-9440 Allow cancelation and reset of timers
• links to: GitHub Pull Request #6062