Created attachment 256039 [details] [review]
repo: Add ostree.sizes metadata on commit containing archived and unpacked size

This in-band metadata key will allow UI like 'ostree pull' as well as
higher level programs to accurately compute the bandwidth cost to
download a particular commit.

That all looks ok to me, I'll grab the patch and test it out here shortly.

Ok, I've taken your attachment here, and rebased vivek's other commits on top of it, on my sizes branch here: http://cgit.collabora.com/git/user/jwhiting/ostree.git/log/?h=sizes

Take a look and try it when you get a moment.

One concern I had about this was the size of the additional metadata.  Here's some real world statistics from gnome-continuous, generated from the quick attached C program.

For just the latest commit:

$ ./objstats ~ostree/ostbuild/work/repo/ gnome-continuous/buildmaster/x86_64-devel-debug 0
63606 objects in 1 commits
4396 metadata objects occupying 3754480 bytes
59210 content objects occupying 810502589 bytes
0.004632 metadata overhead
$

(Numbers are quite similar for -runtime)

For the history since it was renamed to continuous:

$ ./objstats ~ostree/ostbuild/work/repo/ gnome-continuous/buildmaster/x86_64-devel-debug -1
139310 objects in 1500 commits
41755 metadata objects occupying 239146435 bytes
97555 content objects occupying 6770878349 bytes
0.035320 metadata overhead
$

So the total size of metadata relative to content is 3%, which seems quite acceptable.  

Now, let's consider the sizes metadata as it exists now:

sizes size = ~63606*(32+8+8) = 3053088 bytes

Where 32 is a checksum length, 8 bytes for guint64 compressed/uncompressed.  Notice that's an increase of ** 81% ** in the metadata size per commit.

Total for all 1500 commits, that's over 4 gigabytes.  Taken over all ~7000 commits since I've been running Continuous, that's 21GB.  Not a trivial increase, and well worth considering optimizations.

One obvious thing; we could use varints for sizes.  We could fit a lot of dirtree objects sizes in one byte, and from what I can tell almost all of them in two bytes.  That could save us 70% of the overhead.

And in fact since metadata is stored uncompressed, we only need one size byte for it.  That shrinks it to 68%.  But clearly most of the space here is from the sheer object count.

Most of the metadata objects are *tiny* - they're smaller than the HTTP request to retrieve them I'm sure.  We could omit entries for ones smaller than say 512 bytes, and just default to that in the pull request.  That'd involve some loss of precision; would anyone care?

Yet another approach here is to use something like perfect hashing.  We don't need to ship a literal list of checksums - we only need to ship a mapping which can convert a checksum->size.  A perfect hash would be able to look at say the first 3 bytes, which could be able to uniquely identify the checksum in the set.

But bottom line: I'd like to consider these optimizations before landing sizes.  Alternatively, we could do a few basic optimizations, and have sizes be opt-in. I assume for many OS builders you're only shipping *major* upgrades to clients, and there you just don't care about the overhead.

Created attachment 256845 [details]
commit stats

Updated my branch again using your commit from the deltas branch to convert guint64 into a bytearray for storing in the metadata.

Some discussion on IRC; varints would save 10% of the space - which is worthwhile but not a solution on its own either.

Other stuff like perfect hashing would get very complex implementation wise, doesn't seem worth the engineering effort.

So current plan of record is to make ostree.sizes opt in.  Something like OstreeRepoCommitFlags and OSTREE_REPO_COMMIT_FLAG_GENERATE_SIZES ?

Created attachment 257033 [details]
updated commit stats program

Regarding:

    pull: Implement a metadata-only pull mode

This is really OSTREE_REPO_PULL_FLAGS_COMMIT_ONLY or something.  Dirtree/dirmeta are metadata too, but we're not pulling them.

Per mailing list discussion, I'd like to have this state *explicitly* represented in the repository somehow, rather than implicitly represented by the lack of .dirtree/.dirmeta.  (For one thing, we'll just blindly continue on *other* errors besides ENOENT too)   One idea: change the suffix in this case to .commit-thin or .commit-only or something.

Would prefer the followup commit:

    repo-pull: If we have metadata for a commit, another pull fetches the content

...to be squashed

Ok, added --generate-sizes option to ostree commit.
Squashed the two commits into one.
Changed PULL_FLAGS_METADATA to PULL_FLAGS_COMMIT_ONLY

I force pushed to my sizes branch. The .commit is still called .commit when pulling --commit-only though.

+gboolean _ostree_repo_commit_generate_sizes = FALSE;


Should avoid global variables; this isn't even marked static (although it won't be exported due to the symbol regexp).  This should instead be a regular gboolean in the repo struct.

I'll fix this up.

(In reply to comment #12)

> I'll fix this up.

Done.  I also fixed a few other things:

* We were storing each entry as (ayayay), but this loses a good bit of the benefit of varints, as GVariant is forced to store the length of each varint.  We need to instead do just one "ay".  I made it be (checksum[32], compressed, uncompressed).

Also the logic in ot-builtin-commit.c broke the test suite, because we were no longer creating an OstreeRepoCommitModifier for statoverrides.

I created a test-sizes.js which tests the sizes bits.

Pushed to master:

https://git.gnome.org/browse/ostree/commit/?id=f583c4ab0b42b96caf47e4c068394ca1771115c0

Thanks for fixing up that commit and merging it to master, but the pull stuff with the OSTREE_REPO_PULL_FLAGS_COMMIT_ONLY is what I need for the daemon branch rebasing. Is there a problem with the other commits on the sizes branch?

(In reply to comment #14)
> Thanks for fixing up that commit and merging it to master, but the pull stuff
> with the OSTREE_REPO_PULL_FLAGS_COMMIT_ONLY is what I need for the daemon
> branch rebasing. Is there a problem with the other commits on the sizes branch?

I found myself a little hung up on the bit of the COMMIT_ONLY flag that checked whether or not we had only the commit by trying to access the .dirmeta.

Sorry I was delaying here, just took a while to mull it over.  I ended up working on this:

https://git.gnome.org/browse/ostree/commit/?h=wip/thin-commits&id=574c82303fc29ffa4323987da00b62f969c579c1

Which is the ".committhin" idea I posted about on the list.  It's a bit invasive; we have to grow new API to read/write commits with a "gboolean is_thin_commit" flag.  But I think ultimately this is going to be a lot better.

I'd like to keep the invariant that if the commit exists, then everything else does.  Otherwise things start to get tricky in all of the other commands.

Sorry for the late reply..

(In reply to comment #4)
> One concern I had about this was the size of the additional metadata.  Here's
> some real world statistics from gnome-continuous, generated from the quick
> attached C program.
> 
> For just the latest commit:
> 
> $ ./objstats ~ostree/ostbuild/work/repo/
> gnome-continuous/buildmaster/x86_64-devel-debug 0
> 63606 objects in 1 commits
> 4396 metadata objects occupying 3754480 bytes
> 59210 content objects occupying 810502589 bytes
> 0.004632 metadata overhead
> $
> 
> (Numbers are quite similar for -runtime)
> 
> For the history since it was renamed to continuous:
> 
> $ ./objstats ~ostree/ostbuild/work/repo/
> gnome-continuous/buildmaster/x86_64-devel-debug -1
> 139310 objects in 1500 commits
> 41755 metadata objects occupying 239146435 bytes
> 97555 content objects occupying 6770878349 bytes
> 0.035320 metadata overhead
> $
> 
> So the total size of metadata relative to content is 3%, which seems quite
> acceptable.  
> 
> Now, let's consider the sizes metadata as it exists now:
> 
> sizes size = ~63606*(32+8+8) = 3053088 bytes
> 
> Where 32 is a checksum length, 8 bytes for guint64 compressed/uncompressed. 
> Notice that's an increase of ** 81% ** in the metadata size per commit.
> 
> Total for all 1500 commits, that's over 4 gigabytes.  Taken over all ~7000
> commits since I've been running Continuous, that's 21GB.  Not a trivial
> increase, and well worth considering optimizations.
> 
> One obvious thing; we could use varints for sizes.  We could fit a lot of
> dirtree objects sizes in one byte, and from what I can tell almost all of them
> in two bytes.  That could save us 70% of the overhead.
> 
> And in fact since metadata is stored uncompressed, we only need one size byte
> for it.  That shrinks it to 68%.  But clearly most of the space here is from
> the sheer object count.

That type of optimization address the per-commit overhead, but they don't address the duplication which causes the total repository size to blow up. Unlike the other meta-data objects, .sizes contains the global view of a commit so even if the difference between previous commits are small the size information is a complete duplicate.

Compare that to e.g. .dirtree  & .dirmeta objects which can be re-used over different commits as long as the data they represent doesn't change. Which prevents the total repository size blowing up due to meta-data when you do a lot of "small" changes as i suspect -continous does.

> Most of the metadata objects are *tiny* - they're smaller than the HTTP request
> to retrieve them I'm sure.  We could omit entries for ones smaller than say 512
> bytes, and just default to that in the pull request.  That'd involve some loss
> of precision; would anyone care?

That should work. 

> Yet another approach here is to use something like perfect hashing.  We don't
> need to ship a literal list of checksums - we only need to ship a mapping which
> can convert a checksum->size.  A perfect hash would be able to look at say the
> first 3 bytes, which could be able to uniquely identify the checksum in the
> set.

Sounds like a good way of compressing the hash indeed. We can also reduce the precision, e.g. report sizes in kilobytes instead of bytes, which means 32 bits will be enough to represent files up to 4T (that's enough for everyone right?).  Which already saves you 8 bytes for every entry.

Ideally we'd figure out a way of re-using the sizing information over commits though, similar to how dir{tree,meta}s tend to be re-used. That should prevent the general blow-up problem.  However it needs to be done in a way that prevents clients form doing a lot of http request to get all information together

> But bottom line: I'd like to consider these optimizations before landing sizes.
>  Alternatively, we could do a few basic optimizations, and have sizes be
> opt-in. I assume for many OS builders you're only shipping *major* upgrades to
> clients, and there you just don't care about the overhead.

That would work. Also we might more aggressively prune older updates then -continous does as the devices on the field do not really care about intermediate udpates they want to go from current to latest. So the repository size on the server is less important.

(In reply to comment #16)
>
> That would work. Also we might more aggressively prune older updates then
> -continous does as the devices on the field do not really care about
> intermediate udpates they want to go from current to latest. So the repository
> size on the server is less important.

The space on the server is important to me, but so is the size of a small upgrade.  

Now for the Continuous type use case I could just turn off the sizes metadata.

But as I mentioned before, after sitting on this for a while (and sorry about being slow there) I rather think that the use cases here of major upgrades are much better served by static deltas.

I'm not completely opposed to landing the sizes stuff - I know you guys did a lot of work on it, and I'm sorry to have not applied it.  But I'm hopeful that we can push the static deltas over the edge into a functional state and have a (what I believe to be) all around better system.

See https://bugzilla.gnome.org/show_bug.cgi?id=721799

(In reply to comment #17)
> (In reply to comment #16)
> >
> > That would work. Also we might more aggressively prune older updates then
> > -continous does as the devices on the field do not really care about
> > intermediate udpates they want to go from current to latest. So the repository
> > size on the server is less important.
> 
> The space on the server is important to me, but so is the size of a small
> upgrade.  

I meant for our use-case the space on the server is less of an issue per se as we can prune more aggressively then continous does which keeps all commits round. Size overhead for smaller upgrades does bother me as well though.

> Now for the Continuous type use case I could just turn off the sizes metadata.

Right, or having the sizes meta-data as a separate file as in our initial versions which means you can prune those from the archive for older revisions as well (or have the client decide to pick them up).

I've spent some time thinking how to get a good middle-ground between added meta-data size, repository bloating and minimizing http gets, but thusfar i've failed to come up with a great solution :(

> But as I mentioned before, after sitting on this for a while (and sorry about
> being slow there) I rather think that the use cases here of major upgrades are
> much better served by static deltas.

No worries, i've been failing to get back at this for a while as well ;).

> I'm not completely opposed to landing the sizes stuff - I know you guys did a
> lot of work on it, and I'm sorry to have not applied it.  But I'm hopeful that
> we can push the static deltas over the edge into a functional state and have a
> (what I believe to be) all around better system.

I think static deltas would be awesome to have, but they seem a bit orthogonal to me. I'm not at all tied to one particular implementation though, so if deltas do solve the issue in some way, great ;)

What the size meta-data gives us is the ability to tell the user exactly how much data will be download and used (on disk) going from any revision to the current revision. I'm unsure how a static delta would give you the same unless you have a way of ensuring you have deltas between all revisions (or at least deltas from any revisions to current HEAD)?  

> See https://bugzilla.gnome.org/show_bug.cgi?id=721799

(In reply to comment #18)
>
> I meant for our use-case the space on the server is less of an issue per se as
> we can prune more aggressively then continous does which keeps all commits
> round. Size overhead for smaller upgrades does bother me as well though.

Right.

> What the size meta-data gives us is the ability to tell the user exactly how
> much data will be download and used (on disk) going from any revision to the
> current revision. I'm unsure how a static delta would give you the same

The header definitely has both compressed and uncompressed (or more generally, "un-deltaed") size.

> unless
> you have a way of ensuring you have deltas between all revisions (or at least
> deltas from any revisions to current HEAD)?  

In the current model you can generate deltas between any revisions you want, after the fact.  Obviously this can start to use substantial disk space, particularly if you have multiple branches, as I do with both gnome-continuous and rpm-ostree.

My thinking is that in practice, people will have separate "release" repositories from internal CI repositories.  For the internal repos, maybe you don't bother with deltas.


One thing though - in the current static deltas design, they can refer to both *other* deltas, as well as fallback to plain fetch of individual objects as before.

This could allow saving significant space on the server, at the cost of some additional unnecessary download for the client.

For example, imagine we have a branch with commits A, B, C, D.  The client is on A, and wants to go to D.

D has just been generated.  C has been around a while, and we already have a static delta going from A->C.  We can generate a new delta which points to A->C, and then just the additional C->D.

In the case where commits C and D change different content, this is close to a pure win.  Now if C and D change exactly the same files, it's likely to be a pure *loss*.

Determining this would come down to the delta compiler.

Which is the idea - by having a very flexible format and design, we can choose on the server (compiler) side what kinds of resources to spend.  Do we want to regenerate deltas every time a new version lands?  Would require more CPU on the server, but would benefit the network and reduce disk usage on the client.

This is basically now moved to #756266

*** This bug has been marked as a duplicate of bug 756266 ***