This year at Blacksmith, the number of jobs we run and the fleet of machines on which we run them have grown dramatically. This post describes how we engineered the scheduling process to be better at utilizing the fleet, fairer across tenants, and more resilient to failure at this much greater scale. Along the way, we’ll look at the specific shape of the scheduling problems we face, how the initial version of job placement worked, problems we ran into with it, and the architecture we rely on now. A critical tool in the development of this new system is simulation, so I’ve built a mock simulator you can play with to gain intuition about the problem. It shows both the old approach to scheduling, with all the hacksand the newer centralized
Scheduling jobs at Blacksmith began reasonably enough, it began with a control plane writing demand for jobs to a Redis instance, and then the few nodes that comprised the cluster would poll and take work. Over time, to compensate for failure and other challenges we’ll later discuss, this grew into a rather complex Lua script to coordinate job state management executed by each of the agents in the fleet.
To clarify, each host runs a process we call the VM agent. Whenever the machine has free cores, it polls Redis to execute the script to apply a series of checks in order (size fit check, rootfs version check, an organization concurrency, etc.). Redis executes scripts serially, which makes the whole thing relatively straightforward to coordinate and to understand. There was never a race between two hosts adopting the same job. The agent then reserves cores in its own durable local state and boots the VM. This mostly works, but it’s worth mentioning some ways in which it fails.
One issue is the need to deal with machine failures. The challenge is that the agent has already claimed a job and mutably updated the state before the job has actually started running. More complex bookkeeping protocols could be built, but the load on the data store in use, Redis, already poses yet another major challenge. In order to handle this class of problem, the control plane tracks which jobs it expected to see run actually started, and if after a few minutes they had not, it enqueues a duplicate. Thus recovery from failure, in the best case, happens on the order of minutes.
A deeper problem is that this architecture cannot enact policies that need global visibility. Fairness across organizations is an inherently a global question, so hosts pulling independently from the FIFO can’t enforce it. Another rarely used knob, organization-level concurrency limits, were enforced only at adoption time, against a counter that required background reconciliation with what was actually running.
Wide jobs are the worst problem. Much of the Blacksmith fleet consists of consumer 32 vCPU gaming chips, the fastest in terms of single core performance that money can buy. The only way to get a 32-vCPU job, a wide job, placed on such a box is to make sure nothing else is running there. The naive initial approach was to not schedule any jobs deeper in the queue if the head couldn’t fit. That could regularly take fleet utilization below 70% as many hosts partially emptied out before one became fully empty. This amounts to a totally unacceptable loss of capacity. Interestingly, by reserving some segment of the fleet just for these large jobs you can dramatically increase the overall utilization of the fleet, but getting the tuning right is tricky. We will come back to how the assigner deals with wide jobs more gracefully later.
The serial script execution that made the model easy to reason about also made Redis itself the bottleneck. Every poll from every host ran the script, so the load on Redis grew with the fleet. The primary mitigation then was to reduce the polling rate, making the fleet slightly less responsive to new load arrivals. In the rest of the post we’ll cover how we moved the system to a more principled design ready for the next two orders of magnitude. Instead of hosts pulling work, a central service that sees the whole fleet pushes assignments to hosts.
Before we can lay out a design, we need to nail down some constraints, scope, goals, and terms.
Job runtime up front is unknown. The only bound we have is the timeout (default 12 hours, max 72), which dwarfs the typical job and is useless for planning. Runtime statistics can become an optimization, but never a dependency. Even worse, Github provides scant information about which job is going to run before it starts.
No preemption. This is a technical constraint rather than a fundamental one: technology to do live migration of workloads exists out there (Loophole Labs, for one), but we haven’t implemented it. A CI job forty minutes into its run must not be sacrificed to make room for another. This closes off most of the classical toolkit. The hard case, fitting a job that needs a whole or nearly whole empty machine, can only be solved by waiting for capacity to free naturally and making sure the waiting job has first claim on it when it does.
The scheduler places demand, not jobs. This is an oddity of the GitHub API. We provision a runner VM of a given shape (org, os, vCPUs), and once the VM boots and registers a GitHub Actions runner, GitHub binds whichever matching queued job it likes. The job whose webhook triggered provisioning and the job that actually runs routinely differ, and that is expected. The practical unit of scheduling is "a live runner of shape S for org O," not a job ID which we'll call a demand.
Demand is bursty. A single push can turn a quiet CI fleet into a very busy one. Running a fleet for one organization means choosing how much spare capacity to keep idle and how long jobs can wait while more capacity comes online. Making that work requires a scheduler that can keep machines busy while ensuring one organization’s burst doesn’t leave everyone else waiting.
The goals:
These constraints then can help guide a design. We know this system needs to be high availability, but will all the work fit on a single machine? Let's look at some numbers.
By Little's law, 1000 placements per second times a mean runtime of a few minutes is a couple hundred thousand concurrent VMs at fleet saturation. At 256 bytes budgeted per allocation, the whole registry is less than a hundred megabytes. We'll want some per-machine state, which, at 30,000 hosts and perhaps 1 KiB per node is 30 MiB. The leader's in-flight demand records dominate at hundreds of megabytes, and total domain state fits under a gigabyte. On the event side, an idle-report floor of 2,000 reports per second (machines send updates every 15s if nothing happened), plus change-driven reports bounded by the transition rate puts ingest around 4,000 updates per second per instance, about 4 MB/s of bandwidth (there’s room to make this incremental if need be). We can work backwards from the goal of scheduling 10,000 jobs a second to recognize that we want to then spend no more than 100μs processing any individual job placement. This means that we need the scheduling policies to operate over indexed structures and generally not to be performing more than, say, hundreds of lookups from such data structures. That turns out to be easy enough. In practice, we can pile a good bit of scheduling complexity into the algorithm so long as we carefully maintain the relevant in-memory indexes.
One can thus conclude that all of this fits comfortably on a single machine, nowhere near CPU, memory, or bandwidth limits at target load. And that conclusion, combined with the constraints, is what picks the basic design. Org limits and cross-org fairness are global questions that cannot be answered across shards that don't see each other, and one machine handles the whole load, so sharding the decision-maker would be complexity in exchange for nothing. The simplest design that satisfies everything is one global in-memory scheduler, with one elected instance making decisions at a time. This all culminates in the design of such a server: the assigner.
The sketch we just described only makes assumptions about operating over in-memory data structures. Given we want this system to be widely fault tolerant, durable side effects need to happen somewhere. The design we went with thus is to split durability between two distinct places and coordinate between them in a classic two-phase protocol: demand initially is written into the queue, committed on disk on an agent, then removed from the queue, and then can later be removed from that agent’s disk. The assigner's in-memory state never represents ownership of resources in a way that cannot be recovered from those two places. A VM is identified end-to-end by a single ID, the control-plane-minted unique ID.
Separately, a single assigner instance acts to move that state forward. Mutual exclusion between assigner instances is coordinated through an etcd. The lease is for liveness, not correctness. A deposed leader can generally keep acting for up to roughly the lease TTL, and the consequences (duplicate placements, brief limit overshoot) are accepted by the design; strict mutual exclusion is not a hard design requirement.
This service has to be highly available. In a very rare hard failure of an instance, we do not want to accept more than, say, 10s of downtime. This of course means running more than one instance. Multiple instances of services imply a need for duplication of state, and generally that requires protocol complexity to get right. To try to keep this system simple, I figured it’d be best to have exactly one communication protocol, agent to assigner, rather than having the agent talk to the assigner and the assigner leader talking to replicas. At the cost of duplicating messages from agents to all assigner instances, we keep the protocol totally symmetrical. The agent has no awareness of assigner leadership, and assigner instances have no awareness of each other (outside of etcd leases).
Concretely, every agent dials every instance and holds one long-lived gRPC stream to each, pushing node reports up. Each instance independently applies that firehose to build the same in-memory picture of the fleet, including every allocation on every host. All state changes that update the view of the fleet happen over the report channel going to every instance. The leader just happens to be the one instance that additionally acts. It reads demand off the queue, decides placements against its picture, and writes Assign commands back down the streams it already holds.
The symmetry makes failover fast. A peer is a hot standby by construction. It has been ingesting the same reports all along and needs no catch-up transfer, no replication protocol, and no communication with the other assigner instances at all. The only coordination between instances is the etcd lease. The price is bandwidth, since every agent sends every report a few times over, and at our scale that price is small. Agents do reply to Assign messages, and the replies resolve the in-flight attempt (a refusal never shows up in any report, since nothing was persisted), but the durable state that matters comes back through the reports, which every instance sees.
This state model is also the whole durability story. Any state the assigner loses is one of three kinds. It is reconstructable from a reachable host, or it is about work on a genuinely dead host (gone with the host, so correctly absent), or it is pending demand, safe in the queue. So there is nothing to replicate and no scheduler database to operate, back up, or restore. (For completeness, besides the queue and the lease, the assigner also reads a tiny durable instance roster that agents use to discover which instances to dial.)
Inside the assigner, there are two major pieces: the monitor that receives all the updates from all the agents and synthesizes them into a global picture of the fleet, and an actuator existing only on the leader that runs the scheduling algorithm and orchestrates its decisions back out to the fleet. One neat thing about this design is that the monitor exposes point-in-time snapshots that are cheap to take (primarily backed with O(1) clone CoW BTrees for indexes). The scheduler then takes a snapshot of the fleet state, combines it with in-flight operations, and then acts on it. Due to having a single writer, this generally shouldn’t be exposed to hazards. The scheduling algorithm itself is completely pluggable, and can be validated on its own.
We benchmark the index structures the scheduler consults each round to ensure the algorithms meet the design constraints. Furthermore, we make sure we can exercise the policy against a deterministic simulation of the fleet, replaying production traces and adversarial workloads against candidate policies before any of them touch real hosts. That simulation infrastructure is worthy of a whole separate post.
Now back to the problem of scheduling jobs that take up entire machines. We refuse to do what the old scheduling system did and drain capacity widely across the fleet to make room. Instead we take a multi-phase approach to the problem. First we try to mitigate it, and then if we do need to free up capacity, we try to do it smartly. The first line of defense is to realize that as the fleet utilization rises, we can make sure there are whole free machines so long as we pack new jobs tightly. Above a certain utilization rate, the scheduler prefers to fill open hosts tightly rather than spread load, so small jobs concentrate and empty hosts form naturally instead of every host hovering at partially full.
The second level of protection is targeted drain reservations. When we truly don’t have a place to stick a wide job, then we need to make one rather than just praying one will open up soon. To do this we want to pick the machine we think will open up next so long as we stop putting new jobs on it. Unfortunately jobs don’t have deterministic runtimes, so we don’t have such an oracle. A simple and somewhat effective approach would be to choose to place these drain reservations on the least full machines. Unfortunately this can go quite poorly because a single long-running 2vCPU job could keep that host occupied for hours. A significant improvement to this scheme is to realize that once jobs start, then we do have a good deal of history about runtimes. Every hour we collect up a per job name statistics representing the distribution of runtimes and use these priors to estimate the machine that will free up next. This turns out to work quite well and has moved the deep tail of 32 vCPU scheduling latency in by an order of magnitude.
Centralizing the scheduling layer allowed us to build a foundation we can trust for the scale we’re currently operating and for growth for a while yet to come. Making sure the napkin math lines up for the design before building it was critical for project success. Avoiding durable state or replication protocols inside this admittedly complex piece of software makes it much easier to reason about. Tools like simulation, and reliable benchmarking along component boundaries means that operating the software comes with few surprises. At Blacksmith, we spread both compute capacity and the engineering investment across our many organizations to get your jobs running as fast as possible. The work entire scheduling system you don’t have to build or operate.
