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)