Reusable tasks

Tom Clegg
Last Updated: October 6, 2014

Overview

Objective

Say jobs A and B, although not identical, have some tasks in common. Job A is complete. Job B starting now. They use the same script, version, docker image, etc. The only difference between A and B is that B's input collection has one more file; the rest of the files are identical. The script processes each input file independently, and it is a pure function (re-computing the same files will produce the same result). This means most of Job B's work has already been done. Task re-use will allow Arvados to recognize this condition and re-use the outputs of Job A's tasks instead of recomputing them.

Task re-use will not attempt to detect equivalence conditions like differently-encoded collection manifests with identical data, differing git commits with identical trees, and differing docker images with functionally equivalent content.

The intended audience for this document is software engineers.

Background

The arvados.v1.jobs.create API offers a find_or_create feature which searches for an existing job which meets criteria specified by the client (e.g., same script, compatible script_version) and additional criteria (e.g., did not fail, is not marked impure/nondeterministic, does not diagree with other jobs passing the same criteria about what the correct output is).

Alternatives

Always recompute each task (i.e., leave existing behavior).

This makes desirable use cases prohibitively expensive.

Use smaller jobs, and more jobs per pipeline.

We could make the dynamic-structure capabilities of crunch jobs available at the pipeline level, and de-emphasize or stop using the features that encourage long-running jobs. Disadvantages include:

  • The process of running a pipeline is not done in a controlled environment. This effectively reduces the utility of reproducibility and provenance features.
  • Pipelines are currently encoded as JSON which is awkward to use as a DSL.

Tradeoffs

TODO

High Level Design

Before executing a job_task that qualifies for re-use, crunch-job uses the API to discover existing job_tasks that are functionally identical, are marked as "pure", and have already finished. If any are found, crunch-job copies the existing job_tasks' output into the new job_task instead of executing the task.

Specifics

Detailed Design

The JobTask schema has a new boolean flag is_pure (not null, default false).

Just before starting a task having is_pure==true, crunch-job does an API query look up other tasks with is_pure=true and identical inputs, parameters, script_version, etc.
  • Some attributes like script and script_version are currently stored in the job record, not the job_task record. This will make the lookup interesting, in the absence of a generic "join" API.
  • This should be done just before executing the task, rather than upon noticing the task has been queued. This increases the chance of finding duplicates when jobs overlap. (Otherwise, two identical jobs that run at nearly the same time will both find no reusable tasks, both queue the same set of tasks, and both execute all of them.)
Job tasks have one especially noteworthy side effect: queueing additional tasks. In order to reuse tasks safely without races, we need additional restraints:
  • Tasks with is_pure==true cannot queue additional tasks, and is_pure cannot change from false to true.
  • Tasks do not qualify for reuse until they have completed1. When reusing a task, copy (and reset to "todo" state) each task whose created_by_job_task_uuid attribute references the task being reused.

1 At least in the short term, this constraint is a good way to limit the complexity of implementation without sacrificing too much of the user benefit.

Code Location

sdk/cli/bin/crunch-job will have new task reuse logic.

services/api/db/migrate will have a new migration, which will be reflected in services/api/db/structure.sql.
  • add :is_pure boolean
services/api/app/models/job_task.rb will
  • add :is_pure to the API response
  • prohibit any transaction that changes is_pure from false to true. (IOW, is_pure can be set to true only at creation time.)

doc/api/schema/JobTask.html.textile.liquid will document the is_pure flag.

Testing Plan

TODO

Logging

crunch-job will log the fact that it has copied its output attribute (and, if applicable, queued additional tasks) from an existing completed task.

Debugging

TODO

Caveats

To be determined.

Security Concerns

The existing permission model can prevent user A's job from reusing completed tasks merely because they were initiated by a different user. In such cases (where user A has no other way of knowing about user B's job or task), this is preferable to exposing to user A the fact that any other user has run the task.

Open Questions and Risks

In the absence of a generic join API, it might be easy enough to implement a subset of full (ha, ha) join functionality to enable queries like filters=[["job.script_version","=","abc123..."]] under some simplifying conditions:
  • the current model (job_tasks) has a belongs_to relation called "job". (This could extend easily to a few other relations.)
  • anyone with permission to read a job_task also has permission to read the corresponding job. (This seems correct for job_task→job, but not for most other relations.)
Should purity be enforced or monitored?
  • Each task could be given a token with scopes restricting it to reading the collection hashes in its parameters hash and its own JobTask and Job resources.
  • API server could notice when a task with is_pure=true retrieves a collection record keyed by UUID, or any other resource that isn't content-addressed, and turn off is_pure automatically. This would be less disruptive, but can waste resources by going unnoticed.

Will there be a special-purpose API for looking up a reusable task, or a generic join-and-filter API? If neither, crunch-job will have to fetch multiple pages of job_tasks and jobs in order to reject ones with mismatched script, script_version, docker image, etc.

Do we indicate in the job_task record that the output was copied from an existing task? If so, how? (Note that a reference to the existing job_task can become stale due to permission changes.)

What are the appropriate values for a job_task's start/finish timestamp attributes, if the task's outputs were copied from existing tasks?

Work Estimates

TODO

Future Work

The database tables could be refactored into jobs, job_tasks, and tasks where job_tasks establishes a many-to-many relationship.

Table Significance of a row
jobs A user initiated some work (requested an output) using Crunch.
job_tasks A job must run a task in order to generate part of its output.
tasks A unit of work was (or will be, or is being) performed as part of a job.

This way, jobs could reference existing tasks directly rather than copying data between rows in job_tasks. Jobs could share tasks even before the tasks have completed.

A facility (and incentive) could be provided to denote tasks as reusable even by users to whom they are otherwise invisible: "If you can guess exactly what I did, and you have permission to read the inputs, I'll admit I did that work and I'll show you the output."

Revision History

Date Revisions Made Author Reviewed By
October 6, 2014 Initial Draft Tom Clegg ----
October 15, 2014 (cont'd) Tom Clegg ----
December 10, 2014 (cont'd) Tom Clegg ----