6 ms·
If you are going to have a directory with millions of files, probably there's one more interesting thing to consider. As you might know ext* and some other FSs
by avaika 5y ago
If you are going to have a directory with millions of files, probably there's one more interesting thing to consider.
As you might know ext* and some other FSs store filenames right in the directory file. Means the more files you have in the directory, the bigger directory size gets. In majority of cases nothing unusual happens, cause people have maybe a few dozens of dirs / files.
However if you'll put millions of files, then directory size grows up to a few megabytes in size. If you decide to clean up later, you'd probably expect the directory size to shrink. But it never happens. Unless you run fsck or re-create a directory.
That's because nobody believes the implementation effort really worth it. Here's a link to lkml discussion: https://lkml.org/lkml/2009/5/15/146 https://lkml.org/lkml/2009/5/15/146
PS. Here's a previous discussion of the very same article posted in this submission. It's been 10 years already :) https://news.ycombinator.com/item?id=2888820 https://news.ycombinator.com/item?id=2888820
upd. Here's a code example:
$ mkdir niceDir && cd niceDir
# this might take a few moments
$ for ((i=1;i<133700;i++)); do touch long_long_looong_man_sakeru_$i ; done
$ ls -lhd .
drwxr-xr-x 2 user user 8.1M Aug 2 13:37 .
$ find . -type f -delete
$ ls -l
total 0
$ ls -lhd .
drwxr-xr-x 2 user user 8.1M Aug 2 13:37 .
- exdsq 5y agoCan you mv niceDir/* newNiceDir/ && rm -fr niceDir to reset the directory size?
- jhgb 5y agoI'd probably 1) hardlink all the files from the old directory into a temporary new directory, and 2) rename the new directory to the old directory's name. I'm no Unix guru but I believe that this should be completely unintrusive to even running processes, or at least less intrusive than your approach. Also failing in the middle seems more graceful.
- codetrotter 5y ago> completely unintrusive to even running processes Unless between the time that you create the hardlinks and the time that you delete the old directory, a process creates new files in the old directory. Unlikely of course, but not impossible.
- jhgb 5y agoYep, I've already thought of it in the several minutes after posting it. If it were possible to make a hardlink to a directory, my solution for a directory with a varying set of files would be: 1) hardlink all the files from the old directory ("foobar") into a temporary new directory ("foobar_tmp1"), 2) create a hardlink ("foobar_tmp2") to the old directory ("foobar"), 3) rename the new directory ("foobar_tmp1") to the old directory's name ("foobar"), 4) patch the "old" directory ("foobar" now linking to the shrunk directory) with the new files in "foobar_tmp2", 5) get rid of "foobar_tmp2". Still doesn't take care of all possible issues such as a program creating a file in "foobar" between steps 2) and 3) and reopening it very quickly after step 3), but at least it seems to avoid the issue of lost files. Sadly step 2) seems impossible. I still believe the original version should be transparent for a directory with a fixed set of files, but of course very large directories probably have a higher chance on average of their set of files changing in a short period of time. That may or may not be a problem. EDIT: Maybe a mandatory lock on the directory around the original step 2) with an additional check whether the directory's file set didn't change would work on Linux, if such a thing works the way I think it does (quite possibly it doesn't).
- remram 5y agoYou can't hardlink directories on Linux.
- LanternLight83 5y agoThey seem well aware of that :p
- 3np 5y agoI assume that if you could create hardlinks to directories, it would be to the same directory file and thereby point to the same garbage you want to get rid of. Don’t do that and you have a symlink.
- jhgb 5y agoNo, the point is to preserve the original set of files to account for lost file creations after the directory rename. What point would a symlink achieve? The original directory (the i-node, NOT the entry in the parent directory) with the new, unaccounted-for files would be gone and the symlink would point to a directory with only those files that would have been already preserved by the rename. So pointing "to the same old garbage" is exactly the point.
- remram 5y agoYou can't rename over a non-empty directory, so you can't do this atomically without using a symlink.
- jhgb 5y agoOh crap, I've never noticed that (or maybe I did many years ago and promptly ignored that because it wasn't what I was looking for at that time). Well, there goes the whole idea. Symlinks are of no use here, or at least I don't see how they help.
- remram 5y agoIf you know in advance that you'll need to switch a directory atomically, you can make `dir` a symlink to `dir_v1`. Then you can atomically replace it with a symlink to `dir_v2`. This doesn't really solve the situation we're discussing though.
- dreamcompiler 5y agoWouldn't you need a step 1.5: rm -rf <old directory>
- jhgb 5y agoWell, apparently I would, which mildly sucks because it takes too much time that I wanted to avoid completely by the ole' atomic rename technique. Worst case, at least one could possibly rename the old directory to a temporary name and then immediately rename the new directory with the new file links to the old name and hope for the best. Sadly the atomic technique doesn't seem to work here. I never noticed that I can't do this with a directory. Well, shit.
- Someone 5y agoOn top of what others said, creating a copy of an existing directory isn’t trivial. You have to copy - owner and group, - rwx flags, - OS-specific flags such as the FreeBSD immutable ones, - ACLs, - extended file attributes - possibly stuff I forgot Some of these you should set before copying in the files for security reasons, some of these you can only set after doing that. If the directory isn’t writable, for example, you can’t simply create it writable, copy in the files, and make the directory read only, as that opens a hole where others can write files to the directory. I think the only safe way is to create a directory that’s only readable and writable by you, copy in the files, then set the attributes right.
- barosl 5y agoThis issue is what makes me paranoid when putting a lot of files into a directory. Having directories whose sizes cannot be shrunk makes me really uncomfortable, so I try to avoid such a situation as much as possible. What's unfortunate is that you cannot predict at what point a directory will grow above its initial size, because the size of a directory is affected by not only the number of files, but also the varying lengths of their filenames. It's a complete mess. I wondered if NTFS on Windows is also not capable of shrinking already-grown directories but could not find information about it. As Windows doesn't report the size of a directory itself, it is hard to test the situation.
- nayuki 5y agoIt's hard to shrink the Master File Table (MFT) on Windows/NTFS. Each file or directory consumes 1 KiB in the MFT. So this is similar to the ext* directory-shrinking problem, but at the level of the entire volume instead.
- lisper 5y agoThe real problem here is that the unix file system is kinda sorta like a database but not really. So people try to use it like a database and it kinda sorta works, but not really. Someone ought to write a clean-sheet OS with an embedded copy of SQLite built in to the kernel. That would kick some serious tushy.
- deleted 5y ago[deleted]
- tzs 5y agoI haven't done any low Unix level filesystem stuff since the System V days. My recollection is that back then directories were just files that contained name to inode mappings. All the magic that made them directories was in how the system interpreted the data in them and in the access rules the system imposed on them. Allocating space for a directory was the same as allocating space for any other file, and the same for shrinking a directory. It sounds like the ext family of Linux filesystems didn't work that way, with directory storage managed in some manner completely separate from file storage. If that is the case I'm curious why.
- aidenn0 5y agoIIRC it does work that way, but deleting a file just zeros the entry for the file, so the file never shrinks
- infogulch 5y agoIs this an issue on ZFS?
- cryptonector 5y agoWay way back in 2005, before ZFS shipped, I actually checked this. Solaris' ls(1) with the `-f` option was able to list a directory with millions of files very quickly. But before I tried the `-f` flag I tried plain `ls`, and that failed miserably because a) ls(1) wants to sort the listing, which means reading the whole directory into memory then sorting it, b) I was using en_US.UTF-8 as my locale, and sorting in UTF-8 locales was way slower than sorting in the C locale. Any time you're dealing with such massive directories, you really must use the `-f` option to ls(1).
- chias 5y agoInteresting - a while ago I had a runaway script create files in a directory until the system ran out of inodes. I thought I had cleaned up after myself, and while that directory only has a hundred or so files in it now, the directory itself is still 154 megs. Wild. Fixing it by just creating a new dir and copying the files over is, thankfully, relatively straight-forward in my case :)
- gpderetta 5y agoGenerational garbage collection for the win!
- saltcured 5y agoSounds more like a plain old stop-and-copy/two space GC... Generational would be if they built a chain of directories to represent one (like with an overlay filesystem of some kind) and then periodically GC'd those at different rates, moving the persistent entries into less and less frequently scanned dirs.
- trasz 5y agoIt’s worth noting that the last problem is Linux-specific. In the BSD world, directories are “shrunk” when you create a new file or subdirectory; you don’t need to recreate the directory. (They are not compacted though, so if the last directory entry remains, the directory size won’t shrink.)
- southerntofu 5y ago> if the last directory entry remains, the directory size won’t shrink So if you keep appending data the directory will never be shrinked? If so i would say "the BSD world" is also affected by this problem, in practice. I'm assuming it all depends on the specifics of your filesystem, though.
- trasz 5y agoIf you keep appending the directory obviously won’t shrink because those entries need to fit somewhere - to shrink you’d need to remove stuff. Let me rephrase, though. In UFS/FFS, the kernel will try to truncate the directory size every time you add a new entry. However, it will only cut off the free space at the end, it won’t punch a hole inside. This means that if you remove a bunch of files/subdirectories, but leave the one occupying the last (highest numbered) directory entry, that directory won’t shrink. It will shrink after you remove that last one.
- southerntofu 5y agoYeah that's what i mean, that for a sort of append-only cache where a garbage collector kicks in to remove old entries (<-- the part i forgot to mention), the directory size will in fact grow forever. I must say that came as a surprise to me (i've used this pattern more than once, but never with millions of files), so thanks for telling me!
- suifbwish 5y agoMlocate can also be used for this so long as the updatedb index config contains the path of interest. Just run “updatedb” then run “locate /full/path/of/interest > file”