Preempt ordering issue

[raravena80]

Description

We have 2 nodes with 4 GPU each and we have the following jobs deployed

• 1 Job (Job 2 ) with a high priority class with 4 tasks that need 1 GPU each and takes up 1 whole node
• 1 Job (Job 1) with low priority class and 2 replicas that need 1 GPU each
  • 1 job (Job 3) with low priority class and 2 replicas that need 1 GPU each
  • The low priority jobs takes up all the GPU capacity of the 2nd Node
• A new Job (Job 4) with 1 replica that needs 1 GPU each is deployed
  • For each task in the New Job (Job 4) the following above preemption flow takes place
    • For the first replica, the eligible Node is the 2nd node where the low priority jobs are deployed
    • The victim preemptable tasks are the tasks that are part of the low priority jobs
    • Since the lower priority class has the same priorityclass the ordering is taken by either the creationTimestamp or the task UID. Which causes the ranking to be nondeterministic.

      Victims list 
      Task (dev/preempt-dev-job1-low-priority-nginx-0)
      Task (dev/preempt-dev-job3-low-nginx-1)
      Task (:dev/preempt-dev-job1-low-priority-nginx-1)
      Task (:dev/preempt-dev-job3-low-nginx-0)
      

    • This task to be evicted as the first highest priority task is preempt-dev-job3-low-nginx-1 which is part of a gang job.

      Preemptor task <dev/preempt-dev-job4-high-nginx-0> on Node <ip-10-64-x-x.ec2.internal>. 
      Preemptee task preempt-dev-job3-low-nginx-1
      

    • When the preemption flow runs again for the second replica of the high priority job the victim list is again prioritized in non deterministic manner without considering gang semantics of the task that was already pipelined for eviction:

      Preemptor <mltraining-dev/preempt-dev-job4-high-nginx-1> on Node <ip-10-64-x-x.ec2.internal> victims
      Task (dev/preempt-dev-job1-low-priority-nginx-0)
      Task (dev/preempt-dev-job1-low-priority-nginx-1)
      Task (dev/preempt-dev-job3-low-nginx-0)
      

    • This leads to task from another gang job being evicted

      Premptor <dev/preempt-dev-job4-high-nginx-1> on Node <ip-10-64-x-x.ec2.internal>. preemptee 
      preempt-dev-job1-low-priority-nginx-1
      

    • This leads 2 gang jobs being terminated and 4 GPU being freed instead of 2
    • Notice that the the preemptees preempt-dev-job3-low-nginx-1 and preempt-dev-job1-low-priority-nginx-1 always show as second on the victims list (Those are the ones picked as victims)

Steps to reproduce the issue

1. See description

Describe the results you received and expected

Expect to always to have consistent ordering for preempting victims.

What version of Volcano are you using?

1.10

Any other relevant information

No response

[hwdef]

I will check this later
/cc

[hwdef]

Thank you for the scene you mentioned, which is very detailed.
I think the modification you made in PR #3960 can solve the problem, but we have to consider the namespace.

[hwdef]

@lowang-bh @Monokaix @JesseStutler
PTAL, Do you have any suggestions?

[JesseStutler]

This leads 2 gang jobs being terminated and 4 GPU being freed instead of 2, after checking your scenario, preempt-dev-job3-low-nginx-1 and preempt-dev-job1-low-priority-nginx-1 will be evicted to free 2GPUs, why is 4GPU will be freed?

I didn't get why your PR fixes the problem you're talking about, in the problem you're describing it doesn't make a difference if the Job is sorted by UUID or by Name, if MinAvailable is 1 and the gang plugin is turned on, both job-1 and job-3 can't be preempted below 1 replica

[raravena80]

preempt-dev-job3-low-nginx-1 and preempt-dev-job1-low-priority-nginx-1 both have and need 4 GPUs broken down in 2 separate nodes.

preempt-dev-job3-low-nginx-1 -> node 1 (2 GPUs), node 2 (2 GPUs)
preempt-dev-job1-low-priority-nginx-1 -> node 1 (2 GPUs), node 2 (GPUs)

I didn't get why your PR fixes the problem you're talking about, in the problem you're describing it doesn't make a difference if the Job is sorted by UUID or by Name, if MinAvailable is 1 and the gang plugin is turned on, both job-1 and job-3 can't be preempted below 1 replica

I believe we have MinAvailable 0 (or default). What we found is that when the victim list on a node (tasks) was sorted by UUID rather than by name, the sorting order wasn't consistent across all nodes. Makes sense?

[JesseStutler]

First of all, I am a little confused about the description of your issue. You said that the 4 pods of job-2 occupy the 4 GPUs of Node-1, and then job2 and job3 each have two replicas, occupying node-2, so it should be preempt-dev-job1-low-priority-nginx-1(node 2, 1GPU), preempt-dev-job1-low-priority-nginx-0(node 2, 1GPU), preempt-dev-job3-low-nginx-1 (node2,1GPU), preempt-dev-job3-low-nginx-0(node2, 1GPU):

• 1 Job (Job 2 ) with a high priority class with 4 tasks that need 1 GPU each and takes up 1 whole node

• 1 Job (Job 1) with low priority class and 2 replicas that need 1 GPU each

  • 1 job (Job 3) with low priority class and 2 replicas that need 1 GPU each
  • The low priority jobs takes up all the GPU capacity of the 2nd Node

Besides, the logic of the code is:

1. First filter out all the pods on all nodes, and then sort
2. Sort pods according to job order, and then sort them according to pods.

This is not related to node order, and your minAvailable is 0, both job2 and job3's priorities are the same, so there is no difference between UUID and Name. job3's pods or job2's pods will be preempted first.

volcano/pkg/scheduler/actions/preempt/preempt.go

Lines 261 to 276 in 7584551

	for _, task := range node.Tasks {
	if filter == nil {
	preemptees = append(preemptees, task.Clone())
	} else if filter(task) {
	preemptees = append(preemptees, task.Clone())
	}
	}
	victims := ssn.Preemptable(preemptor, preemptees)
	metrics.UpdatePreemptionVictimsCount(len(victims))
	if err := util.ValidateVictims(preemptor, node, victims); err != nil {
	klog.V(3).Infof("No validated victims on Node <%s>: %v", node.Name, err)
	continue
	}
	victimsQueue := ssn.BuildVictimsPriorityQueue(victims)

[raravena80]

Thanks for the feedback. The last explanation was different from the original one in the issue (I'm actually relaying information from one of my teammates)

We do have fork where we changed sorting from job UID to job Name and it's working for us. (we were seeing 2 different jobs with the same UID)

Do you know where UID comes from? what guarantees that it's always unique?

Also, happy to chat on the CNCF slack if you are there.

Thanks!