{"thread":{"id":"1","subject":"Re: Index/hash order","startedAt":"2005-04-13T20:02:37Z","lastAt":"2005-04-27T08:15:23Z","messageCount":20,"participants":["Ingo Molnar","H. Peter Anvin","Linus Torvalds","Baruch Even","Florian Weimer","Chris Wedgwood","Nick Craig-Wood","Wout"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"1","messageId":"20050413200237.GA26635@elte.hu","threadId":"1","inReplyTo":"Pine.LNX.4.58.0504131144160.4501@ppc970.osdl.org","subject":"Re: Index/hash order","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2005-04-13T20:02:37Z","receivedAt":"2005-04-13T20:02:37Z","isPatch":false,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* Linus Torvalds wrote:\n\n> > with a plaintext repository we could do the 'hardlink trick' (which \n> > brings in other manageability problems and limitations but is at least a \n> > partially good idea), which would make the working tree and the \n> > repository share the same inode in most cases.\n\n> However, the real issue is that you're really asking for trouble. \n> There are tons of tools that modify files without breaking the \n> hardlink. Even some editors do. So you just use the wrong tool on the \n> tree by mistake, and not only is your archive corrupt, you've \n> corrupted all other archives that might have shared the same object \n> directory.\n\nthat's what i loosely meant under 'manageability problems'.\n\nI mentioned one solution earlier: to make the repository object an \nimmutable file (the +i flag on the inode) - it really wants to be \nimmutable after all. That would solve a whole range of 'accidental \ncorruption' issues.\n\nAnother solution (suggested by Christer Weinigel) was to enforce \nimmutability by making it owned by another user/group (git:git or \nwhatever).\n\nbut having a binary compressed format is 'soft immutability', done \ncleverly.\n\n\tIngo\n"},{"id":"2","messageId":"425D7C0F.2050109@zytor.com","threadId":"1","inReplyTo":"20050413200237.GA26635@elte.hu","subject":"Re: Index/hash order","fromName":"H. Peter Anvin","fromEmail":"hpa@zytor.com","sentAt":"2005-04-13T20:07:43Z","receivedAt":"2005-04-13T20:07:43Z","isPatch":false,"sender":{"key":"hpa@zytor.com","avatar":null},"body":"Ingo Molnar wrote:\n> \n> that's what i loosely meant under 'manageability problems'.\n> \n> I mentioned one solution earlier: to make the repository object an \n> immutable file (the +i flag on the inode) - it really wants to be \n> immutable after all. That would solve a whole range of 'accidental \n> corruption' issues.\n> \n\nI think abusing the immutable bit quickly will decend into the same \nrathole which makes u-w often useless. u-w will actually be preserved \nby more tools -- simply because they know about it -- than +i.\n\nEither which way, it feels to me that this idea has already been ruled \nout, so it's probably pointless to keep debating just exactly what we're \nnot actually going to do.\n\n\t-hpa\n"},{"id":"4","messageId":"20050413201523.GC27088@elte.hu","threadId":"1","inReplyTo":"425D7C0F.2050109@zytor.com","subject":"Re: Index/hash order","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2005-04-13T20:15:23Z","receivedAt":"2005-04-13T20:15:23Z","isPatch":false,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* H. Peter Anvin wrote:\n\n> >that's what i loosely meant under 'manageability problems'.\n> >\n> >I mentioned one solution earlier: to make the repository object an \n> >immutable file (the +i flag on the inode) - it really wants to be \n> >immutable after all. That would solve a whole range of 'accidental \n> >corruption' issues.\n> >\n> \n> I think abusing the immutable bit quickly will decend into the same \n> rathole which makes u-w often useless. u-w will actually be preserved \n> by more tools -- simply because they know about it -- than +i.\n\nwell, the 'owned by another user' solution is valid though, and doesnt \nhave this particular problem. (We've got a secure multiuser OS, so can \nas well use it to protect the DB against corruption.)\n\n> Either which way, it feels to me that this idea has already been ruled \n> out, so it's probably pointless to keep debating just exactly what \n> we're not actually going to do.\n\n(even if it sounds stupid, i keep discussing decisions that are done for \nreasons i cannot fully agree with (yet), even if i happen to agree with \nthe net decision. It's all technological arguments, so it's not like \nthere's anything fuzzy about any of these issues.)\n\n\tIngo\n"},{"id":"3","messageId":"Pine.LNX.4.58.0504131314150.4501@ppc970.osdl.org","threadId":"1","inReplyTo":"425D7C0F.2050109@zytor.com","subject":"Re: Index/hash order","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-04-13T20:15:57Z","receivedAt":"2005-04-13T20:15:57Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 13 Apr 2005, H. Peter Anvin wrote:\n> \n> Either which way, it feels to me that this idea has already been ruled \n> out, so it's probably pointless to keep debating just exactly what we're \n> not actually going to do.\n\nHey, isn't that how most discussions progress? ;)\n\nI don't mind alternatives per se. I'm just lazy. I came up with one\nsolution to the issues I percieved, and I like that one. But dammit, if\nsomebody comes up with something _clearly_ superior, I'll just bow down in\nyour general direction, and promptly implement that.\n\n\t\tLinus\n"},{"id":"5","messageId":"20050413201836.GA27694@elte.hu","threadId":"1","inReplyTo":"20050413201523.GC27088@elte.hu","subject":"Re: Index/hash order","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2005-04-13T20:18:36Z","receivedAt":"2005-04-13T20:18:36Z","isPatch":false,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* Ingo Molnar wrote:\n\n> > I think abusing the immutable bit quickly will decend into the same \n> > rathole which makes u-w often useless. u-w will actually be preserved \n> > by more tools -- simply because they know about it -- than +i.\n> \n> well, the 'owned by another user' solution is valid though, and doesnt \n> have this particular problem. (We've got a secure multiuser OS, so can \n> as well use it to protect the DB against corruption.)\n\nbut ... this variant doesnt have any 'wow' feeling to it either, and it \nclearly brings in a number of other limitations. I might as well shut up \nuntil i can suggest something obviously superior :)\n\n\tIngo\n"},{"id":"6","messageId":"20050413202102.GA27733@elte.hu","threadId":"1","inReplyTo":"20050413201836.GA27694@elte.hu","subject":"Re: Index/hash order","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2005-04-13T20:21:02Z","receivedAt":"2005-04-13T20:21:02Z","isPatch":false,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* Ingo Molnar wrote:\n\n> > > I think abusing the immutable bit quickly will decend into the same \n> > > rathole which makes u-w often useless. u-w will actually be preserved \n> > > by more tools -- simply because they know about it -- than +i.\n> > \n> > well, the 'owned by another user' solution is valid though, and doesnt \n> > have this particular problem. (We've got a secure multiuser OS, so can \n> > as well use it to protect the DB against corruption.)\n> \n> but ... this variant doesnt have any 'wow' feeling to it either, and \n> it clearly brings in a number of other limitations. I might as well \n> shut up until i can suggest something obviously superior :)\n\ni think the killer argument is compression. A 2 GB compressed repository \nwill be a hard sell already, 4 GB is pretty much out of question. And \nonce we accept that we have to have _some_ form of compression, it's \nLinus' scheme that wins.\n\n\tIngo\n"},{"id":"7","messageId":"425D8083.70105@zytor.com","threadId":"1","inReplyTo":"20050413202102.GA27733@elte.hu","subject":"Updated base64 patches","fromName":"H. Peter Anvin","fromEmail":"hpa@zytor.com","sentAt":"2005-04-13T20:26:43Z","receivedAt":"2005-04-13T20:26:43Z","isPatch":false,"sender":{"key":"hpa@zytor.com","avatar":null},"body":"I have uploaded two new base64 patches, one which uses the flat \nrepository and one which doesn't:\n\nftp://ftp.kernel.org/pub/linux/kernel/people/hpa/git-0.04-base64-3.diff\nftp://ftp.kernel.org/pub/linux/kernel/people/hpa/git-0.04-base64-flat-3.diff\n\n... both are still against the git-0.04 tarball.\n\nThe only differences is changing \"char\" to \"signed char\" in places where \nit actually matters (since plain char is unsigned on some platforms), \nand, for the non-flat version, allowing the cache subdirectories to be \nlazily created (if ENOENT is returned, try mkdir before giving up.)\n\n\t-=hpa\n"},{"id":"8","messageId":"425D8104.9030109@ev-en.org","threadId":"1","inReplyTo":"20050413182909.GA25221@elte.hu","subject":"Re: Index/hash order","fromName":"Baruch Even","fromEmail":"baruch@ev-en.org","sentAt":"2005-04-13T20:28:52Z","receivedAt":"2005-04-13T20:28:52Z","isPatch":false,"sender":{"key":"baruch@ev-en.org","avatar":null},"body":"Ingo Molnar wrote:\n> with a plaintext repository we could do the 'hardlink trick' (which \n> brings in other manageability problems and limitations but is at least a \n> partially good idea), which would make the working tree and the \n> repository share the same inode in most cases.\n> \n> While in the compressed case we'd have a separate compressed inode \n> (taking up RAM with all its contents) and the working directory inode \n> (taking up RAM) - summing up to more RAM than if we only had a single \n> inode per object.\n> \n> furthermore, when generating/destroying large trees (which is a quite \n> common thing), a hardlinked solution is faster, as it doesnt create \n> 250MB+ of dirty RAM. In some cases (e.g. handling dozens of 'merge \n> trees') it's dramatically faster.\n\nYou could still have the hardlink way by way of a .git/cache that keeps \nuncompressed files, keep the files with their hash names but uncompressed.\n\nIt will be easy to find, fully hard-linkable, only keep the needed files \n uncompressed and the three year old file compressed. The\n\nYou can even save some CPU time by checking if the file is in the cache \nbefore decompressing it, though it does cost you with an extra disk \naccess to see if it's there or not. If you repeat the operation enough \nyou'll have the uncompressed version in the cache most of the times anyway.\n\nClear the cache weekly or so to avoid stale files from an ancient version.\n\nBaruch\n"},{"id":"9","messageId":"Pine.LNX.4.58.0504131404380.4501@ppc970.osdl.org","threadId":"1","inReplyTo":"20050413201523.GC27088@elte.hu","subject":"Re: Index/hash order","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-04-13T21:04:59Z","receivedAt":"2005-04-13T21:04:59Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 13 Apr 2005, Ingo Molnar wrote:\n> \n> well, the 'owned by another user' solution is valid though, and doesnt \n> have this particular problem. (We've got a secure multiuser OS, so can \n> as well use it to protect the DB against corruption.)\n\nSo now you need root to set up new repositories? No thanks.\n\n\t\tLinus\n"},{"id":"10","messageId":"87aco2gxu2.fsf@deneb.enyo.de","threadId":"1","inReplyTo":"Pine.LNX.4.58.0504131008500.4501@ppc970.osdl.org","subject":"Re: Index/hash order","fromName":"Florian Weimer","fromEmail":"fw@deneb.enyo.de","sentAt":"2005-04-13T21:40:05Z","receivedAt":"2005-04-13T21:40:05Z","isPatch":false,"sender":{"key":"fw@deneb.enyo.de","avatar":null},"body":"* Linus Torvalds:\n\n> - I want things to distribute well. This means that it has to be based \n> on a \"append data\" model, where historical data never changes, and you \n> only append on top of it (either by adding totally new files, or by \n> just letting the files grow).\n\nYes, I think this is something which can easily dominate the choice of\ndata structure.\n\n> This works in a forward-delta environment (which is fundamentally based \n> on the notion of \"we know the old version, we're adding new stuff on\n> top of it\"), but does _not_ work in the backwards model of \"we keep the\n> old history as a delta against the new\" model.\n\nForward deltas don't have to be terribly inefficient. You can get\nO(log n) access to revision n fairly easily, using the trick described\nthere:\n\n \n\nI've run a few tests, just to get a few numbers of the overhead\ninvolved. I used the last ~8,000 changesets from the BKCVS kernel\nrepository. With cold cache, a checkout from cold cache takes about\n250 seconds on my laptop. I don't have git numbers, but a mere copy\nof the kernel tree needs 40 seconds.\n\nFor the hot-cache case, the difference is 140 seconds vs. 2.5 seconds\n(or 6 seconds with decompression).\n\nUh-oh. I wouldn't have imaged the difference would be *that*\ndramatic. The file system layer is *fast*.\n\nSubversion's delta implementation is not a speed daemon (it handles\narbitrarily large files, which increases complexity significantly and\nslows things down, compared to simpler in-memory algorithms), but it\nwill be very hard to come even close to the 2.5 seconds.\n\nOn the storage front, we have 220 MB for the skip deltas vs. 106 MB\nfor pure deltas-to-previous vs. 1.1 GB for uncompressed files\n(directories are always delta-compressed, so to speak[1]). In the\nfirst two cases, the first revision in the repository is deltaed\nagainst /dev/null and itself and thus compressed, in case you think\nthe numbers are suspiciously low.\n\n1. AFAICS, you can't really avoid that if you want to track file\n identity information without introducing arbitrary file IDs.\n"},{"id":"14","messageId":"Pine.LNX.4.58.0504131503180.4501@ppc970.osdl.org","threadId":"1","inReplyTo":"87aco2gxu2.fsf@deneb.enyo.de","subject":"Re: Index/hash order","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-04-13T22:11:57Z","receivedAt":"2005-04-13T22:11:57Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Wed, 13 Apr 2005, Florian Weimer wrote:\n> \n> I've run a few tests, just to get a few numbers of the overhead\n> involved. I used the last ~8,000 changesets from the BKCVS kernel\n> repository. With cold cache, a checkout from cold cache takes about\n> 250 seconds on my laptop. I don't have git numbers, but a mere copy\n> of the kernel tree needs 40 seconds.\n\nI will bet you that a git checkout is _faster_ than a kernel source tree\ncopy. The time will be dominated by the IO costs (in particular the read\ncosts), and the IO costs are lower thanks to compression. So I think that\nthe cold-cache case will beat your 40 seconds by a clear margin. It\ngenerally compresses to half the size, so 20 seconds is not impossible\n(although seek costs would tend to stay constant, so I'd expect it to be\nsomewhere in between the two).\n\n> For the hot-cache case, the difference is 140 seconds vs. 2.5 seconds\n> (or 6 seconds with decompression).\n> \n> Uh-oh. I wouldn't have imaged the difference would be *that*\n> dramatic. The file system layer is *fast*.\n\nDid I mention that I designed git for speed?\n\nYes. The whole damn design is really about performance, distribution, and \nbuilt-in integrity checking. \n\n> On the storage front, we have 220 MB for the skip deltas vs. 106 MB\n> for pure deltas-to-previous vs. 1.1 GB for uncompressed files\n> (directories are always delta-compressed, so to speak[1]).\n\nThat's actually pretty encouraging. Your 1.1GB number implies to me that a\ncompressed file setup should be about half that, which in turn says that\nthe cost of full-file is not at all outrageous. Sure, it's 2-3 times\nlarger than your skip deltas, but considering that the performance is\nabout fifty times faster (and I can do distributed stuff without any\nlocking synchronization and you can't), that's a tradeoff I'm more than\nhappy with.\n\nOr maybe I misunderstood what you were comparing?\n\nOf course, the numbers will all depend on how the history looks etc, so \nthis is all pretty much just guidelines.\n\n\t\t\tLinus\n"},{"id":"16","messageId":"87br8ithsv.fsf@deneb.enyo.de","threadId":"1","inReplyTo":"Pine.LNX.4.58.0504131503180.4501@ppc970.osdl.org","subject":"Re: Index/hash order","fromName":"Florian Weimer","fromEmail":"fw@deneb.enyo.de","sentAt":"2005-04-13T22:48:00Z","receivedAt":"2005-04-13T22:48:00Z","isPatch":false,"sender":{"key":"fw@deneb.enyo.de","avatar":null},"body":"* Linus Torvalds:\n\n> I will bet you that a git checkout is _faster_ than a kernel source tree\n> copy. The time will be dominated by the IO costs (in particular the read\n> costs), and the IO costs are lower thanks to compression. So I think that\n> the cold-cache case will beat your 40 seconds by a clear margin. It\n> generally compresses to half the size, so 20 seconds is not impossible\n> (although seek costs would tend to stay constant, so I'd expect it to be\n> somewhere in between the two).\n\nIt's indeed slightly faster (34 seconds). The hot-cache case is about\n6 seconds. Still okay.\n\nHowever, I should redo these tests with a real git. The numbers could\nbe quite different because seek overhead is a bit hard to predict.\nWhich version should I try?\n\n> That's actually pretty encouraging. Your 1.1GB number implies to me that a\n> compressed file setup should be about half that, which in turn says that\n> the cost of full-file is not at all outrageous.\n\nI usually try to avoid the typical O(f(n)) fallacy because constant\nfactors do matter in practice. But the way you put it -- maybe delta\ncompression isn't worth the complexity after all. At least I'm\nbeginning to have doubts.\n\nEspecially since the same Subversion repository, stored by the\nBerkeley DB backend, requires a whopping 1.3 GB of disk space.\n\n> Or maybe I misunderstood what you were comparing?\n\nMy estimates only cover file data, not metadata. Based on the\nSubversion dumps, it might be possible to get some rough estimates for\nthe cost of storing directory information. What is the average size\nof a directory blob? Is it true that for each tree revision, you need\nto store a new directory blob for each directory which indirectly\ncontains a modified file?\n\nDoes your 50% estimate include wasted space due to the file system\nblock size?\n"},{"id":"46","messageId":"20050414070422.GA3226@elte.hu","threadId":"1","inReplyTo":"Pine.LNX.4.58.0504131503180.4501@ppc970.osdl.org","subject":"Re: Index/hash order","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2005-04-14T07:04:22Z","receivedAt":"2005-04-14T07:04:22Z","isPatch":false,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* Linus Torvalds wrote:\n\n> > I've run a few tests, just to get a few numbers of the overhead\n> > involved. I used the last ~8,000 changesets from the BKCVS kernel\n> > repository. With cold cache, a checkout from cold cache takes about\n> > 250 seconds on my laptop. I don't have git numbers, but a mere copy\n> > of the kernel tree needs 40 seconds.\n> \n> I will bet you that a git checkout is _faster_ than a kernel source \n> tree copy. The time will be dominated by the IO costs (in particular \n> the read costs), and the IO costs are lower thanks to compression. So \n> I think that the cold-cache case will beat your 40 seconds by a clear \n> margin. It generally compresses to half the size, so 20 seconds is not \n> impossible (although seek costs would tend to stay constant, so I'd \n> expect it to be somewhere in between the two).\n\ni'd be surprised if it was twice as fast - cache-cold linear checkouts \nare _seek_ limited, and it doesnt matter whether after a 1-2 msec \ntrack-to-track disk seek the DMA engine spends another 30 microseconds \nDMA-ing 60K uncompressed data instead of 30K compressed... (there are \nother factors, but this is the main thing.)\n\n\tIngo\n"},{"id":"65","messageId":"20050414105018.GA5408@elte.hu","threadId":"1","inReplyTo":"20050414070422.GA3226@elte.hu","subject":"cache-cold repository performance","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2005-04-14T10:50:18Z","receivedAt":"2005-04-14T10:50:18Z","isPatch":false,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* Ingo Molnar wrote:\n\n> i'd be surprised if it was twice as fast - cache-cold linear checkouts \n> are _seek_ limited, and it doesnt matter whether after a 1-2 msec \n> track-to-track disk seek the DMA engine spends another 30 microseconds \n> DMA-ing 60K uncompressed data instead of 30K compressed... (there are \n> other factors, but this is the main thing.)\n\ni've benchmarked cache-cold compressed vs. uncompressed performance, to \nshed some more light on the performance differences between flat and \ncompressed repositories.\n\ni did alot of testing, and i primarily concentrated on being able to \n_trust_ the benchmark results, not to generate some quick numbers. The \nmajor problem was that the timing of the reads associated with 'checking \nout a large tree' is very unstable, even on a completely isolated \ntestsystem with very common (and predictable) IO hardware.\n\nthe content i tested was a vanilla 2.6.10 kernel tree, with 19042 files \nin it, taking 246 MB uncompressed, and 110 MB compressed (via gzip -9). \nAverage file size is 13.2 KB uncompressed, 5.9 KB compressed.\n\nFirstly, the timings are very sensitive to the way the tree was created. \nTo have a 'fair' on-disk layout the trees have to be created in an \nidentical fashion: e.g. it is not valid to copy the uncompressed tree \nand run gzip over it - that will create a 'sparse' on-disk layout \npenalizing the compressed layout and making it 30% slower than the \nuncompressed layout! I first created the two trees, then i \"cp -a\"-ed \nthem over into a new directory one after each other, so that they get on \nsimilar on-disk positions as well. I also created 2 more pairs of such \ntrees to make sure disk layout is fair.\n\nall timings were taken fresh after reboot, on a UP 1 GB RAM Athlon64 \n3200+, using a large, top of the line IDE disk. The kernel was \n2.6.12-rc2, the filesystem was ext3 with enough free space to not be \nfragmented, both noatime and nodiratime was specified so that no write \nactivities whatever occur during the 'checkout'.\n\nthe operation timed was a simple:\n\n time find . -type f | xargs cat > /dev/null\n\ndone in the root of the given tree. This generates the very same \nreadonly IO pattern for each test. I've run the tests 10 times (i.e. \nhave done 10 fresh reboots), but after every reboot i permutated the \norder of trees tested - to make sure there is no interaction between \ntrees. (there was no interaction)\n\nhere are the raw numbers, elapsed real time in seconds:\n\n flat-1: 29.7 29.5 29.4 29.4 29.5 29.5 29.7 29.6 29.4 29.6 29.5 29.4: 29.5\n gzip-1: 41.2 40.9 40.7 40.7 40.5 41.7 41.0 40.3 40.6 40.8 40.8 40.9: 40.8\n\n flat-2: 28.0 28.2 27.7 27.9 27.8 27.9 27.7 27.9 27.9 28.1 27.9 28.0: 27.9\n gzip-2: 27.2 27.4 27.4 27.2 27.2 27.2 27.2 27.2 27.1 27.3 27.2 27.4: 27.2\n flat-3: 27.0 27.8 27.6 27.7 27.8 27.8 27.8 27.7 27.8 27.6 27.8 27.8: 27.6\n gzip-3: 25.8 26.8 26.6 26.5 26.5 26.5 26.6 26.4 26.5 26.7 26.6 26.7: 26.5\n\nThe final column is the average. (Standard deviation is below 0.1 sec, \nless than 0.3%.)\n\nflat-1 is the original tree, created via tar. gzip-1 is a cp -a copy of \nit, per-file compressed afterwards. flat-2 is a cp -a copy of flat-1, \ngzip-2 is a cp -a copy of gzip-1. flat-3/gzip-3 are cp -a copies of \nflat-2/gzip-2.\n\nnote that gzip-1 is ~40% slower due to the 'sparse layout', so its \nresults approximate a repository with 'bad' file layout. I'd not expect \nGIT repositories to have such a layout normally, so we can disregard it.\n\nflat-2/3 and gzip-2/3 can be directly compared. Firstly, the results \nshow that the on-disk layout cannot be constructed reliably - there's a \n1% systematic difference between flat-2 and flat-3, and a 3% systematic \ndifference between gzip-2 and gzip-3 - both systematic errors are larger \nthan the 0.5% standard deviation, so they are not measurement errors but \nreal layout properties of these trees.\n\nthe most interesting result is that gzip-2 is 2.5% faster than flat-2, \nand gzip-3 is 4% faster than flat-3. These differences are close to the \nlayout-related systematic error, but slightly above it, so i'd conclude \nthat a compressed repository is 3% faster on this hardware.\n\n(since these results were in line with my expectations i double-checked \neverything again and did another 10 reboot tests - same results.)\n\nconclusion [*]: there's a negligible cache-cold performance hit from \nusing an uncompressed repository, because cache-cold performance is \ndominated by number of seeks, which is almost identical in the two \ncases.\n\n\tIngo\n\n[*] lots of conditionals apply: these werent flat/compressed GIT \nrepositories (although they were quite similar to it), nor was the GIT \nworkload measured (although the one measured should be quite close to \nit).\n\n"},{"id":"950","messageId":"20050420074053.GA22436@elte.hu","threadId":"1","inReplyTo":"Pine.LNX.4.58.0504131404380.4501@ppc970.osdl.org","subject":"enforcing DB immutability","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2005-04-20T07:40:53Z","receivedAt":"2005-04-20T07:40:53Z","isPatch":false,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* Linus Torvalds wrote:\n\n> On Wed, 13 Apr 2005, Ingo Molnar wrote:\n> > \n> > well, the 'owned by another user' solution is valid though, and doesnt \n> > have this particular problem. (We've got a secure multiuser OS, so can \n> > as well use it to protect the DB against corruption.)\n> \n> So now you need root to set up new repositories? No thanks.\n\nyeah, it's a bit awkward to protect uncompressed repositories - but it \nwill need some sort of kernel enforcement. (if userspace finds out the \nDB contains uncompressed blobs, it _will_ try to use them.)\n\n(perhaps having an in-kernel GIT-alike versioned filesystem will help - \nbut that brings up the same 'I have to be root' issues. The FS will \nenforce the true immutability of objects.)\n\nperhaps having a new 'immutable hardlink' feature in the Linux VFS would \nhelp? I.e. a hardlink that can only be readonly followed, and can be \nremoved, but cannot be chmod-ed to a writeable hardlink. That i think \nwould be a large enough barrier for editors/build-tools not to play the \ntricks they already do that makes 'readonly' files virtually \nmeaningless.\n\n\tIngo\n"},{"id":"952","messageId":"20050420074948.GA22620@elte.hu","threadId":"1","inReplyTo":"20050420074053.GA22436@elte.hu","subject":"Re: enforcing DB immutability","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2005-04-20T07:49:48Z","receivedAt":"2005-04-20T07:49:48Z","isPatch":false,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* Ingo Molnar wrote:\n\n> perhaps having a new 'immutable hardlink' feature in the Linux VFS \n> would help? I.e. a hardlink that can only be readonly followed, and \n> can be removed, but cannot be chmod-ed to a writeable hardlink. That i \n> think would be a large enough barrier for editors/build-tools not to \n> play the tricks they already do that makes 'readonly' files virtually \n> meaningless.\n\nimmutable hardlinks have the following advantage: a hardlink by design \nhides the information where the link comes from. So even if an editor \nwanted to play stupid games and override the immutability - it doesnt \nknow where the DB object is. (sure, it could find it if it wants to, but \nthat needs real messing around - editors wont do _that_)\n\ni think this might work.\n\n(the current chattr +i flag isnt quite what we need though because it \nworks on the inode, and it's also a root-only feature so it puts us back \nto square one. What would be needed is an immutability flag on \nhardlinks, settable by unprivileged users.)\n\n\tIngo\n"},{"id":"954","messageId":"20050420075320.GA22676@elte.hu","threadId":"1","inReplyTo":"20050420074948.GA22620@elte.hu","subject":"Re: enforcing DB immutability","fromName":"Ingo Molnar","fromEmail":"mingo@elte.hu","sentAt":"2005-04-20T07:53:20Z","receivedAt":"2005-04-20T07:53:20Z","isPatch":false,"sender":{"key":"mingo@elte.hu","avatar":null},"body":"\n* Ingo Molnar wrote:\n\n> > perhaps having a new 'immutable hardlink' feature in the Linux VFS \n> > would help? I.e. a hardlink that can only be readonly followed, and \n> > can be removed, but cannot be chmod-ed to a writeable hardlink. That i \n> > think would be a large enough barrier for editors/build-tools not to \n> > play the tricks they already do that makes 'readonly' files virtually \n> > meaningless.\n> \n> immutable hardlinks have the following advantage: a hardlink by design \n> hides the information where the link comes from. So even if an editor \n> wanted to play stupid games and override the immutability - it doesnt \n> know where the DB object is. (sure, it could find it if it wants to, \n> but that needs real messing around - editors wont do _that_)\n\nso the only sensible thing the editor/tool can do when it wants to \nchange the file is precisely what we want: it will copy the hardlinked \nfiles's contents to a new file, and will replace the old file with the \nnew file - a copy on write. No accidental corruption of the DB's \ncontents.\n\n(another in-kernel VFS solution would be to enforce that the files's \nname always matches the sha1 hash. So if someone edits a DB object it \nwill automatically change its name. But this is complex, probably cannot \nbe done atomically, and brings up other problems as well.)\n\n\tIngo\n"},{"id":"957","messageId":"20050420085822.GC3263@taniwha.stupidest.org","threadId":"1","inReplyTo":"20050420075320.GA22676@elte.hu","subject":"Re: enforcing DB immutability","fromName":"Chris Wedgwood","fromEmail":"cw@f00f.org","sentAt":"2005-04-20T08:58:22Z","receivedAt":"2005-04-20T08:58:22Z","isPatch":false,"sender":{"key":"cw@f00f.org","avatar":null},"body":"On Wed, Apr 20, 2005 at 09:53:20AM +0200, Ingo Molnar wrote:\n\n> so the only sensible thing the editor/tool can do when it wants to\n> change the file is precisely what we want: it will copy the\n> hardlinked files's contents to a new file, and will replace the old\n> file with the new file - a copy on write. No accidental corruption\n> of the DB's contents.\n\neditors that have SCM smarts and know about the files different states\ncan do this\n\ni really like the way this works under BK btw --- files are RO until i\ndo the magic thing which will do a 'bk edit' and i can then do\ncheckins or similar as needed (this assumes you can do per-file\ndeltas)\n"},{"id":"983","messageId":"20050420145725.GA23072@craig-wood.com","threadId":"1","inReplyTo":"20050420074948.GA22620@elte.hu","subject":"Re: enforcing DB immutability","fromName":"Nick Craig-Wood","fromEmail":"nick@craig-wood.com","sentAt":"2005-04-20T14:57:25Z","receivedAt":"2005-04-20T14:57:25Z","isPatch":false,"sender":{"key":"nick@craig-wood.com","avatar":null},"body":"On Wed, Apr 20, 2005 at 09:49:48AM +0200, Ingo Molnar wrote:\n> * Ingo Molnar wrote:\n> \n> > perhaps having a new 'immutable hardlink' feature in the Linux VFS \n> > would help? I.e. a hardlink that can only be readonly followed, and \n> > can be removed, but cannot be chmod-ed to a writeable hardlink. That i \n> > think would be a large enough barrier for editors/build-tools not to \n> > play the tricks they already do that makes 'readonly' files virtually \n> > meaningless.\n> \n> immutable hardlinks have the following advantage: a hardlink by design \n> hides the information where the link comes from. So even if an editor \n> wanted to play stupid games and override the immutability - it doesnt \n> know where the DB object is. (sure, it could find it if it wants to, but \n> that needs real messing around - editors wont do _that_)\n\nThis has already been implemented for the linux vserver project. Take\na look in the patch here :-\n\n http://vserver.13thfloor.at/Experimental/patch-2.6.11.7-vs1.9.5.x5.diff.bz2\n\n(Its not split out, but search for IMMUTABLE and you'll see what I mean)\n\nIt implements immutable linkage invert, which basically allows people\nto delete hardlinks to immutable files, but not do anything else to\nthem. It uses another bit out of the attributes to \"invert\" the\nimmutability of the linkage of immutable files.\n\nIts used in the vserver project so that individual vservers (which are\nbasically just fancy chroots) can share libraries, binaries and hence\nmemory, can't muck each other up, but can upgrade their libs/binaries.\n\n-- \nNick Craig-Wood -- http://www.craig-wood.com/nick\n"},{"id":"1856","messageId":"20050427081523.GA23726@moon","threadId":"1","inReplyTo":"20050420074948.GA22620@elte.hu","subject":"Re: enforcing DB immutability","fromName":"Wout","fromEmail":"git@bliepbliep.net","sentAt":"2005-04-27T08:15:23Z","receivedAt":"2005-04-27T08:15:23Z","isPatch":false,"sender":{"key":"git@bliepbliep.net","avatar":null},"body":"On Wed, Apr 20, 2005 at 09:49:48AM +0200, Ingo Molnar wrote:\n> \n> * Ingo Molnar wrote:\n> \n> > perhaps having a new 'immutable hardlink' feature in the Linux VFS \n> > would help? I.e. a hardlink that can only be readonly followed, and \n> > can be removed, but cannot be chmod-ed to a writeable hardlink. That i \n> > think would be a large enough barrier for editors/build-tools not to \n> > play the tricks they already do that makes 'readonly' files virtually \n> > meaningless.\n> \n> immutable hardlinks have the following advantage: a hardlink by design \n> hides the information where the link comes from. So even if an editor \n> wanted to play stupid games and override the immutability - it doesnt \n> know where the DB object is. (sure, it could find it if it wants to, but \n> that needs real messing around - editors wont do _that_)\n> \n> i think this might work.\n> \n> (the current chattr +i flag isnt quite what we need though because it \n> works on the inode, and it's also a root-only feature so it puts us back \n> to square one. What would be needed is an immutability flag on \n> hardlinks, settable by unprivileged users.)\n> \n> \tIngo\n> -\n> To unsubscribe from this list: send the line \"unsubscribe git\" in\n> the body of a message to majordomo@vger.kernel.org\n> More majordomo info at http://vger.kernel.org/majordomo-info.html\n\n\nSlightly off-topic for this list. Apologies to those offended.\n\nWould a filesystem that allows sharing of blocks between inodes\nbe useful here? Each block would need a reference count (refco).\nWriting a block would be impossible once refco > 1. If someone\nattempts to write to such a block, a new block is allocated for\nthat particular inode and the refco of the original is decreased.\n\nNext to this there would have to be a clone_file() function:\n clone_file(src-file, dst-file, mode)\n\nThis function would create file dst-file with a new inode that\nreferences the blocks belonging to src-file (increasing the\nblocks' reference counts). The owner/group of dst-file are the\ncaller, not the owner of src-file.\n\nThings to check for are:\n - read permissions for src-file\n - write permissions for dst-file\n - are src-file and dst-file in the same filesystem (if not,\n one could implement copy)\n - ...?\n\n\nSuppose I have a file foo:\n\n foo -> inode1(blk1[1], blk2[1], blk3[1], blk4[1])\n\nThe [n] value on the blocks is the reference count.\nI now call clone_file(\"foo\", \"bar\", 0644):\n\n foo -> inode1(blk1[2], blk2[2], blk3[2], blk4[2])\n bar -> inode2(blk1[2], blk2[2], blk3[2], blk4[2])\n\nNext I modify blk2 of bar (write):\n\n foo -> inode1(blk1[2], blk2[1], blk3[2], blk4[2])\n bar -> inode2(blk1[2], blk5[1], blk3[2], blk4[2])\n\n\nI see the following uses:\n\n- Checking out a tree of (uncompressed) files with git could be\n done using the clone_file() call on each file. This means no\n extra disk space is used unless files are edited later.\n\n- Easy way to freeze files for backups. A database (mysql, ...)\n could bring its files into an acceptable state, call clone_file()\n on them and proceed with its work.\n\n- It could be used to protect user files from external tampering.\n Someone mentioned the problems with malware killing his files.\n The impact of this could be reduced by having a script that did\n a clone_file() on everything as root periodically. If files are\n deleted, root would have a backup.\n\n\nNotes:\n\n- Small changes to files would probably cause all the blocks to\n be copied as programs (editors) usually write out the complete\n file.\n\n- I don't know anything about implementing filesystems so all of\n the above could be complete nonsense.\n\n- The idea isn't mine, I've come across this before under the name\n of 'snapshot filesystems' and I think it was patented. I've never\n heard of anyone doing this for individual files though.\n\nWout\n"}]}