Checkpoint and Restart: Making a Multi-Hour Batch Job Resumable

A batch job that runs for six hours is a liability. The machine’s schedule assumes it completes; the night’s window is sized for it; the output it produces is the input to the morning’s work. If it fails in the fifth hour, the response cannot be to run it again from the beginning, because the rerun will not finish before the window closes. The job has to be resumable, and resumability has to be designed into it, because the operating system cannot supply it from outside.

The mechanism is a checkpoint: a record, written at intervals, of everything that must be restored for execution to continue from a chosen point. The design question is what “everything” means, and the answer is larger than it first appears.

What a checkpoint must contain

The naive answer is the program’s storage. If the job’s entire region is copied to a data set, the job can be reloaded from that copy and resumed. This works and it is wasteful: a region of 200 KB written every ten minutes for six hours is over seven megabytes of checkpoint data, and the writing competes with the job’s own I/O.

The refined answer separates what is volatile from what is recoverable.

Volatile state is what exists only in storage and nowhere else: the program’s working variables, its control blocks, its buffers with partially assembled records, the position of its own logic (which is to say, the instruction address and register contents at the checkpoint point). This must be written.

Recoverable state is what can be reconstructed from a durable artifact: input that has already been read can be re-read from the beginning, and output that has been written can be kept. But reconstructing by re-reading is only correct if re-reading produces the same records in the same order, and only if the job’s position in each input can be re-established exactly.

The checkpoint therefore consists of the region image plus a description of every open data set: which one, at what position, in which direction, with what buffered data. The position is the hard part.

Why a byte offset is not enough

A sequential data set on tape or disk has a position that is not a byte count. On tape, the unit of positioning is the block, and blocks are separated by gaps that have no addressable length; the drive reports its position by block count from the load point, and a block count is meaningful only if the tape has not been repositioned by another job in between. On a direct-access device, the position is a track and a record number within the track, and the mapping from a logical record number to that pair depends on the blocking factor.

Worse, the position is not sufficient even when it is exact, because the record format can be variable. A data set of variable-length records has no constant relationship between record number and byte offset, so resuming at “byte 4,000,000” requires reading the length fields from the beginning to find the record boundary. The checkpoint must therefore record a position that the access method itself can interpret, which in practice means the access method’s own position information rather than a number the program computes.

The consequence is that checkpointing is an access-method service, not an application service. The program calls a checkpoint routine, and the routine asks each open data set for its position in a form the same access method can restore later. An application that manages its own file positions by counting records can checkpoint, but only if it also records the count and can seek by count on restart, which requires the count-to-position mapping to be stable across the restart. For a fixed-blocked data set it is. For anything else it is not, and the checkpoint is wrong in a way that appears only on the resumed run.

The interval, and what it trades

Checkpoint frequency is a classic trade with two costs pulling in opposite directions.

A checkpoint costs the time to write the region image and the data set descriptions. If a job’s region is 200 KB and the checkpoint device sustains a few hundred kilobytes per second, one checkpoint takes on the order of a second, and the job’s total run time grows by the number of checkpoints times that cost. Checkpointing every minute for six hours adds three hundred and sixty seconds, which is a few percent. Checkpointing every five minutes adds about seventy seconds.

The expected loss on failure is the other side. If a job fails at a random time and checkpoints every T minutes, it loses on average half of T of work, plus the fixed cost of the restart itself: reloading the region, repositioning the data sets, re-reading whatever input had been consumed since the checkpoint. The restart cost is not zero, and for a job with a large region it can be tens of seconds.

Total expected cost is therefore checkpoint overhead plus failure probability times expected loss, and the optimum interval depends on the failure rate. For a job that fails once in a hundred runs, a long interval is correct. For a job that fails because a specific input record is malformed and always fails at the same point, no interval helps, and the correct response is to fix the record.

There is a third cost that is easy to miss: the checkpoint writes to a data set, and that data set occupies space and consumes a channel. A job checkpointing a 200 KB region every minute for six hours writes seventy megabytes, and if the checkpoint data set is kept on the same volume as the job’s data, the checkpoint traffic competes with the job’s own reads. Shops put checkpoints on a separate volume for this reason.

Restart, and the state that is not in the image

A restart is not a resume from a stored image. The image contains the program’s storage at the moment of the checkpoint, but the program was in the middle of a supervisor call or an I/O operation when the checkpoint was taken, and that operation’s supervisor state is not in the image.

The restart procedure handles this by re-establishing the job’s environment before loading the image: it allocates the region at the same address, assigns the same key, opens the same data sets, and positions them from the checkpoint record. Only then does it load the region image and transfer control to the saved instruction address.

Two failure modes are specific to this sequence.

The first is an address change. If the region is allocated at a different address than it had before, every absolute address in the image is wrong. This is the same problem as compaction in storage keys and region sizing, and the answer is the same: either the region must be reallocated at its original address, which the checkpoint record must therefore include, or the program must be relocatable, which on a machine without dynamic address translation means it must be assembled as position-independent or adjusted by a relocation table at load time. A checkpoint taken on a machine with dynamic address translation can be reloaded at any virtual address, which is one of the reasons virtual storage made checkpointing simpler.

The second is an incomplete output. A checkpoint is taken at a point where the job’s output data sets are in some state, and the restart resumes writing from that state. If the job failed after the checkpoint and the output data set was partially written, the restart’s writes will duplicate or overwrite the partial output depending on whether the data set was repositioned. The correct discipline is to position output data sets at the checkpoint’s recorded position and to discard anything written after it, which requires that the output data set be a direct-access data set rather than a tape, since a tape cannot be rewritten in place.

Generation data sets: reruns without destruction

A checkpoint handles a failure discovered during a run. A rerun handles a failure discovered after the run, and a rerun needs the previous run’s output to still exist. Versioning the output is how that is arranged, and it is also why a job’s printed output goes through a spool queue rather than straight to a printer: a spooled data set can be held and discarded, and paper cannot.

A generation data group is a named collection of data sets that share a base name and differ by a generation number. When a job writes a new generation, the group’s relative generation numbers shift: the newest becomes generation zero, the previous generation zero becomes generation minus one, and so on. The absolute name of each data set is fixed once created, so a job that references generation minus one gets the previous run’s output, unchanged, while the new run’s output goes to a new data set.

The effect is that a rerun does not destroy the output of the run it is replacing. If the rerun produces worse output than the original, the original is still there as generation minus one. If the rerun is correct, the original can be deleted by the group’s retention policy, which keeps a configured number of generations and deletes the oldest.

The mechanism also solves the restart problem for output. A job that fails and is restarted writes to a new generation, so the partial output of the failed run is a separate data set and does not corrupt the resumed run’s output. The restart’s data sets are positioned as if the failed run’s output never existed.

The cost is naming discipline. Every reference to a generation data set must be by relative generation number, and the numbers shift whenever a new generation is created. A job that references generation zero twice within one run will, if the first reference created a generation, get a different data set the second time. The shift is catalogued atomically, which is the property that makes the scheme usable: the catalog entry for the group is updated once, and every reference resolves against the updated set.

The general shape

Checkpoint and restart is an application of a pattern that appears at every level of durable systems: establish a consistent point, record enough to resume from it, and make the act of recording atomic.

In a database, the consistent point is a log record and the atomicity comes from the log’s ordering. In a file system, it is a journal commit. In a batch job, it is the checkpoint data set plus the catalog entry for the output generations. The differences are in what must be recorded, and the batch case is unusual in that the program’s own memory is part of the state, which is why the checkpoint is large and why the interval is a real trade rather than a formality.

The limitation is that the checkpoint captures a single job’s state, not a system’s. Two jobs that cooperate through a shared data set cannot be checkpointed independently and restarted consistently, because each one’s position depends on the other’s writes. Making that work requires the shared data set to be recoverable, which means a log or a two-phase discipline, and it is the point at which batch processing stops being able to solve its own problems and needs a transaction manager. That boundary is where the batch era’s techniques end and the online era’s begin.