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.
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/$outentry.m: the array of the dependencies paths as described in RFC #17, either as their$outor as their$casdeps: tree object referencing all dependency trees. This way the git tree object is enough to have the complete closure of the entrymeta.json: JSON format, with alphabetically sorted keys and single tab character indentation + newlines (for consistency and readability). Its keys are:hash: either$outor the$casof the patchedentryandentry.m(as in RFC #17)patch: nested object following the tree underentry; keys are directory items needing patching, sub-objects are directories, leaves are file patch lists like[ [type,] data... ].typeis 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,
datacould be apatchobject, 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
- The patcher is responsible for the best representation of
datais patcher-specific. By default it's a flat sequence of<offset, depId>...offsetis the byte index since the last refdepIdis the index in the dependency array. 0 is the self reference, 1 isdeps[0], etc
- If we need to make an incompatible change we can add a
versionfield
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.
- 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.
- 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
$caswith our own checksum, so any collisions in the git repo would result in$casbeing wrong.
- But we still use
- 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.
Note, this works for both $out and $cas-built packages, but it’s best to build from $cas
- Remember
$outas dep 0 - Depth-first recurse files to generate the
entrytree:- Discover type
- Let the patcher find store refs, replacing them with
####characters and remembering location and$out(to adjust to shorter$caslength, 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
depstree 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.jsonas 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.mfile: sorted deps array without self, either the$outor$cas. - Generate
meta.jsonfile: add thehashkey and thepatcharray 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$casis known, for discovery) and$cas(if known)
-
If a package build results in the same
$cas, it might stop a build if none of the other$caschanged. -
If a built package results in the
entryobject having the same git SHA1 object id but a differententry.mormeta.json, rebuilding of dependents could instead just replacedeps. Examples: newnodepatch version, not requiring changing scripts, or newopenssllibrary 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
entrywill still help save resources.
- If you don't have the
$oid, get the$casor$outof the requested package and read the tag to look up the$oid - Read the dependency array from
entry.m(index 0 is$casor$out) and thepatchobject frommeta.json - In a temporary directory under the Nix store, recursively restore patched files (throw an error if not replacing
#chars or if$casis wrong after restore) - Move the result to
$casor$outin the store, as described in RFC #17 - Optionally symlink
$outto$cas
- Figure out
$oidvia your Trust DB, or use$outor$casto 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
depstree - Git won’t care which repos you use to get the objects
- Git won’t copy objects it doesn’t need
- Publish Trust DB information somehow: The
$oid, the list of$outpointing to it, the$casif known, the$name, and any other desired subjective data - Push the relevant tags to the remote git repo
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 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.
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).
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.
UPDATE: adjusted the text for the below, and made it handle
$outand$casbothJust 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.