follow up: coscheduling queue sort plugin starves pods

[googs1025]

Since the issue #110 has been open for a long time and has not been resolved, I would like to open a new issue as a follow up.

There is no very depth research, but there are roughly two problems I think:

• The sort plugins use InitialAttemptTimestamp to sort, which can easily cause pod starvation for pods enqueue later than pggroup's pod. Not all pods enqueued are managed by the podgroup, and there may be a large number of other pods. Therefore, it seems inappropriate to use only InitialAttemptTimestamp. based on coscheduling queue sort plugin starves pods #110 (comment)

• When considering only InitialAttemptTimestamp enqueue in podgroup, there seems to be other problems: for example, podgroup should also consider minMember, we should satisfy most of the podgroup first, and then satisfy the pods of other numbers in the podgroup.

According to the above, can it be modified like this:

1. Priority Comparison:
   First, compare the priorities of the two Pods.

2. PodGroup Check:
   to get the PodGroup info for each Pod.
   If one Pod does not belong to any PodGroup and the other does:
   We use podInfo timestamp sorting.
   If both Pods belong to PodGroups, proceed to the next step.

3. MinMember Comparison:
   For Pods belonging to PodGroups, check whether each PodGroup has met its minMember requirement.
   Give priority to PodGroups that have not yet met their minMember.
   If both PodGroups do not meet their minMember or both meet their minMember, compare the creation time of the PodGroups.

[googs1025]

similar issue: #110 (comment)

[googs1025]

@Huang-Wei @ffromani Could you please help me see if there is any problem with this idea? 🤔

[googs1025]

/kind bug

[Huang-Wei]

FYI: another proposal #661 (closed due to inactivity)

[Bowser1704]

We use podInfo timestamp sorting.
If both Pods belong to PodGroups, proceed to the next step.

It maybe cause potential issues. Consider this scenario:

• podC: t4 (with pgc t0)
• podB: t2 (with pgb t1)
• podA: t3 (without pg)

so:

podC > podB, podB > podA, podA > podC

It's a circle, the sorting order is non-deterministic.

[Bowser1704]

I believe that each pod's timestamp should be stable and independent of the comparison object.

The issue arises when we use InitialAttemptTimestamp as the non-podGroup timestamp; this can lead to normal pods being starved, as seen in issue #110.

Conversely, using podInfo timestamp for early podGroups can also cause normal pods to be starved, because while the podGroup timestamp remains unchanged and early, the podInfo timestamp does not.

I propose the following short-term solution:

1. For pods without a podGroup, use podInfo.timestamp.
2. For podGroups, use podGroup.timestamp.

We also need to address the issue of the unchanging podGroup timestamp.

[googs1025]

thanks @Bowser1704 for the feedback!

1. Priority Comparison: If Pod1 has a higher priority than Pod2, Pod1 will be dequeued first. Conversely, if Pod2 has a higher priority, Pod2 will be dequeued first.

2. Determine whether Pod1 and Pod2 are PodGroup-type Pods:

   • If neither Pod1 nor Pod2 is a PodGroup-type Pod, compare their creation times to determine the order.
   • If Pod1 is a PodGroup-type Pod and Pod2 is not, check whether the minMember requirement of Pod1's PodGroup is satisfied. If not satisfied, Pod1 takes precedence over Pod2. If satisfied, Pod2 takes precedence over Pod1.
   • If both Pod1 and Pod2 are PodGroup-type Pods, compare whether the minMember requirements of their respective PodGroups are satisfied. If one is not satisfied, it takes precedence. If neither is satisfied or both are satisfied, compare the creation times of the PodGroups.

Perhaps this sorting method can solve the problem of this cycle:
in the end,

• the first priority will be the pod with the highest priority
• the second will be the pods of the podgroup type that do not meet the minMember, and they will be sorted by the podgroup creation time
• the third will be the pods of non-podgroup type and sorted by the pod creation time
• the fourth will be the pods of the podgroup type that have met the minMember and sorted by the podgroup creation time.

[googs1025]

If I understand correctly, we should give higher priority to pods of podgroup type that do not meet minMember, because meeting it is more important, right?

[Bowser1704]

If I understand correctly, we should give higher priority to pods of podgroup type that do not meet minMember, because meeting it is more important, right?

I disagree. IMO, the creation timestamp of each pod should be factored into the queueSort.

[googs1025]

My understanding is that QueueSortPlugin is to sort the pods entering scheduling queue. We do not necessarily always use the pod's creation time as the basis for comparison. For example, QosPlugin or PriorityPlugin in k/k do not prioritize using the pod's creation time as the sorting ; I think sorting by pod creation time is more of a fallback option.

[googs1025]

thanks @Bowser1704 for the feedback!

1. Priority Comparison: If Pod1 has a higher priority than Pod2, Pod1 will be dequeued first. Conversely, if Pod2 has a higher priority, Pod2 will be dequeued first.

2. Determine whether Pod1 and Pod2 are PodGroup-type Pods:

   • If neither Pod1 nor Pod2 is a PodGroup-type Pod, compare their creation times to determine the order.
   • If Pod1 is a PodGroup-type Pod and Pod2 is not, check whether the minMember requirement of Pod1's PodGroup is satisfied. If not satisfied, Pod1 takes precedence over Pod2. If satisfied, Pod2 takes precedence over Pod1.
   • If both Pod1 and Pod2 are PodGroup-type Pods, compare whether the minMember requirements of their respective PodGroups are satisfied. If one is not satisfied, it takes precedence. If neither is satisfied or both are satisfied, compare the creation times of the PodGroups.

Perhaps this sorting method can solve the problem of this cycle: in the end,

• the first priority will be the pod with the highest priority
• the second will be the pods of the podgroup type that do not meet the minMember, and they will be sorted by the podgroup creation time
• the third will be the pods of non-podgroup type and sorted by the pod creation time
• the fourth will be the pods of the podgroup type that have met the minMember and sorted by the podgroup creation time.

in coscheduling, it is crucial to schedule the remaining members of a PodGroup that has not yet met its minMember requirement as soon as possible. Following this logic, we can sort the pods in the scheduling queue as follows:

• Pods with higher priority.
• Pods belonging to PodGroups that have not satisfied minMember, sorted by the creation time of the PodGroup (earlier creation times first) if PodGroup creation time the same, sorted by the creation time of the Pod.
• General pods (those not part of any PodGroup), sorted by their creation time.
• Pods belonging to PodGroups that have already satisfied the minMember requirement, sorted by the creation time of the PodGroup (earlier creation times first) if PodGroup creation time the same, sorted by the creation time of the Pod.

[Bowser1704]

You're right, timestamp isn't important.

My understanding of adding a queuesort plugin in coscheduling is to prevent deadlocks.

Scenario:

Pods A1, A2, A3, A4 (group A)
Pods B1, B2, B3, B4 (group B)

If the sorted order is A1 > B1 > A2 > B2 > A3 > B3 > A4 > B4, both group A and group B might get stuck in the permit stage.

I'm confused of your proposal for this situation.

[googs1025]

Is there really such an alternating scenario: If neither podgroupA nor podgroupB meets minMember, the podgroup creation time will be compared. If podgroupA is created first, all its pods should be higher than podgroupB. If podgroupA does not meet minMember, all its pods should be higher than podgroupB. If podgroupA and podgroupB both meet minMember, the podgroup creation time will be compared. If podgroupA is created first, all its pods should be higher than podgroupB. 🤔