You can list a directory containing 8M files, but not with ls
be-n.com
be-n.com
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
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
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 .
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.
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.
https://web.archive.org/web/20170213221835/http://www.nobius...
Turning off case sensitivity lead to orders of magnitude difference in directory performance, and since most applications just use what they get from the system for filenames, there's very few problems in practice.
My main machines are all Windows and I've been running my NAS with case sensitivity off for almost a decade now, and only a few times did I have to manually rename some file through the NAS (two files with same name but different case). I use my NAS actively for a lot of things, including sharing files across my machines.
What filesystem are you using? I assume case-insensitivity means your filesystem does not support UTF-8 filenames. Is that the case?
You can set ZFS and in newer Linux Kernels for a filesystem to be case insensitive, and neither really cares about UTF8 to begin with as long as the filename contains no NUL characters.
Windows only requires the filename to be somewhat valid UCS-2 (ie, UTF-16 with the safeties off) on NTFS, FAT does the same for ASCII (though nothing stops a kernel from putting UTF8 in a FAT filename.
I assumed in your case that meant ASCII encoding, but i still don't understand how turning off case sensitivity would speed up things. Was that a typo, or am i missing something?
> nothing stops a kernel from putting UTF8 in a FAT filename
Except interoperability with other systems who may access this filesystem of course. Thanks for this explanation.
Maybe it's very Samba specific, but when doing a directory listing on a case-insensitive SMB share it parses the entire directory first before returning the first result.
I forgot the exact reason why, maybe to resolve conflicts, say "foo.txt" and "FOO.txt" can only have one entry.
Regardless, the result is a massive initial delay. Marking the share as case-sensitive skips all this. Worked wonders for me anyway.
Also, when creating "Foo.txt" on a case-insensitive share, it has to check that it doesn't collide with any existing file with different case, etc.
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.
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.
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).
This doesn't really solve the situation we're discussing though.
- owner and group,
- rwx flags,
- OS-specific flags such as the FreeBSD immutable ones,
- ACLs,
- extended file attributes
- possibly stuff I forgot
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.
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.
Any time you're dealing with such massive directories, you really must use the `-f` option to ls(1).
Fixing it by just creating a new dir and copying the files over is, thankfully, relatively straight-forward in my case :)
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.
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.
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!
It turns out that cleaning this up is decidedly non-trivial. Worse still, this was "managed" cloud storage with strict IOPS limits. The "one op per file delete" model seems logical until you're staring down the barrel of multi-week completion times.
I tried various things, but in the end the only practical solution was to copy the valid data across to a new volume and drop the old one. There was almost no reasonable way to delete that many files. As in this article, even the most basic command line tools like "ls" were useless!
You know you're in a bad spot when you're using "kill" on "ls" multiple times per hour...
It almost sounds like the cloud was someone else's computer all along, and we don't have any control over it. Thanks for sharing this anecdote!
The first section header reads "Why doesn’t ls work?", for instance.
Pages that haven‘t been adapted to HTML 5 in the last 10 years or so are exceedingly unlikely to do so in year 11.
Plus "ISO-8859-1" is treated as Windows-1252 by browsers, while unicode uses ISO-8859-1 extended with the ISO 6429 control characters for its initial 256 codepoints.
If it decodes successfully as UTF-8 it's probably UTF-8.
And yeah, add some sensible limits to this logic of course. Most web pages aren't never-ending nor multi-GB of text.
Also the only reference I find to this 1024 limit is for the charset meta element[1] in HTML5, which also seems highly redundant given that the very same page states UTF-8 must be used regardless.
Limits are good, but 1k is way to low.
[1]: https://html.spec.whatwg.org/multipage/semantics.html#charse...
I’m not sure this is correct, though the WHATWG docs[1] are kind of confusing. From what I can tell, it seems like HTML5 documents are required to be UTF-8, but also this is required to be explicitly declared either in the Content-Type header, a leading BOM, or a <meta> tag in the first 1024 bytes of the file. Reading this blog post[2] it sounds like there is a danger that if you don’t do this then heuristics will kick in and try to guess the charset instead; the documented algorithm for this doesn't seem to consider the doctype at all.
[1]: https://html.spec.whatwg.org/dev/semantics.html#charset
[2]: https://blog.whatwg.org/the-road-to-html-5-character-encodin...
>>> ftfy.fix_and_explain("’")
ExplainedText(
text="'",
explanation=[
('encode', 'sloppy-windows-1252'),
('decode', 'utf-8'),
('apply', 'uncurl_quotes')
]
)You can play around with FTFY here (open the “Decoding steps” to see the explanation of what it did and why): https://www.linestarve.com/tools/mojibake/?mojibake=’
0xe2 is â in iso8859-1. 0x80 is not in iso8859-1, but is € in windows-1252. 0x99 is not in iso8859-1, but is ™ in windows-1252.
So, the browser here appears to be defaulting to windows-1252.
(This used to happen a lot ~15 years ago. Did the dominance of UTF-8 make people forget about these encoding issues?)
https://0kalmi.blogspot.com/2020/02/quick-moving-of-billion-...
This doesn't pass my smell test:
> Putting two and two together I could see that the reason it was taking forever to list the directory was because ls was reading the directory entries file 32K at a time, and the file was 513M. So it would take around 16416 system calls of getdents() to list the directory. That is a lot of calls, especially on a slow virtualized disk.
16,416 system calls is a little inefficient but not that noticeable on human terms. And the author is talking as if each one waits 10 ms for a disk head to move to the correct position. That's not true. The OS and drive both do readahead, and they're both quite effective. I recently tried to improve performance of a long-running sequential read on an otherwise-idle old-fashioned spinning disk by tuning the former ("sudo blockdev --setra 6144 /path/to/device"). I found it made no real difference: "iostat" showed OS-level readahead reduces the number of block operations (as expected) but also that total latency doesn't decrease. It turns out in this scenario the disk's cache is full of the upcoming bytes so those extra operations are super fast anyway.
The real reason "ls" takes a while to print stuff is that by default it will buffer everything before printing anything so that it can sort it and (when stdout is a terminal) place it into appropriately-sized columns. It also (depending on the options you are using) will stat every file, which obviously will dwarf the number of getdents calls and access the inodes (which are more scattered across the filesystem).
"ls -1 -f" disables both those behaviors. It's reasonably fast without changing the buffer size.
moonfire-nvr@nuc:/media/14tb/sample$ time ls -1f | wc -l
1042303
real 0m0.934s
user 0m0.403s
sys 0m0.563s
~/test$ time for I in `seq -w 1 1000000`; do touch $I; done real 27m8.663s user 14m15.410s sys 12m24.411s
OK
~/test$ time ls -1f | wc -l 1000002
real 0m0.604s user 0m0.180s sys 0m0.422s
~/test$ time ls -f | wc -l 1000002
real 0m0.574s
~/test$ time perl -E 'opendir(my $d,".");say while readdir $d' |wc -l 1000002
real 0m0.597s
All seems reasonable. Directory size alone is 23M, somewhat larger than the typical 4096 bytes.
find . I recently was involved with a Windows filesystem driver. Windows lowest-level usermode APIs support iterating through directory contents for infinitely sized directories. (You just need to make sure whatever wrapper your language provides doesn't wrap the result in a pre-allocated array.)
For example, in C#, the System.IO.Directory static methods that return IEnumerables will let you iterate over millions of files without issue, at least on Windows. They probably will do the same on Linux and Mac.
(For that matter, streaming isn’t a panacea if your goal is, as the article states, to determine the number of files in the directory.)
In C#, at that point counting the number of files in a giant directory is trivial. (I was wrong about the method being static) Basically, "new DirectoryInfo(path).EnumerateFiles().Count()" is all you need. You're going to hit the most efficient APIs on Windows, so all you're limited by is hardware speed. (It's also worth checking on Linux.)
Anyway the coreutils shouldn't have arbitrary limits like this, at least if they do then the limits should be so high that you have to be really trying hard in order to reach them.
We had a special directory for temporary files produced when generating labels for barcode printer, and as they were very small (and always caused problems) - we never removed them so we can check out later if something went wrong.
After a few years customer complained some barcodes doesn't print. The error message was "cannot create a file XYZ" or something similar.
I logged in, checked the disk usage (plenty of space), checked the privileges (correct), did a "touch random_file_name" in that directory - worked fine, copied a few files into this directory - still works fine. Then I did "touch XYZ" and it failed :) But the file XYZ didn't already existed in that directory.
I don't remember the exact case (I think it was problem with index growing too big and depending on filename it was assigned to different levels or sth similar). Or maybe it was a hash collision in the filesystem? I don't even remember what filesystem it was - probably reiserfs or ext3.
The solution was to remove files after printing them, obviously.
Fortunately, the filenames were timestamp-based (down to the nanosecond), so could be be solved in one line of `sed`, and the hierarchy made tons of sense.
Normally, especially knowing older filesystem limits, I would've done such a filesystem hierarchy from the start (even if something wasn't as inherently hierarchical as timestamp strings, like if it used hash strings).
But this wealth of files (originally a secondary QA/debugging check, now a potentially valuable training data set) was due to unexpected success of an MVP launch, and it held up perfectly in production. I only cleaned it up when saving that data offline the other week, so it would be convenient&correct to use with tools that might not scale as well as that Linux filesystem and GNU tools did.
Additionally, having 8 million anything in a single directory screams bad planning. It's common for some hashing if directory structure to be planned.
"-1 list one file per line." and "-f do not sort, enable -aU, disable -ls --color"
It's not obvious to me that this would bypass the buffer and fix the problem of being able to list a large number of files. Just that I would get the files unsorted, one line at a time.
ls is slow because it will first load everything to ram, then do a bunch of operations (and it's not really optimized on those, it seems, at least not for speed) and if you have certain options enabled it will also need to stat() each file first.
Been there, done that, learnt not to run ls without -1f in a directory that would result in half-hour run.
The problem is when ls then tries to do all kinds of things after reading that data in order to sort, columnize, colorize, etc.
For example, just figuring out if you should add / after filename to indicate directory can, in worst case, require stat() call on every returned file - because there's no guarantee that file type will be filled in response from readdir()/getdents(). Sorting and displaying in columns is particularly slow. All sorts of things that are nice to have, cheap quality of life benefits, breakdown and become huge slowdowns with such insane directories.
Kinda reminds me of MS Excel when it first started defaulting to 1048576 rows. You could ctrl-downArrow to the bottom row, but if you ever tried to fill 1M rows it would hang.
https://unix.stackexchange.com/questions/120077/the-ls-comma...
Its interesting enough that I'm going to run my own test now.
1.1M files -> 120 seconds
1.8M files -> 270 seconds (this could be related to system load being over 90 heh)
Which filesystem you use will also make a big difference here. You could imagine some filesystem that uses the getdirentries(2) binary format for dirents, and that could literally memcpy cached directory pages for a syscall. In FreeBSD, UFS gets somewhat close, but 'struct direct' differs from the ABI 'struct dirent'. And the FS attempts to validate the disk format, too.
FWIW, FreeBSD uses 4kB (x86 system page size) where glibc uses 32kB in this article[1]. To the extent libc is actually the problem (I'm not confident of that yet based on the article), this will be worse than glibc's larger buffer.
[1]: https://github.com/freebsd/freebsd-src/blob/main/lib/libc/ge...
2.25M and its 60 seconds
I'm also spamming about 16-18 thousand new files per second to disk using a very inefficient set of csh scripts...
seq 1 8000000 | xargs touchStrangely "jot -w file 8000000 1 | xargs touch" worked.
I'm going to try to replicate this because I sense some kind of tomfoolery.
"ls" is using 2.5GB of ram, 76 seconds.
"ls -f" is using 2.4GB of ram, 18 seconds.
"ls -mf" uses like 2.4GB of ram, 20 seconds.
For those who say "cache!", no, I pre-warmed the cache and this is the result after that.
There are a few other things that could be related since the original article was about a VM. The VM is going to be affected by SPECTRE/Meltdown patches, a known performance thief. I've got them enabled on this box but I'll disable them shortly and re-test. Also my test box has 64GB of ram and is running FreeBSD 13 with ZFS. I get about 150MB/sec and 1100IOPs with the spinning rust drives.
Update: Turned off Spectre/Meltdown patches, "ls -f" takes 17 seconds, "ls -mf" takes 18 seconds, "ls" takes 70 seconds.
-f do not sort, enable -aU, disable -ls --color
-a do not ignore entries starting with .
-U do not sort; list entries in directory order
-l use a long listing format
-s print the allocated size of each file, in blocks
--color colorize the output
However, lets just accept that regular people don't know those tricks and we should keep files in subfolders? I have that logic in any app that has potential to spam a directory. You can still show them as a single folder (somewhere called branch view) if you like but every other tools that uses ls will work like a charm (such as your backup shell script)
I haven't looked in to the details but one system I can imagine is hashing the file names and then placing the file in the folder named with the first x parts of the hash. Then to look up you can use the filename to work out exactly which folder the file is in and you never exceed a set limit for files in one folder.
If we say 3000 files is perfectly safe in a single folder, 3000 folders with 3000 files holds 9M files.