wmertens/nix-store-in-git.md

## nix-store-in-git.md

      
    Raw
  

              nix-store-in-git.md
            
          
    Store Nix store in git

The Nix store is an immutable file tree store, addressed by output hashes ($outhash-$name or $out), but could also be tweaked to be addressed by the content hash of the file tree ($cas).
Git is a content-addressed immutable object store. It is optimized for storing files as blobs and directories as tree objects.
Here we consider using a git repository for deduplicating, compressing and distributing the Nix store. We want to achieve maximum deduplication so we extract small changes from files before storing, so they become more similar.
Method

Each Nix store entry (top level files or directories) goes into the git repo as a git tree object, with the entry contents scrubbed of store references and all runtime dependencies connected by referencing.
This tree object contains entry with refs replaced by the # character, optionally entry.m with the objective metadata described in RFC #17, meta.json with patch list, and deps, resulting in the tree object {deps,entry,entry.m,meta.json}
We define the git object id of this tree object as the $oid of the Nix store entry. This $oid therefore depends on the entry contents and all its runtime dependencies.

entry: the file or directory that’s normally at /nix/store/$out
entry.m: the array of the dependencies paths as described in RFC #17, either as their $out or as their $cas
deps: tree object referencing all dependency trees. This way the git tree object is enough to have the complete closure of the entry
meta.json: JSON format, with alphabetically sorted keys and single tab character indentation + newlines (for consistency and readability). Its keys are:

hash: either $out or the $cas of the patched entry and entry.m (as in RFC #17)
patch: nested object following the tree under entry; keys are directory items needing patching, sub-objects are directories, leaves are file patch lists like [ [type,] data... ].

type is either missing, or a string describing the patcher, e.g. "gzip" or "jar".

The patcher is responsible for the best representation of data, but probably relative_offset+depId.
To enable nested packages like .jar files, data could be a patch object, and the patcher would put each file into individual blobs.
The patcher has to referenced by name because it is code that needs to run on all architectures


data is patcher-specific. By default it's a flat sequence of <offset, depId>...

offset is the byte index since the last ref
depId is the index in the dependency array. 0 is the self reference, 1 is deps[0], etc


If we need to make an incompatible change we can add a version field


Note that $cas could just be the $out as before, and deduplication would still work. Converting to $cas is still desirable for many reasons but not required for this proposal to work. Using $out is somewat safer though, since it will not change the binaries after restoring.
If packages are built with dependencies referenced as their $cas, there will be little difference.
Benefits


Immutable, probably verifying checksums
Compressed
Maximum deduplication achievable, allowing shortcutting builds
Well-tested format
Efficient transfers with individual blob granularity
Many implementations exist
Dependency replacement is trivial. E.g. instead of relying on runtime binding to OpenGL libraries, the correct package for the system can be composed on the target system.

Disadvantages


This increases the needed storage versus just a store.

Git is very good at packing the data however. It will certainly be a boon for Hydra.
Very tiny systems could have their git repo mounted from a nearby bigger system (they can even share the same repo).
When using FUSE, it will actually use less space.


Git checksums are weaker than the ones we use now.

But we still use $cas with our own checksum, so any collisions in the git repo would result in $cas being wrong.


Extra complexity.

Most of the complexity is handled by git.


There will be a lot of tags and the repo will get big.

Git can handle this just fine, but some git clients won’t like the resulting repo.


Storing a package

Note, this works for both $out and $cas-built packages, but it’s best to build from $cas

Remember $out as dep 0
Depth-first recurse files to generate the entry tree:

Discover type
Let the patcher find store refs, replacing them with #### characters and remembering location and $out (to adjust to shorter $cas length, add multiple ///// over the beginning of $out), finally writing the file to a git blob

Note that the patcher might convert a file into a git tree object


For each found store ref:

If self ref, remember as index 0, else:
Ensure ref is in repo, get it $cas (or $out)
Note that dep indexes will change until package scanning is done, so store by $cas (or $out)


Generate the deps tree object; each dependency is named for its $cas (or $out) and links to its $oid. Also ensure extra runtime deps that were passed (workaround for unscannable refs).
Store deps (if not empty) + entry + entry.m (if not empty) + meta.json as a git tree object
If implementing RFC #17, calculate $cas (the hash of entry with all reference placeholders replaced by their $cas reference), perhaps by creating the package in the Nix store directory
Generate entry.m file: sorted deps array without self, either the $out or $cas.
Generate meta.json file: add the hash key and the patch array if it's not empty
Generate the combined tree object, get its $oid
Add git tags pointing to $oid (for preventing garbage collection, and for listing repo contents) named $out (optional when $cas is known, for discovery) and $cas (if known)

Build shortcuts


If a package build results in the same $cas, it might stop a build if none of the other $cas changed.


If a built package results in the entry object having the same git SHA1 object id but a different entry.m or meta.json, rebuilding of dependents could instead just replace deps. Examples: new node patch version, not requiring changing scripts, or new openssl library patch.

This will likely change the ordering of the deps and thus the indexes in the patch object.
This optimization is not always safe, for example:

App c uses lib a, which uses dep b to change the build process for app c.
Suppose a new version of b only changes a's meta.json, then c would still have to be rebuilt.


Even when not using this optimization, the deduplication of entry will still help save resources.


Unpacking a package into the Nix store


If you don't have the $oid, get the $cas or $out of the requested package and read the tag to look up the $oid
Read the dependency array from entry.m (index 0 is $cas or $out) and the patch object from meta.json
In a temporary directory under the Nix store, recursively restore patched files (throw an error if not replacing # chars or if $cas is wrong after restore)
Move the result to $cas or $out in the store, as described in RFC #17
Optionally symlink $out to $cas

Downloading a package


Figure out $oid via your Trust DB, or use $out or $cas to read the tag on the remote
Use the git protocol to fetch $oid, from any repo, anywhere
If you know $cas, check it after fetching, so you're protected against git SHA1 clashing attacks
Git will only fetch missing objects, and will also fetch all missing deps thanks to the the deps tree
Git won’t care which repos you use to get the objects
Git won’t copy objects it doesn’t need

Uploading a package


Publish Trust DB information somehow: The $oid, the list of $out pointing to it, the $cas if known, the $name, and any other desired subjective data
Push the relevant tags to the remote git repo

Mounting as FS

With e.g. FUSE (by adapting gitfs project), we could present the store directly from the git repo. Entries are tags, files are patched on the fly (compressed objects will need a cache), writes are impossible.
This will need some careful consideration at boot time if this virtual filesystem can't be part of stage1; the closure for mounting stage2 must then be unpacked.
Commits, branches

Commits and branches are not necessary to implement this.
However, Hydra could create signed commits with build information for each build. Create tree objects named for each built attribute; git will deduplicate and use the naming for better packing diffs.
Each collection of builds from a tracked branch can be gathered in a timestamped branch. This will create lots of branches over time but that's not an issue.
Git web server can be used to allow browsing.
Shared storage

Reading from a git repo on networked storage is no problem.
For writing:

The index can’t be shared by multiple writers, but it’s not used when storing packages.
Packing might cause problems when two hosts do it simultaneously, we should test.
Adding objects should be fine.
Git GC should be fine too, if leaving new objects alone (--prune-older).

Git packing

For optimizing storage, git will pack objects and store them as diffs using heuristics to find good starting points. We could investigate how to best hint git about previous versions for smaller diffs.