RFC: Dynamic Priority Queue for Batch Jobs

[mismithhisler]

Proposal

We are looking for community feedback on the usefulness of implementing dynamic priorities for batch jobs. This issue will serve as an explanation of what this feature will be, and hopefully a consolidated place for feedback as development progresses.

What are dynamic priorities for batch jobs?

All jobs today can be assigned a priority. Jobs with a higher priority get scheduled before lower priority jobs. If more batch jobs are created than the cluster has capacity for, the jobs are blocked (put into a pending state), and jobs of the highest priority are picked "at random" to be scheduled next.

But what happens if Department A kicks off a ton of long running batch jobs.. Then some time later, Department B kicks off a batch job that should succeed fairly quickly!? Well, Dept. B's jobs may get scheduled soon, or may not. The ordering is not guaranteed as the underlying implementation is Golang's container/heap package (Side note, this could partially be solved by having Dept. A and B in separate namespaces with Quotas, but that could leave idle compute, which is something else we are looking into!).

Instead, we dynamically adjust the priority of a job based on some configurable parameters. In our first pass we are looking at various "weights" that can be applied to the base priority of a job depending on the time the job has spent in the "pending" state:

1. Time in the queue: The longer a job has been in the queue, the more/less we add/subtract to the priority
2. Job Size: A rough estimation of job size (CPU Mhz + Mem MB) that adjusts the base priority. If I want smaller jobs to have higher priority in the queue, I can configure that, and vice versa.
3. Cluster Utilization: A configurable way to say "who has used cluster resources". This could be configured to use namespaces, or a field in a jobs metadata. In the previous example, this could be used to assign a higher weighting to Department B's job, because that department has used less cluster resources than Department A. The next time cluster resources become available, Department B's job will be guaranteed to run.

The various weights would all be combined into a single final adjusted priority. The calculation will look something like:

AdjustedPriority =  Base Priority + 
             (WorkloadAge / MaxAge * AgeWeight) + 
      ((1 - TenantUsage / TotalUsage) * UsageWeight) + 
           ((1 – JobSize / MaxSize) * SizeWeight) 

Example:

Going back to the previous Dept A and B, lets say the cluster is at capacity, is configured with weights of 10, and both submit jobs of priority 10 at the same time. However, Dept. A has been running batch jobs all days on the cluster so they have 100% of the utilization. Dept A's job would not see any increased priority from the utilization factor, while Dept B would see +((1 - 0 / 100 = 1) * 10) = 10 priority. However, lets say that Dept A has a job on the queue that has been there for the MaxAge factor of 24 hours. Then even though Dept A has used a lot of the cluster, that job still gets +( 24 / 24 * 10) = 10 added to it's priority.

Current caveats/limitations

This serializes the scheduling of batch jobs that are configured to use the queue. Also, this only affects batch job registrations, not other cluster events, which are still processed concurrently. Because of the serial scheduling, all the jobs in the queue should have the same, or very similar constraints. Otherwise Nomad may wait for cluster capacity for a job which could have been scheduled much earlier.

Use-cases

We think this could be useful for Nomad users who regularly launch more batch jobs than their cluster is capable of running, and who would like more advanced controls over which of those pending jobs is scheduled next.

[the-maldridge]

One of the major themes in this RFC that is a current shortcoming in Nomad is the concept of "who's job is this?" While namespaces and quotas can encourage teams to launch only in their space, this isn't exactly something that's immediately queriable to determine who's compute is hogging the cluster since you'd need to crawl the namespaces API and then the jobs API to get a full picture.

It would be ideal as part of this proposal to introduce a top level (job scope) attribute to record the owning entity that a job is being run for. My thoughts for this would be that you'd have an owning_entity and an owning_component field that allow for quick policy decisions to key off of like the dynamic priority queue, while also providing a unified place for extending reporting tools. You could then key off of either of these in such a dynamic policy, and the component provides the second layer sharding that is alluded to but not called out in the RFC as a means of saying "this particular part of our stack should run quickly, but is really important that it does actually run".

My $0.02.

[shantanugadgil]

My 0.0002:

Not related to the dynamic priorities, but we need a more guaranteed way to enforce job timeout for batch jobs.
On more than few occasions, have I seen docker jobs stuck around way past its possible runtime.
This "stuck" behavior has prompted us to invent a heuristic "is the job stuck" parser based on it's cron schedule and the runtime of the job itself.

Example: if a "per-minute" job is running for more that 5 minutes it is an error. (heuristics like that)

[mismithhisler]

Thank you both for the feedback!

@the-maldridge You're right about the issue of "who's job is this?". I did not do a great job explaining this originally so I'll make an update soon, but the current mechanism we plan is to have 2 ways to configure "who owns the job". When configuring the Dynamic Priority Queue you would choose either of these.

1. Namespace, which I used in my examples.
2. Job level metadata field. When choosing this, you would need to configure an additional field to tell Nomad what metadata to look for. In you example you would configure something like:

server {
  scheduler_config {
    batch_queue {
      ...
      tenant_type = "metadata"
      metadata_key = "owning_entity"
      ...
    }
  }
}

@shantanugadgil - I think we've got you covered with #27803, which is currently finishing up it's review and will be merged soon.

[schmichael]

The nice thing about the tenant_type approach is that if we ever did add a first class field specifically for handling tenancy (eg owning_entity), we can easily add Dynamic Priority Queue support for it by adding a new tenant_type.