Heaps made simple

This is the third post in the Perl scheduler series. We'll look at the CPAN modules that support our scheduler. As we've kept the design simple, there are only two modules involved (apart from Moose): Heap::Simple and Event.

Each scheduler must have a priority queue where tasks are kept waiting for their execution. These queues typically use a heap. Our heap is kindly provided by Heap::Simple. Heap::Simple claims to be only an interface, so you must also install one of its implementations (XS or pure Perl). The priority of a task is its scheduled execution time (represented as unix time) and Heap::Simple allows us to provide the priorites as object methods. So we initialize the heap like this:

my $heap = Heap::Simple->new( elements => [Object => 'next_time'] )

This tells the heap that its elements will be objects and the next_time method will provide the priority associated with the element. Since we use unix time which is an integer, the ordering of priorities is straightforward. In fact it's the default (numerical, less-than) order provided by the module.

We can add one or more tasks:

$heap->insert( $task, $another_task, @still_other_tasks );

And we can extract all due tasks from the queue:

$heap->extract_upto( time() );

We might also want to inspect all tasks in the queue, without extracting them (for example to save the queue to disk):

my @tasks = $heap->values;

To design a scheduler

Welcome back to the second installment of the Perl scheduler series. The previous post talked about the motivation behind this project, but now it's time for some design decisions. The goal of this first iteration is to have a task scheduler which can execute perl subroutines, methods and external commands. The scheduler should support both cron-style (i.e. recurring execution at fixed intervals) and at-style (i.e. single execution at a fixed time) scheduling. And we're trying to keep the design as simple as possible.

Let's look at the characteristics of existing schedulers. The standard implementation for Linux and BSD (aka the Vixie cron) has a time resolution of 1 minute. This means you can only schedule tasks (they call them cron jobs) at a full minute mark. We wish to allow a finer grained scheduling resolution (one second).

Cron will execute only the tasks which are scheduled at the present moment and will skip tasks which were due earlier but didn't execute (due to downtime, for example). We want to be able to take into account overdue tasks, in case our scheduler crashes or the machine goes down. This implies some sort of persistence for the tasks and their queue.

Cron also allows execution of tasks with a specific user's credentials. Execution with user credentials is also a good thing to have, but it requires root privileges so we'll leave that for later.

And finally, cron can rescan its configuration, looking for new jobs, either periodically or when the user demands it.

To make the design simple we'll start with a process which wakes up and executes a series of task objects (representing those tasks which are overdue and due, in chronological order, i.e. oldest first). The task list will be stored in a heap with the scheduled execution time as the priority. The scheduler can also wake up on demand (on a HUP signal) and re-read it configuration to rebuild its task list.

To "cron" in Perl

My first (and to date only) attempt at releasing a Perl module into the wild (a.k.a. CPAN) was the poorly named and implemented Catalyst::Engine::JobQueue::POE. Why poorly named? Well, it has nothing to do with batch processing and job queues. What it does is allow you to run predefined HTTP requests for your Catalyst application at periodic intervals (a la cron). As for the poor implementation, it has only some basic features and it's based on the POE Catalyst engine which is deprecated today. So it's a pretty sorry excuse for a cron replacement and, need I say?, highly NOT recommended.

Despite this minor setback, I have not abandoned the idea of writing a task scheduler in Perl. Therefore I'm starting a new project to implement cron and at functionality. It's a good pretext to practice Moose (and try out MooseX::* extensions) and IOC-style programming.

Because I have no chance to beat the unix cron implementation in regards to performance, I've chosen to focus on flexibility, extensibility and Perl specific integration (like Catalyst integration).

Next up: To design a scheduler