Sparkles

Appearance

Nix git-hashing ​

One system, two level-1 schemes — the direct precedent for computing a git-shaped Merkle identity internally while still emitting a NAR at the interoperability boundary.

EcosystemNix (experimental feature git-hashing)
Level 1git tree objects, over Nix's FSO model
Level 2git blobs
Node modelthe Nix FSO triple — mapped onto git's modes, partially
Entry orderinggit's, implemented by suffixing directory keys with /
DigestSHA-1 or SHA-256
Implementationsrc/libutil/git.cc, git.hh

Overview ​

What it solves ​

Nix needed a Merkle-graph content-addressing method alongside serial NAR hashing, and rather than invent one it adopted git's. Its reasoning (file-system-object/content-address.md):

Git's file system model is very close to Nix's, and so Git's content addressing method is a pretty good fit. Just as with regular Git, files and symlinks are hashed as git "blobs", and directories are hashed as git "trees".

That is the whole case for reusing git's shape: an existing, ubiquitous, independently-implemented Merkle DAG whose node model is a near-match.

Design philosophy ​

The interesting part is what Nix documents as not fitting, because it is the sharpest available statement of git's structural limitation:

Plain files, executable files, and symlinks are not differentiated as distinctly addressable objects, but by their context: by the directory entry that refers to them. That means so long as the root object is a directory, there is no problem […] However, if the root object is not a directory, then we have no way of knowing which one of an executable file, non-executable file, or symlink it is supposed to be.

In response to this, we have decided to treat a bare file as non-executable file. […] To avoid an address collision, attempts to hash a bare executable file or symlink will result in an error […] Thus, Git can encode some, but not all of Nix's "File System Objects", and this sort of content-addressing is likewise partial.

A scheme that is partial over its own model, and says so, is a better guide than one that pretends otherwise.

How it works ​

git.cc is a compact, readable second implementation of git's object formats. Blobs:

cpp
auto s = fmt("blob %d\0"s, std::to_string(size));

Trees, with the ordering trick made explicit:

cpp
for (auto & [name, entry] : entries) {
    auto name2 = name;
    if (entry.mode == Mode::Directory) {
        assert(!name2.empty());
        assert(name2.back() == '/');
        name2.pop_back();
    }
    v1 += fmt("%o %s\0"s, static_cast<RawMode>(entry.mode), name2);
    std::copy(entry.hash.hash, entry.hash.hash + entry.hash.hashSize, std::back_inserter(v1));
}

The Tree type is a std::map keyed by name, and git.hh states the invariant in a comment that is the clearest one-line account of git ordering anywhere in this survey:

Directory names must end in a / for sake of sorting. See https://github.com/mirage/irmin/issues/352

So: append / to directory keys, let the ordered map sort byte-wise, strip the / when writing. An independent reimplementation arriving at the same trick — and the cited irmin issue is a third project arriving there too — is good evidence that this is the only practical way to get git's order from a byte-wise container.

A symlink is dumped as a blob of its target, and the whole path is gated on the experimental feature: every entry point calls xpSettings.require(Xp::GitHashing).

What it demonstrates for a fileset design ​

Three things, each directly load-bearing:

  1. Two level-1 schemes can coexist over one node model. Nix computes NAR hashes and git hashes from the same SourceAccessor walk. The walk does not know which scheme will consume it.
  2. The two orderings cannot share a primitive. Nix's NAR path sorts raw names; its git path sorts /-suffixed keys. They are separate code with separate containers, in one codebase, by necessity — see the ordering axis.
  3. Partiality is a property to surface, not to paper over. The bare executable file and bare symlink cases are errors, not silent reinterpretations, and the flat method is documented as having the same limitation for the same reason.

Strengths ​

  • Merkle identity with two independent oracles — git hash-object / git write-tree, and Nix's own implementation.
  • A second, readable implementation of git's formats, useful as a reference when porting.
  • The partiality is documented and enforced, not discovered later.

Weaknesses ​

  • Experimental, and gated at every entry point.
  • Partial over the FSO model — bare executable files and bare symlinks cannot be addressed.
  • Inherits git's ordering, and therefore needs the /-suffix workaround in any container that sorts byte-wise.

Key design decisions and trade-offs ​

DecisionRationaleTrade-off
Adopt git's method rather than design a Merkle oneGit's model "is very close to Nix's"; enormous existing toolingInherits git's ordering quirk and its mode-in-the-parent partiality
Error on bare executable files and symlinks"To avoid an address collision"Some FSOs simply have no git address
Suffix directory keys with / in an ordered mapThe only way to get git's order from a byte-wise containerA representation invariant to assert, and to strip on output
Keep both NAR and git hashingSerial for the store's existing identity, Merkle where a graph helpsTwo canonical orderings, two serializers, in one codebase
Gate behind an experimental featureThe method is partial and not yet committed toConsumers cannot rely on it

Sources ​