{"thread":{"id":"15415","subject":"Storing Large Flat Namespaces","startedAt":"2008-09-08T01:58:30Z","lastAt":"2008-09-08T13:58:43Z","messageCount":3,"participants":["Jaap Suter","Nicolas Pitre"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"90036","messageId":"21d738060809071858p703149ccmbec0276ad4ad8f88@mail.gmail.com","threadId":"15415","inReplyTo":null,"subject":"Storing Large Flat Namespaces","fromName":"Jaap Suter","fromEmail":"git@jaapsuter.com","sentAt":"2008-09-08T01:58:30Z","receivedAt":"2008-09-08T01:58:30Z","isPatch":false,"sender":{"key":"git@jaapsuter.com","avatar":null},"body":"Hello,\n\nI'm investigating the possibility of using Git to store a large flat\nnamespace. As an example, imagine a single directory containing\nthousands or millions of files, each named using a 16-byte guid,\nevenly distributed.\n\nI'm aware that the Git object model makes various trade-offs,\ntypically in favor of managing source-tree layouts - which it does\nextremely well. However, perhaps it is possible to carry some of Git's\nfeatures as a content revision tracker over to other storage\napplications?\n\nCurrently, tree objects for large flat directories are quite large.\nDoing a git-init, git-add, git-push on a flat directory with 10,000\nfiles creates a tree object that is 24 kilobytes compressed. Any\nchange to a single file would create a whole new tree object, 24\nkilobytes every time.\n\nThe obvious thought is to \"virtualize\" or \"tree-ify\" the namespace,\nsimilar to how Git stores its own loose objects. (Is there a proper\nname for this technique?)\n\nThis archive thread touches on that idea:\n\n   http://kerneltrap.org/mailarchive/git/2006/2/8/200585\n\nIn particular (quoting Linus):\n\n   \"Final note: this means, for example, that git is relatively bad at\ntracking a \"hashed\" nested file directory (like the one git itself\nuses), because new files will end up randomly appearing in every\ndirectory, and no directory is ever \"stable\".\n\nI wonder how bad it is, so I did some calculations. What if Git could\n\"virtualize\" the namespace when going from the working directory to\nthe object store, without the user ever realizing it. In other words,\nGit would insert \"fake\" tree nodes to split apart large directories.\nThis leaves the question of how useful a working directory with a\nmillion loose files is, but pretend for a moment that I have a Git\nfrontend that doesn't do full check-outs to a file system but allows a\nuser to grab single objects from the object store straight into\nmemory.\n\nOk, this is all back-of-the-napkin:\n\n   H = sizeof(hash) = 20 bytes.\n   G = sizeof(name) =  16 bytes.\n\n   N = number of assets = let's say one million (hypothetical)\n\nThat means the theoretical minimum size of a tree object (without\nvirtualization) is:\n\n  (H + G) * N = 36 megabytes\n\nIf we virtualize, using these parameters:\n\n   B = number of bits we chop from the head of the filename, to create\nthe tree prefix (i.e., internal nodes)\n   D = depth of virtualization (number of internal nodes we need to\ntraverse before we hit a bucket)\n\n   (...in git's loose object store, B equals 8 and D equals 1.)\n\nWe get the following formulas:\n\n                      2^(B*D)  = number of buckets (leaf tree objects)\n                N / (2^(B*D)) = number of files per bucket\n   (H+G) *  N / (2^(B*D)) = size of a bucket\n\n     2^B * H = size of an internal node\n\nThe storage overhead of a single file commit then becomes the size of\na new bucket plus the size of the internal nodes back to the root.\nI.e.,\n\n    (D * (2^B) * H)     +     (H+G) * N / (2^(B*D))\n\nThe other interesting parameter is the total number of objects\ninvolved in just virtualization overhead. For simplicity's sake, the\nnumber of leaf objects is a good metric.\n\nFor different values of B and D, this leads to the following overhead\non a million-file directory.\n\n    B = 0, D = 0 (how git treats large flat directories today)\n        number of buckets: 1\n        single change commit overhead: 36 megabyte\n\n    B = 8, D = 1:\n        number of buckets: 256\n        single change commit overhead: 145736 bytes\n\n    B = 8, D = 1:\n        number of buckets: 65536\n        single change commit overhead: 10780 bytes\n\n    B = 3, D = 4:\n        number of buckets: 4096\n        single change commit overhead: 9424 bytes\n\nUltimately, the trade-off is between how may objects are involved in\nthe tree-ification, how many lookups need to be done to get an object,\nand the storage overhead of commits.\n\nThe more I think about it, the less certain I am this kind of\ndata-structure is suitable for my application. I guess Linus's quote\nat the top summed it up.\n\nI'm wondering if anybody else has put any thought into this kind of\nthing, and has suggestions for alternate data structures that could\nenable Git to store large flat namespaces.\n\nThoughts are welcome. Or am I out to lunch?\n\nThanks,\n\nJaap Suter - http://jaapsuter.com\n"},{"id":"90044","messageId":"loom.20080908T042124-621@post.gmane.org","threadId":"15415","inReplyTo":"21d738060809071858p703149ccmbec0276ad4ad8f88@mail.gmail.com","subject":"Re: Storing Large Flat Namespaces","fromName":"Jaap Suter","fromEmail":"git@jaapsuter.com","sentAt":"2008-09-08T04:26:08Z","receivedAt":"2008-09-08T04:26:08Z","isPatch":false,"sender":{"key":"git@jaapsuter.com","avatar":null},"body":"\n> I'm investigating the possibility of using Git to store a large flat\n> namespace. As an example, imagine a single directory containing\n> thousands or millions of files, each named using a 16-byte guid,\n> evenly distributed.\n\nI realize that an obvious suggestion may be to figure out if there is a way to \nleverage the internal structure of the files to create a more Git-friendly tree \nlayout.\n\nUnfortunately the internal structure is largely opaque to me, and highly \ndynamic.\n\nThanks,\n\nJaap\n"},{"id":"90080","messageId":"alpine.LFD.1.10.0809080923250.23787@xanadu.home","threadId":"15415","inReplyTo":"21d738060809071858p703149ccmbec0276ad4ad8f88@mail.gmail.com","subject":"Re: Storing Large Flat Namespaces","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2008-09-08T13:58:43Z","receivedAt":"2008-09-08T13:58:43Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sun, 7 Sep 2008, Jaap Suter wrote:\n\n> Hello,\n> \n> I'm investigating the possibility of using Git to store a large flat\n> namespace. As an example, imagine a single directory containing\n> thousands or millions of files, each named using a 16-byte guid,\n> evenly distributed.\n> \n> I'm aware that the Git object model makes various trade-offs,\n> typically in favor of managing source-tree layouts - which it does\n> extremely well. However, perhaps it is possible to carry some of Git's\n> features as a content revision tracker over to other storage\n> applications?\n> \n> Currently, tree objects for large flat directories are quite large.\n> Doing a git-init, git-add, git-push on a flat directory with 10,000\n> files creates a tree object that is 24 kilobytes compressed. Any\n> change to a single file would create a whole new tree object, 24\n> kilobytes every time.\n\nSure.  But as soon as you repack that repository, there will be only one \n24-kilobyte tree object for the latest revision and older revisions will \nhave their tree object stored as a delta against the latest one, which \nshould be merely the size of the changed entry only.\n\nAs to the idea of splitting a large flat directory namespace into \nsub-trees... that would only help in the commit case which isn't that \ninteresting since commits are done much less frequent than, say, \ndirectory walking.  In the later case, you might end up inflating less \nobject data for files at the beginning of the directory but more for \nfiles towards the end, which on average won't be a gain.  And in all \ncases you're looking up more objects.  And, to benefit from any \nadvantage left if any, you'd need to do significant surgery in the tree \nwalking code, otherwise simply reconstructing the current object format \nfrom subtree objects won't bring any advantage over the current packed \nformat using deltas.\n\nThe pack V4 should in theory be much better with large directories since \nthe design of its tree object representation would allow walking partial \ntree by recursively following deltas making a complete tree walk almost \nlinear in terms of processing and data touched.  But that too requires a \nmajor surgery of the tree walking code (the main reason holding me back \nfrom rushing into any pack v4 work at the moment).  But pack v4 won't \nchange anything in the commit case -- you would still have to repack in \norder to benefit from it.\n\n\nNicolas\n"}]}