Introducing Selene - an open source library for scheduling tasks on iOS

September 11, 2014

Last month we released Connected for iOS, an app which surfaces contextually relevant relationship opportunities like job changes, work anniversaries and mentions in the news for people in your network.

To ensure that the user has the most up-to-date data we need to periodically perform tasks such as:

  • Upload calendar events (only if user has given permission)
  • Upload address book (only if user has given permission)
  • Download contacts
  • Download feature flags

In the interest of having the data ready for consumption the moment the app is opened, we wanted to leverage the background fetch capability, while keeping the following points in mind:

  • The completion handler should be invoked within 30 seconds. This is of paramount importance, as failure to do so will result in the application receiving fewer background fetch opportunities later (or possibly even result in the app being suspended).
  • It is not necessary for every task to be executed on every cycle of background fetch. Executing all tasks on every cycle may not be optimal, for reasons such as performance, battery consumption, and bandwidth. Additionally, because the iOS background fetch capability is opportunistic, only the tasks that are deemed most important should execute.
Why 30 seconds? Background fetch is not intended for CPU intensive operations, or long running tasks, but rather for performing quick content updates. As such, 30 seconds should be ample time to finish all desired tasks.

The result of our work is Selene - an iOS library which schedules the execution of tasks on a background fetch.

Check out Selene on GitHub now!

The Selene solution

At every execution of the application delegate's application::performFetchWithCompletionHandler: Selene determines which tasks should run, via its scheduling policy.

Scheduling Policy

Currently, Selene's scheduling policy ranks the tasks according to their priority, average response time, and elapsed time since last execution.

The mere mention of scheduling policy is reminiscent of the Linux Scheduler. That's not too far off, as Selene attempts to emulate the behavior, but for a much more simplified objective.

Priority

Assigned by the user, the value ranging from 1-5, in increasing priority value.

Average response time

Initially, this is set by the user. The response time should be relative to how expensive the operation is. For example, if the operation makes an HTTP request which is known to take a considerable time, then the response time is high. Therefore, we can consider the response time to be a function of time, memory consumption, and other factors, typically approximated as a constant. After the first execution of the operation, the response time is then calculated dynamically as a simple moving average (SMA) using the previous n response times.

Elapsed time since last execution

This value is calculated at run-time, by Selene.

For the simple moving average calculation, Selene uses the default period of 3. You may choose a different value by implementing numberOfPeriodsForResponseTime. Choosing a value for the period depends entirely on the objective of the task. The greater the period, the smoother the average will be. As an example, for HTTP requests it may be best suited to choose a smaller period, as it would result in an average that is more susceptible to current changes. Specifically, during network peak times, there may be increased response times, which in turn would increase a task's response time SMA, consequently resulting in (possibly) less subsequent executions of the task.

With the values above, each task can then be ranked according to their score, described below.

Score

Selene calculates the score using the (somewhat rudimentary) following formula:

$$score = P'⋅T'$$

Where

  • P' is the normalized priority, and
  • T' is the normalized elapsed time since last execution.

Normalization is done using the rescaling method: $x' = {x - min(x)} / {max(x) - min(x)}$

Determining which tasks to execute

Since there's only a finite amount of time (30 seconds) in which tasks should execute (and complete), Selene needs to determine which tasks can best complete within that timeframe. The algorithm can be written as:

https://gist.github.com/krisk/f67c6f6809cd9e4c78b6.js

Example

For the purpose of this example, let the total available time be 10 seconds (as opposed to the max of 30s). Suppose we have the following tasks:

For illustrative purposes, the values for the average response time are exaggerated. Hopefully, in the real world, your response times are somewhat speedier.

Click on the button below (multiple times) to simulate a background fetch cycle. Waiting a few seconds before clicks will demonstrate the ranking and execution order.

Execute

Try it out!

Here's everything you need to know to start using it today.

Get involved

Feel free to fork Selene on Github and send us some pull requests!

Acknowledgements

Thanks to Walter Fender, Haider Sabri, and Roman Inozemtsev for a lot of ideas.

Topics