Undo vs. Redo
The atomic transaction algorithm I've just discussed performs filesystem actions as they are requested, and handles rollback and recovery by undoing actions. In contrast to this undo-based algorithm, a redo-based algorithm adds actions to a journal when they are requested, but does not actually perform them until commit. In practice, a redo algorithm maintains "shadow" copies of all files changed during a transaction, and replaces the originals with the shadows when the transaction commits.
As a simple example, let's contrast the undo and redo versions of a basic atomic file write. Here is the undo version, repeated from above for convenience:
E1u. Rename the original file to a backup file. If there is an error doing this, then delete the backup file, if any, and report failure.
E2u. Write the file. If there is an error doing so, then restore the backup and report failure.
E3u. Otherwise, delete the backup and report success.
This is the redo version:
E1r. Write to a shadow file. If there is an error doing so, then report failure.
E2r. Rename the shadow file to the original file (deleting the original first, if this is necessary).
The redo version is a bit simpler, but its greatest advantage is in recovery. If there is a crash during or just after E1r, then the original file was never changed, so recovery isn't necessary (except for the detail of cleaning up the shadow file). In filesystems that permit renaming to an existing file, step E2r is atomic, and its successful completion commits the transaction. (In filesystems that require that the original is deleted before the rename can take place, a crash between the delete and rename necessitates recovery.)
We can generalize the redo approach to sequences of actions. Actions are written to a journal as they are requested, and performed at commit time. If a crash occurs before commit, then no recovery is necessary because nothing has been changed.
This lack of need for recovery makes the redo approach very attractive. The algorithm seems simpler, and more importantly, after a crash, the filesystem is in a consistent state, even if the program that generated the transactions never runs again. But there are some hidden problems with the redo approach.
First, if a crash occurs while the actions are being carried out during commit, then the file system is in an inconsistent state, requiring recovery. In other words, the redo approach doesn't eliminate the need for recovery; it just shortens the window of time when it is necessary. The recovery and rollback steps involved if a crash occurs during commit are essentially the same as in the undo approach.
A second and more important flaw with the redo approach is that problems with an action are not reported until commit, since the action doesn't actually take place until then. Say the user performs a delete under a transaction, and then executes other actions as part of that transaction, assuming that the delete succeeded. The user must wait until commit time to discover whether the delete failed, and thus whether the other actions were justified. In fact, it is impossible to write a transaction that behaves differently depending upon whether or not an action succeeded, since this fact can't be known until a commit is requested. Typical filesystems provide no way to test whether an action would succeed other than actually performing the action.
For these reasons, I believe that the undo approach is better than the redo approach for implementing atomic filesystem transactions.
A Tour of the Package
com.astrel.io.atomic package implements the undo logic described above. In addition to the classes
Transaction, there is a
Journal class that handles the details of reading and writing the journal, an
Action class that represents a single filesystem action, and subclasses of
Action for each of the supported actions. There are also several exception classes, which I won't discuss.
This class manages a set of transactions. It maintains the directory where journal files are written and provides each transaction with a unique number. It also performs recovery by scanning the directory for journal files and asking the
Journal class to perform rollback on each file.
This class ensures that a sequence of actions is performed atomically. Its constructor creates a journal. The methods
rename are really just one-line convenience methods that create an instance of the appropriate
Action subclass, and then call the
run method with the action. The code for
run (simplified slightly to ease explanation) is shown in Listing 1. Since it is one of the central methods of the system, I describe it in detail.
Transaction.run takes an action as argument and returns a value that depends on the action (a
FileOutputStream, for example, in the case of the action corresponding to the
openOutputStream method). The action has already been created, and so it has all the information necessary for it to be executed (e.g., the name of the file to open). The job of
run is to generate undo information for the action, write it to the journal, execute the action, and return its results. The task is complicated by the need to handle errors correctly. Errors in the action's execution are returned to the caller normally. Problems with generating or saving the undo information are caught and rethrown as
TransactionExceptions, after rolling back the transaction. Problems in rollback cause
InconsistentStateException to be thrown.
run method begins by calling the action's
prepare method. This causes the action to determine all information necessary for undo. Typically, this is the name of a backup file. It may also be part of a file's current state. For instance, an action that changes the permissions on a file would need to know the current permissions for undo purposes. The action should place the information in its nontransient instance variables.
prepare returns, the action is serialized into the journal. The undo information, saved in nontransient instance variables, is thus written to disk.
Journal.writeAction ends with a call to
FileDescriptor.sync to make sure the action's serialized form is on disk before proceeding. Then the action's
createBackup method is called, which actually creates the backup file, if any.
If any one of these three methods --
Action.createBackup -- fails, then the transaction is rolled back and a
TransactionException is thrown to indicate a problem with the transaction machinery itself.
Finally, the action is executed and its result is returned. Errors here result in the journal entry for the action being erased (the job of
Journal.actionFailed). Since the problem occurred while executing the action itself, and not in the transaction system, the original exception is rethrown. The transaction is not rolled back (unless
Journal.actionFailed itself has a problem); it can be continued with a different action. (The assumption is that if an action fails, it does not change the state of the filesystem. Thus each action must itself be atomic.)
This abstract class contains the methods required to perform and undo a single action, as well as convenience methods that can help in this task. Particular actions are subclasses of this class. Listing 2 shows the class for deleting a file, called
DeleteAction. You can provide your own actions by writing your own subclass of
The constructor will receive the arguments of the action, and can choose to throw exceptions if it determines that the action cannot be carried out. For example, the
DeleteAction constructor throws a
FileNotFound exception if it is asked to delete a file that does not exist.
prepare method has the job of saving any information needed to undo the action. Often this involves naming a backup file. The
generateBackupFilename provides a robust way to do this. It generates a unique name in the same directory as the original file, using the original file name, a unique sequence number, and the extension
.abk. (This extension can be changed by setting a property or by calling a method in the
TransactionManager class.) At the time it returns, it guarantees that the file doesn't exist.
prepare method simply invokes
generateBackupFilename on the original filename and stores the result in an instance variable.
createBackup method is responsible for actually making the backup. The
copyNotDeleting are useful for this. As their names suggest, these methods will not delete the target file if it exists; instead they throw an exception. This prevents inadvertent erasure of backup files that may have been generated by some other process. Since
generateBackupFilename ensures that the filename created doesn't exist, and since
createBackup is called milliseconds later, it is extremely unlikely that this error will occur.
createBackup method calls
renameNotDeleting to rename the original to the backup.
When should a backup be created by copying the file, and when by renaming? Renaming is much faster, but copying makes more sense if the original must continue to exist -- for example, when appending to a file.
execute method carries out the action, possibly returning an
execute method has nothing to do, since renaming the original file to the backup has effectively deleted the file. The
execute method of the
Action subclass for opening a file creates and returns a
At the end of the transaction,
close method is called to close files or perform other normal ending operations.
In a successfully committed transaction, only the
close methods will be called.
During rollback, an action's
undo method will be called. The
undo method must undo the action if it in fact occurred. The method is responsible for detecting this -- that is, for implementing the local undo property. (See the appendix for a description of this property.)
DeleteAction's undo method renames the backup file to the original file.
cleanup method gives the action a chance to delete backups or other filesystem states. It is called after a successful commit or rollback.
This class uses a
RandomAccessFile to manipulate the journal. It contains methods for writing actions and markers into the file. It is careful to flush all in-memory data to disk using
sync method after each method call, to ensure that crashes are handled correctly. For example, if an action's undo information is not written to disk before the action executes, it will be impossible to undo the action after a crash.
Frank O'Dwyer of Rainbow Diamond Limited in Ireland has independently written a similar file transaction package. The idea of using
end methods instead of commit and rollback methods is his, as is the method of creating backup files. There are a number of minor differences in our systems, but the main one is that his uses redo logic instead of undo logic. For reasons I discussed above, I think the undo approach is superior.
This article described a package that makes it possible to perform filesystem actions like writing, deleting, and renaming files atomically. Although the underlying algorithms are complex and subtle, using the package is quite straightforward. Consider it as an alternative to a database when only atomicity is required.
Continue to next page for Appendix: Correctness of the Algorithm
Jonathan Amsterdam is Senior Consulting Engineer at DataSynapse, Inc. Prior to that, he was president and founder of Astrel, Inc., a Java training and consulting firm.
Return to ONJava.com.