# space compression (again) 10 messages from 2005-04-15 to 2005-04-19. Participants: C. Scott Ananian, Linus Torvalds, Derek Fawcus, Martin Uecker. Thread: https://gitlist.dev/t/36 ## C. Scott Ananian, 2005-04-15 17:19 Subject: space compression (again) Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.61.0504151232160.27637%40cag.csail.mit.edu ``` I've been reading the archives (a bad idea, I know). Here's a concrete suggestion for GIT space-compression which is (I believe) consistent with the philosophy of GIT. Why are blobs per-file? [After all, Linus insists that files are an illusion.] Why not just have 'chunks', and assemble *these* into blobs (read, 'files')? A good chunk size would fit evenly into some number of disk blocks (no wasted space!). We already have the rsync algorithm which can scan through a file and efficiently tell which existing chunks match (portions of) it, using a rolling checksum. (Here's a refresher: http://samba.anu.edu.au/rsync/tech_report/node2.html ). Why not treat the 'chunk' as the fundamental unit, and compose files from chunks? This should get better space utilization: a small change to file X will only require storage to save the changed chunk, plus meta data to describe the chunks composing the new file. I propose keeping this only one-level deep: we can only specify chunks, not pieces of files. Unlike xdelta schemes, there is no 'file' dependency. Chunks for a blob can be and are shared among *all the other files and versions in the repository*. Moving pieces from file 'a' to file 'b' "just works". Best of all, I believe this can be done in a completely layered fashion. From git's perspective, it's still 'open this blob' or 'write this blob'. It just turns out that the filesystem representation of a blob is slightly more fragmented. Even better, you ought to be able to convert your on-disk store from one representation to the other: the named blob doesn't change, just 'how to fetch the blob' changes. So, for example, Linus' tree can be unchunked for speed, but the release tree (say) can pull pruned history from Linus into a chunked on-disk representation that can be efficiently wget'ted (only new chunks need be transferred). My first concern is possible fragmentation: would we end up with a large number of very small chunks, and end up representing files as a list of lines (effectively)? Maybe someone can think of an effective coalescing strategy, or maybe it is sufficient just to avoid creating chunks smaller than a certain size (ie, possibly writing redundant data to a new chunk, just to improve the possibility of reuse). I'm also not sure what the best 'chunk' size is. Smaller chunks save more space but cost more to access (# of disk seeks per file/blob). Picking a chunk half the average file size should reduce space by ~50% while only requiring ~2 additional seeks per file-read. OTOH, rsync experience suggests 500-1000 byte chunk sizes. Probably empirical testing is best. Lastly, we want to avoid hitting the dcache to check the existence of chunks while encoding. In a large repository, there will be a very large number of chunks. We don't *have* to index all of them, but our compression gets better the more chunks we know about. The rsync algorithm creates hash tables of chunks at different levels of granularity to avoid doing a full check at every byte of the input file. How large should this cached-on-disk chunk hash table be to avoid saturating it as the repository grows (maybe the standard grow-as-you-go hash table is fine; you only need one bit per entry anyway)? Thoughts? Is the constant-factor overhead of indirection-per-blob going to kill git's overwhelming speed? --scott JUBILIST explosion MKULTRA HTAUTOMAT Indonesia Shoal Bay RUCKUS ammunition GPFLOOR Hager SDI MKDELTA KUBARK Dictionary Soviet BLUEBIRD Delta Force ( http://cscott.net/ ) ``` ## Linus Torvalds, 2005-04-15 18:34 Subject: Re: space compression (again) Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.58.0504151117360.7211%40ppc970.osdl.org In-Reply-To: ``` On Fri, 15 Apr 2005, C. Scott Ananian wrote: > > Why are blobs per-file? [After all, Linus insists that files are an > illusion.] Why not just have 'chunks', and assemble *these* > into blobs (read, 'files')? A good chunk size would fit evenly into some > number of disk blocks (no wasted space!). I actually considered that. I ended up not doing it, because it's not obvious how to "block" things up (and even more so because while I like the notion, it flies in the face of the other issues I had: performance and simplicity). The problem with chunking is: - it complicates a lot of the routines. Things like "is this file unchanged" suddenly become "is this file still the same set of chunks", which is just a _lot_ more code and a lot more likely to have bugs. - you have to find a blocking factor. I thought of just going it fixed chunks, and that just doesn't help at all. - we already have wasted space due to the low-level filesystem (as opposed to "git") usually being block-based, which means that space utilization for small objects tends to suck. So you really want to prefer objects that are several kB (compressed), and a small block just wastes tons of space. - there _is_ a natural blocking factor already. That's what a file boundary really is within the project, and finding any other is really quite hard. So I'm personally 100% sure that it's not worth it. But I'm not opposed to the _concept_: it makes total sense in the "filesystem" view, and is 100% equivalent to having an inode with pointers to blocks. I just don't think the concept plays out well in reality. Linus ``` ## C. Scott Ananian, 2005-04-15 18:45 Subject: Re: space compression (again) Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.61.0504151437100.27637%40cag.csail.mit.edu In-Reply-To: ``` On Fri, 15 Apr 2005, Linus Torvalds wrote: > The problem with chunking is: > - it complicates a lot of the routines. Things like "is this file > unchanged" suddenly become "is this file still the same set of chunks", > which is just a _lot_ more code and a lot more likely to have bugs. The blob still has the same hash; therefore the file is still the same. Nothing looks inside blobs; they just want either the hash or the full contents (if I understand the algorithms correctly). I agree it's more code, but I think it can be nicely layered. > - you have to find a blocking factor. I thought of just going it fixed > chunks, and that just doesn't help at all. rsync uses a fixed chunk size, but this chunk can start at any offset (ie, not constrained to fixed boundaries). This means that adding a single line to the file works like you'd expect, even though all the chunk boundaries change. [I think this is what you're talking about.] > - we already have wasted space due to the low-level filesystem (as > opposed to "git") usually being block-based, which means that space > utilization for small objects tends to suck. So you really want to > prefer objects that are several kB (compressed), and a small block just > wastes tons of space. Not on (say) reiserfs, and not over the network. I'm proposing (at the moment) easy conversion from chunked to unchunked disk representation, so that you can leave things unchunked if (for example) you know you're running ext2 with a large block size. > - there _is_ a natural blocking factor already. That's what a file > boundary really is within the project, and finding any other is really > quite hard. Well, yes, it may be nontrivial. But 'quite hard' depends on your perspective, I guess. Given a cache of existing chunks, it's just a few table lookups. =) > So I'm personally 100% sure that it's not worth it. But I'm not opposed to > the _concept_: it makes total sense in the "filesystem" view, and is 100% > equivalent to having an inode with pointers to blocks. I just don't think > the concept plays out well in reality. So I guess I'll have to implement this and find out, won't I? =) --scott AMLASH overthrow SDI Suharto HBDRILL SMOTH SUMAC SYNCARP kibo Blair Diplomat Kojarena CIA cracking counter-intelligence CABOUNCE anthrax ( http://cscott.net/ ) ``` ## Derek Fawcus, 2005-04-15 18:50 Subject: Re: space compression (again) Message-ID: <20050415195038.E6735@mrwint.cisco.com> URL: https://gitlist.dev/e/20050415195038.E6735%40mrwint.cisco.com In-Reply-To: ``` On Fri, Apr 15, 2005 at 01:19:30PM -0400, C. Scott Ananian wrote: > Why are blobs per-file? [After all, Linus insists that files are an > illusion.] Why not just have 'chunks', and assemble *these* > into blobs (read, 'files')? A good chunk size would fit evenly into some > number of disk blocks (no wasted space!). [ I've only been earwigging, not paying a lot of attention, however ...] Funny I was just think of this having read Linus' discourse on "files don't matter", the obvious chunking factor would be say a function. The problem being tending towards having very small files - I know I tend to prefer small functions. Hmm - a underlying filesystem that efficiently stores small files - why does that ring a bell :-) However the simple answer is to have a preparser for a file / tree checkin which split say a .c file into it's associated chunks, anf represented it in git as a signed/hashed object. i.e. a automatically created extra level of indirection (as I seem to recall was added somewhere else?). So say fred.c: /* * File boiler */ #include #include /* * Fn a boiler */ int fn_a(args) { } /* * Fn b boiler */ long fn_b(args) { } Would be split into 4 parts within git, the 'file object' which simply points to the content objects, and 3 contents objects, being the stuff before 'Fn a boiler', fn_a and it's boiler, fn_b and it's boiler. The interesting bit is needing a preprocessor which can roughly parse the code - i.e. detect where to place the boiler blocks. You would then do most of your tree operations upon the file objects, but get the space savings from the content objects being shared. I suspect that simply to prevent pathological conditions you'd have to arrange that the contents objects have a minimal size, irrespective of the number of desired chunks (functions) they would naturally contain. i.e. for compresion efficiency, you may choose something like 2K as the minimal pre compression content object size. DF ``` ## Derek Fawcus, 2005-04-15 19:00 Subject: Re: space compression (again) Message-ID: <20050415200054.F6735@mrwint.cisco.com> URL: https://gitlist.dev/e/20050415200054.F6735%40mrwint.cisco.com In-Reply-To: ``` On Fri, Apr 15, 2005 at 02:45:55PM -0400, C. Scott Ananian wrote: > > - we already have wasted space due to the low-level filesystem (as > > opposed to "git") usually being block-based, which means that space > > utilization for small objects tends to suck. So you really want to > > prefer objects that are several kB (compressed), and a small block just > > wastes tons of space. > > Not on (say) reiserfs, and not over the network. I'm proposing (at the > moment) easy conversion from chunked to unchunked disk representation, > so that you can leave things unchunked if (for example) you know you're > running ext2 with a large block size. Or if one does not care about space, and simply want's speed, add another layer of indirection - a flattened container object which has hashses as normal, then as it's content simply has the 'chunk list object' and the 'chunk objects' concatenated. It's then a per user / database as to if the flattened objects, or the heirarcal objects are storred locally. DF ``` ## Linus Torvalds, 2005-04-15 19:11 Subject: Re: space compression (again) Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.58.0504151210590.7211%40ppc970.osdl.org In-Reply-To: ``` On Fri, 15 Apr 2005, C. Scott Ananian wrote: > > So I guess I'll have to implement this and find out, won't I? =) The best way to shup somebody up is always to just do it, and say "hey, I told you so". It's hard to argue with numbers. Linus ``` ## Martin Uecker, 2005-04-16 14:39 Subject: Re: space compression (again) Message-ID: <20050416143905.GA10370@macavity> URL: https://gitlist.dev/e/20050416143905.GA10370%40macavity In-Reply-To: ``` On Fri, Apr 15, 2005 at 12:11:43PM -0700, Linus Torvalds wrote: > On Fri, 15 Apr 2005, C. Scott Ananian wrote: > > > > So I guess I'll have to implement this and find out, won't I? =) > > The best way to shup somebody up is always to just do it, and say "hey, I > told you so". It's hard to argue with numbers. The right thing (TM) is to switch from SHA1 of compressed content for the complete monolithic file to a merkle hash tree of the uncompressed content. This would make the hash independent of the actual storage method (chunked or not). Martin -- One night, when little Giana from Milano was fast asleep, she had a strange dream. ``` ## C. Scott Ananian, 2005-04-16 15:11 Subject: Re: space compression (again) Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.61.0504161101470.29343%40cag.csail.mit.edu In-Reply-To: <20050416143905.GA10370@macavity> ``` On Sat, 16 Apr 2005, Martin Uecker wrote: > The right thing (TM) is to switch from SHA1 of compressed > content for the complete monolithic file to a merkle hash tree > of the uncompressed content. This would make the hash > independent of the actual storage method (chunked or not). It would certainly be nice to change to a hash of the uncompressed content, rather than a hash of the compressed content, but it's not strictly necessary, since files are fetched all at once: there's not 'read subrange' operation on blobs. I assume 'merkle hash tree' is talking about: http://www.open-content.net/specs/draft-jchapweske-thex-02.html ..which is very interesting, but not quite what I was thinking. The merkle hash approach seems to require fixed chunk boundaries. The rsync approach does not use fixed chunk boundaries; this is necessary to ensure good storage reuse for the expected case (ie; inserting a single line at the start or in the middle of the file, which changes all the chunk boundaries). Further, in the absence of subrange reads on blobs, it's not entirely clear what using a merkle hash would buy you. --scott WASHTUB supercomputer security Mk 48 justice ODUNIT radar COBRA JANE SSBN 731 BATF KUJUMP SECANT operation class struggle SYNCARP KGB ODACID ( http://cscott.net/ ) ``` ## Martin Uecker, 2005-04-16 17:37 Subject: Re: space compression (again) Message-ID: <20050416173702.GA12605@macavity> URL: https://gitlist.dev/e/20050416173702.GA12605%40macavity In-Reply-To: ``` On Sat, Apr 16, 2005 at 11:11:00AM -0400, C. Scott Ananian wrote: > On Sat, 16 Apr 2005, Martin Uecker wrote: > > >The right thing (TM) is to switch from SHA1 of compressed > >content for the complete monolithic file to a merkle hash tree > >of the uncompressed content. This would make the hash > >independent of the actual storage method (chunked or not). > > It would certainly be nice to change to a hash of the uncompressed > content, rather than a hash of the compressed content, but it's not > strictly necessary, since files are fetched all at once: there's not 'read > subrange' operation on blobs. > > I assume 'merkle hash tree' is talking about: > http://www.open-content.net/specs/draft-jchapweske-thex-02.html > ..which is very interesting, but not quite what I was thinking. > The merkle hash approach seems to require fixed chunk boundaries. I don't know what is written there, but I don't consider fixed chunk boundaries part of the definition. > The rsync approach does not use fixed chunk boundaries; this is necessary > to ensure good storage reuse for the expected case (ie; inserting a single > line at the start or in the middle of the file, which changes all the > chunk boundaries). Yes. The chunk boundaries should be determined deterministically from local properties of the data. Use a rolling checksum over some small window and split the file it it hits a special value (0). This is what the rsyncable patch to zlib does. > Further, in the absence of subrange reads on blobs, it's not entirely > clear what using a merkle hash would buy you. The whole design of git is a hash tree. If you extend this tree structure into files you end up with merkle hash trees. Everything else is just more complicated. Martin -- One night, when little Giana from Milano was fast asleep, she had a strange dream. ``` ## Martin Uecker, 2005-04-19 12:39 Subject: Re: space compression (again) Message-ID: <20050419123935.GA8091@macavity> URL: https://gitlist.dev/e/20050419123935.GA8091%40macavity In-Reply-To: <20050416173702.GA12605@macavity> ``` On Sat, Apr 16, 2005 at 07:37:02PM +0200, Martin Uecker wrote: > On Sat, Apr 16, 2005 at 11:11:00AM -0400, C. Scott Ananian wrote: > > The rsync approach does not use fixed chunk boundaries; this is necessary > > to ensure good storage reuse for the expected case (ie; inserting a single > > line at the start or in the middle of the file, which changes all the > > chunk boundaries). > > Yes. The chunk boundaries should be determined deterministically > from local properties of the data. Use a rolling checksum over > some small window and split the file it it hits a special value (0). > This is what the rsyncable patch to zlib does. This is certainly uninteresting for source code repositories but for people who manage repositories of rsyncable binary packages this would save a lot of space, bandwidth and cpu time (compared to rsync because the scanning phase is not necessary anymore). Martin -- One night, when little Giana from Milano was fast asleep, she had a strange dream. ```