Skip to content

Instantly share code, notes, and snippets.

@wmertens
Last active September 7, 2022 19:57
Show Gist options
  • Save wmertens/eceebe0fc05461ebdc8fb106d90a6871 to your computer and use it in GitHub Desktop.
Save wmertens/eceebe0fc05461ebdc8fb106d90a6871 to your computer and use it in GitHub Desktop.
Store Nix store in git

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.

@wmertens
Copy link
Author

wmertens commented Jan 25, 2021

UPDATE: adjusted the text for the below, and made it handle $out and $cas both

Just realized that packed files like .jar could also be unpacked for reference detection and deduplication.
So the patch object should be able to describe this, perhaps by making the leaf value be ["zip",{...nested patch object}].

There may be complications due to checksums though - to be handled on a case by case basis.

@L-as
Copy link

L-as commented Aug 16, 2021

If this ever happens it would likely be with SHA-256 Git, so you can probably remove the parts about the checksum being bad.

@mikepurvis
Copy link

Refs can be anything! There's just some extra porcelain for when they're called heads or tags. When I know I'm going to have a lot of them generated by automation, I'll intentionally call them something else— Github and GitLab will accept and persist these, but they won't make a mess of the web UI.

Projects like git-bug do similar things to stash metadata in a git repo; this isn't a path down which I'd expect to find a ton of gremlins.

@wmertens
Copy link
Author

@mikepurvis Interesting, thanks! How you you name them something else?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment