[FLINK-22767] Optimize the initialization of LocalInputPreferredSlotSharingStrategy

• Type: Sub-task
• Status: Closed
• Priority: Major
• Resolution: Done
• Affects Version/s: 1.13.0
• Fix Version/s: 1.14.0
• Component/s: Runtime / Coordination
• Labels: pull-request-available
• Assignee: Zhilong Hong
• Reporter: Zhilong Hong
• Created: 25/May/21 08:09
• Updated: 15/Aug/21 11:50
• Resolved: 15/Aug/21 11:50

Description

Based on the scheduler benchmark introduced in FLINK-21731, we find that during the initialization of LocalInputPreferredSlotSharingStrategy, there's a procedure that has O(N^2) complexity: ExecutionSlotSharingGroupBuilder#build located in LocalInputPreferredSlotSharingStrategy.

The original implementation is: 

for all SchedulingExecutionVertex in DefaultScheduler:
  for all consumed SchedulingResultPartition of the SchedulingExecutionVertex:
    get the result partition's producer vertex and determine the ExecutionSlotSharingGroup where the producer vertex locates is available for current vertex

This procedure has O(N^2) complexity.

Instead of iterating over the ExecutionSlotSharingGroups of producer vertices for all consumed result partitions, we can maintain a set of all available ExecutionSlotSharingGroups for the consumed result partitions. Once a group is assigned, it will be removed from the available group set. This will decrease the complexity from O(N^2) to O(N).

The optimization of this procedure will speed up the initialization of DefaultScheduler. It will accelerate the submission of a new job, especially for OLAP jobs.

Issue Links

• links to: GitHub Pull Request #16687