[FLINK-21330] Optimize the performance of PipelinedRegionSchedulingStrategy

• Type: Sub-task
• Status: Closed
• Priority: Major
• Resolution: Fixed
• Fix Version/s: 1.13.0
• Component/s: Runtime / Coordination
• Labels: pull-request-available pull-requests-available
• Assignee: Zhilong Hong
• Reporter: Zhilong Hong
• Created: 09/Feb/21 07:28
• Updated: 28/Aug/21 10:34
• Resolved: 29/Mar/21 17:39

Description

PipelinedRegionSchedulingStrategy is used for task scheduling. Its initialization is located at PipelinedRegionSchedulingStrategy#init. The initialization can be divided into two parts:

1. Calculating consumed result partitions of SchedulingPipelinedRegions
2. Calculating the consumer pipelined region of SchedulingResultPartition

Based on FLINK-21328, the consumedResults of DefaultSchedulingPipelinedRegion can be replaced with ConsumedPartitionGroup.

Then we can optimize the procedures we mentioned above. After the optimization, the time complexity decreases from O(N^2) to O(N).

The related usage of getConsumedResults should be replaced, too. Furthermore, PipelinedRegionSchedulingStrategy#maybeScheduleRegion can be optimized at the same time.

The detailed design doc is located at: https://docs.google.com/document/d/1OjGAyJ9Z6KsxcMtBHr6vbbrwP9xye7CdCtrLvf8dFYw/edit#heading=h.a1mz4yjpry6m
 

Issue Links

• links to: GitHub Pull Request #15310