4 ms·

> e.g. not have 10e7 files in a single folder, which is something that Linux has some opinions (none of them good) about. I keep running in to this as a common

> e.g. not have 10e7 files in a single folder, which is something that Linux has some opinions (none of them good) about. I keep running in to this as a common anti-pattern in software, even with software developers that should know better (having fallen afoul of it before). I ran in to it with some semi-bespoke software once, used by a remarkable number of state departments across the country. It was one of many, many things wrong with that godawful thing. Worse, not only were they dumping files in a single directory, almost any time they went to do something with the directory they'd request a directory listing too. Like many of the bizarre things the app did, it never actually used the information it acquired that way.

cm2187 9y ago
I never understood why it mattered that files would be in a single directory or split over multiple directories. At the end of the day it is the same file system with the same number of files. The directories are just a logical structure. Why would there be a difference?
- jamie_ca 9y ago
  Spinning disks. If you want raw file access, your ideal filesystem is a giant key-value store that keys on the full path to the file. This choice means doing a directory listing will involve a lot of random access reads across the disk, and in the days before SSDs this would be a performance killer. So instead, a directory would have a little section of disk to write its file entries to. These would be fairly small, because most directories are small, and if there were more files added than there was room, another block would be allocated. Doing a file listing would be reasonably quick as you're just iterating over a block and following the link to the next block, but random file access would get slower the more files are added. It's probably a solvable problem in filesystem design, but because current filesystems fall down hard on the million-files-in-a-directory use case, nobody actually does that, so there's no drive to make a filesystem performant in that case.
  - the8472 9y ago
    ext4 uses btrees for the directory index, so accessing files by name is just as fast as manually splitting it into a prefix-based directory tree. Searching by filename on the other hand can be much faster with a prefix tree because directories only allow linear scans, not range-based ones.
    - ngrilly 9y ago
      I'm missing something. What difference do you see between "accessing files by name" and "searching by filename"?
      - the8472 9y ago
        f = open("/path/to/file"); // do something with file vs. d = opendir("path/to") while((dent = readdir(d)) != NULL) { if(!dent.name.startsWith("file")) continue; // do something with first matched entry } The former is O(log n) on ext4, O(n) on older filesystems that use flat lists. The latter is always O(n)
        ngrilly 9y ago
        Understood. Thanks ;-)
  - cm2187 9y ago
    Ok but listing 100 directories with 10,000 files each should take the same time than listing one directory with 1,000,000 files (what you are describing is a filesystem with more files vs less files, not with more subdirectories than less subdirectories).
    - hulahoof 9y ago
      The benefit is with accessing single files and not requiring a 1,000,000 directory listing lookup
- HeavyStorm 9y ago
  Well, my Linux-fu isn't very up-to-date, but my guess (which actually goes for any file system) is that a directory is a bit more than just a logical organization. It's an actual "thing" in your hard drive which keeps track of everything beneath it. And so it grows in size when more files are there, which slow down access.

cm2187 9y ago

I never understood why it mattered that files would be in a single directory or split over multiple directories. At the end of the day it is the same file system with the same number of files. The directories are just a logical structure. Why would there be a difference?

jamie_ca 9y ago
Spinning disks. If you want raw file access, your ideal filesystem is a giant key-value store that keys on the full path to the file. This choice means doing a directory listing will involve a lot of random access reads across the disk, and in the days before SSDs this would be a performance killer. So instead, a directory would have a little section of disk to write its file entries to. These would be fairly small, because most directories are small, and if there were more files added than there was room, another block would be allocated. Doing a file listing would be reasonably quick as you're just iterating over a block and following the link to the next block, but random file access would get slower the more files are added. It's probably a solvable problem in filesystem design, but because current filesystems fall down hard on the million-files-in-a-directory use case, nobody actually does that, so there's no drive to make a filesystem performant in that case.
- the8472 9y ago
  ext4 uses btrees for the directory index, so accessing files by name is just as fast as manually splitting it into a prefix-based directory tree. Searching by filename on the other hand can be much faster with a prefix tree because directories only allow linear scans, not range-based ones.
  - ngrilly 9y ago
    I'm missing something. What difference do you see between "accessing files by name" and "searching by filename"?
    - the8472 9y ago
      f = open("/path/to/file"); // do something with file vs. d = opendir("path/to") while((dent = readdir(d)) != NULL) { if(!dent.name.startsWith("file")) continue; // do something with first matched entry } The former is O(log n) on ext4, O(n) on older filesystems that use flat lists. The latter is always O(n)
      - ngrilly 9y ago
        Understood. Thanks ;-)
- cm2187 9y ago
  Ok but listing 100 directories with 10,000 files each should take the same time than listing one directory with 1,000,000 files (what you are describing is a filesystem with more files vs less files, not with more subdirectories than less subdirectories).
  - hulahoof 9y ago
    The benefit is with accessing single files and not requiring a 1,000,000 directory listing lookup
HeavyStorm 9y ago
Well, my Linux-fu isn't very up-to-date, but my guess (which actually goes for any file system) is that a directory is a bit more than just a logical organization. It's an actual "thing" in your hard drive which keeps track of everything beneath it. And so it grows in size when more files are there, which slow down access.