Why kernel.org is slow

Note that fragmenting a file in this manner tends not to be a performance issue since large linear reads still mostly read the file of interest, and skipping a few blocks doesn't typically cause a seek. That is why I imagine it's not widely considered an issue. It's quite a bit different than, say, the old MS-DOS first-fit policy that could cause a file to be literally spread piecemeal across the entire filesystem. That sort of fragmentation destroys performance.

Just curious,
Etienne.

ext3 for large directories hashes the filename and looks it up in a
btree. Using a hash of the filename results in a better branching
factor in your btree. So the on-disk data structures are not at
a disadvantage.

I haven't looked but ext2+ directories should all be kept in the same
block group which is roughly a single disk track. So even with
fragmentation the disk track cache should work well. I don't remember
if block groups are small enough so that they always map to the
same disk track though.

So I'm pretty certain the issue is the large directories the inode
semaphore.

Read-ahead should help a lot if the pages don't get thrown out before we
use them.

Changing the locking to allow more concurrency is a trickier problem.
If done right my gut feel is that you should be able to operate
essentially lock free, with multiple concurrent writes and reads going on
simultaneously. The readdir semantics allow for it. But anything with a
high degree of concurrency comes with tricky corner cases.

Eric

It's a bit a mystery for me why nobody has attacked this problem a long time ago. Directory read was always a pain in the neck, and you can imagine how slow it is if you compare locate with find (and how big the impact of rebuilding the locate database is).

From a more abstract point of view, the directory is a data base with file names, and a n:1 relation between file names and parent directories. The relation between overall file system size and directory size is quite good, i.e. the directory size is a small percentage figure. On a larger file sever here with about 1TB space used, the locatedb (which contains just everything) is only ~64MB. Even when you use a larger, less space-efficient directory structure, 128MB/TB should be completely sufficient. A modern RAID array can read 128MB in a fraction of a second, the memory is there to keep it all, so a find / -name '*' can - if well implemented - print a result within a second or less.

I'd suggest the following to the file system implementors: Forget everything you'd read about Unix directories. Start from scratch. Get a decent knowledge about how data bases work, the directory is a data base. An extremely simple one, so to say. Create a single directory file for the directory data base; make sure that it won't fragment much over time (if the directory grows beyond the previously allocated space, allocate a larger space, and copy the directory over completely). Do read-aheads and all the other caching stuff like for any other file, when accessing the directory data base. Keep the file names easy to access by using a large hash table (on disk - not to be computed on the fly!). Hash key is computed as usual from the directory id+file name hash.

And for the locking: Make sure that readers never have to lock a directory. They'll maybe get stale content, when a writer adds or removes files from a directory, but that's ok. You can never rely on getdents() entries to be valid when you open() them later. Writers should use a RCU mechanism for updating directories.