6 ms·

One Billion Files: Scalability Limits in Linux File Systems (2010) [pdf]

62 points by tim_sw 11y ago

koverstreet 11y ago
another thing to benchmark in bcachefs. the architecture ought to scale to a billion files quite nicely :)
- loeg 11y ago
  ^ For other readers, Kent is the author of bcachefs and bcache. Unfortunately this slide deck is from 2010 and I don't believe bcachefs was around at the time. I, too, would be interested to see bcachefs's performance relative to the traditional Linux fs set (ext4 & XFS).
tyingq 11y ago
Mentioned in the presentation, but there are also much lower practical limitations with readdir(), stat(), etc, when you have lots of files in a single directory. If you want to be able to use ls, find, tar, etc without waiting eons: A typical workaround is to to take a hash (md5 or similar) of the filename and then pick some number of nested directories to store it in. Like: md5("data-file-one") == "0278c2451c1cd1dd98815260159c44e0" Assuming you go with 4 levels, then: mkdir -p "0/2/7/8/c" && mv data-file-one 0/2/7/8/c/data-file-one I believe apache's mod_cache takes this approach.
- leni536 11y ago
  And git's object store (but with sha1).
- chiph 11y ago
  We had to do this at a previous job, but on Windows. We split it out by 100's so this gave us fewer levels to traverse. This was on Windows Server 2000, so an earlier release of NTFS. The problem manifested itself by 100% I/O consumption by Windows Indexing service - turns out that when you added or updated a file it reindexed the entire directory. By using nested folders we reduced the number of files it would scan to an acceptable level. We then bought FAST. Microsoft later purchased them and folded into the Windows OS, becoming Windows Search. Which is pretty nice - I have it turned on for my local TFS workspace.
- lmm 11y ago
  Protip: if you just want to see what files are there use "echo *", it's much faster than ls.
  - MichaelBurge 11y ago
    It might be faster, but it won't work for large directories. For large directories, I either use 'ls --color=never' or the example C program in 'man 2 getdents'.
    - gnosek 11y ago
      ls -U avoids the default sort by name. Without -U you get all the names at once at the end of the directory scan. With the option you get them one by one (in some unspecified order) and can make sort of a progress bar for counting files in large directories: ls -U huge_dir | awk 'NR % 100000 == 0 { print NR } END { print NR }' (prints the count every 100k files and the total at the end).
    - sua_mae 11y ago
      /bin/ls do the trick to avoid all options on the alias.
  - tyingq 11y ago
    Tested a few things. "ls -U" seems to be the fastest approach I could find. -U disables sorting. $ mkdir testdir && cd testdir # make 200k files $ perl -e 'for (1..200000) {open(FOO,">$_");close(FOO)}' $ time echo * >>/dev/null real 0m1.607s user 0m1.480s sys 0m0.128s $ time ls >> /dev/null real 0m1.458s user 0m1.324s sys 0m0.132s $ # globs $ time perl -e 'for (glob("*")) {print "$_\n"}' >>/dev/null real 0m0.679s user 0m0.404s sys 0m0.272s $ time find . -maxdepth 1 -print >> /dev/null real 0m0.239s user 0m0.128s sys 0m0.108s $ time ls -U >> /dev/null real 0m0.195s user 0m0.064s sys 0m0.132s
- dr_zoidberg 11y ago
  Example from another field: data recovery on a hard drive yielded over 1,5 million posible JPGs. Linux died whenever we tried to get on the folder to do anything at all (we couldn't even move/rename the files with perl or python). Finally, we just deleted the directory and modified the carver program slightly[0] to extract 10k files, then make a new directory for another 10k files[1]. This was a few years so it might not happen anymore (with "just" 1.5M files) [0] this program was an in-house solution that handled some edge cases other programs available at the time didn't handle so well. [1] which is pretty much standard behaviour in file carvers, but wasn't part of the in-house development yet.
- masklinn 11y ago
  > mkdir -p "0/2/7/8/c" That's at most 16 entries per directory which seems unnecessarily low. Taking 2 chars/level gives 96 entries per directory which seems better, that's what Git uses (3 is 4096 which may be a tad high). Yields a flatter but not too broad hierarchy.
  - tyingq 11y ago
    That's a reasonable optimization, but wouldn't help much with runtime, since you aren't traversing any of it, but rather opening with full paths. I suppose it might make backups, or some sort of monitoring more efficient.
    - masklinn 11y ago
      > That's a reasonable optimization, but wouldn't help much with runtime, since you aren't traversing any of it Depends what data you're storing (or not storing) I guess. If you're storing all metadata anyway, you may even discard the original file name entirely and have the full path be composed of hash sections. But you may want to traverse the tree (because you're not storing much/any) data, and split things out because there's a number of APIs which don't deal well with humongous directories.
      - tyingq 11y ago
        Right, but open("a/b/c/d/e/f/0/1/2/3") isn't slower than open("ab/cd/ef/01/23"). Flatter only matters if you are traversing the hierarchy, which wouldn't be a normal use case for this.
        loeg 11y ago
        Sure it is. You have to do twice as many directory lookups, even if they're cached.
        tyingq 11y ago
        The open() system call isn't doing recursive "directory lookups" (like readdir()) per se. It does have to traverse a linked list (dentries) to map the path+filename into an inode. But 6 deep into a linked list vs 3 deep is, I suspect, hardly measurable in terms of elapsed time. It's all hashed, and cached.
- technion 11y ago
  I've run into this in production with PHP session files in /tmp. At a certain amount, just running "ls" would hang your process until you killed it.
  - tyingq 11y ago
    PHP does have a config setting that will spread them across subdirectories. See: http://php.net/manual/en/session.configuration.php#ini.session.save-path http://php.net/manual/en/session.configuration.php#ini.sessi...
    - technion 11y ago
      Yeah, this is more an experience related to be called in after the fact. Which has been fairly recurrent for me.
jerven 11y ago
The XFS metadata performance has improved a lot and is now faster than ext4. See for example https://lwn.net/Articles/476263/ https://lwn.net/Articles/476263/ Of course there are still a lot of issues with reading that many files.
- koverstreet 11y ago
  One thing I've noticed lately is XFS deletion performance is still by far the worst of all the filesystems I've been benchmarking. Aside from deletion, XFS does perform quite well though.
  - GauntletWizard 11y ago
    Deletion can and should be done super asynchronously, though - If you're doing a lot of deletes, rename your files into a garbage directory, and then clean that out in another thread.

62 points by tim_sw 11y ago

koverstreet 11y ago

another thing to benchmark in bcachefs. the architecture ought to scale to a billion files quite nicely :)

loeg 11y ago
^ For other readers, Kent is the author of bcachefs and bcache. Unfortunately this slide deck is from 2010 and I don't believe bcachefs was around at the time. I, too, would be interested to see bcachefs's performance relative to the traditional Linux fs set (ext4 & XFS).

tyingq 11y ago

Mentioned in the presentation, but there are also much lower practical limitations with readdir(), stat(), etc, when you have lots of files in a single directory. If you want to be able to use ls, find, tar, etc without waiting eons: A typical workaround is to to take a hash (md5 or similar) of the filename and then pick some number of nested directories to store it in. Like: md5("data-file-one") == "0278c2451c1cd1dd98815260159c44e0" Assuming you go with 4 levels, then: mkdir -p "0/2/7/8/c" && mv data-file-one 0/2/7/8/c/data-file-one I believe apache's mod_cache takes this approach.

leni536 11y ago
And git's object store (but with sha1).
chiph 11y ago
We had to do this at a previous job, but on Windows. We split it out by 100's so this gave us fewer levels to traverse. This was on Windows Server 2000, so an earlier release of NTFS. The problem manifested itself by 100% I/O consumption by Windows Indexing service - turns out that when you added or updated a file it reindexed the entire directory. By using nested folders we reduced the number of files it would scan to an acceptable level. We then bought FAST. Microsoft later purchased them and folded into the Windows OS, becoming Windows Search. Which is pretty nice - I have it turned on for my local TFS workspace.
lmm 11y ago
Protip: if you just want to see what files are there use "echo *", it's much faster than ls.
- MichaelBurge 11y ago
  It might be faster, but it won't work for large directories. For large directories, I either use 'ls --color=never' or the example C program in 'man 2 getdents'.
  - gnosek 11y ago
    ls -U avoids the default sort by name. Without -U you get all the names at once at the end of the directory scan. With the option you get them one by one (in some unspecified order) and can make sort of a progress bar for counting files in large directories: ls -U huge_dir | awk 'NR % 100000 == 0 { print NR } END { print NR }' (prints the count every 100k files and the total at the end).
  - sua_mae 11y ago
    /bin/ls do the trick to avoid all options on the alias.
- tyingq 11y ago
  Tested a few things. "ls -U" seems to be the fastest approach I could find. -U disables sorting. $ mkdir testdir && cd testdir # make 200k files $ perl -e 'for (1..200000) {open(FOO,">$_");close(FOO)}' $ time echo * >>/dev/null real 0m1.607s user 0m1.480s sys 0m0.128s $ time ls >> /dev/null real 0m1.458s user 0m1.324s sys 0m0.132s $ # globs $ time perl -e 'for (glob("*")) {print "$_\n"}' >>/dev/null real 0m0.679s user 0m0.404s sys 0m0.272s $ time find . -maxdepth 1 -print >> /dev/null real 0m0.239s user 0m0.128s sys 0m0.108s $ time ls -U >> /dev/null real 0m0.195s user 0m0.064s sys 0m0.132s
dr_zoidberg 11y ago
Example from another field: data recovery on a hard drive yielded over 1,5 million posible JPGs. Linux died whenever we tried to get on the folder to do anything at all (we couldn't even move/rename the files with perl or python). Finally, we just deleted the directory and modified the carver program slightly[0] to extract 10k files, then make a new directory for another 10k files[1]. This was a few years so it might not happen anymore (with "just" 1.5M files) [0] this program was an in-house solution that handled some edge cases other programs available at the time didn't handle so well. [1] which is pretty much standard behaviour in file carvers, but wasn't part of the in-house development yet.
masklinn 11y ago
> mkdir -p "0/2/7/8/c" That's at most 16 entries per directory which seems unnecessarily low. Taking 2 chars/level gives 96 entries per directory which seems better, that's what Git uses (3 is 4096 which may be a tad high). Yields a flatter but not too broad hierarchy.
- tyingq 11y ago
  That's a reasonable optimization, but wouldn't help much with runtime, since you aren't traversing any of it, but rather opening with full paths. I suppose it might make backups, or some sort of monitoring more efficient.
  - masklinn 11y ago
    > That's a reasonable optimization, but wouldn't help much with runtime, since you aren't traversing any of it Depends what data you're storing (or not storing) I guess. If you're storing all metadata anyway, you may even discard the original file name entirely and have the full path be composed of hash sections. But you may want to traverse the tree (because you're not storing much/any) data, and split things out because there's a number of APIs which don't deal well with humongous directories.
    - tyingq 11y ago
      Right, but open("a/b/c/d/e/f/0/1/2/3") isn't slower than open("ab/cd/ef/01/23"). Flatter only matters if you are traversing the hierarchy, which wouldn't be a normal use case for this.
      - loeg 11y ago
        Sure it is. You have to do twice as many directory lookups, even if they're cached.
        tyingq 11y ago
        The open() system call isn't doing recursive "directory lookups" (like readdir()) per se. It does have to traverse a linked list (dentries) to map the path+filename into an inode. But 6 deep into a linked list vs 3 deep is, I suspect, hardly measurable in terms of elapsed time. It's all hashed, and cached.
technion 11y ago
I've run into this in production with PHP session files in /tmp. At a certain amount, just running "ls" would hang your process until you killed it.
- tyingq 11y ago
  PHP does have a config setting that will spread them across subdirectories. See: http://php.net/manual/en/session.configuration.php#ini.session.save-path http://php.net/manual/en/session.configuration.php#ini.sessi...
  - technion 11y ago
    Yeah, this is more an experience related to be called in after the fact. Which has been fairly recurrent for me.

jerven 11y ago

The XFS metadata performance has improved a lot and is now faster than ext4. See for example https://lwn.net/Articles/476263/ https://lwn.net/Articles/476263/ Of course there are still a lot of issues with reading that many files.

koverstreet 11y ago
One thing I've noticed lately is XFS deletion performance is still by far the worst of all the filesystems I've been benchmarking. Aside from deletion, XFS does perform quite well though.
- GauntletWizard 11y ago
  Deletion can and should be done super asynchronously, though - If you're doing a lot of deletes, rename your files into a garbage directory, and then clean that out in another thread.