1

Assume you are tasked with implementing a "cronjob as a service" where you are supposed to be able to run potentially millions of periodical tasks (to simplify, making HTTP requests to URLs) with different schedules.

For example, these tasks could be:

This "cronjob as a service" should ideally:

  • not miss/drop invocations
  • execute the task rather on time (a few seconds delaying is OK)
  • reassign the invocation to another worker if the assigned worker isn’t executing (maybe unresponsive?)

I foresee some edge cases such as a significant portion of the tasks being scheduled at the beginning of an hour etc where the load "peaks".

How would you design such a service that can scale and operate reliably with hundreds of thousands of tasks with different timetables?

I'm more interested in how would you keep up with the schedule and respond to tasks being added/deleted dynamically?

This is basically what the Google Cloud Scheduler service does, and I'm looking forward to a discussion on how would that be implemented?

1
  • 1
    "I foresee some edge cases such as a significant portion of the tasks being scheduled at the beginning of an hour etc where the load peaks." - Jenkins handles this in part by encouraging the user to use an H (the job's hash) in the schedule, e.g. (H * * * * ) would run the job H minutes after the hour. Commented Apr 23, 2019 at 4:36

1 Answer 1

4

This is a very broad question, the answer would be by designing such a system.

I think however you are more interested in what techniques can be used to minimise the impact of a node failing, and restoring the behaviour of that node somewhere else in a reasonable amount of time.

Pairs

Pair every server. They are going to be responsible for one schedule. The schedule isn't necessarily what the customer considers to be their schedule. It is just a list of jobs, hopefully optimised to execute reasonably well on that pair.

One server is going to be the worker, and the other its watcher.

The worker is responsible for actually executing the task. It sends a periodic heartbeat, and other events to the watcher. It expects to receive a series of acknowledgements. It will only start a task once it has been acknowledged.

Conversely the watcher executes no tasks, and simple keeps a secondary book updated by the streamed events and heartbeats. In turn it sends acknowledgements. It is also responsible for streaming confirmed events through to a distributed database. (To support UI and recovery operations).

  • Should the worker not receive an acknowledgement within a period of X, it presumes that the network was cut between it and the watcher, and starts recovery.
  • Should the watcher not hear any event within a period of X, it presumes that the worker has died, and starts recovery.
  • Should the watcher see that its heart beat to the distributed database has not stabilised within some period Y, then it should stop acknowledging its partner (even though it should acknowledge the heartbeats). This places the pair into a holding pattern until the distributed database recovers.
  • Should the watcher observe that someone other pair has obtained the schedule when the database re-stabilises it should inform its partner and both of them join the unpaired pool, otherwise it resumes acknowledging the start requests that have been piling up.

Split/Broken Pair Recovery

Recovery is relatively simple. There exists a distributed database. Each partner of the severed pair attempts to join with a new partner. There is a pool of unpaired servers floating around willing to partner up. The pair establish a connection, and then register themselves with the distributed database as a replacement for the previous pair.

  • As the pair holds one of the original servers, the pair being replaced is obvious, and also allowed to replace the previous pair early (before the Y period).
  • If only one node survived from the old pair, there is no conflict about re-pair-ing.
  • If both nodes survived but are split, the distributed database will refuse one of the requests to update the schedule's pair. Either because the other pair was already accepted, or the distributed database is too fractured to ensure a single unique update.
  • The pair can only start processing tasks once the database has reached a distributed agreement.

Total Pair Failure and Recovering Unassigned Schedules

You will still need a watcher to watch the watched. That distributed database should receive a stream of updates as tasks are executed and completed. It should also receive a heartbeat (though a much slower beat) from each pair.

That pool of unpaired servers are not standing idle. Their job is to monitor the status of the schedules and their assigned pair in the distributed database, while they are waiting. If a pair has not been active in some Y (Y>X) window of time, then the unpaired partner up, and apply to become the new pair in charge of that schedule.

Schedule Updates

When the customer changes the tasks they want executed, they make a change to their schedule and commit it. The unpaired servers determine which schedules need to be updated, and send tasks the watchers in that pair. The watchers are then responsible for communicating the update locally, and committing it to the distributed database.

If for some reason the request requires a new schedule, the unpaired will create it, then notice that it has not got an active pair and recover it as if the pair assigned to it had failed totally.

There are some issues here regarding the consistency of the update.

  • As the database is distributed all of the fun of eventual consistency needs to be addressed.
  • Similarly because the schedules being assigned to servers may not match the schedules being created by users there is a mismatch.

It would make sense to offer updates to take effect at some point in the future. This would allow time to push the update through all affected servers, and ensure a consistent approach. If the deadline arrives without consistency having been reached, then the old schedule can simply be followed. The update might be rejected or modified to take effect at some later point. The user of the service can unambiguously see what schedule is currently in effect, and whether or not a change has been commenced, skipped, rejected, missed, etc... and hopefully see why.

Robustness

Should a pair become temporarily split, they can still heal by receiving an event within the X window. The smaller this period of time the more likely that a disruption will break the pair, but also the more likely that an actual failure can be quickly resolved (by finding a new partner). Obviously this pair should be as independent as possible, but they still need to be closely co-located to keep the delay low.

Should both servers in a pair become unavailable then the pool of unpaired servers will eventually notice this, generate a partner and resume processing. The Y window needs to be much larger than the X window. At least long enough to ensure that news of the pair healing, or recovering can be seen by all. In a distributed sense there might be several pools of unpaired/prepaired servers across several geographically separate locations.

Achilles Heel

However there still exists a single point of failure. Namely fragmentation and this is primarily a problem of the distributed database. There needs to be sufficient voting power left in a fragment to ensure that when the database is recovered that the current narrative is the only narrative.

Of course if you do not care about how often a task is actually executed this is not too much of a problem. Similarly the assignment of schedules to a pair is not too much of an issue either.

It does become problematic though when considering updating a customers schedule. How long between a customer requesting a change, and that change being made manifest can be tolerated?

There is also the problem of recovering a schedule when one of the tasks was started, but not yet confirmed as complete.

  • Do you retry?
  • Do you skip it?
  • Do you hold the schedule, and ask a Human?

Distributed Database

You can use an off the shelf distributed database, though you will need to break out the fine print. Many of these systems have odd eventual consistency guarantees or lack there of. You may need to implement your own consensus algorithm. Take a look at Raft.

No Pairs

Of course you can skip the paired watcher, combine the roles of watcher and worker together, and rely simply on the pool of workers without a schedule to recover the schedule after a Y period of time.

This will be much more efficient in terms of servers required (about 50%), but the trade off is responsiveness to failure. This is because the database must reach consensus that the old worker is dead, and which new worker will replace them. This can be significantly slower, particularly as most of the pooled workers will be vying for that position. In the paired scenario at most two pairs will be competing in all but total failure, and they will have commenced recovery much sooner (At X instead of the much later Y). In the event of total failure the system would still take Y time to recovery, although in this case there are probably grander issues afoot in the system.

You might consider critical and non-critical schedules. Critical schedules are assigned to pairs as they must be responsive. Non-critical schedules can be assigned to individuals, at the cost of a longer time to recovery.

1
  • Thanks for the thorough write-up, really appreciate it! Commented Jun 3, 2019 at 6:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.