{"thread":{"id":"11423","subject":"On the many files problem","startedAt":"2007-12-29T18:22:29Z","lastAt":"2007-12-31T23:31:25Z","messageCount":6,"participants":["Yannick Gingras","Linus Torvalds","Junio C Hamano","Martin Langhoff"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"64182","messageId":"87y7bdweca.fsf@enceladus.ygingras.net","threadId":"11423","inReplyTo":null,"subject":"On the many files problem","fromName":"Yannick Gingras","fromEmail":"ygingras@ygingras.net","sentAt":"2007-12-29T18:22:29Z","receivedAt":"2007-12-29T18:22:29Z","isPatch":false,"sender":{"key":"ygingras@ygingras.net","avatar":"https://gravatar.com/avatar/9e1b648dd1e0ce5e42fb8be1ffbee13a0d5c9743b872ec312ae2dac4eee0c5bd?d=mp&s=160"},"body":"\nGreetings Git hackers,\n\nNo doubt, you guys must have discussed this problem before but I will\npretend that I can't find the relevant threads in the archive because\nMarc's search is kind of crude.\n\nI'm coding an application that will potentially store quite a bunch of\nfiles in the same directory so I wondered how I should do it.  I tried\na few different files systems and I tried path hashing, that is,\nstoring the file that hashes to d3b07384d113 in d/d3/d3b07384d113.  As\nfar as I can tell, that's what Git does.  It turned out to be slower\nthan anything except ext3 without dir_index.  You can see my results\nand the benchmarking code that I used here:\n\n  http://ygingras.net/b/2007/12/too-many-files:-reiser-fs-vs-hashed-paths\n\nQuick like that, I would be tempted to say that hashing paths always\nmakes things slower but the Git development team includes people with\nreally intimate knowledge of several file system implementations so\nI'm tempted to say that you guys know something that I don't.\n\nCan you describe how you hash the paths and what trick is done to\nensure fast creating and access to the subdirectories?  Is path\nhashing generally faster or are you trying to avoid problems for\npeople using git on baroque file systems?\n\nBest regards, \n\n-- \nYannick Gingras\n"},{"id":"64184","messageId":"alpine.LFD.0.9999.0712291055470.2778@woody.linux-foundation.org","threadId":"11423","inReplyTo":"87y7bdweca.fsf@enceladus.ygingras.net","subject":"Re: On the many files problem","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-12-29T19:12:38Z","receivedAt":"2007-12-29T19:12:38Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Sat, 29 Dec 2007, Yannick Gingras wrote:\n> \n> I'm coding an application that will potentially store quite a bunch of\n> files in the same directory so I wondered how I should do it.  I tried\n> a few different files systems and I tried path hashing, that is,\n> storing the file that hashes to d3b07384d113 in d/d3/d3b07384d113.  As\n> far as I can tell, that's what Git does.  It turned out to be slower\n> than anything except ext3 without dir_index.\n\nNote that git doesn't hash paths because it *wants* to, but because it \n*needs* to. \n\nBasically, what git very fundamnentally wants as the basic operation, is \nto look up a SHA1 hashed object. \n\n> Quick like that, I would be tempted to say that hashing paths always\n> makes things slower but the Git development team includes people with\n> really intimate knowledge of several file system implementations so\n> I'm tempted to say that you guys know something that I don't.\n\nNo, no. The fastest way to store a bunch of files is to basically:\n\n - make the filenames as small as possible\n\n   This improves density, and thus performance. You'll get more files to \n   fit in a smaller directory, and filename compares etc will be faster \n   too.\n\n   If you don't need hashes, but can do with smaller names (for example, \n   your names are really just sequential, and you can use some base-64 \n   encoding to make them smaller than numbers), you'll always be better \n   off.\n\n - store them in a good final order. This is debatable, but depending on \n   your load and the filesystem, it can be better to make sure that you \n   create all files in order, because performance can plummet if you start \n   removing files later.\n\n   I suspect your benchmark *only* tested this case, but if you want to \n   check odder cases, try creating a huge directory, and then deleting \n   most files, and then adding a few new ones. Some filesystems will take \n   a huge hit because they'll still scan the whole directory, even though \n   it's mostly empty!\n\n   (Also, a \"readdir() + stat()\" loop will often get *much* worse access \n   patterns if you've mixed deletions and creations)\n\n - it's generally *much* more efficient to have one large file that you \n   read and seek in than having many small ones, so if you can change your \n   load so that you don't have tons of files at all, you'll probably be \n   better off.\n\nAnyway, git is not a good thing to look at for \"lots of files\" performance \nif you have any options. The reasons git does what it does is:\n\n - as mentioned, the SHA1 hash is the fundamental unit of lookup, so the \n   name *must* be the hash, since that's all we ever have!\n\n - If you don't have indexing, you really *really* don't want to have a \n   flat file structure (as your benchmark found out). And git didn't want \n   to assume you have indexing, since a lot of filesystems don't (I \n   suspect a lot of ext3 installations _still_ don't enable it, for \n   example, even if the capability is there!)\n\nSo the first point explains the use of hashes for filenames, and the \nsecond point explains the use of a single level of indexing. But neither \nof them are about absolute performance per se, both are about basic \nrequirements.\n\nFor good performance, look at the git pack-files. Those are designed to be \ndata-dense, and only a few files that can be opened and mapped just once. \nThere, performance was one of the guiding goals (along with the ability to \nalso use them for streaming, and still being *reasonably* simple, of \ncourse).\n\n\t\t\tLinus\n"},{"id":"64186","messageId":"7vabntb8t8.fsf@gitster.siamese.dyndns.org","threadId":"11423","inReplyTo":"87y7bdweca.fsf@enceladus.ygingras.net","subject":"Re: On the many files problem","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-12-29T19:27:31Z","receivedAt":"2007-12-29T19:27:31Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Yannick Gingras <ygingras@ygingras.net> writes:\n\n> Greetings Git hackers,\n>\n> No doubt, you guys must have discussed this problem before but I will\n> pretend that I can't find the relevant threads in the archive because\n> Marc's search is kind of crude.\n>\n> I'm coding an application that will potentially store quite a bunch of\n> files in the same directory so I wondered how I should do it.  I tried\n> a few different files systems and I tried path hashing, that is,\n> storing the file that hashes to d3b07384d113 in d/d3/d3b07384d113.  As\n> far as I can tell, that's what Git does.  It turned out to be slower\n> than anything except ext3 without dir_index.\n\nWe hash like d3/b07384d113, but your understanding of we do is\nmore or less right.\n\nIf we never introduced packed object storage, this issue may\nhave mattered and we might have looked into it further to\nimprove the loose object access performance.  But in reality, no\nsane git user would keep millions of loose objects unpacked.\nAnd changing the layout would mean a backward incompatible\nchange for dumb transport clients.  There is practically no\nupside and are downsides to change it now.\n\nTraditionally, avoiding large directories when dealing with a\nlarge number of files by path hashing was a tried and proven\nwisdom in many applications (e.g. web proxies, news servers).\nNewer filesystems do have tricks to let you quickly access a\nlarge number of files in a single directory, and that lessens\nthe need for the applications to play path hashing games.\n\nThat is a good thing, but if that trick makes the traditional\nway of dealing with a large number of files _too costly_, it may\nbe striking the balance at a wrong point.  That is favoring\nnewly written applications that assume that large directories\nare Ok (or ones written by people who do not know the historical\nbehaviour of filesystems), by punishing existing practices too\nheavily.\n\nThe person who is guilty of introducing the hashed loose object\nstore is intimately familiar with Linux.  I do not speak for\nhim, but if I have to guess, the reason he originally chose the\npath hashing was because he just followed the tradition, and he\ndid not want to make the system too dependent on Linux or a\nparticular feature of underlying filesystems.\n"},{"id":"64256","messageId":"873atjtbmu.fsf@enceladus.ygingras.net","threadId":"11423","inReplyTo":"alpine.LFD.0.9999.0712291055470.2778@woody.linux-foundation.org","subject":"Re: On the many files problem","fromName":"Yannick Gingras","fromEmail":"ygingras@ygingras.net","sentAt":"2007-12-31T10:13:45Z","receivedAt":"2007-12-31T10:13:45Z","isPatch":false,"sender":{"key":"ygingras@ygingras.net","avatar":"https://gravatar.com/avatar/9e1b648dd1e0ce5e42fb8be1ffbee13a0d5c9743b872ec312ae2dac4eee0c5bd?d=mp&s=160"},"body":"\nThanks to you and to Junio for your replies, \n\nLinus Torvalds <torvalds@linux-foundation.org> writes:\n> No, no. The fastest way to store a bunch of files is to basically:\n>\n>  - make the filenames as small as possible\n>\n>    This improves density, and thus performance. You'll get more files to \n>    fit in a smaller directory, and filename compares etc will be faster \n>    too.\n>\n>    If you don't need hashes, but can do with smaller names (for example, \n>    your names are really just sequential, and you can use some base-64 \n>    encoding to make them smaller than numbers), you'll always be better \n>    off.\n\nThis is really interesting and I would not have suspected it.  But it\nbegs the question: why does Git use the base-16 hash instead of the\nbase-64 hash?  \n\nAfter your replies I took a serious look at Git's storage and there is\nindeed not that many loose objects in a typical repo: most is kept\ninto packs.  So I guess Git doesn't need that much density and keeping\nthe filename in the format that is used in the UI probably helps power\nusers.\n\n>  - store them in a good final order. This is debatable, but depending on \n>    your load and the filesystem, it can be better to make sure that you \n>    create all files in order, because performance can plummet if you start \n>    removing files later.\n>\n>    I suspect your benchmark *only* tested this case, \n\nThat is true.\n\n>    but if you want to check odder cases, try creating a huge\n>    directory, and then deleting most files, and then adding a few\n>    new ones. Some filesystems will take a huge hit because they'll\n>    still scan the whole directory, even though it's mostly empty!\n>\n>    (Also, a \"readdir() + stat()\" loop will often get *much* worse access \n>    patterns if you've mixed deletions and creations)\n\nThis is something that will be interesting to benchmark later on.  So,\nan application with a lot of turnaround, say a mail server, should\ndelete and re-create the directories from time to time?  I assume this\nis specific to some file system types.\n\n>  - it's generally *much* more efficient to have one large file that you \n>    read and seek in than having many small ones, so if you can change your \n>    load so that you don't have tons of files at all, you'll probably be \n>    better off. \n\nThat makes a lot of sense.  \n\nThanks again for those clarifications.\n\n-- \nYannick Gingras\n"},{"id":"64279","messageId":"alpine.LFD.1.00.0712311237521.32517@woody.linux-foundation.org","threadId":"11423","inReplyTo":"873atjtbmu.fsf@enceladus.ygingras.net","subject":"Re: On the many files problem","fromName":"Linus Torvalds","fromEmail":"torvalds@linux-foundation.org","sentAt":"2007-12-31T20:45:04Z","receivedAt":"2007-12-31T20:45:04Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 31 Dec 2007, Yannick Gingras wrote:\n> \n> This is really interesting and I would not have suspected it.  But it\n> begs the question: why does Git use the base-16 hash instead of the\n> base-64 hash?  \n\nBecause I was stupid, and I'ma lot more used to hex numbers than to \nbase-64.\n\nAlso, the way the original encoding worked, the SHA1 of the object was \nactually the SHA1 of the *compressed* object, so you could verify the \nintegrity of the object writing by just doing a\n\n\tsha1sum .git/objects/4f/a7491b073032b57c7fcf28c9222a5fa7b3a6b9\n\nand it would return 4fa7491b073032b57c7fcf28c9222a5fa7b3a6b9 if everything \nwas good. That was a nice bonus in the first few days of git development, \nwhen it all was a set of very low-level object routines hung together with \nprayers and duct-tape.\n\nSo consider it historical. It wasn't worth fixing, since it became obvious \nthat the real fix would never be to try to make the individual files or \nfilenames smaller.\n\n> >    (Also, a \"readdir() + stat()\" loop will often get *much* worse access \n> >    patterns if you've mixed deletions and creations)\n> \n> This is something that will be interesting to benchmark later on.  So,\n> an application with a lot of turnaround, say a mail server, should\n> delete and re-create the directories from time to time?  I assume this\n> is specific to some file system types.\n\nThis is an issue only for certain filesystems, and it's also an issue only \nfor certain access patterns.\n\nA mail server, for example, will seldom *scan* the directory. It will just \nopen individual files by name. So it won't be hit by the \"readdir+stat\" \nissue, unless you actually do a \"ls -l\".\n\n(There are exceptions. Some mailbox formats use a file per email in a \ndirectory. And yes, they tend to suck from a performance angle).\n\nAnd you can avoid it. For example, on most unixish filesystems, you can \nget better IO access patterns by doing the readdir() into an array, then \nsorting it by inode number, and then doing the stat() in that order: that \n*often* (but not always - there's no guarantee what the inode number \nactually means) gives you better disk access patterns.\n\n\t\t\tLinus\n"},{"id":"64284","messageId":"46a038f90712311531x17b6d94aua1bac2d3d186f186@mail.gmail.com","threadId":"11423","inReplyTo":"873atjtbmu.fsf@enceladus.ygingras.net","subject":"Re: On the many files problem","fromName":"Martin Langhoff","fromEmail":"martin.langhoff@gmail.com","sentAt":"2007-12-31T23:31:25Z","receivedAt":"2007-12-31T23:31:25Z","isPatch":false,"sender":{"key":"martin.langhoff@gmail.com","avatar":"https://gravatar.com/avatar/1e3f311b6c4c15836501901ca58f8c0b0667246488084ba524d8bc9867e22fd9?d=mp&s=160"},"body":"On Dec 31, 2007 11:13 PM, Yannick Gingras <ygingras@ygingras.net> wrote:\n> >    but if you want to check odder cases, try creating a huge\n> >    directory, and then deleting most files, and then adding a few\n> >    new ones. Some filesystems will take a huge hit because they'll\n> >    still scan the whole directory, even though it's mostly empty!\n> >\n> >    (Also, a \"readdir() + stat()\" loop will often get *much* worse access\n> >    patterns if you've mixed deletions and creations)\n>\n> This is something that will be interesting to benchmark later on.  So,\n> an application with a lot of turnaround, say a mail server, should\n> delete and re-create the directories from time to time?  I assume this\n> is specific to some file system types.\n\nThis is indeed the case. Directories with a lot of movement get\nfragmented on most FSs -- ext3 is a very bad case for this -- and\nthere are no \"directory defrag\" tools other than regenarating them.\nThe \"Maildir\" storage used for many IMAP servers these days shows the\nproblem.\n\nThis (longish) threads has some interesting tidbits on getdents() and\ndirectory fragmentation.\nhttp://kerneltrap.org/mailarchive/git/2007/1/7/235215\n\ncheers,\n\n\nm\n"}]}