Lijie Wang created FLINK-30544:
----------------------------------
Summary: 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
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)
