{"thread":{"id":"36","subject":"space compression (again)","startedAt":"2005-04-15T17:19:30Z","lastAt":"2005-04-19T12:39:35Z","messageCount":10,"participants":["C. Scott Ananian","Linus Torvalds","Derek Fawcus","Martin Uecker"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"226","messageId":"Pine.LNX.4.61.0504151232160.27637@cag.csail.mit.edu","threadId":"36","inReplyTo":null,"subject":"space compression (again)","fromName":"C. Scott Ananian","fromEmail":"cscott@cscott.net","sentAt":"2005-04-15T17:19:30Z","receivedAt":"2005-04-15T17:19:30Z","isPatch":false,"sender":{"key":"cscott@cscott.net","avatar":"https://gravatar.com/avatar/3551c2aefb299a0c45807f7677f5b26d8a5be4a4af359b4bf4fabbdd1f2b990e?d=mp&s=160"},"body":"I've been reading the archives (a bad idea, I know).  Here's a concrete \nsuggestion for GIT space-compression which is (I believe) consistent with \nthe philosophy of GIT.\n\nWhy are blobs per-file?  [After all, Linus insists that files are an \nillusion.]  Why not just have 'chunks', and assemble *these* \ninto blobs (read, 'files')?  A good chunk size would fit evenly into some \nnumber of disk blocks (no wasted space!).\n\nWe already have the rsync algorithm which can scan through a file and \nefficiently tell which existing chunks match (portions of) it, using a \nrolling checksum. (Here's a refresher:\n    http://samba.anu.edu.au/rsync/tech_report/node2.html\n).  Why not treat the 'chunk' as the fundamental unit, and compose files \nfrom chunks?\n\nThis should get better space utilization: a small change to file X \nwill only require storage to save the changed chunk, plus meta data to \ndescribe the chunks composing the new file.  I propose keeping this only \none-level deep: we can only specify chunks, not pieces of files.\n\nUnlike xdelta schemes, there is no 'file' dependency.  Chunks for a blob \ncan be and are shared among *all the other files and versions in the \nrepository*.  Moving pieces from file 'a' to file 'b' \"just works\".\n\nBest of all, I believe this can be done in a completely layered fashion. \nFrom git's perspective, it's still 'open this blob' or 'write this blob'. \nIt just turns out that the filesystem representation of a blob is slightly \nmore fragmented.  Even better, you ought to be able to convert your \non-disk store from one representation to the other: the named blob doesn't \nchange, just 'how to fetch the blob' changes.  So, for example, Linus' \ntree can be unchunked for speed, but the release tree (say) can pull \npruned history from Linus into a chunked on-disk representation that can \nbe efficiently wget'ted (only new chunks need be transferred).\n\nMy first concern is possible fragmentation: would we end up with a large \nnumber of very small chunks, and end up representing files as a list of \nlines (effectively)?  Maybe someone can think of an effective coalescing \nstrategy, or maybe it is sufficient just to avoid creating chunks smaller \nthan a certain size (ie, possibly writing redundant data to a new chunk, \njust to improve the possibility of reuse).\n\nI'm also not sure what the best 'chunk' size is.  Smaller chunks save more \nspace but cost more to access (# of disk seeks per file/blob).  Picking a \nchunk half the average file size should reduce space by ~50% while only \nrequiring ~2 additional seeks per file-read. OTOH, rsync experience \nsuggests 500-1000 byte chunk sizes.  Probably empirical testing is best.\n\nLastly, we want to avoid hitting the dcache to check the existence of \nchunks while encoding.  In a large repository, there will be a very large \nnumber of chunks.  We don't *have* to index all of them, but our \ncompression gets better the more chunks we know about.  The rsync \nalgorithm creates hash tables of chunks at different levels of granularity \nto avoid doing a full check at every byte of the input file.  How large \nshould this cached-on-disk chunk hash table be to avoid saturating it as \nthe repository grows (maybe the standard grow-as-you-go hash table is \nfine; you only need one bit per entry anyway)?\n\nThoughts?  Is the constant-factor overhead of indirection-per-blob going \nto kill git's overwhelming speed?\n  --scott\n\nJUBILIST explosion MKULTRA HTAUTOMAT Indonesia Shoal Bay RUCKUS ammunition \nGPFLOOR Hager SDI MKDELTA KUBARK Dictionary Soviet  BLUEBIRD Delta Force\n                          ( http://cscott.net/ )\n"},{"id":"229","messageId":"Pine.LNX.4.58.0504151117360.7211@ppc970.osdl.org","threadId":"36","inReplyTo":"Pine.LNX.4.61.0504151232160.27637@cag.csail.mit.edu","subject":"Re: space compression (again)","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-04-15T18:34:19Z","receivedAt":"2005-04-15T18:34:19Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 15 Apr 2005, C. Scott Ananian wrote:\n> \n> Why are blobs per-file?  [After all, Linus insists that files are an \n> illusion.]  Why not just have 'chunks', and assemble *these* \n> into blobs (read, 'files')?  A good chunk size would fit evenly into some \n> number of disk blocks (no wasted space!).\n\nI actually considered that. I ended up not doing it, because it's not \nobvious how to \"block\" things up (and even more so because while I like \nthe notion, it flies in the face of the other issues I had: performance \nand simplicity).\n\nThe problem with chunking is:\n - it complicates a lot of the routines. Things like \"is this file \n   unchanged\" suddenly become \"is this file still the same set of chunks\",\n   which is just a _lot_ more code and a lot more likely to have bugs.\n - you have to find a blocking factor. I thought of just going it fixed \n   chunks, and that just doesn't help at all. \n - we already have wasted space due to the low-level filesystem (as \n   opposed to \"git\") usually being block-based, which means that space \n   utilization for small objects tends to suck. So you really want to \n   prefer objects that are several kB (compressed), and a small block just\n   wastes tons of space.\n - there _is_ a natural blocking factor already. That's what a file \n   boundary really is within the project, and finding any other is really \n   quite hard.\n\nSo I'm personally 100% sure that it's not worth it. But I'm not opposed to\nthe _concept_: it makes total sense in the \"filesystem\" view, and is 100%\nequivalent to having an inode with pointers to blocks. I just don't think \nthe concept plays out well in reality.\n\n\t\tLinus\n"},{"id":"232","messageId":"Pine.LNX.4.61.0504151437100.27637@cag.csail.mit.edu","threadId":"36","inReplyTo":"Pine.LNX.4.58.0504151117360.7211@ppc970.osdl.org","subject":"Re: space compression (again)","fromName":"C. Scott Ananian","fromEmail":"cscott@cscott.net","sentAt":"2005-04-15T18:45:55Z","receivedAt":"2005-04-15T18:45:55Z","isPatch":false,"sender":{"key":"cscott@cscott.net","avatar":"https://gravatar.com/avatar/3551c2aefb299a0c45807f7677f5b26d8a5be4a4af359b4bf4fabbdd1f2b990e?d=mp&s=160"},"body":"On Fri, 15 Apr 2005, Linus Torvalds wrote:\n\n> The problem with chunking is:\n> - it complicates a lot of the routines. Things like \"is this file\n>   unchanged\" suddenly become \"is this file still the same set of chunks\",\n>   which is just a _lot_ more code and a lot more likely to have bugs.\n\nThe blob still has the same hash; therefore the file is still the same.\nNothing looks inside blobs; they just want either the hash or the full \ncontents (if I understand the algorithms correctly).\nI agree it's more code, but I think it can be nicely layered.\n\n> - you have to find a blocking factor. I thought of just going it fixed\n>   chunks, and that just doesn't help at all.\n\nrsync uses a fixed chunk size, but this chunk can start at any offset (ie, \nnot constrained to fixed boundaries).  This means that adding a single \nline to the file works like you'd expect, even though all the chunk \nboundaries change.  [I think this is what you're talking about.]\n\n> - we already have wasted space due to the low-level filesystem (as\n>   opposed to \"git\") usually being block-based, which means that space\n>   utilization for small objects tends to suck. So you really want to\n>   prefer objects that are several kB (compressed), and a small block just\n>   wastes tons of space.\n\nNot on (say) reiserfs, and not over the network.  I'm proposing (at the \nmoment) easy conversion from chunked to unchunked disk representation,\nso that you can leave things unchunked if (for example) you know you're \nrunning ext2 with a large block size.\n\n> - there _is_ a natural blocking factor already. That's what a file\n>   boundary really is within the project, and finding any other is really\n>   quite hard.\n\nWell, yes, it may be nontrivial.  But 'quite hard' depends on your \nperspective, I guess.  Given a cache of existing chunks, it's just a \nfew table lookups. =)\n\n> So I'm personally 100% sure that it's not worth it. But I'm not opposed to\n> the _concept_: it makes total sense in the \"filesystem\" view, and is 100%\n> equivalent to having an inode with pointers to blocks. I just don't think\n> the concept plays out well in reality.\n\nSo I guess I'll have to implement this and find out, won't I? =)\n  --scott\n\nAMLASH overthrow SDI Suharto HBDRILL SMOTH SUMAC SYNCARP kibo Blair \nDiplomat Kojarena CIA cracking counter-intelligence CABOUNCE anthrax\n                          ( http://cscott.net/ )\n"},{"id":"233","messageId":"20050415195038.E6735@mrwint.cisco.com","threadId":"36","inReplyTo":"Pine.LNX.4.61.0504151232160.27637@cag.csail.mit.edu","subject":"Re: space compression (again)","fromName":"Derek Fawcus","fromEmail":"dfawcus@cisco.com","sentAt":"2005-04-15T18:50:38Z","receivedAt":"2005-04-15T18:50:38Z","isPatch":false,"sender":{"key":"dfawcus@cisco.com","avatar":null},"body":"On Fri, Apr 15, 2005 at 01:19:30PM -0400, C. Scott Ananian wrote:\n> Why are blobs per-file?  [After all, Linus insists that files are an \n> illusion.]  Why not just have 'chunks', and assemble *these* \n> into blobs (read, 'files')?  A good chunk size would fit evenly into some \n> number of disk blocks (no wasted space!).\n\n[ I've only been earwigging,  not paying a lot of attention,  however ...]\n\nFunny I was just think of this having read Linus' discourse on\n\"files don't matter\", the obvious chunking factor would be say\na function.\n\nThe problem being tending towards having very small files - I know\nI tend to prefer small functions.  Hmm - a underlying filesystem that\nefficiently stores small files - why does that ring a bell :-)\n\nHowever the simple answer is to have a preparser for a file / tree\ncheckin which split say a .c file into it's associated chunks,  anf\nrepresented it in git as a signed/hashed object.  i.e. a automatically\ncreated extra level of indirection (as I seem to recall was added\nsomewhere else?).\n\n  So say fred.c:\n\n  /*\n   * File boiler\n   */\n  #include <guff>\n  #include <more guff>\n\n  /*\n   * Fn a boiler\n   */\n  int fn_a(args) {\n  }\n\n  /*\n   * Fn b boiler\n   */\n  long fn_b(args) {\n  }\n\nWould be split into 4 parts within git,  the 'file object' which simply\npoints to the content objects,  and 3 contents objects,  being the stuff\nbefore 'Fn a boiler',  fn_a and it's boiler,  fn_b and it's boiler.\n\nThe interesting bit is needing a preprocessor which can roughly parse\nthe code - i.e. detect where to place the boiler blocks.\n\nYou would then do most of your tree operations upon the file objects,\nbut get the space savings from the content objects being shared.\n\nI suspect that simply to prevent pathological conditions you'd have to\narrange that the contents objects have a minimal size,  irrespective\nof the number of desired chunks (functions) they would naturally\ncontain.  i.e. for compresion efficiency,  you may choose something like\n2K as the minimal pre compression content object size.\n\nDF\n"},{"id":"235","messageId":"20050415200054.F6735@mrwint.cisco.com","threadId":"36","inReplyTo":"Pine.LNX.4.61.0504151437100.27637@cag.csail.mit.edu","subject":"Re: space compression (again)","fromName":"Derek Fawcus","fromEmail":"dfawcus@cisco.com","sentAt":"2005-04-15T19:00:54Z","receivedAt":"2005-04-15T19:00:54Z","isPatch":false,"sender":{"key":"dfawcus@cisco.com","avatar":null},"body":"On Fri, Apr 15, 2005 at 02:45:55PM -0400, C. Scott Ananian wrote:\n> > - we already have wasted space due to the low-level filesystem (as\n> >   opposed to \"git\") usually being block-based, which means that space\n> >   utilization for small objects tends to suck. So you really want to\n> >   prefer objects that are several kB (compressed), and a small block just\n> >   wastes tons of space.\n> \n> Not on (say) reiserfs, and not over the network.  I'm proposing (at the \n> moment) easy conversion from chunked to unchunked disk representation,\n> so that you can leave things unchunked if (for example) you know you're \n> running ext2 with a large block size.\n\nOr if one does not care about space,  and simply want's speed,  add another\nlayer of indirection - a flattened container object which has hashses as\nnormal,  then as it's content simply has the 'chunk list object' and the\n'chunk objects' concatenated.\n\nIt's then a per user / database as to if the flattened objects,  or the\nheirarcal objects are storred locally.\n\nDF\n"},{"id":"236","messageId":"Pine.LNX.4.58.0504151210590.7211@ppc970.osdl.org","threadId":"36","inReplyTo":"Pine.LNX.4.61.0504151437100.27637@cag.csail.mit.edu","subject":"Re: space compression (again)","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-04-15T19:11:43Z","receivedAt":"2005-04-15T19:11:43Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 15 Apr 2005, C. Scott Ananian wrote:\n> \n> So I guess I'll have to implement this and find out, won't I? =)\n\nThe best way to shup somebody up is always to just do it, and say \"hey, I \ntold you so\". It's hard to argue with numbers.\n\n\t\t\tLinus\n"},{"id":"307","messageId":"20050416143905.GA10370@macavity","threadId":"36","inReplyTo":"Pine.LNX.4.58.0504151210590.7211@ppc970.osdl.org","subject":"Re: space compression (again)","fromName":"Martin Uecker","fromEmail":"muecker@gmx.de","sentAt":"2005-04-16T14:39:05Z","receivedAt":"2005-04-16T14:39:05Z","isPatch":false,"sender":{"key":"muecker@gmx.de","avatar":null},"body":"On Fri, Apr 15, 2005 at 12:11:43PM -0700, Linus Torvalds wrote:\n\n\n> On Fri, 15 Apr 2005, C. Scott Ananian wrote:\n> > \n> > So I guess I'll have to implement this and find out, won't I? =)\n> \n> The best way to shup somebody up is always to just do it, and say \"hey, I \n> told you so\". It's hard to argue with numbers.\n\nThe right thing (TM) is to switch from SHA1 of compressed\ncontent for the complete monolithic file to a merkle hash tree\nof the uncompressed content. This would make the hash\nindependent of the actual storage method (chunked or not). \n\n\nMartin\n\n-- \nOne night, when little Giana from Milano was fast asleep,\nshe had a strange dream.\n\n"},{"id":"313","messageId":"Pine.LNX.4.61.0504161101470.29343@cag.csail.mit.edu","threadId":"36","inReplyTo":"20050416143905.GA10370@macavity","subject":"Re: space compression (again)","fromName":"C. Scott Ananian","fromEmail":"cscott@cscott.net","sentAt":"2005-04-16T15:11:00Z","receivedAt":"2005-04-16T15:11:00Z","isPatch":false,"sender":{"key":"cscott@cscott.net","avatar":"https://gravatar.com/avatar/3551c2aefb299a0c45807f7677f5b26d8a5be4a4af359b4bf4fabbdd1f2b990e?d=mp&s=160"},"body":"On Sat, 16 Apr 2005, Martin Uecker wrote:\n\n> The right thing (TM) is to switch from SHA1 of compressed\n> content for the complete monolithic file to a merkle hash tree\n> of the uncompressed content. This would make the hash\n> independent of the actual storage method (chunked or not).\n\nIt would certainly be nice to change to a hash of the uncompressed \ncontent, rather than a hash of the compressed content, but it's not \nstrictly necessary, since files are fetched all at once: there's not 'read \nsubrange' operation on blobs.\n\nI assume 'merkle hash tree' is talking about:\n   http://www.open-content.net/specs/draft-jchapweske-thex-02.html\n..which is very interesting, but not quite what I was thinking.\nThe merkle hash approach seems to require fixed chunk boundaries.\nThe rsync approach does not use fixed chunk boundaries; this is necessary \nto ensure good storage reuse for the expected case (ie; inserting a single \nline at the start or in the middle of the file, which changes all the \nchunk boundaries).\n\nFurther, in the absence of subrange reads on blobs, it's not entirely \nclear what using a merkle hash would buy you.\n  --scott\n\nWASHTUB supercomputer security Mk 48 justice ODUNIT radar COBRA JANE \nSSBN 731 BATF KUJUMP SECANT operation class struggle SYNCARP KGB ODACID\n                          ( http://cscott.net/ )\n"},{"id":"329","messageId":"20050416173702.GA12605@macavity","threadId":"36","inReplyTo":"Pine.LNX.4.61.0504161101470.29343@cag.csail.mit.edu","subject":"Re: space compression (again)","fromName":"Martin Uecker","fromEmail":"muecker@gmx.de","sentAt":"2005-04-16T17:37:02Z","receivedAt":"2005-04-16T17:37:02Z","isPatch":false,"sender":{"key":"muecker@gmx.de","avatar":null},"body":"On Sat, Apr 16, 2005 at 11:11:00AM -0400, C. Scott Ananian wrote:\n> On Sat, 16 Apr 2005, Martin Uecker wrote:\n> \n> >The right thing (TM) is to switch from SHA1 of compressed\n> >content for the complete monolithic file to a merkle hash tree\n> >of the uncompressed content. This would make the hash\n> >independent of the actual storage method (chunked or not).\n> \n> It would certainly be nice to change to a hash of the uncompressed \n> content, rather than a hash of the compressed content, but it's not \n> strictly necessary, since files are fetched all at once: there's not 'read \n> subrange' operation on blobs.\n> \n> I assume 'merkle hash tree' is talking about:\n>   http://www.open-content.net/specs/draft-jchapweske-thex-02.html\n> ..which is very interesting, but not quite what I was thinking.\n> The merkle hash approach seems to require fixed chunk boundaries.\n\nI don't know what is written there, but I don't\nconsider fixed chunk boundaries part of the definition.\n\n> The rsync approach does not use fixed chunk boundaries; this is necessary \n> to ensure good storage reuse for the expected case (ie; inserting a single \n> line at the start or in the middle of the file, which changes all the \n> chunk boundaries).\n\nYes. The chunk boundaries should be determined deterministically\nfrom local properties of the data. Use a rolling checksum over\nsome small window and split the file it it hits a special value (0).\nThis is what the rsyncable patch to zlib does.\n\n> Further, in the absence of subrange reads on blobs, it's not entirely \n> clear what using a merkle hash would buy you.\n\nThe whole design of git is a hash tree. If you extend\nthis tree structure into files you end up with merkle\nhash trees. Everything else is just more complicated.\n\nMartin\n \n\n-- \nOne night, when little Giana from Milano was fast asleep,\nshe had a strange dream.\n\n"},{"id":"816","messageId":"20050419123935.GA8091@macavity","threadId":"36","inReplyTo":"20050416173702.GA12605@macavity","subject":"Re: space compression (again)","fromName":"Martin Uecker","fromEmail":"muecker@gmx.de","sentAt":"2005-04-19T12:39:35Z","receivedAt":"2005-04-19T12:39:35Z","isPatch":false,"sender":{"key":"muecker@gmx.de","avatar":null},"body":"On Sat, Apr 16, 2005 at 07:37:02PM +0200, Martin Uecker wrote:\n> On Sat, Apr 16, 2005 at 11:11:00AM -0400, C. Scott Ananian wrote:\n \n> > The rsync approach does not use fixed chunk boundaries; this is necessary \n> > to ensure good storage reuse for the expected case (ie; inserting a single \n> > line at the start or in the middle of the file, which changes all the \n> > chunk boundaries).\n> \n> Yes. The chunk boundaries should be determined deterministically\n> from local properties of the data. Use a rolling checksum over\n> some small window and split the file it it hits a special value (0).\n> This is what the rsyncable patch to zlib does.\n\nThis is certainly uninteresting for source code repositories\nbut for people who manage repositories of rsyncable binary\npackages this would save a lot of space, bandwidth and\ncpu time (compared to rsync because the scanning phase is\nnot necessary anymore). \n\nMartin\n\n-- \nOne night, when little Giana from Milano was fast asleep,\nshe had a strange dream.\n\n"}]}