You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@flink.apache.org by "ASF GitHub Bot (JIRA)" <ji...@apache.org> on 2018/05/23 13:44:00 UTC
[jira] [Commented] (FLINK-9423) Implement efficient deletes for
heap based timer service
[ https://issues.apache.org/jira/browse/FLINK-9423?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=16487272#comment-16487272 ]
ASF GitHub Bot commented on FLINK-9423:
---------------------------------------
GitHub user StefanRRichter opened a pull request:
https://github.com/apache/flink/pull/6062
[FLINK-9423][state] Implement efficient deletes for heap-based timer …
…service.
## What is the purpose of the change
This PR introduces `InternalTimerHeap`, as data structure of in-flight timers that are stored in memory. This structure is a combination of the previous `PriorityQueue` and `HashSet` that have previously been used by the `HeapInternalTimerService`, enhanced by a support for faster deletion of timers.
## Brief change log
- Made `InternalTimer` and interface, `TimerHeapInternalTimer` is currently the only implementation. The interface is in place to hide management methods like `setTimerHeapIndex(...)` from code that deals with the net information of timers.
- Introduced `InternalTimerHeap` structure and replaced PQ+set in `HeapInternalTimerService`.
## Verifying this change
Added the test `InternalTimerHeapTest` for `InternalTimerHeap`. Everything else is covered by existing tests.
## Does this pull request potentially affect one of the following parts:
- Dependencies (does it add or upgrade a dependency): (no)
- The public API, i.e., is any changed class annotated with `@Public(Evolving)`: (no)
- The serializers: (no)
- The runtime per-record code paths (performance sensitive): (yes)
- Anything that affects deployment or recovery: JobManager (and its components), Checkpointing, Yarn/Mesos, ZooKeeper: (yes)
- The S3 file system connector: (no)
## Documentation
- Does this pull request introduce a new feature? (no)
- If yes, how is the feature documented? (not applicable)
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/StefanRRichter/flink timer-effcient-deletes
Alternatively you can review and apply these changes as the patch at:
https://github.com/apache/flink/pull/6062.patch
To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:
This closes #6062
----
commit fffc7ff6750509de2c97ea7ed44d2404669acd35
Author: Stefan Richter <s....@...>
Date: 2018-05-08T14:00:55Z
[FLINK-9423][state] Implement efficient deletes for heap-based timer service.
----
> Implement efficient deletes for heap based timer service
> --------------------------------------------------------
>
> Key: FLINK-9423
> URL: https://issues.apache.org/jira/browse/FLINK-9423
> Project: Flink
> Issue Type: Improvement
> Components: Streaming
> Affects Versions: 1.6.0
> Reporter: Stefan Richter
> Assignee: Stefan Richter
> Priority: Major
>
> 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.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)