Repo scalability issues and solutions

[Alexander Larsson <alexl redhat com>]

For the next flatpak release I'm doing some work on repo scalability.
See 
https://lists.freedesktop.org/archives/flatpak/2020-August/002027.html

As flathub gets larger, there are some fundamental scalability
problems:
 * More apps means summary file changes more often
 * More apps means summary file is larger
 * Adding new architecures explodes the number of refs, and thus
summary size

Since almost any operation need a fresh summary file available locally
this leads to a lot of network transfers and waiting, but the size of
the file can also mean that local operations are slower due to longer
load and processing times.

Flathub transfers the summary file with transfer-encoding gzip which
does make the size somewhat smaller on the network, but its still
rather large.  Here are some stats so you can get a feeling for
absolute size and the increase over time.

flathub summary 2020-08-24: 6.3M (gzip 1.7M)
flathub summary 2020-06-03: 5.8M (gzip 1.6M)

I did some analysis of the summary, and it splits down sizewise
like this:
* ref to commit map: 1.4M
* ostree.static-deltas: 1.1M
* xa.cache: 3.6M (mainly app metadata)
* xa.sparse-cache: 164k

Summaries are sorted and incrementally changed, which should delta
well. To verify this I ran bsdiff on the uncompressed summaries and
got:

 2020-06-03 -> 2020-08-24: 643k
 2020-08-24 -> 2020-08-25: 45k

In order to improve scalability I propose we add a completely new
version of summaries, which will be used by newer versions of ostree
(leaving the old one for older clients). And, while we do this change
we should try to be forward-looking and solve other outstanding issues
we can think of.

For example:
 * Being able to create subsets of the refs in a repo (flathub wants
   this for creating e.g. a subset without non-free software).
 * Improving the ability to estimate download sizes.

The main ideas I have for improvements are:
 * Improve efficiency in the summary format
 * Move deltas out of the summary
 * Split summary file into per-arch versions
 * Add deltas for incremental updates of summaries

I'll talk a bit about each of these

Improve efficiency in the summary format
==========================================

The current format is quite verbose, because it is using strings in
many places that end up being duplicated. For example, each ref in the
ref-map has a dict which has a 'ostree.commit.timestamp' key. If we had
a single string table and used string offsets for all the dicts in the
file that would be a lot better. It would probably be more efficient
to process too.

In flatpak, we have a metadata field called "xa.cache" which maps from
ref to some per-app metadata. This duplicates each of the refs (as a
string) again. If we could refer to the ref via the index in the
existing ref table that would be a lot more efficient. Unfortunately
ostree_repo_regenerate_summary() requires passing the extra metadata
before the list of refs is generated so this is not possible. If we
changed this API to take a callback which can add additional metadata
we could use the chosen ref indexes in the callback.

Flatpak stores for each app the metadata file of the app which is a
small text file. Compressing small files like this doesn't help a lot
(got it down to 60% when experimenting). However, since the files
repeat a lot I was able to compress it down to 30% by creating a 32k
zlib dictionary, and if we store this in the summary that would make
the flathub app metadata go from 2.8M to 0.8M which is pretty good.

Move deltas out of the summary
==============================

Deltas are really only used when downloading a particular commit (they
are even indexed by commit id), so having *all* of them in the summary
seems non-ideal. We could store them in the detached metadata instead,
then you would only need to download them for the specific commit you
are pulling.

One issue is that the summary is signed, but the detached metadata is
typically not. I don't believe this is a problem though, because the
delta handling verifies the signature of the commit it writes.

Split summary file into per-arch versions
=========================================

Adding a minor architecture (say ppc) to flathub atm adds a *lot* of
refs, which badly bloats the summary file for regular users. What
I would like is to generate the current summary with only the old
arches, and then create one summary per arch, and have the flatpak
client pick the right one when doing and update.

The "per-arch" part of this is going to have to be specific to
flatpak, but I imagine the support for this as being able to define
named subsets of the repository, via some tag list in the commit
objects. Then the client can specify the default subset in the remote
configuration (or flatpak could pick it automatically based on the
current arch).

I did some experimenting with the flathub summary, and by removing
non-x86-64 refs and the deltas, I got the flathub summary from 6.3M to
1.8M, which is pretty good.

This could also be used to solve the "FSF free flathub" issue, by
using named subsets not only for architecture. I.e. we can have
subsets "x86_64" as well as "free-x86_64".

Add deltas for incremental updates of summaries
===============================================

This only helps with the network transfer, but OTOH, it does so
extremely well. A simple bsdiff of the entire summary is probably the
easiest way to do this.

However, for this to work we need to be able to identify the summary
version you have (and which is on the server), and to store multiple
versions of if. The easiest way to do so is to store them by sha256,
just like objects.  Then you have some top-level summary index file
that list the sha256 of the current summary file. In fact, it probably
will have a list of summary files (for the per-arch summaries), which
is good because this single file will allow atomically updating all
the sub-summary files in one change.


Does the above make sense to everyone? Do we have any other ideas how
we could do better? Do we have some important feature we would like in
the new format?

Note: While some of these changes apply to ostree, some apply just to
flatpak. However, I want to synchronize the changes so that we only
have to do a single format-change.