[FLINK-21920] Optimize ExecutionGraphToInputsLocationsRetrieverAdapter

• Type: Sub-task
• Status: Closed
• Priority: Major
• Resolution: Later
• Affects Version/s: 1.13.0
• Component/s: Runtime / Coordination
• Labels: auto-unassigned pull-request-available
• Assignee: Unassigned
• Reporter: Zhilong Hong
• Created: 23/Mar/21 04:06
• Updated: 28/Aug/21 13:08
• Resolved: 03/Aug/21 07:10

Description

Based on the scheduler benchmark introduced in FLINK-21731, we find that there's a procedure related to DefaultScheduler#allocateSlots that has O(N^2) complexity, which is: ExecutionGraphToInputsLocationsRetrieverAdapter#getConsumedResultPartitionsProducers.

The original implementation is:

for all SchedulingExecutionVertex in DefaultScheduler:
  for all ConsumedPartitionGroup of the SchedulingExecutionVertex:
    for all IntermediateResultPartition in the ConsumedPartitionGroup:
      get producer of the IntermediateResultPartition 

This procedure has O(N^2) complexity.

We can see that for each SchedulingExecutionVertex, the producers of its ConsumedPartitionGroup is calculated separately. For the SchedulingExecutionVertices in the same ConsumerVertexGroup, they have the same ConsumedPartitionGroup. Therefore, we don't need to calculate the producers over and over again. We can use a local cache to cache the producers. This will decrease the complexity from O(N^2) to O(N).

 

Issue Links

• links to: GitHub Pull Request #15387