Balancing builds over several build servers

I always have a tendency to strive to find uses for the academic problem solving techniques I learned when I achieved my masters. This is something that is a bit fun, doesn’t take too long and gives a quick starting template for balancing builds over several build agents in TFS2008.

The problem: Our build environment is set up by several small builds that build parts of the system independently. We have two build agents to balance the load of the building, and can do so by defining the default build agent to use in the build definition. Were of course using the built in Continues Integration in TFS2008. Now we want our builds to utilize these agents as much as possible. So when I do a check-in that will start more than one build I want the builds to be distributed across several build agents.

**The solution: **First of Id like to start out by point out that this solution is, by far, not an optimal solution, it does not take into account the direction of dependencies nor the build time of each build. This does however provide a low cost, fast, starting point for deploying the builds across agents.

Now; the Continues Integration in TFS2008 uses the workspace mappings to trigger builds. For example; if you check in under the “Forms” folder in source control, all builds that have that folder under its workspace mapping will be triggered.

So say we have 5 builds; Rest Service, Domain Objects, Integration Service, Windows Client and Windows UI Components. These builds all depend on each other which means that parts of them have the same sources mapped in their workspace mappings. Now for the fun part.

Let each build represent a node in a graph. Let each node be connected by a edge, based on the similarities in the workspace mappings. Lets call an edge a dependency. Using our 5 builds example we could get a graph that looks something like the following:

Now to balance the 5 builds across 2 build agents. To do this, we apply classic graph coloring. Let each build server be represented by a color. Now assign a color to a build in the graph. The nodes (builds) connected the colored node now has to be colored with a different color than the one used. Continue coloring the nodes so that no nodes are connected to each other and have the same color. The above graph above is colored with two colors green and blue, each representing a build agent.

What we achieve by this is that if we check-in in the Windows UI Components parts of the trunk the following builds will be triggered:

**Build Agent 1 ****Build Agent 2 **
Windows UI componentsWindows Client
However; we can see that the Domain Objects build is highly centric, checking in in this part of the trunk will trigger 4 builds; Domain objects, Rest Service, Integration Service and the Windows Client builds. With a distribution that looks like:
**Build Agent 1 ****Build Agent 2 **
Domain ObjectsWindows Client
Integration Service
Rest Service
This is due to two problems; the domain objects build is highly coupled and used in the other builds, and that this approach for balancing the builds does not take the build duration or weight into account.
The above graph is of course possible to color using two colors, it might not be the case that the graph of your build system is possible to color using two colors, then just cant efficiently load the builds across just two build agents.

The graph above was created using the Carya.Net tool.