Atomic delete for large amounts of files

Question

I am trying to delete 10000+ files at once, atomically e.g. either all need to be deleted at once, or all need to stay in place.

Of course, the obvious answer is to move all the files into a temporary directory, and delete it recursively on success, but that doubles the amount of I/O required.

Compression doesn't work, because 1) I don't know which files will need to be deleted, and 2) the files need to be edited frequently.

Is there anything out there that can help reduce the I/O cost? Any platform will do.

EDIT: let's assume a power outage can happen anytime.

Answer 1

Kibbee is correct: you're looking for a transaction. However, you needn't depend on either databases or special file system features if you don't want to. The essence of a transaction is this:

1. Write out a record to a special file (often called the "log") that lists the files you are going to remove.
2. Once this record is safely written, make sure your application acts just as if the files have actually been removed.
3. Later on, start removing the files named in the transaction record.
4. After all files are removed, delete the transaction record.

Note that, any time after step (1), you can restart your application and it will continue removing the logically deleted files until they're finally all gone.

Please note that you shouldn't pursue this path very far: otherwise you're starting to reimplement a real transaction system. However, if you only need a very few simple transactions, the roll-your-own approach might be acceptable.

Answer 2

On *nix, moving files within a single filesystem is a very low cost operation, it works by making a hard link to the new name and then unlinking the original file. It doesn't even change any of the file times.

If you could move the files into a single directory, then you could rename that directory to get it out of the way as a truly atomic op, and then delete the files (and directory) later in a slower, non-atomic fashion.

Are you sure you don't just want a database? They all have transaction commit and rollback built-in.

Answer 3

I think what you are really looking for is the ability to have a transaction. Because the disc can only write one sector at a time, you can only delete the files one at a time. What you need is the ability to roll back the previous deletions if one of the deletes doesn't happen successfully. Tasks like this are usually reserved for databases. Whether or not your file system can do transactions depends on which file system and OS you are using. NTFS on Windows Vista supports Transactional NTFS. I'm not too sure on how it works, but it could be useful.

Also, there is something called shadow copy for Windows, which in the Linux world is called an LVM Snapshot. Basically it's a snapshot of the disc at a point in time. You could take a snapshot directly before doing the delete, and on the chance that it isn't successfully, copy the files back out of the snapshot. I've created shadow copies using WMI in VBScript, I'm sure that similar apis exist for C/C++ also.

One thing about Shadow Copy and LVM Snapsots. The work on the whole partition. So you can't take a snapshot of just a single directory. However, taking a snapshot of the whole disk takes only a couple seconds. So you would take a snapshot. Delete the files, and then if unsucessful, copy the files back out of the snapshot. This would be slow, but depending on how often you plan to roll back, it might be acceptable. The other idea would be to restore the entire snapshot. This may or may not be good as it would roll back all changes on the entire disk. Not good if your OS or other important files are located there. If this partition only contains the files you want to delete, recovering the entire snapshot may be easier and quicker.

Answer 4

Instead of moving the files, make symbolic links into the temporary directory. Then if things are OK, delete the files. Or, just make a list of the files somewhere and then delete them.

Answer 5

Couldn't you just build the list of pathnames to delete, write this list out to a file to_be_deleted.log, make sure that file has hit the disk (fsync()), then start doing the deletes. After all the deletes have been done, remove the to_be_deleted.log transaction log.

When you start up the application, it should check for the existence of to_be_deleted.log, and if it's there, replay the deletes in that file (ignoring "does not exist" errors).

Answer 6

I think the copy-and-then-delete method is pretty much the standard way to do this. Do you know for a fact that you can't tolerate the additional I/O?

I wouldn't count myself an export at file systems, but I would imagine that any implementation for performing a transaction would need to first attempt to perform all of the desired actions, and then it would need to go back and commit those actions. I.E. you can't avoid performing more I/O than doing it non-atomically.

Answer 7

Do you have an abstraction layer (e.g. database) for reaching the files? (If your software goes direct to the filesystem then my proposal does not apply).

If the condition is "right" to delete the files, change the state to "deleted" in your abstraction layer and begin a background job to "really" delete them from the filesystem.

Of course this proposal incurs a certain cost at opening/closing of the files but saves you some I/O on symlink creation etc.

Answer 8

On Windows Vista or newer, Transactional NTFS should do what you need:

HANDLE txn = CreateTransaction(NULL, 0, 0, 0, 0, NULL /* or timeout */, TEXT("Deleting stuff"));
if (txn == INVALID_HANDLE_VALUE) {
  /* explode */
}
if (!DeleteFileTransacted(filename, txn)) {
  RollbackTransaction(txn); // You saw nothing.
  CloseHandle(txn);
  die_horribly();
}
if (!CommitTransaction(txn)) {
  CloseHandle(txn);
  die_horribly();
}
CloseHandle(txn);

Answer 9

The basic answer to your question is "No.". The more complex answer is that this requires support from the filesystem and very few filesystems out there have that kind of support. Apparently NT has a transactional FS which does support this. It's possible that BtrFS for Linux will support this as well.

In the absence of direct support, I think the hardlink, move, remove option is the best you're going to get.