Add a mechanism to consider preemption cost when finding preemption candidates

[mwysokin]

What would you like to be added:

A mechanism to consider preemption cost when looking for and sorting candidates for preemption. The field would be set by some external controller (with a referential implementation of such controller included as part of the feature). Kueue should include a signal from that controller and should try to minimize the preemption cost.

Something that we need some feedback for would be whether the preemption cost parameter should be used only to sort/compare workloads with the same priority (e.g. 3 workloads A, B, C have workload priority medium, but A: has high preemption cost, B has medium preemption cost and C has low preemption cost, in this case the order of considering them for preemption should be: C, B, A) or whether it should be a combination of workload priority and the preemption cost (e.g. when having a low priority workload D with a critical preemption cost and a medium priority workload E having low preemption cost the order of preemptions should be: E, D).

Why is this needed:

Cost of preemption is not equal across pods. Pods which have a relatively long initialization time (minutes) are cheap to preempt if the initialization didn't finish but expensive to preempt when they already started carrying out some work. The same applies to checkpointing. If a pod carried out some work already but hasn't created a checkpoint yet it's costly to preempt it and its effort would be wasted, meanwhile a pod that just finished checkpointing is relatively cheap to preempt.

Since access to accelerators is so expensive and the accelerators are so scarce I think Kueue should try to care about the preemption cost and should use additional signals when looking for and sorting candidates for preemptions.

Also I don't think that Kueue itself should include some well defined policies how to calculate the cost of preemption but rather should allow external controllers to populate this information and Kueue should consider it during identifying and sorting the preemption candidates. We could offer a reference implementation of such controller that'd be a good example for folks trying to implement their own accordingly to the policies at their organizations and their business goals. I think a good referential example would be a controller that increases the preemption cost for every preemption that already happened. We store that number in the schedulingStats (thanks @PBundyra !) so it should be easy to use and react to this field to calculate the referential preemption cost field.

Completion requirements:

This enhancement requires the following artifacts:

• Design doc
• API change
• Docs update

The artifacts should be linked in subsequent comments.

[mwysokin]

CC @mimowo @tenzen-y @kannon92 @mwielgus @PBundyra @gabesaba @pajakd @amy @ichekrygin

[sanposhiho]

/cc

[sanposhiho]

This would be really a valuable feature for users to extend the preemptions.

---

Something that we need some feedback for would be

This is an interesting question. I'd vote to "it should be a combination of workload priority and the preemption cost".
I guess I'd use this feature basically for tie-breaking among the workloads with the same priority. But, there could be some exception scenarios:

• If a low-priority workload has experienced too many preemptions, I would want to prioritize this low-priority job over a higher-priority workload at some point. I don't want low-priority jobs to keep being preempted and never complete.
• If a workload is very very close to complete/checkpoint, I might prefer to sacrifice a higher priority workload.

I was wondering if we can do <WorkloadPriority.value> + <preemption cost> for this sorting.
Then, let's say if you have value: 100/200/300 on your workload priorities. You can put preemption_cost 1~99 if you want the cost to be used just for tie-breaking. And, you can put 100+ if you want the cost to break the boundary of priorities.

---

Also, one point from me on the API design: we should allow multiple scores to be defined at a single workload (and Kueue would take a total at the calculation). Like @mwysokin mentioned, there're multiple use cases already, and they are not exclusive. i.e., people might want to use this preemption cost for both the num of preemptions and for the phase of workloads.

[sanposhiho]

I think a good referential example would be a controller that increases the preemption cost for every preemption that already happened.

I was considering one thing on this usecase actually: we need to be careful not to introduce a preemption flapping by this. Like: jobA is preempted and get a higher preemption cost -> jobB is preempted by jobA and get a higher preemption cost -> jobA is preempted by jobB (because jobB's preemption cost is increased) ...
Some better algorithm is necessary here..

[mimowo]

Yes, introducing different ordering functions for admission and preemption creates the risk of infinite preemption cycles. So this should be an important consideration for the design.

[pajakd]

I was considering one thing on this usecase actually: we need to be careful not to introduce a preemption flapping by this. Like: jobA is preempted and get a higher preemption cost -> jobB is preempted by jobA and get a higher preemption cost -> jobA is preempted by jobB (because jobB's preemption cost is increased) ...
Some better algorithm is necessary here..

To handle cycles like that we can use the following mechanism. JobA should calculate JobB's "preemption priority" after the hypothetic preemption and admission of JobA and preempt only if JobB's "preemption priority" would not increase beyond its own. Similar mechanism is used to prevent cycles in fair sharing preemption (see https://kueue.sigs.k8s.io/docs/concepts/fair_sharing/#proof-that-two-workloads-wont-preempt-each-other).

[sanposhiho]

To handle cycles like that we can use the following mechanism. JobA should calculate JobB's "preemption priority" after the hypothetic preemption and admission of JobA and preempt only if JobB's "preemption priority" would not increase beyond its own.

Is that even possible? What if it's a cycle involving many jobs? like jobA preempts jobB, which will make jobB preempt jobC, which will then make jobC preempt jobD .... which will make jobZ preempt jobA?
Also, if I understand what @mwysokin meant correctly, we'll implement a controller for this preemption cost calculated by the num of preemptions externally outside Kueue as a "referential example". But, your proposal requires Kueue itself to understand how much a score will be increased by each preemption. i.e., Kueue's preemption needs to somehow know how much a jobB's cost is increased after a preemption by the external controller managing these preemption costs.

---

I was imagining a simpler (but not-beautiful?) solution: increase the preemption cost not every after a preemption but every after a few preemptions. Then, such a flapping could occur once at the most in the worst case, but won't recur.
The worst case scenario for example is: jobA preempts jobB -> jobB's cost is increased -> jobB preempts jobA -> jobA's cost is increased -> jobA preempts jobB -> (jobB's cost shouldn't be increased this time).

[pajakd]

Is that even possible? What if it's a cycle involving many jobs? like jobA preempts jobB, which will make jobB preempt jobC, which will then make jobC preempt jobD .... which will make jobZ preempt jobA?

It is possible (at least it should be). If there is some "preemption priority", then this sequence of preemptions jobA -> jobB -> jobC ... defines a decreasing sequence of such priorities. Which will prevent jobZ from preempting jobA. We have to make sure that the "preemption priority" is well-defined.

Also, if I understand what @mwysokin meant correctly, we'll implement a controller for this preemption cost calculated by the num of preemptions externally outside Kueue as a "referential example". But, your proposal requires Kueue itself to understand how much a score will be increased by each preemption. i.e., Kueue's preemption needs to somehow know how much a jobB's cost is increased after a preemption by the external controller managing these preemption costs.

This is how I imagined it. The external controllers might set some cost of preemptions (based on some checkpointing, time-to-complete etc.). But in some fixed time, Kueue should be able to simulate the preemption jobA->jobB to verify that jobB will not be able to immediately "strike back". It is fine (I think) if this changes after some time (because eg jobA's cost is lowered by the external controller).

If the cost might be changed in an unpredictable way by some external controller after each preemption, then we risk the infinite preemption cycles.

[sanposhiho]

I think a good referential example would be a controller that increases the preemption cost for every preemption that already happened.

To be clear, I'm specifically talking about this ^ usecase: preempting jobB increases a preemption cost of jobB immediately, which may allow jobB to preempt jobA. However, Kueue cannot simulate that by itself, unless somehow involving the external controller.

[tenzen-y]

I basically agree with introducing such a mechanism.
We should care about the following points when we introduce this mechanism:

• Avoid introducing batch users facing API (like annotation) since the evil users can exploit this mechanism so that their Job has never been preempted by others. The workload API field would be better.
• How to prioritize between the new scoring mechanism and the existing preemption mechanism.
  • What if the workload is higher priority based on DRS, but the new scoring mechanism says that the workload is lower priority?
  • What if workload A has a higher cost and B has a lower cost, but workload A is consuming borrowed quotas, and B is consuming a nominal quota?
  • etc...

[tenzen-y]

I think a good referential example would be a controller that increases the preemption cost for every preemption that already happened.

To be clear, I'm specifically talking about this ^ usecase: preempting jobB increases a preemption cost of jobB immediately, which may allow jobB to preempt jobA. However, Kueue cannot simulate that by itself, unless somehow involving the external controller.

Right, this could happen. So, I think that we probably need to introduce a lock time, which means the workload cost can not be changed during a fixed time if we want to allow drastic changes in cost based on preemptions. Or we might be able to just ignore admitted workloads recently when the Kueue selects preemptees. Anyway, we might need to have some safety mechanisms.

[sanposhiho]

Avoid introducing batch users facing API (like annotation) since the evil users can exploit this mechanism so that their Job has never been preempted by others. The workload API field would be better.

+1

What if the workload is higher priority based on DRS, but the new scoring mechanism says that the workload is lower priority?

Does a fair sharing consider a priority today? IIUC, a job can preempt other high-priority jobs on a different CQ if that's necessary for a fair sharing, right?
My core idea is <WorkloadPriority.value> + <preemption cost> that I mentioned at first. That means basically the preemption cost just influences the priority value, which means the cost can do what priorities can do (and cannot do what priorities cannot do)

What if workload A has a higher cost and B has a lower cost, but workload A is consuming borrowed quotas, and B is consuming a nominal quota?

So, ditto here: it should behave the same as if today workloadA has a higher priority and B have a lower priority. That's my mental model here.

So, I think that we probably need to introduce a lock time, which means the workload cost can not be changed during a fixed time if we want to allow drastic changes in cost based on preemptions.

No, I do not agree. The costs can be changed frequently and hugely based on job's phase. Your idea would make a new risk that jobA has a low cost right now, users need to increase the cost for some reason but cannot due to this lock time, and jobA ends up being preempted although it shouldn't.
So, IMO, we should allow the costs to be changed as frequent as users want, and we can just say it's a responsibility for users to avoid this kind of preemption flapping on their controller implementation. And, I'm talking about how we should implement the referential example controller to avoid this problem.

Or we might be able to just ignore admitted workloads recently when the Kueue selects preemptees. Anyway, we might need to have some safety mechanisms.

Yup, it might be nicer as a safe guard.

[sanposhiho]

EDIT: I meant to say <WorkloadPriority.value> + <preemption cost> 🙃 (the higher cost it is, the less probability a job should be preempted)

[tenzen-y]

What if the workload is higher priority based on DRS, but the new scoring mechanism says that the workload is lower priority?

Does a fair sharing consider a priority today? IIUC, a job can preempt other high-priority jobs on a different CQ if that's necessary for a fair sharing, right?
My core idea is <WorkloadPriority.value> + that I mentioned at first. That means basically the preemption cost just influences the priority value, which means the cost can do what priorities can do (and cannot do what priorities cannot do)

AFAIK, priorities are considered regardless of fair sharing to evaluate if the situation satisfies preemptionPolicy. IIUC, if we specify the Always preemption policy, the priority will not be considered. So the primary problem is the situation for preemptionPolicy × fairSharing × preemption cost.

What if workload A has a higher cost and B has a lower cost, but workload A is consuming borrowed quotas, and B is consuming a nominal quota?

So, ditto here: it should behave the same as if today workloadA has a higher priority and B have a lower priority. That's my mental model here.

Yes, kueue considers whether or not the workload consumes nominal quota or borrowed quota when it computes DRS.
So, AFAIK, mentioned conflict situation could happen.

So, I think that we probably need to introduce a lock time, which means the workload cost can not be changed during a fixed time if we want to allow drastic changes in cost based on preemptions.

No, I do not agree. The costs can be changed frequently and hugely based on job's phase. Your idea would make a new risk that jobA has a low cost right now, users need to increase the cost for some reason but cannot due to this lock time, and jobA ends up being preempted although it shouldn't.
So, IMO, we should allow the costs to be changed as frequent as users want, and we can just say it's a responsibility for users to avoid this kind of preemption flapping on their controller implementation. And, I'm talking about how we should implement the referential example controller to avoid this problem.

That sounds reasonable. The cost changes should be allowed, but we might need to consider ignoring the recently admitted workloads for the preemptee, as I mentioned.