multi item packed files

Hello,

There have been a few threads on making git more space efficient, and eventually someone mentions tiny files and space fragmentation. Now that git object names are decoupled from their compression, it's easier to consider a a variety of compression algorithms. I whipped up a really silly "pack files together" compression.

This would maintain the write once semantics but allow a simple mechanism where objects are combined together. Choosing which objects to combine is easy, things put together into update-cache go together. This gives us more space efficiency and no seeks when reading that packed file off disk.

A natural extension to this is to make update-cache --commit-tree, which includes the files produced by write-tree and commit-tree into the same packed file. (I haven't coded this).

The layout works like this:

1) a new object type "packed" is added.
2) new objects are buffered into a packed object, until it gets to around 32k in size. This is complete arbitrary but felt about right.
3) The packed object is writting to git storage and then hard links are made to the packed object from the sha1 filename of each object inside.
4) read_sha1_file is changed to recognize the packed object and search inside.

I did a simple test on the 2.6.11 tree with my 100 patches applied. Without packing, .git is 99MB. With packing it only needs 62MB:

read speeds don't suffer with this, time to read-tree ; checkout-cache -a -f from a cold cache were the same. I could get the times lower with the patch by caching the uncompressed data, since in theory I should be faster here.

Using this on data you care about would be a really bad idea right now. I'm only posting the patch to get the basic idea across for benchmarking and discussion.

-chris

diff -ur linus.back/cache.h linus/cache.h
@@ -109,7 +109,7 @@
 
 /* Read and unpack a sha1 file into memory, write memory to a sha1 file */
 extern void * map_sha1_file(const unsigned char *sha1, unsigned long *size);
-extern void * unpack_sha1_file(void *map, unsigned long mapsize, char *type, unsigned long *size);
+extern void * unpack_sha1_file(const unsigned char *sha1, void *map, unsigned long mapsize, char *type, unsigned long *size);
 extern void * read_sha1_file(const unsigned char *sha1, char *type, unsigned long *size);
 extern int write_sha1_file(char *buf, unsigned len, unsigned char *return_sha1);
 extern int check_sha1_signature(unsigned char *sha1, void *buf, unsigned long size, const char *type);

@@ -117,6 +117,10 @@
 /* Convert to/from hex/sha1 representation */
 extern int get_sha1_hex(const char *hex, unsigned char *sha1);
 extern char *sha1_to_hex(const unsigned char *sha1);	/* static buffer result! */
+extern int pack_sha1_buffer(void *buf, unsigned long buf_len, 
+		     unsigned char *returnsha1, char **dest, 
+		     unsigned long *dest_size);
+int write_packed_buffer(void *buf, unsigned long len);
 
 /* General helper functions */
 extern void usage(const char *err);

diff -ur linus.back/cat-file.c linus/cat-file.c
@@ -23,7 +23,7 @@
 		type[size] = '\n';
 		size++;
 	} else if (strcmp(type, argv[1])) {
-		die("cat-file %s: bad tag", argv[2]);
+		die("cat-file %s: bad tag (%s: %s)", argv[2], type, argv[1]);
 	}
 
 	while (size > 0) {

diff -ur linus.back/fsck-cache.c linus/fsck-cache.c
@@ -85,7 +85,7 @@
 		if (map) {
 			char type[100];
 			unsigned long size;
-			void *buffer = unpack_sha1_file(map, mapsize, type, &size);
+			void *buffer = unpack_sha1_file(sha1, map, mapsize, type, &size);
 			if (!buffer)
 				return -1;
 			if (check_sha1_signature(sha1, buffer, size, type) < 0)

Careful.

This is something that needs history to tell whether it's effective. In particular, if one file changes and another one does not, your packed archive now ends up being a new blob, so while you "saved space" by having just one blob for the object, in reality you didn't save any space at all because with the <x> files changing, you just guaranteed that the packed blob changes <x> times more often.

See? Your "packing in space" ends up also resulting in "packing in time", and you didn't actually win anything.

(If you did a good job of packing, you hopefully didn't _lose_ anything either - you needed 1:<x> number of objects that took 1:<x> the space if the packing ended up perfect - but since you needed <x> times more of these objects unless they all change together, you end up with exactly the same space usage).

So the argument is: you can't lose with the method, and you _can_ win. Right?

Wrong. You most definitely _can_ lose: you end up having to optimize for one particular filesystem blocking size, and you'll lose on any other filesystem. And you'll lose on the special filesystem of "network traffic", which is byte-granular.

I don't want to pee on peoples parades, and I'm all for gathering numbers, but the thing is, the current git isn't actually all that bad, and I guarantee that it's hard to make it better without using delta representation. And the current thing is really really simple.

Linus

The packed blob lives in git but never makes it into a tree. Lets say that I have a packed blob with files "a, b, c", and another packed blob with files "x, y, z". Someone changes files, b and z and then runs update-cache b z.

Now we have 2 unchanged packed blobs: "a, b, c", "x, y, z", and one new packed blob: "b_new, z_new". This means that in order for the packing to help, we have to change more then one file at a time. That's why it would be good to have update-cache include the write-tree and commit-tree.

The patch does have one extra directory entry (for the packed blob), but from a network point of view roughly the same number of bytes should be copied. The hardlinks won't play nice with rsync though, soft links might be better.

packing isn't just about filesystem block sizes, it's about locality. All the hashing means pretty much every access in git is random. With packing we can at least try to put a single changeset together on disk. Right now it doesn't matter much, but when the git tree is 6GB in two years we'll feel the pain.

Grin, if I thought you wanted the patch I might have tried to pretty it up a little. The point is that all the discussions about ways to make git use less space end up stuck in "but wait, that'll make a bunch of tiny files and filesystems aren't good at that". So I believe some kind of packing is a required building block for any kind of delta storage.

-chris

If someone needs better on-disk ratio, (s)he can go with 1 KB filesystem or something like that, without all the added complexity of packing.

If we want to optimize that further, I would try doing it at the underlying filesystem level. For example, loop-mounted one.

Krzysztof Halasa

Shrug, we shouldn't need help from the kernel for something like this. git as a database hits worst case scenarios for almost every FS.

We've got:

1) subdirectories with lots of files
2) wasted space for tiny files
3) files that are likely to be accessed together spread across the whole disk

One compromise for SCM use would be one packed file per commit, with an index that lets us quickly figure out which commit has a particular version of a given file. My hack gets something close to that (broken into 32k chunks for no good reason), and the index to find a given file is just the git directory tree.

But my code does hide the fact that we're packing things from most of the git interfaces. So I can almost keep a straight face while claiming to be true to the original git design...almost. The whole setup is far from perfect, but it is one option for addressing points 2 & 3 above.

-chris

I really disagree.

On the other hand, git does a lot of things that are just _lovely_ for a filesystem:

- it never rewrites a file. Rewriting a file is unquestionably _the_ single worst access pattern for any filesystem. In contrast, never writing to a file again means that filesystems can optimize their layout and that things like defragmentation actually works.

- it caches beautifully, and efficiently. Part of it comes from never modifying files after they are written (which means that any network filesystem automatically breathes a huge sign of relief), but part of it is that it always reads full files, and the layout is done so that it really actually _uses_ everything it reads.

It also caches beautifully on a memory subsystem level, largely for the same reasons.

- it doesn't use tons of directories.

You say that "subdirectories with lots of files" is painful, but that's not really the whole story. A _deep_ directory structure tends to actually be worse in many ways, because it's much easier to optimize a flat directory structure than a deep one. In other words, git ends up making name hashing etc _productive_.

So yes, it's a bit wasteful. But it's wasteful of what is absolutely the cheapest resource around: disk space. It's not a huge downside, and in fact I really do believe that the biggest downside _by_far_ in diskspace utilization is the _seek_ costs, not the space itself. Let's face it, anybody who wants three years of kernel archives and thinks that 3GB of disk is too much, has some serious problems.

The _seek_ issue is real, but git actually has a very nice architecture even there: not only dos it cache really really well (and you can do a simple "ls-tree $(cat .git/HEAD)" and populate the case from the results), but the low level of indirection in a git archive means that it's almost totally prefetchable with near-perfect access patterns.

In seeking, the real cost is synchronization, and the git model actually means that there are very few seeks that have to be synchronized. You could literally do the "ls-tree" thing and make an absolutely trivial prefetcher that did the prefetching with enough parallellism that the filesystem could probably get decent IO performance out of a disk.

In other words, we really could have a "git prefetch" command that would populate the cache of the current head quite efficiently. Because the data layout supports that.

Linus

[ ... ]

We somewhat agree on most of this, I snipped out the parts that aren't worth nitpicking over. git is really fast right now, and I'm all for throwing drive space at things to solve problems. I just don't think we have to throw as much space at it as we are.

We can sort by the files before reading them in, but even if we order things perfectly, we're spreading the io out too much across the drive. It works right now because the git archive is relatively dense. At a few hundred MB when we order things properly the drive head isn't moving that much.

At 3-6 GB this hurts more. The data gets farther apart as things age, and drive performance rots away. I'll never convince you without numbers, which means I'll have to wait for the full load of old history and try it out ;)

-chris

No we don't.

It's easy to just copy the repository in a way where this just isn't true:
you sort the objects by how far they are from the current HEAD, and you just copy the repository in that order ("furthest" objects first - commits last).

That's what I meant by defragmentation - you can actually do this on your own, even if your filesystem doesn't support it.

Do it twice a year, and I pretty much guarantee that your performance will stay pretty constant over time. The one exception is fsck, which doesn't seek in "history order".

And this works exactly because:
- we don't do no steenking delta's, and don't have deep "chains" of data to follow. The longest chain we ever have is just a few deep, and it's trivial to just encourage the filesystem to have recent things together.
- we have an append-only mentality.

In fact, it works for exactly the same reason that makes us able to drop old history if we want to. We essentially "drop" the history to another part of the disk.

Linus

This certainly can help. Based on some ideas from andrea I made a poor man's defrag script last year that was similar. It worked by copying files into a flat dir in the order you expected to read them in, deleting the original, then hard linking them into their original name.

Copying in order straight into a new git tree doesn't help much when the filesystem is using the subdirectory as a hint to block allocation. So you'll probably have to copy them all into a flat directory and then hard link back into the git tree (the flat dir can then be deleted of course).

The problem I see for git is that once you have enough data, it should degrade over and over again somewhat quickly. My own guess is that you'll need to run the script at least monthly. If we're designing the thing now and say 'wow, that's going to be really slow without help', it doesn't hurt to look at alternatives.

I grabbed Ingo's tarball of 28,000 patches since 2.4.0 and applied them all into git on ext3 (htree). It only took ~2.5 hrs to apply. I did use my write-tree patch where you had to give write-tree a list of directories to search, but I don't think this helped much since the operation was mostly disk write bound.

Anyway, I ended up with a 2.6GB .git directory. Then I:

rm .git/index
umount ; mount again
time read-tree tree-id (24.45s)
time checkout-cache --prefix=../checkout/ -a -f (4m30s)

--prefix is neat ;)

The tree that ended up in checkout was 239456k, giving us an effective io rate for checkout-cache of 885k/s. (this drive gets 24MB/s sequential reads).

I'll have numbers for the packed files later on today. No, I don't really expect the numbers will convince you to implement some kind of packing ;) But it's still a good data point to have, and generating them here is just poking the box every 2 hours or so.

-chris

I really doubt that.

There's a more or less constant amount of new data added all the time: the number of changes does _not_ grow with history. The number of changes grows with the amount of changes going on in the tree, and while that isn't exactly constant, it definitely is not something that grows very fast.

Btw, this is how git is able to be so fast in the first place. Git is fast because it knows that the "size of the change" is a lot smaller than the "size of the repository", so it fundamentally at all points tries to make sure that it only ever bothers with stuff that has changed.

Stuff that hasn't changed, it ignores very _very_ efficiently.

That's really the whole point of the index file: it's a way to quickly ignore the stuff that hasn't changed - both for simple operations like "show-diff", but also for complex operations like "merge these three trees".

And it works exactly because the number of changes does _not_ grow at all linearly with the history of the project. In fact, in most projects, the rate of change does _down_ when the project grows, because the projects matures and generally gets more complicated and thus harder to change.

(The kernel _really_ is pretty special. I am willing to bet that there are not a lot of big projects that have been able to continue to take changes at the kind of pace that the kernel does. But we've had to work at it a lot, including obviously using SCM tools that are very much geared towards scaling. Why do you think the kernel puts more pressure on SCM's than other projects? It's exactly because we're trying to scale our change acceptance to bigger numbers).

So when you say "once you have enough data, it will degrade quickly" ignores the fact that the rate of change isn't (the "second derivative of the size of the project in time") really isn't that high.

Ok, I'd actually wish it took even less, but that's still a pretty impressive average of three patches a second.

That sounds pretty acceptable. Four minutes is a long time, but I assume that the whole point of the exercise was to try to test worst-case behaviour. We can certainly make sure that real usage gets lower numbers than that (in particular, my "real usage" ends up being 100% in the disk cache ;)

Linus

it's the distance between them. The amount of new data is constant, but the speed of accessing the new data is affected by the bulk of old data on disk.

Even with defragging you hopefully end up with a big chunk of the disk where everything is in order. Then you add a new file and it goes either somewhere behind that big chunk or in front of it. The next new file might go somewhere behind or in front etc etc. Having a big chunk just means the new files are likely to be farther apart making reads of the new data very seeky.

git as a write engine is very fast, and we definitely write more then we read.

Yeah, and this was a relatively old machine with slowish drives. One run to apply into my packed tree is finished and only took 2 hours. But, I had 'tuned' it to make bigger packed files, and the end result is 2MB compressed
objects. Great for compression rate, but my dumb format doesn't hold up
well for reading it back.

If I pack every 64k (uncompressed), the checkout-tree time goes down to 3m14s. That's a very big difference considering how stupid my code is .git was only 20% smaller with 64k chunks. I should be able to do better...I'll do one more run.

I had a tree with 28,000 patches. If we pretend that one bk changeset will equal one git changeset, we'd have 64,000 patches (57k without empty mergesets), and it probably wouldn't fit into ram anymore ;) Our bk cset rate was about 24k/year, so we'll have to trim very aggressively to have reasonable performance.

For a working tree that's fine, but we need some fast central place to pull the working .git trees from, and we're really going to feel the random io there.

-chris

This run also packed tree files together (everything produced by write-tree went into a packed file), but not the commits. I estimate I could save about another 168m by packing the tree files and commits into the same file with the blobs, but this wouldn't make any of the times below faster.

git - original (28k commits) packed
FS size 2,675,408k 1,723,820k
read-tree 24.45s 18.9s
checkout-cache 4m30s 3m5s
patch time 2h30m 1h55m

The format for the packed files could be smarter, such that it didn't require decompressing the whole packed file to read one item. I would guess I could get another 20% checkout-cache performance out of it via more tuning, and probably another 10% of space savings.

Of course, none of this is likely to convince you ;) If you decide later on it's worthwhile, I don't think it would be difficult to add then.

-chris

It was a rainy weekend, so I took a break from lawn care and hacked in some simple changes to the packed file format. There's now a header listing the sha1 for each subfile and the offset where to find it in the main file. Each subfile is compressed individually so you don't have to decompress the whole packed file to find one. commits were added into the packed files as well.

Some results were about what I expected:

FS size -- 1,614,376k
read-tree -- 18s
checkout-cache -- 2m35s (cold cache)
checkout-cache -- 18s (hot cache)
patch time -- 96m

vanilla git needs 56s to checkout with a hot cache. The hot cache numbers weren't done before because I hadn't expected my patch to help at all. Even though we both do things entirely from cache, vanilla git is much slower at writing the checked out files back to the drive. I've made no optimizations to that code, and the drive is only 30% full, so this seems to just be a bad interaction with filesystem layout.

I also expected vanilla git to perform pretty well when there were no commits in the tree. My test was to put a copy of 2.6.11 under git.
vanilla packed
update-cache (for all files) 2m1s 48s
checkout-cache (cold) 1m23s 28s
checkout-cache (hot) 12s 15s

The difference in hot cache checkout time is userland cpu time. It could be avoided with smarter caching of the packed file header. Right now I'm decompressing it over and over again for each checkout. Still, the performance hit is pretty small because I try to limit the number of subfiles that get packed together.

My current patch is attached for reference, it's against a git from late last week. I wouldn't suggest using this for anything other than benchmarking, and since I don't think I can get much better numbers easily, I'll stop playing around with this for a while.

-chris

diff -ur linus.back/cache.h linus/cache.h
@@ -64,6 +64,16 @@
 	char name[0];
 };
 
+struct packed_item {
+	/* lenght of compressed data */
+	unsigned long len;
+	struct packed_item *next;
+	/* sha1 of uncompressed data */
+	char sha1[20];
+	/* compressed data */
+	char *data;
+};
+
 #define CE_NAMEMASK  (0x0fff)
 #define CE_STAGEMASK (0x3000)
 #define CE_STAGESHIFT 12

@@ -117,7 +127,7 @@
 
 /* Read and unpack a sha1 file into memory, write memory to a sha1 file */
 extern void * map_sha1_file(const unsigned char *sha1, unsigned long *size);
-extern void * unpack_sha1_file(void *map, unsigned long mapsize, char *type, unsigned long *size);
+extern void * unpack_sha1_file(const unsigned char *sha1, void *map, unsigned long mapsize, char *type, unsigned long *size);
 extern void * read_sha1_file(const unsigned char *sha1, char *type, unsigned long *size);
 extern int write_sha1_file(char *buf, unsigned len, unsigned char *return_sha1);
 extern int check_sha1_signature(unsigned char *sha1, void *buf, unsigned long size, const char *type);

@@ -125,6 +135,9 @@
 /* Convert to/from hex/sha1 representation */
 extern int get_sha1_hex(const char *hex, unsigned char *sha1);
 extern char *sha1_to_hex(const unsigned char *sha1);	/* static buffer result! */
+extern int pack_sha1_buffer(void *buf, unsigned long buf_len, 
+                            unsigned char *returnsha1, struct packed_item **);
+int write_packed_buffer(struct packed_item *head);
 
 /* General helper functions */
 extern void usage(const char *err);

@@ -137,4 +150,9 @@
 						unsigned long *size,
 						unsigned char *tree_sha1_ret);
 
+extern int write_tree(struct cache_entry **cachep, int maxentries, const char *base, int baselen, unsigned char *returnsha1, struct packed_item **head);
+
+#define MAXPARENT 16
+extern int commit_tree(char *tree_sha1_hex, unsigned char parent_sha1[MAXPARENT][20], int num_parents, struct packed_item **head);
+extern void check_valid_sha1_file(unsigned char *sha1, const char *expect);
 #endif /* CACHE_H */

diff -ur linus.back/fsck-cache.c linus/fsck-cache.c
@@ -85,7 +85,7 @@
 		if (map) {
 			char type[100];
 			unsigned long size;
-			void *buffer = unpack_sha1_file(map, mapsize, type, &size);
+			void *buffer = unpack_sha1_file(sha1, map, mapsize, type, &size);
 			if (!buffer)
 				return -1;
 			if (check_sha1_signature(sha1, buffer, size, type) < 0)

diff -ur linus.back/Makefile linus/Makefile
@@ -23,7 +23,7 @@
 install: $(PROG)
 	install $(PROG) $(HOME)/bin/
 
-LIB_OBJS=read-cache.o sha1_file.o usage.o object.o commit.o tree.o blob.o
+LIB_OBJS=read-cache.o sha1_file.o usage.o object.o commit.o tree.o blob.o lib-tree.o
 LIB_FILE=libgit.a
 LIB_H=cache.h object.h
 

@@ -71,6 +71,7 @@
 show-diff.o: $(LIB_H)
 show-files.o: $(LIB_H)
 tree.o: $(LIB_H)
+lib-tree.o: $(LIB_H)
 update-cache.o: $(LIB_H)
 usage.o: $(LIB_H)
 unpack-file.o: $(LIB_H)

Not sure.

Correct. But git doesn't search dirs so it's not that bad.

... depends on block size. With 2 KB:

defiant:~$ du -s /pub/mirror/linux-2.6.git
88366   /pub/mirror/linux-2.6.git
defiant:~$ du -s --apparent-size /pub/mirror/linux-2.6.git
63400   /pub/mirror/linux-2.6.git

Not bad, is it?

... across the whole filesystem.

Well, probably it isn't best to have git and .iso archives on the same filesystem.

Krzysztof Halasa

I really think the argument that "you can use filesystem feature XYZ" is bogus.

I know that I'm not willing to switch filesystems on a whim. I suspect nobody else is either. I'm not going to create a loopback filesystem just for git, it's just too much pain.

And dammit, if I'm the original author and likely biggest power-user, and _I_ can't be bothered to use special filesystems, then who can? Nobody.

This is why I absolutely do not believe in arguments like "if your filesystem doesn't do tail packing, you shouldn't use it" or "if your don't have name hashing enabled in your filesystem it's broken".

I'm perfectly willing to optimize for the common case, but that's as far as it goes. I do not want to make fundamental design decisions that depend on the target filesystem having some particular feature.

(I'll happily make decisions that say that the target _OS_ has to have a particular feature, though. I'll require a sane base-level for functionality, but not something like filesystem details).

Linus

If someone is motivated enough, and if the task is quite trivial (as it seems to be) someone may try it. I can see nothing wrong with it as long as it doesn't affect other people.

Of course. But one may consider using a filesystem with, say, different settings. Or a special filesystem for this task, such as CNFS used by news servers (it seems news servers do quite the same what git does, except they also purge old contents, i.e., container files don't grow up).

The optimization would be (in) the underlying filesystem (i.e., the OS thing, or possibly a shared preloaded library?), not git itself.

Krzysztof Halasa

and nttp would give a nice transfer method for git objects...

Martin

One night, when little Giana from Milano was fast asleep,
she had a strange dream.