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

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

events.linuxfoundation.org

62 pointstim_sw26 comments

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.

And git's object store (but with sha1).

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.

Protip: if you just want to see what files are there use "echo *", it's much faster than ls.

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'.

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).

/bin/ls do the trick to avoid all options on the alias.

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

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.

> 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.

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.

> 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.

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.

Sure it is. You have to do twice as many directory lookups, even if they're cached.

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.

I must be stupid; with 2 hex chars (dir structure like 0a/7b/...) wouldn't we have 16*16 = 256 (edit: can't do math) entries per directory, not 96?

256 actually, but I have no idea where that 96 comes from, it was probably the alcohol typing (or I was already thinking 4096 and I wrote part of that instead of the correct number)

Worth mentioning that's "directory entries per directory". The "data files per directory" isn't driven by the intermediate path...just the total number of "full paths".

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.

PHP does have a config setting that will spread them across subdirectories.

See: http://php.net/manual/en/session.configuration.php#ini.sessi...

Yeah, this is more an experience related to be called in after the fact. Which has been fairly recurrent for me.

The XFS metadata performance has improved a lot and is now faster than ext4. See for example https://lwn.net/Articles/476263/

Of course there are still a lot of issues with reading that many files.

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.

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.

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

^ 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).

Reply on news.ycombinator.com