You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@flink.apache.org by "Lijie Wang (Jira)" <ji...@apache.org> on 2023/01/03 08:21:00 UTC
[jira] [Updated] (FLINK-30544) Speed up finding minimum watermark across all channels by introducing heap-based algorithm
[ https://issues.apache.org/jira/browse/FLINK-30544?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Lijie Wang updated FLINK-30544:
-------------------------------
Description:
Currently, every time a task receives a watermark, it tries to update the minimum watermark.Currently, we use the traversal algorithm to find the minimum watermark across all channels(see [StatusWatermarkValue#findAndOutputNewMinWatermarkAcrossAlignedChannels|https://github.com/apache/flink/blob/master/flink-streaming-java/src/main/java/org/apache/flink/streaming/runtime/watermarkstatus/StatusWatermarkValve.java#:~:text=private%20void-,findAndOutputNewMinWatermarkAcrossAlignedChannels,-(DataOutput%3C%3F%3E] for details), and the time complexity is O(N), where N is the number of channels.
We can optimize it by introducing a heap-based algorthim, reducing the time complexity to O(log(N))
was:
Currently, every time a task receives a watermark, it tries to update the minimum watermark.Currently, we use the traversal algorithm to find the minimum watermark across all channels(see [StatusWatermarkValue#findAndOutputNewMinWatermarkAcrossAlignedChannels|https://github.com/apache/flink/blob/master/flink-streaming-java/src/main/java/org/apache/flink/streaming/runtime/watermarkstatus/StatusWatermarkValve.java#:~:text=private%20void-,findAndOutputNewMinWatermarkAcrossAlignedChannels,-(DataOutput%3C%3F%3E] for details), and the time complexity is O(N), where N is the number of channels.
We can optimize it by introducing a heap-based algorthim, reducing the time complexity to O(log(N)))
> Speed up finding minimum watermark across all channels by introducing heap-based algorithm
> ------------------------------------------------------------------------------------------
>
> Key: FLINK-30544
> URL: https://issues.apache.org/jira/browse/FLINK-30544
> Project: Flink
> Issue Type: Improvement
> Components: Runtime / Task
> Reporter: Lijie Wang
> Assignee: Lijie Wang
> Priority: Major
> Fix For: 1.17.0
>
>
> Currently, every time a task receives a watermark, it tries to update the minimum watermark.Currently, we use the traversal algorithm to find the minimum watermark across all channels(see [StatusWatermarkValue#findAndOutputNewMinWatermarkAcrossAlignedChannels|https://github.com/apache/flink/blob/master/flink-streaming-java/src/main/java/org/apache/flink/streaming/runtime/watermarkstatus/StatusWatermarkValve.java#:~:text=private%20void-,findAndOutputNewMinWatermarkAcrossAlignedChannels,-(DataOutput%3C%3F%3E] for details), and the time complexity is O(N), where N is the number of channels.
> We can optimize it by introducing a heap-based algorthim, reducing the time complexity to O(log(N))
--
This message was sent by Atlassian Jira
(v8.20.10#820010)