3

I've been working on some data-deduplication which forced me to use the file system as a hash-table. This resulted in some directories which it took literal hours to delete using almost any reasonable method (i.e. rm -rf, ls -f1 | xargs rm, find -delete, etc.)

Under Ext2/3/4 file systems, a directory is a file containing a hash table from filenames to inode numbers (in my case, reaching around 60 MB!) As I understand, running rm -rf and friends is slow, because it follows this methodology:

Iterate over the hash table in the directory file. For every filename-inode pair encountered, atomically:

  1. Decrement the name count on the inode.
  2. Remove the entry from the hash table.

(Deletion of the files/inodes occurs when their name count reaches 0 and there are no programs having file descriptors open which are pointing to those inodes.)

Decrementing the name-count of an inode is fast.

Deleting a file (especially a small one) is also fast: one simply designates the drive blocks the file owns as free in the availability table.

The slowdown, as I can tell, arises in the removal of entries from the hash table. Each deletion probably has a chance to trigger a re-hashing, seeing as I observed the directory file's size diminishing as files were removed.

What I am asking is twofold:

  • Is my reasoning correct, in it being the hash-table manipulation that slows down the process?
  • If it is, is there is a tool that does the following (and which is thereby, probably a lot faster?)

    1. Decrement the name count of every inode listed in the directory file.
    2. Delete all content of the entire directory at once.
3

The ext3/4 directory isn't a hash table per-se. It's actually a hash tree. That is, the filename is hashed, and the hash is used as an index to insert into a b+ tree. The fastest way to delete all of the files will be to sort the files by inode number, since it will minimize the disk seeks required to pull the inodes from the inode table into memory, and the updates of the inode table as the files are deallocated. This will also tend to delete the files in the order they were created, which will optimize how the various block and inode allocation bitmaps need to be updated. One more thing you can do that will help is to increase the size of the journal (remove the journal using tune2fs and then recreate it with a larger journal size).

Ultimately, you should keep in mind that a file system is not optimized to be a database. If you want to do dedup, you really should consider using a database, and not try to hack around it by using a shell script and using a directory as a quick and dirty database. As you have discovered, that doesn't work terribly well....

2
  • 2
    Theodore Ts'o answering some random question about ext3/4. Nice. :) I've also seen Nobel Prize laureate physicist answering on Physics SE and I love when such things happen! Maybe the Pope on Christianity SE could beat this but I haven't seen that happen (yet). – Kamil Maciorowski Jan 20 '18 at 23:27
  • Thank's for clearing that up! And yeah, a database would have been much preferable; but setting it up to work would take longer than hacking it. I work in data science, and I am ashamed. – Karl Damgaard Asmussen Jan 23 '18 at 14:03
2

Deleting an entire tree is an expensive operation, but there may be ways to speed it up.

Did you try the solution listed in this answer and this answer? rsync seems to be the fastest because it optimizes the delete operations instead of simply going over the list of files as rm, find,... do.

Also, did you try this alternative?

EDIT:

Please Note: I haven't benchmarked this commands.

Commands I'm referring to in case the links break in the future:

rsync command of first two links:

mkdir blank
rsync -a --delete blank/ test/

Third link: "Move them to hidden directory, and then remove it in the background":

mkdir ../.tmp_to_remove
mv -- * ../.tmp_to_remove
nohup rm -rf ../.tmp_to_remove &

As explained in that answer, this approach assumes that (even if the removal is very expensive) as the deletion happens in the background in another tree, the user may not care for the actual cost. In my opinion, this is true as long as you do not try to close your bash/ssh session before the delete operation happens. In order to fix this, I've added a nohup to the rm command.

1
  • @KamilMaciorowski thank you for your feedback. I've updated my answer following your suggestion. – miravalls Jan 22 '18 at 8:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.