Inner Workings: The Project Scheduler

The Heart of the Matter

The core of CruiseControl.Net is the project scheduler. This is the piece of code that is responsible for scheduling builds – without which CruiseControl.Net just wouldn’t work.

Before I delve into the actual workings of the scheduler, let’s quickly review how builds can be scheduled.

First and foremost, in order to schedule a project build a trigger is required. There are a number of different types of trigger – from interval triggers to scheduled triggers to projects that monitor other locations or projects. Additionally triggers can be combined or filtered. But one thing all filters have in common is they tell the scheduler a build needs to be performed.

The second part of the scheduler is the queues. Early versions of CruiseControl.Net had each project running in its own little world – they didn’t affect other projects. As the number of projects increased, this lead to increased contention on the build servers and a lack of resources. To counter this queues were added. A queue is a group of projects, of which only one can have a running build at any point in time. Generally they work on a first-in, first-out basis, but it is possible to set queue priorities.

With this background, let’s delve into how project scheduling actually works

Managers, Integrators and Queues

The main class that handles everything in CruiseControl.Net is CruiseServer. This is responsible for starting everything and handling all user interactions. But, it doesn’t actually handle the scheduling of builds. This is handled by a number of other classes.

Looking at CruiseServer, there is a IntegrationQueueManager class. This encapsulates all the actual projects and their integrators. Now an integrator implements IProjectIntegrator and is responsible for the actual triggering of a build. In a moment I’ll return to how it does this, but first, how is an integrator started.

When IntegrationQueueManager is instantiated it iterates through all the projects and ensures that there is a queue for each project. If there is no queue, then it creates a new queue with the same name as the project. These queues are all added to an IntegrationQueueSet.

Once the queues have been initialised, the IntegrationQueueManager then calls ProjectIntegratorListFactory to generate all the project integrators. As well as containing the project configuration, the integrator also contains a reference to the associated queue. At the moment there is only one IProjectIntegrator – ProjectIntegrator.

This completes the initial setup of the queues and integrators, the next step is to start the projects integrating. This is done by calling the StartAllProjects() method (by CruiseServer), or by calling Start() for a specific project (StopAllProjects() and Stop() do the opposite).

When StartAllProjects() is called, it iterates through all the project integrators and checks to see whether the project can start. This involves checking the configuration and then the state persistence (both new in 1.4.3). If both these checks start, then the integrator is started. The actual starting of the integrator is done by calling the Start() method on the integrator.

Nice and simple, but here’s a diagram to illustrate this process:

Triggering Builds

The above initialisation got to the point of calling Start() on ProjectIntegrator. This method starts a new thread that contains a polling loop. This loop checks to see if there is an integration every 100ms. If there is an integration it then calls the Integrate() method on Project which performs the actual integration (e.g. pre-build, source control, tasks and publishers).

This check consists of two parts. First it checks the queue to see if there is a pending integration request. If there is a request, it locks any queues that need to be locked, starts a new request and calls the Integrate() method. After this it cleans up and exits the check logic.

The second part of the check, which is only performed if there is no pending request, is to check all the triggers. Each trigger has a Fire() method, which performs the actual check. The output of the fire method is an integration request or null – if the output is not null then it gets added to the queue.

The root level trigger is a combination trigger, which merely iterates through each child trigger and calls its Fire() method – it is up to each child trigger whether it returns a request or not.

Once the trigger checking has finished, it checks the queue to see if the request is next. If not, it enters a loop until the request is ready. Then when the request is ready, the check logic finishes – it doesn’t actually call Integrate() after the trigger checking. What happens is the polling loop goes through another cycle and then the integration request gets returned from the first part of the check.

The following diagram shows this:

Queues

The final piece of the puzzle is the integration queues. I’ve already mentioned them a couple of times, but let’s pull them apart and see how they actually work.

First of all, queues do not use the built-in queue classes – they use a List<> instance instead. The reason for this very simple – they do more than just adding and removing items – they also allow re-ordering (based on priorities). Plus items on the queue are not removed until completed – which would cause issues with de-queuing.

In turns of how they work. When an item comes in, the queue checks to see if it already exists. If the item exists it applies any re-ordering rules (ignore, re-add or replace existing), otherwise it just adds it to the queue. It will look at any other items in the queue and then add it after the last item with the same priority, or before the next highest priority.

When the integrator checks for a request, it will always return the item in position 0 (the start of the list). This item remains there until the integrator performs its clean-up.

Finally, there are a few call-back methods that are used to synchronise the state between the queue and the integrator.

And that’s all there really is to queues – very, very simple. The following diagram shows how queues relate to the integration polling cycle.

Summary

This post has covered how project integrations work and how builds are scheduled.

The main driver for the process is IntegrationQueueManager, which responsible for initialising everything and then starting the actual integration cycle. The actual integration cycles are handled by a polling thread within each integrator.

The actual process for starting a build is controlled by both the integrator and the queue. The integrator checks the triggers to see if a build should be scheduled, and when one is found it adds it to its associated queue. Then, in the next polling cycle it retrieves the request off the queue and actually performs the integration.

The queues act to limit the number of project builds at any time, and do this by storing requests. The integrator will only perform a request when it is the first item in the queue.

Final Note

This post is about how builds are scheduled – I haven’t covered how an actual build is performed. But that is an entirely different topic, so I will leave that for another time

An Oversight in the Queues

An Assumption

I while back I wrote a patch to CruiseControl.Net to allow queues to be configured. It all worked fine, and allowed other people to add additional queue functionality.

However, it was recently pointed out, I made an assumption in the development My assumption was people would configure it properly – including setting up the links to queues correctly. Instead, someone configured it so the queues weren’t being used by any projects and wondered why the new queue functionality wasn’t working.

When he found the documentation, he then understood why it was happening, but pointed out the application should have validated the configuration and not let it happen. And I agree, the application should stop people making mistakes like this.

Thanks to Alex Hutton for pointing this out.

How Configuration Works

Before I look at resolving the issue, first I’ll quickly cover how CruiseControl.Net handles the configuration, and why this issue can occur.

The configuration file contains a number of XML elements, which are loaded by Exortech.NetReflector. This converts the XML into .Net objects – it uses attributes on the classes and dynamic look-ups to achieve this. The end-result is an XML element goes in and an object comes out. NetReflector applies some validation rules (mainly from the attibutes) and raised any errors.

CruiseControl.Net then checks the type of the returned object. If it is a project, it gets added to the list of projects, likewise if it is a queue. Any other object types will cause an exception to be raised (since these are the only two types that can be handled at the top-level).

And that’s it for validation – no more checks are done after this!

Validating Configuration

Now that I’ve shown that we have two lists – one for projects and the other for queues – it’s time to do some validation. Currently I’m only going to add one validation rule: all queues must be referenced by a project. It is not an issue if a project references a non-defined queue as CruiseControl.Net will automatically create the required definitions (using the default settings).

The check itself is very simple:

• Iterate through the list of queues
• For each queue definition, check that at least one project uses it (the QueueName has been set to the name of the queue)
• If the queue is not used, then raise an exception

It was a little bit harder deciding where to add this exception. In the end I decided to add it to NetReflectorConfigurationReader. This is the class that is responsible for doing the actual load from XML. I put it in here for two reasons:

• It already handles the unknown item validation (plus since it wraps NetReflector it has its validation)
• Sometimes people will do a validation call to the console – this calls to this class and no further

End of Assumption

And that finishes the fix for my assumption. Now CruiseControl.Net will validate the queues and make sure they are being used. I have added it to the trunk and it will be included in the next release.

Queues Update

Code Committed

My modifications on configuring queues (read about them here) has been added to the trunk (thanks Daniel). This fixes the issue with ForceBuild not being added to a queue when there is already an IfModificationExists for the same project on the queue.

If you get the latest nightly build you can test this functionality for yourself. Have fun

Extending Queues

New Queue Functionality

There have been a couple of requests in the mailing lists recently about queues and how they work. I recently wrote a post on how they work (read it here). Now it’s time to look at extending the queue functionality.

One of the issues about queues is the way new projects are added to it. We have the following scenario:

• Project A depends on Project B – so a ForceBuild trigger has been added to Project A.
• Project A also has an interval trigger with an IfModificationExists.
• Project B uses an interval trigger to build

In this scenario it is possible for Project A to be added to the queue with a IfModificationsExists trigger while Project B is building. The outcome people would like is the IfModificationsExists build to be replaced with a ForceBuild instance. This is the specific functionality I’m going to look into.

Note: Before I begin I should tell you that James Chaldecott has already posted a solution to this in CCNET-1095. I’m not going to replace his work, instead I’m going to expand on his work to give people the choice of what will happen.

Planned Work

Since James has already done most of the hard work, here’s what I’m planning on doing:

• Add a new configuration setting called queue to the config file. This will allow the queues to be configured.
• Modify the queue start-up process to associate the configuration information.
• Modify James’s patch to only be applied when the configuration asks for it.
• Add an additional option to queues to replace the existing build request. This is instead of removing and re-adding the build request.

So, let’s start our journey of expansion.

First Step: Configuration

Recently I posted on how the configuration works in CruiseControl.Net and how to extend it (here for the basics and here for extending it). I’m going to build on this knowledge to add a queue item to the configuration file, which will be a top-level item since it will involve multiple projects. Here is how the configuration will look when I’m done:

<cruisecontrol>
   <!-- Project definitions -->
   <queue name="CruiseControl.Net" duplicates="ApplyForceBuildsReAdd"/>
</cruisecontrol>

You’ll see that I’m adding a <queue> tag at the same level as <project> tags. To do this I first defined an interface and then an implementation of the interface. Since this is purely for configuring a queue I’ve added it to the configuration folder. I also added an enumeration for the duplicates value, so the value will be validated.

Queue Configuration Types

The ReflectorType name for DefaultQueueConfiguration is “queue”. The Name and HandlingMode properties have been decorated with ReflectorProperty attributes. That’s the first part.

Next I opened up IConfiguration and added a new property called QueueConfigurations to hold the queues. This required me to also add the property to Configuration. And one last change – I modified NetReflectorConfigurationReader to see if the item is a project or a queue and then add it to the correct location (this post explains why.)

Next Step: Associating with the Queue

The method were queue names are converted to actual queues is the Initialize() method in IntegrationQueueManager. This method takes in an IConfiguration instance and generates the queues. It does this by calling the Add() method on IntegrationQueueSet. This in turn generates a new IntegrationQueue instance and sets the name. Since IntegrationQueue is an implementation of IIntegrationQueue, that’s where I started my changes.

The first thing I did was add a property called Configuration to IIntegrationQueue. Then I modified IntegrationQueue to implement the property. This is read-only, so I also had to modify the constructor to load the property. Next, add a parameter to the Add() method in IntegrationQueueSet to take in the configuration and pass it onto the new IntegrationQueue instance. Finally I modified the Initialize() method in IntegrationQueueManager to find the configuration and pass it into the Add() method.

To make things a bit easier I added a FindQueueConfiguration() method to IConfiguration. This takes in a queue name and returns an IQueueConfiguration. It simply iterates through the lists of queues checking the names. If a match is found, then this is returned. Otherwise it creates a new default instance of DefaultQueueConfiguration and returns it. This way there will always be configuration associated with a queue.

Applying the Patch

Now that I’ve done the ground work, I’m ready to apply James’s patch. His patch modifies the Enqueue() method in IntegrationQueue. So, first I added his patch and made sure it works (it does ) Once his changes were in place I added a switch statment to check the HandlingMode property of the configuration. If the mode is UseFirst I stick with the original logic. If the mode is ApplyForceBuildsReAdd I use James’s logic. Otherwise I throw an exception (since I’m not quite ready to implement ApplyForceBuildsReplace).

Give it a quick test, and it’s still working

Final Step: Replace Mode

Now that I’ve enabled configuration of the way duplicate builds are handled, I wanted to add an additional mode. This is the same as James’s patch, but instead of removing the old item and adding the new item, I will replace the old item (that way the queue order doesn’t change).

The current code (for re-adding the request) removes the requests, calculates the new queue position and adds the new request. What I want to dos is exactly the same, expect without the calculation of the queue position. To handle this I added an override to the AddToQueue() where I could specify the queue position. Then I all had to do was copy the existing code, change the messages slightly and call my new override with the old position.

Turns out this change was quite easy afterall

In Summary

I’ve now built on my knowledge of how both the configuraton and queues work in order to add some requested functionality. The main changes were:

• Adding configuration settings for queues (three new types)
• Based on these settings, allowing the user to specify how duplicate requests should be handled (seven types modified)
• Updated the unit tests (not included in this post, but still needed to be done)

Now, if people are happy with the existing functionality, they don’t have to change (since the existing functionality is the default). However, if people want force builds to be considered more important, they can configure their queues to work this way. Hopefully a win/win situation for everyone involved! I’ll get this posted on Jira and then hopefully it’ll be added to the trunk sometime soon.

Coming up next, security for CruiseControl.Net…

An Introduction to Queues

What are Queues?

I’ve noticed in the mailing lists that there have been a couple of questions about queues lately – either wanting to modify their functionality or thinking there is an error in the way they work. So I took a quick look into the code to try and understand how they work. This posting is my understanding of their current functionality.

To answer my question, a queue is a group of projects. It acts in a FIFO (first-in, first-out) manner to control which projects get built. The purpose behind a queue is only one project in the queue will be built at any one time – hence the FIFO requirement. It also handles prioritisation and prevents duplicates.

But How Do They Work?

You can think of a queue as a wrapper around a project. When CruiseServer recieves a request to build a project (either from a user or from a trigger) it actually calls the queue to schedule the build. If there are no other projects in the queue, then the build gets started immediately, otherwise it has to wait to come to the top of the queue.

The actual queue functionality is implemented in a class called IntegrationQueue. IntegrationQueue is basically an array with some smarts around how items get added. The two main methods for this are Enqueue() and Dequeue(). Enqueue() checks to see if the project is already in the queue, if it is not it checks to see its priority and then adds it to the queue in the correct position. Dequeue() removes the project at the head of the queue and notifies its integrator that it can start building.

And that’s really all there is to queues (there are some other methods around finding out if there are queued items, removing unwanted project builds, etc. but these are ancillary functions).

Missing Builds

A common issue that has been raised on the mailing lists lately around conflicts in builds. We have the following scenario:

• Project A depends on Project B – so a ForceBuild trigger has been added to Project A.
• Project A also has an interval trigger with an IfModificationExists.
• Project B uses an interval trigger to build

The following happens:

1. Project B starts its build
2. Project A is trigger (interval trigger), gets added to the queue with IfModificationExists
3. Project B completes its build, Project A detects this
4. Project A attempts to add itself to the queue with ForceBuild
5. The queue detects it is a duplicate and discards the request
6. Project A starts its build using IfModificationExists
7. …

So, we see the problem is not with how the queues work, but with adding the result from the ForceBuild trigger. As far as I’m aware there is no work-around for this issue. Probably the best approach would be to modify the trigger so it overrides any existing queued project build. If I get some time I’ll look into it (or someone else can give it a try ).

Locking Queues

Another scenario comes when you have multiple queues – queues A, B & C, each with multiple projects. Queue A could be the application framework, while queues B & C are applications. If Queue A is building, then we don’t want to try and build the applications, otherwise we’d get conflicts.

Again, this scenario isn’t handled by the current queue mechanism. Queues are pretty much silos – they don’t communicate with each other. To handle this scenario we’d need to add some way of communicating between the queues (perhaps a lock object). When a queue wants to schedule a build it would need to check any dependant queues for a lock. If there are any locks, then it would need to wait. If there are no locks, then it would lock itself, build the queued projects and then release the lock. At this stage it would then need to notify any dependant queues that they can start.

That’s All Folks

That covers how queues work, and some of the current issues around queues. They are reasonably simple beasts, we just have to understand their limitations. Of course, over time they’ll probably increase in functionality (and complexity) as people refine them, but for now they are a simple, elegant approach to a problem.