[
https://issues.apache.org/jira/browse/FLINK-22767?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Zhilong Hong updated FLINK-22767:
---------------------------------
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#tryFindAvailableProducerExecutionSlotSharingGroupFor}}
located in {{LocalInputPreferredSlotSharingStrategy}}.
The original implementation is:
{code:java}
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{code}
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.
was:
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#tryFindAvailableProducerExecutionSlotSharingGroupFor}}
located in {{LocalInputPreferredSlotSharingStrategy}}.
The original implementation is:
{code:java}
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{code}
This procedure has O(N^2) complexity.
Instead of iterating the ExecutionSlotSharingGroup of producer vertices for all
consumed result partitions, we can maintain an available
ExecutionSlotSharingGroup set for the consumed result partitions. Once the
group is assigned, it will be removed from the available 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.
> Optimize the initialization of LocalInputPreferredSlotSharingStrategy
> ---------------------------------------------------------------------
>
> Key: FLINK-22767
> URL: https://issues.apache.org/jira/browse/FLINK-22767
> Project: Flink
> Issue Type: Sub-task
> Components: Runtime / Coordination
> Affects Versions: 1.13.0
> Reporter: Zhilong Hong
> Assignee: Zhilong Hong
> Priority: Major
> Labels: pull-request-available
>
> 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#tryFindAvailableProducerExecutionSlotSharingGroupFor}}
> located in {{LocalInputPreferredSlotSharingStrategy}}.
> The original implementation is:
> {code:java}
> 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{code}
> 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.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
