Re: A look at some alternative PACK file encodings

An alternative would be to create a small "placeholder" object that just gives an ID, then refer to it by offset.

That would avoid the need for an id/offset bit with every offset, and possibly save more space if the same object was referenced multiple times.

And it just seems simpler.

On 7 Sep 2006 05:07:56 -0400, linux@horizon.com <linux@horizon.com> wrote:

There are 2 million objects in the Mozilla pack. This table would take: 2M * (20b (sha) + 10b(object index/overhead) = 60MB This 60MB is pretty much incompressible and increases download time.

Much better if storage of the sha1s can be totally eliminated and replaced by something smaller. Alternatively this map could be stripped for transmission and rebuilt locally.

Um, I think I wasn't clear. Objects in a "thin" pack (for network updating of a different pack) that are referred to but not included would have stand-ins containing just the object ID. Objects that *are* present would simply be present and referred to by offset as usual.

Imagine you have a "thin" pack containing a delta to an object that the recipient has, so isn't in the pack. The delta has to specify the base object somehow. If the base object is in the pack, you can specify it by offset. If it's not, you can either:

- Generalize the base object pointer to allow an object ID option, or
- Provide a pointer to a magic kind of "external reference" pointer
  object.

I was proposing the latter.

For regular packs, such objects wouldn't even be present, because all base objects are in the pack itself.

And, of course, you'd only create such objects if you needed to, if there was at least one pointer to them.

Compared to putting the object ID directly in the pointer, it has
Cost:	An extra offset pointer and object header.
	Extra time follwoing the indirection resolving the pointer.
Benefit: Non-indirect object pointers are a bit smaller.
	The code is simpler.
	Second and later references to the same external object are
	another offset, not another 20 bytes.

On 7 Sep 2006 09:34:56 -0400, linux@horizon.com <linux@horizon.com> wrote:

Yes I missed the thin pack context. Has anyone tried building a thin pack? Having thin packs would address major concerns with the download time of the initial Mozilla checkout. Right now you have to download 450MB of data that 99% of the people are never going to look at.

Thin packs would also set an 'archival' bit as discussed earlier. The 'archival' bit tells the local tools to leave these packs alone. You don't want to accidentally trigger a 450MB down just because you did a git-repack. Of course git would need to developer error messages indicating that you asked for something in the archive that isn't present.

I'm not sure I would mix these external references in with other objects. Instead I would make a pair of packs, one only contains external reference stubs and is tiny. The second is the full version of the same data. That makes getting the old data easy, it just replaces the stub pack. The stub pack doesn't need to contain stubs for all the objects, only the ones referenced upstream.

I haven't tried doing this, does the current git code support having multiple pack files covering difference pieces of the project? Can we have an archive pack and a local current pack that get merged together?

Unfortunately, no, it wouldn't. There's a second misunderstanding here: thin packs are used by the git on-the-wire protocol to send a delta relative to an object *that you know the recipient already has*.

This can greatly speed up incremental updates. It does NOT have any effect on the initial checkout, because you know the recipient has nothing, so you have to send everything.

What you seem to be talking about is what people call a "shallow clone". Unfortunately, making a shallow clone is difficult for reasons that are deeply embedded in git's incremental update protocol.

When you fetch from a remote repository, it needs to figure out what you need and what you already have. The fundamental assumption which the protocol uses to send this efficiently is that if you have a commit object, you have all its ancestors, and their trees and blobs.

So you can say "I have 60d4684068ff1eec78f55b5888d0bd2d4cca1520" (which is the commit behind tags/v2.6.18-rc5 from the Linux kernel) and the server you're pulling from knows a lot about what you have.

The first hard part about a shallow repository is describing *efficiently* to git-upload-pack what you don't have.

The second is figuring out what you should get.

Suppose that you clone from a repository that has a linear chain of development, and you cut off everything before version X. Simple enough so far.

Then you try to pull from someone whose work branched off at version X-1. Do you want to fetch everything back to the common ancestor? If you want to cut off their branch, where do we cut it off? A simple timestamp limit? What if you get a bogus timestamp on a commit?

This has been considered by git developers quite carefully and is NOT an easy problem. A solution is welcomed, but if you come up with an easy one, please spend a few minutes considering the possibility that the reason it's so easy is that your solution is flawed.

There are also problems giving sensible error messages if you try to refer to a missing object and making your clone deeper if desired, but those are secondary to the big problems.

Huh?? This is flatly impossible, and completely defeats the purpose. This is one of those "Pray, Mr. Babbage, if you put into the machine wrong figures, will the right answers come out?" questions. I think there is a *serious* miscommunication here.

I have a delta-compressed object. It is stored in the pack as a series of changes to some base object. To be of any use, it needs to identify that base object. If the base object identification takes the form of an intra-pack offset (the new proposal) as opposed to a global 20-byte object ID, then the base object needs to be stored *intra-pack*. Within the same pack.

The whole idea is "hey, we don't allow delta-ing relative to objects not in the pack anyway, so why waste space storing such large pointers?"

This would make the currently forbidden case of a delta relative to an object not in the same pack completely impossible. It's like asking for the square root of 2 in roman numerals.

Yes, it supports it perfectly. A pack is just a bag of objects. There is zero required higher-level structure. In particular, you can have a "100% blobs" pack with no tree or commit objects at all.

Git uses the object relationships in its compression heuristics, but it has no effect on correctness.

The only thing is that the original pack was a *self-contained* bag of objects; every object in the pack could be reconstructed given only the pack itself. In particular, cross-pack deltas were forbidden.

However, then someone realized that making an exception for git protocol updates would be easy and a Really Good Thing. A pack that is missing one or more base objects is called a "thin pack".

So the rule I mentioned above has already been broken. Supporting that is what I'm talking about.

 <linux <at> horizon.com> writes:

It would actually be useful if this restriction were lifted.

Granted, for working repositories there's not much point, because 'git repack -a -d' can be run regularly these days.

But for repositories served by the dumb http:// transport it makes some sense. You don't want to run 'repack -a -d' on those, because anybody tracking them ends up having to download the entire history again every time they pull. But if you pack too often, you incur the cost of the packs containing lots of base objects - it's as though the delta chain lengths can only ever be about 1 or 2.

If the packs were thin, regular pullers would already have the base objects, and occasional pullers would just have to download more of the intervening (thin) packs to get the missing deltas in the middle of the chains. (I think everyone has to download all the .idx files in any case.)

Richard Curnow <rc@rc0.org.uk> writes:

The primary reason why we require the base object to be present in the same pack is because our assumption has always been we mmap a pack as a whole, and we assumed that we can make sure that the address space of a process to be enough to mmap at least one pack (otherwise the user will be given a way to keep size of each pack down to a size that is a mmapable piece) but not necessarily more than one. In other words, while unpacking one object that is deltified, we wanted to make sure everything that is necessary is availble in memory. Otherwise, when multiple packs are needed to reconstitute a single object because the object is a delta in one pack and its base is in the other pack, we might not be able to mmap both of them into the address space at the same time.

The "mmap only parts of a huge packfile into map windows" update Shawn Pearce is working on would lift that worry, so it would be less of a reason.

Having said that, people must realize that keeping thin packs on disk, indexed, is a major undertaking. It can be made to work, but it will be painful.

People can grab a thin pack via rsync or http without realizing it is thin, try to use it and then later (possibly much later, when a delta that is against a missing object happens to be needed) discover some of the pack data is unusable. To avoid this, the dumb transports need to walk the ancestry chains of commits and their associated objects while fetching as they do right now, but also need to walk the delta chains to make sure their base objects are available.

I like the proposal by Linus to have stub objects that records what the missing base object is in the thin pack stream. It simplifies things for the offset representation of bases. But if we were to do so, I suspect indexing such a thing would need more surgery to the .idx format. The question is if we should record the stub object in the .idx file.

Right now we record the beginning of data for each object (either base or delta) without storing anything to say about where it ends -- the pack is assumed to be dense, so the point where next object begins should be where the current one ends. This means that we need to build a reverse index to list the objects in the pack in offset order, when we want to find the end of each object efficiently.

We work this around when using a pack by not doing the full verification. We start decoding the header from the beginning and in either base or delta the deflated stream sits at the end. We inflate that deflated stream until zlib says it got enough, and we do not check if that "enough" point stepped into the location that is supposed to be inside the "next" object (if it did so then it is an error in the packfile we missed to detect). If things inflate well and delta applies cleanly, we are happy.

But pack-objects, when reusing the data from an existing pack, wants to be careful, so it _does_ build a reverse index itself and makes sure that inflate() ends at the location we expect it to. For that process to remain the correct way to determine where each object ends, the .idx file must record the presense of stub objects.

However, if we write the names of stub objects in the .idx file, we have another problem. Currently, the existence of an object name in the .idx means that such an object exists in the corresponding .pack; this will not hold true anymore.

So if we were to do this, we need to give one extra bit to each of the .idx entries to mark which ones are stub and which ones are not. This would allow the reverse index to properly notice where each object ends, and allow the dumb transports to walk the .idx for missing base objects efficiently. The code that looks at .idx at runtime to determine which pack has needed object needs to notice this bit.

Again, all of this can be made to work, but it will be painful.

Jon Smirl wrote:

You've lost me. What are you attempting to do again?

On Thu, 7 Sep 2006, linux@horizon.com wrote:

Well... I'm using object type 6 for deltas with offset reference (instead of object type 7 that is delta with sha1 reference). So there is no extra bit needed and no backward compatibility breakage.

There could be of course a new object type which payload is only a sha1 that deltas type 6 reference. But that can be introduced at a later date if it turns out to be worthwhile (i.e. the actual saving in real use scenarios is worth the (small but still) added complexity).

Well I would not say so. Simply prefixing a delta with the sha1 of its base object cannot be simpler when streaming out a pack.

Nicolas

Ah, my apologies! I didn't realize that you weren't constructing a whole new pack format, or using a global flag. In this case, the overhead is already bought and paid for, so there's no point to not taking advantage of it.

And thin packs should Just Work, once the builder is taught to use type 7 objects when necessary.

In this case, it's only of potential benefit if there is more than one reference to an object, and figuring it out is almost certainly more trouble than it's worth. Deltas usually form long skinny chains, not high branching factor bushes.