Re: kernel.org and GIT tree rebuilding

On Fri, 24 Jun 2005, Linus Torvalds wrote:

Ok, here's how it works.

 - Pick a starting commit (or a hundred)

 - Pick an ending commit (or a hundred)

 - generate the list of objects in between them

	git-rev-list --object end ^start > object-list

 - Pack that list of objects into an "object pack":

	git-pack-objects out < object-list

   (This actually generates two files: "out.idx" is the index file, 
   "out.pack" is the data file, but I'll make it concatenate the two at 
   some point)

 - move the pack-files over somewhere else

 - unpack them

	git-unpack-objects out

and you're done.

Now, the reason I use "pack" and "unpack" instead of just "tar" to transport the objects is that this allows me to do a fairly efficient packing. I wanted these pack-files to be independent (ie they do _not_ depend on any objects outside of the pack-file), but within the objects described in the pack I cna do delta-compression.

Now, that doesn't much help for small updates (where the objects are just unrelated and have no deltas), but it helps increasingly for big ones. The biggest one obviously being the whole path from the start to the HEAD..

For example, the "du -sh .git/objects" for the git project itself is 17MB for me, and I can do:

	torvalds@ppc970:~/git> du -sh .git/objects 
	17M     .git/objects

	torvalds@ppc970:~/git> time git-rev-list --objects HEAD | git-pack-objects out
	Packing 3656 objects

	real    0m3.779s
	user    0m3.169s
	sys     0m0.602s

	torvalds@ppc970:~/git> ls -lh out.*
	-rw-rw-r--  1 torvalds torvalds  87K Jun 26 09:12 out.idx
	-rw-rw-r--  1 torvalds torvalds 2.0M Jun 26 09:12 out.pack

ie it packs down to a nice 2MB pack-file with a small index. Move that over to somewhere else, and unpack it, and you'll get all the regular objects (it doesn't move tags and refs over, you'll have to do that outside of the packing).

Now, you can trade off some packing time to get a better pack:

	torvalds@ppc970:~/git> time git-rev-list --objects HEAD | git-pack-objects --window=100 out
	Packing 3656 objects
	
	real    0m11.953s
	user    0m11.294s
	sys     0m0.663s

	torvalds@ppc970:~/git> ls -lh out.*
	-rw-rw-r--  1 torvalds torvalds  87K Jun 26 09:14 out.idx
	-rw-rw-r--  1 torvalds torvalds 1.6M Jun 26 09:14 out.pack

and if you want to allow deep delta chains (the default delta depth limiting is 10), you can get even better results:

	torvalds@ppc970:~/git> time git-rev-list --objects HEAD | git-pack-objects --window=100 --depth=100 out
	Packing 3656 objects
	
	real    0m12.374s
	user    0m11.704s
	sys     0m0.659s

	torvalds@ppc970:~/git> ls -lh out.*
	-rw-rw-r--  1 torvalds torvalds  87K Jun 26 09:16 out.idx
	-rw-rw-r--  1 torvalds torvalds 1.3M Jun 26 09:16 out.pack

but then unpacking will slightly heavier.

(Doing the same for the kernel is obviously much more expensive just because the kernel is so much bigger. A big delta discovery window like 100 takes about fifteen minutes to pack on my machine, but gets the current kernel archive down to 70MB or so. That's ok for a monthly "pack all the objects" to keep size requirements down, but you clearly don't want to do this all the time ;).

Now, perhaps the more interesting part is that I also designed the pack format so that it should be a good "history" format, not just a way to move objects from one place to the other. Ie if you worry about diskspace, you can pack everything up to the now into one big pack, and then remove the original objects.

Don't do that yet, btw - I haven't actually written the code to read stuff out of packs if we don't find it in the object directory yet, but the layout is such that it should be straightforward and pretty efficient (but there a deep delta chain obviously _will_ cause a performance hit).

I actually like this approach better than having delta-objects in the filesystem. Partly because the pack-file is self-contained, partly because it also solves the fs blocking issue, yet is still efficient to look up the results without having hardlinks etc to duplicate objects virtually. And when you do the packing by hand as an "archival" mechanism, it also doesn't have any of the downsides that Chris' packing approach had.

Nico? Chris? Interested in giving it a look? It's kind of a combination of your things, generalized and then made to have fast lookup with the index.

Fast lookup doesn't matter for a normal unpack, of course, and if I just always wanted to unpack all the objects (ie just an object transfer mechanism) I'd have made the index be a toposort of the objects. But because I wanted to be able to use it as an archival format, I needed it to be "random-access" by object name. So the index is in fact a binary tree (well, sorted array, so the lookup degenerates into a binary search) with a top-level index splitting up the contents based on the first byte (the same way the filesystem layout does).

		Linus