The Mathematics of Build Queue Optimization and Auto-Scaling - Ian Duncan

Index

Archival Note : This is an archived version of a three-part blog post series originally published on the CircleCI blog in the spring of 2016 by Kevin Bell (GitHub: bellkev) — Part 1 on March 28, 2016, Part 2 on April 6, 2016, and Part 3 on April 18, 2016. The original posts have since been removed from CircleCI’s website (this copy is reconstructed from the Internet Archive, including the original figures). I’ve lightly edited the content to be less CircleCI-specific while preserving the technical insights and mathematical analysis. The original simulation code is still available at bellkev/asg-sim.

These posts remain one of the clearest explanations of applying queueing theory to CI/CD infrastructure that I’ve encountered, and the conclusions are applicable to any continuous integration system.

Part 1: Why Build Queues Are Costly

Over the past several years, continuous integration services have run millions of builds on rapidly growing fleets of build containers. Operators have tweaked and tuned countless parameters to ensure their auto-scaling clusters of servers always have capacity to run builds while minimizing unused resources.

A New Challenge

After the launch of on-premises CI solutions, many teams started asking: how should we run our own builds in AWS Auto Scaling groups or similar services? Does auto scaling make sense for them? What parameters will keep their CI instance responsive while minimizing idle server time?

The problem is that these teams don’t want a several-thousand-container cluster to process thousands of builds per hour from a globally distributed pool of developers. They want a few hundred containers to process dozens of builds per hour from a couple buildings’ worth of developers. They also use different machine types, different container specs, and have different traffic patterns from large SaaS CI providers.

We need to understand not just how to run one giant-sized cluster, but how to optimize dozens of heterogeneous, medium-sized clusters.

Thinking about this problem, it occurred to me that there might be a way to model it with a bit of queueing theory. The simple case of a single server running jobs of a fixed duration occurring randomly in time (following a Poisson distribution) is known as an M/D/1 queue, and there are simple closed-form solutions to the expected wait time in such a queue. The multi-server (M/D/c) case has much more complicated closed-form solutions, but adding auto scaling quickly makes the problem intractable. Or at least I didn’t find an answer after several minutes of spirited googling, which is practically the same.

An Experimental Approach

This is where I could’ve built some kind of elaborate computational simulation of auto scaling build clusters and run millions of iterations of Monte Carlo experiments with hundreds of thousands of possible parameters, so of course that’s what I did. It lives at bellkev/asg-sim, and I’ll be using data from that model in the rest of this post.

I should also highlight that while I’m focusing on modeling build clusters, much of what I cover will also apply to selecting appropriate infrastructure sizing or managing clusters of servers running arbitrary jobs.

Before tackling auto scaling, I spent time on the fixed-fleet-size case, because that is the basis of comparison for all auto scaling solutions. After verifying that my model matched the theoretical predictions for the simple M/D/1 case, I started on the problem of balancing queue time and resource utilization.

It’s obviously easy to do a good job of just one of these things. You can underprovision and keep your queue full and machines busy, or you can overprovision and keep your queue empty and your machines idle. The following graph makes this clear.

This graph shows what happens when the same traffic pattern is run against fixed-size clusters of varying sizes. Clearly smaller clusters have higher machine utilization with long queue times and larger clusters have low utilization with short queue times.

A Cost Function

In order to choose some kind of balance point, we need to do a bit of hand-wavy math. Developers’ time is valuable, so there should be some kind of dollar value that can be placed on time they spend waiting for builds in the queue. Large servers are also expensive, and there is a cost associated with keeping them running. You can model the total cost something like this:

cost = idle machine hours × cost per machine hour +<br>queued build hours × cost per developer hour<br>You may be philosophically opposed to the idea of equating human hours to machine hours, or you might argue that five minutes waiting on a build really causes more like thirty minutes of lost productivity because of the interruption it causes. You might even think that queueing time doesn’t really matter, because developers can go get coffee or work on some other feature while their builds...