wanglijie95 opened a new pull request, #21588:
URL: https://github.com/apache/flink/pull/21588
## What is the purpose of the change
Currently, every time a task receives a watermark, it tries to update the
minimum watermark. In current implementation, we use the traversal algorithm to
find the minimum watermark across all channels(see
`StatusWatermarkValue#findAndOutputNewMinWatermarkAcrossAlignedChannels` for
details), and the time complexity is `O(N)`, where `N` is the number of
channels.
In this pr, we optimize it by introducing a heap-based algorthim, reducing
the time complexity to `O(log(N))`
## Verifying this change
This change is already covered by the `StatusWatermarkValveTest`
## 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): (**no**)
- Anything that affects deployment or recovery: JobManager (and its
components), Checkpointing, Kubernetes/Yarn, ZooKeeper: (**no**)
- 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**)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
