7 ms·

Can someone explain why "Items moved from /12345 to /12/34/12345. HN now starts in one fifth the time" that increases performance? why is it better?

by bndr 12y ago

fennecfoxen 12y ago
This is a common technique to limit the number of files in any single directory when you store your date in many many files on disk. You will also see this in things like web cache software and the like.
- VLM 12y ago
  Thats what it is. The specific "why" is there aren't many O(1) directory traverses. So a million files in a dir is going to take longer to access any individual file than if there's only 3 files to pick from. And if it scales worse than linear, a tree structure, although hitting the FS multiple times once at each level, in total can take less time. Finally if you can avoid a smooth distribution hash and intentionally order by something important (time?) then you only need a cache the most recent directories in memory and the deep historical archive can fend for itself rarely accessed without getting in the way of the busy files. If you rarely if ever leave /stuff/thisYear/today/ then whatever is in /stuff/2011/dec25 will never slow today down or get in the way.
oneeyedpigeon 12y ago
Someone will explain this better but, as I understand it, having a huge number of files in a single directory becomes inefficient at a certain number; organising those files hierarchically brings an improvement. If HN really stores each item as a file in one big directory, that directory used to contain almost 8 million files ...
- leephillips 12y ago
  Not only inefficient; some linux commands fail when they're used on more than a few million files at a time - there is a maximum number of arguments that they can handle. EDIT: bzbarsky's explanation below is more accurate.
  - bzbarsky 12y ago
    Typically the issue is not the commands themselves but the shell. Trying to do "something *" on the shell command line will expand out the glob, and if the resulting string is too long (e.g. you fail to malloc() it!) the shell will do something ranging from crashing to not running the command and giving a useful error message.
    - larrys 12y ago
      Not claiming to be an expert here but I typically do this when confronted with a large number of files. Instead of: command * for i in [someregex]* do command $i done I know I could also do command [someregex]* but like the comfort of having each item echo back to the terminal so I know the progress.
      - andreasvc 12y ago
        That still relies on the shell expanding a glob of millions of files. Another method is to use 'find' and 'xargs' to avoid specifying the files as arguments explicitly.
jacquesm 12y ago
Directory scans suck. So if you break up the space into sets of prefixes you limit the number of files in each dir and traversal gets much faster. Ditto adding/removing items. Some filesystems are worse at this than others (xfs... let's not go there).
- adrianmsmith 12y ago
  Would the HN software need to scan the directory e.g. to read in all users, at any point? I don't know the source code of HN but I can't see why that would be necessary. (And if it did need to, presumably it's now need to recursively scan all sub-directories, which would also take a while?)
  - jacquesm 12y ago
    No, you need to scan the directory every time you read a file. So most filesystems do a lot of work to optimize this but it is still a significant factor.
    - adrianmsmith 12y ago
      Not sure I agree with that. I ran the software for community with 6M users, and on 2003 hardware we had millions of files in one directory. That was with advfs on tru64 so things might be different with other file systems. But e.g. zfs can do this no problem as well. I just sort of assumed other FSs must have caught up in the intervening 10+ years but I haven't looked into their source code so an prepared to admit I might be wrong about them. The same way a database fetch doesn't load the whole table, filesystems can and do use trees and hashes to organize directories so that file lookup, creation and deletion by name can be fast and can be concurrent. I posted this in another comment, but this was my understanding of the situation in 2010. http://www.databasesandlife.com/flat-directories/ http://www.databasesandlife.com/flat-directories/ There must be a reason why they did this change, either I am wrong about performance (perhaps my results really were particular to those filesystems) or perhaps I am right and they made the change for another reason. I'd like to learn the answer.
zimpenfish 12y ago
If you look up "directory hashing" (possibly also "directory sharding"), that'll explain things. Particularly relevant to things like email servers and shared web hosts.
deleted 12y ago
[deleted]
js2 12y ago
Large directories can be very slow to scan (readdir). By fanning out the items into more directories of fewer items, performance is improved. Git does something similar with its objects directory. This is an old Unix trick. Note that Linux ext3/ext4 have a dir_index option which improves readdir performance. Edit: it's not readdir performance so much as just name lookups which are improved by this technique (and dir_index): http://ext2.sourceforge.net/2005-ols/paper-html/node3.html http://ext2.sourceforge.net/2005-ols/paper-html/node3.html
- adrianmsmith 12y ago
  My experience was the opposite. In code I wrote - I never needed to scan the directory to find "all users" (after all, if you have millions of users, this is going to take a while whatever directory structure you use) - Modern filesystems either use a tree or hash structure to identify files, meaning that lookup by name, and creating/deleting files, is quick, even if you have millions of files. - Given no performance benefits are to be had by directory nesting, I always went with the option of simplicity, i.e. having everything in one directory. (I blogged about this here: http://www.databasesandlife.com/flat-directories/ http://www.databasesandlife.com/flat-directories/) But no doubt the HN developers had a reason for doing this change, I'd love to know what it is (e.g. if they need to do something I never needed to do, or if they need to do the same things but I was wrong.)
  - caoimhin 12y ago
    The fs caches the directories. So in a large, flat dir structure it has large, flat dirs it needs to cache. Now I'm not sure how big the win will be for accounts since one assumes active vs. inactive accounts will be randomly spread around alphabetically. So loads of these smaller dirs will be loaded. But for articles it should be a win since it's mainly the most recent ones that will be accessed so you'll have a hotspot and the vast majority of the directories won't be accessed.
  - unreal37 12y ago
    The site loads 5 times faster. So clearly there are performance benefits to directory nesting.
deleted 12y ago
[deleted]
eCa 12y ago
An aside: When storing large quantities of things like this my personal preference is to split the id from the end. I was once i charge of a large number of images of book jackets named by the books' isbn. At least in that population (which of course is an extreme example considering how an isbn is created) the distribution is much more even (that is, the directory sizes are relatively equal) when using the end than the beginning, but I would not be surprised if that is a normal outcome. Maybe it's an application of Benford's law [1]. [1] http://en.wikipedia.org/wiki/Benford%27s_law http://en.wikipedia.org/wiki/Benford%27s_law

Can someone explain why "Items moved from /12345 to /12/34/12345. HN now starts in one fifth the time" that increases performance? why is it better?

by bndr 12y ago

Can someone explain why "Items moved from /12345 to /12/34/12345. HN now starts in one fifth the time" that increases performance? why is it better?

fennecfoxen 12y ago

This is a common technique to limit the number of files in any single directory when you store your date in many many files on disk. You will also see this in things like web cache software and the like.

VLM 12y ago
Thats what it is. The specific "why" is there aren't many O(1) directory traverses. So a million files in a dir is going to take longer to access any individual file than if there's only 3 files to pick from. And if it scales worse than linear, a tree structure, although hitting the FS multiple times once at each level, in total can take less time. Finally if you can avoid a smooth distribution hash and intentionally order by something important (time?) then you only need a cache the most recent directories in memory and the deep historical archive can fend for itself rarely accessed without getting in the way of the busy files. If you rarely if ever leave /stuff/thisYear/today/ then whatever is in /stuff/2011/dec25 will never slow today down or get in the way.

oneeyedpigeon 12y ago

Someone will explain this better but, as I understand it, having a huge number of files in a single directory becomes inefficient at a certain number; organising those files hierarchically brings an improvement. If HN really stores each item as a file in one big directory, that directory used to contain almost 8 million files ...

leephillips 12y ago
Not only inefficient; some linux commands fail when they're used on more than a few million files at a time - there is a maximum number of arguments that they can handle. EDIT: bzbarsky's explanation below is more accurate.
- bzbarsky 12y ago
  Typically the issue is not the commands themselves but the shell. Trying to do "something *" on the shell command line will expand out the glob, and if the resulting string is too long (e.g. you fail to malloc() it!) the shell will do something ranging from crashing to not running the command and giving a useful error message.
  - larrys 12y ago
    Not claiming to be an expert here but I typically do this when confronted with a large number of files. Instead of: command * for i in [someregex]* do command $i done I know I could also do command [someregex]* but like the comfort of having each item echo back to the terminal so I know the progress.
    - andreasvc 12y ago
      That still relies on the shell expanding a glob of millions of files. Another method is to use 'find' and 'xargs' to avoid specifying the files as arguments explicitly.

jacquesm 12y ago

Directory scans suck. So if you break up the space into sets of prefixes you limit the number of files in each dir and traversal gets much faster. Ditto adding/removing items. Some filesystems are worse at this than others (xfs... let's not go there).

adrianmsmith 12y ago
Would the HN software need to scan the directory e.g. to read in all users, at any point? I don't know the source code of HN but I can't see why that would be necessary. (And if it did need to, presumably it's now need to recursively scan all sub-directories, which would also take a while?)
- jacquesm 12y ago
  No, you need to scan the directory every time you read a file. So most filesystems do a lot of work to optimize this but it is still a significant factor.
  - adrianmsmith 12y ago
    Not sure I agree with that. I ran the software for community with 6M users, and on 2003 hardware we had millions of files in one directory. That was with advfs on tru64 so things might be different with other file systems. But e.g. zfs can do this no problem as well. I just sort of assumed other FSs must have caught up in the intervening 10+ years but I haven't looked into their source code so an prepared to admit I might be wrong about them. The same way a database fetch doesn't load the whole table, filesystems can and do use trees and hashes to organize directories so that file lookup, creation and deletion by name can be fast and can be concurrent. I posted this in another comment, but this was my understanding of the situation in 2010. http://www.databasesandlife.com/flat-directories/ http://www.databasesandlife.com/flat-directories/ There must be a reason why they did this change, either I am wrong about performance (perhaps my results really were particular to those filesystems) or perhaps I am right and they made the change for another reason. I'd like to learn the answer.

zimpenfish 12y ago

If you look up "directory hashing" (possibly also "directory sharding"), that'll explain things. Particularly relevant to things like email servers and shared web hosts.

deleted 12y ago

[deleted]

js2 12y ago

Large directories can be very slow to scan (readdir). By fanning out the items into more directories of fewer items, performance is improved. Git does something similar with its objects directory. This is an old Unix trick. Note that Linux ext3/ext4 have a dir_index option which improves readdir performance. Edit: it's not readdir performance so much as just name lookups which are improved by this technique (and dir_index): http://ext2.sourceforge.net/2005-ols/paper-html/node3.html http://ext2.sourceforge.net/2005-ols/paper-html/node3.html

adrianmsmith 12y ago
My experience was the opposite. In code I wrote - I never needed to scan the directory to find "all users" (after all, if you have millions of users, this is going to take a while whatever directory structure you use) - Modern filesystems either use a tree or hash structure to identify files, meaning that lookup by name, and creating/deleting files, is quick, even if you have millions of files. - Given no performance benefits are to be had by directory nesting, I always went with the option of simplicity, i.e. having everything in one directory. (I blogged about this here: http://www.databasesandlife.com/flat-directories/ http://www.databasesandlife.com/flat-directories/) But no doubt the HN developers had a reason for doing this change, I'd love to know what it is (e.g. if they need to do something I never needed to do, or if they need to do the same things but I was wrong.)
- caoimhin 12y ago
  The fs caches the directories. So in a large, flat dir structure it has large, flat dirs it needs to cache. Now I'm not sure how big the win will be for accounts since one assumes active vs. inactive accounts will be randomly spread around alphabetically. So loads of these smaller dirs will be loaded. But for articles it should be a win since it's mainly the most recent ones that will be accessed so you'll have a hotspot and the vast majority of the directories won't be accessed.
- unreal37 12y ago
  The site loads 5 times faster. So clearly there are performance benefits to directory nesting.

deleted 12y ago

[deleted]

eCa 12y ago

An aside: When storing large quantities of things like this my personal preference is to split the id from the end. I was once i charge of a large number of images of book jackets named by the books' isbn. At least in that population (which of course is an extreme example considering how an isbn is created) the distribution is much more even (that is, the directory sizes are relatively equal) when using the end than the beginning, but I would not be surprised if that is a normal outcome. Maybe it's an application of Benford's law [1]. [1] http://en.wikipedia.org/wiki/Benford%27s_law http://en.wikipedia.org/wiki/Benford%27s_law