Een build-graaf die dobbelstenen werpt

Toen ik naar het programma keek, zag ik een aantal presentaties over dynamische derivaties. Samen met enkele recente berichten over dit onderwerp, zoals cargo-dyndrv, zette dit me aan het denken om het onderwerp opnieuw te benaderen, voortbouwend op mijn eerdere berichten hierover.

Ik wilde beter begrijpen wat de implicaties van dynamische derivaties zijn en hoe zij de build-graaf veranderen. Aanvankelijk richtte ik me op hoe dit de lang2nix-stijl van build-graafgeneratie zou kunnen vervangen, maar ik realiseerde me dat de implicaties veel breder zijn.

De graaf hoeft namelijk niet vooraf bekend te zijn. Deze kan worden gedefinieerd terwijl de build vordert. 🧐

Wat bedoel ik hiermee?

Traditioneel vereist Nix dat je aangeeft wat er gebouwd moet worden, waarna Nix exact de stappen vertelt die het zal ondernemen. Dit gebeurt in de vorm van "derivations" die samen de build-graaf vormen.

$ nix-store -q --requisites \
$(nix-instantiate '<nixpkgs>' -A hello) | grep -c '\.drv$'
196

Dit is een belangrijke eigenschap van Nix. Het maakt het mogelijk om over builds na te denken zonder ze daadwerkelijk uit te voeren, simpelweg door te begrijpen wat er gebouwd zal worden. Veel Nix-tools vertrouwen op deze eigenschap via nix build --dry-run. Zo vertelt nix-diff waarom twee closures verschillen zonder dat een van beide gebouwd hoeft te worden.

Waarom veranderen dynamische derivaties dit?

Applicatief, monadisch en bind

In functionele talen is het heel gebruikelijk om abstract te worden en chique termen als "applicatief" en "monadisch" te gebruiken om het verschil tussen soorten berekeningen te beschrijven. Het verschil is subtiel, maar fundamenteel.

Traditioneel was Nix een "applicatief" build-systeem. Dynamische derivaties maken het een "monadisch" build-systeem. Het verschil is dat bij een applicatief build-systeem de volledige build-graaf vooraf bekend is, terwijl bij een monadisch build-systeem de graaf gedefinieerd kan worden terwijl de build vordert. (Het paper Build Systems à la Carte is de standaardreferentie over dit onderwerp).

Een manier om het verschil te begrijpen is door te kijken naar de type-signatures van de twee operaties die hen definiëren:

  • <*> apply :: f (a -> b) -> f a -> f b
  • >>= bind :: m a -> (a -> m b) -> m b

apply (applicatief) neemt een waarde f a die vooraf bekend is en retourneert het resultaat f b. Je kunt de volledige graaf zien voordat je deze uitvoert.

bind (monadisch) neemt een functie (a -> m b) om m b te retourneren. Je kunt de volledige graaf niet zien voordat je deze uitvoert.

Je kunt "applicatief" zien als het schrijven van een boodschappenlijst voordat je het huis verlaat. Je leest het recept, schrijft elk ingrediënt op en rijdt één keer naar de winkel. De lijst is een functie van het recept en niets anders.

"Monadisch" is een recept met een stap die zegt: "proef het, en als het te zout is, ga dan een aardappel kopen". Je kunt die boodschappenlijst niet vooraf schrijven. Of de aardappel erop komt te staan, hangt af van de zoutheid, en die zoutheid bestaat pas nadat je al een deel van het kookproces hebt doorlopen.

Nix was voorheen uitsluitend het eerste; dynamische derivaties voegen het tweede toe.

Eigenlijk had Nix altijd al 'bind'

Eigenlijk had ik moeten zeggen: "Nix is nu monadisch in de scheduler". Nix heeft altijd al bind gehad in de evaluator. We doen al jaren aan monadische builds; we noemen dit import from derivation.

let
  inner = pkgs.runCommand "inner" {} "sleep 10; echo hi > $out";
in
  pkgs.runCommand "outer" {} "echo ${builtins.readFile inner} > $out"

builtins.readFile op een derivation-output is een bind in exact de zin zoals hierboven beschreven: wat er vervolgens gebouwd moet worden, is een functie van een waarde die nog niet bestaat. De Nix-evaluator kan de graaf niet produceren zonder die waarde, en de enige manier om die te verkrijgen is door de evaluatie te stoppen en een builder uit te voeren.

Helaas brengt dit veel risico's met zich mee (zoals het feit dat nix-instantiate plotseling tien seconden kan duren), en dat is waarom nixpkgs deze techniek categorisch verbiedt.

Terwijl import from derivation een bind is in de evaluator, voegen dynamische derivaties nu een bind toe in de scheduler. Het verschil is dat de scheduler builders parallel kan uitvoeren, ze naar remote machines kan sturen en hun resultaten uit een cache kan halen. De evaluator kan dat niet.

Dynamische derivaties voegen dus niet de bind toe; die was er altijd al. Wat verandert, is welke laag deze uitvoert. 🤓

Laten we dobbelstenen werpen

Veel voorbeelden van dynamische derivaties richten zich op het genereren van build-grafen via lang2nix-tooling, maar ik wilde de implicaties van dynamische derivaties in een algemenere zin verkennen.

In de ware monadische zin kan de build-graaf worden gedefinieerd terwijl de build vordert. De volgende stap in de build-graaf kan afhangen van het resultaat van een vorige stap.

Hier is een heel eenvoudig voorbeeld, chain.nix & step.sh, dat een dobbelsteen werpt en vervolgens ofwel stopt, ofwel de keten voortzet door een nieuwe derivation-stap aan de build-graaf toe te voegen. De diepte van de keten is willekeurig, en het resultaat van de build is hoe diep we zijn gekomen.

Alleen het meest linkse blok bestaat wanneer je nix-instantiate uitvoert. Alles rechts daarvan wordt geschreven door een builder, terwijl de build al gaande is.

Visuele weergave van het proces:

  • cluster_eval → in chain.nix
  • cluster_run → geschreven door step.sh tijdens de build
  • Stap N: werpt een d6 → resultaat
  • Resultaat is 6: Stop. De uitkomst is de huidige diepte.
  • Resultaat is iets anders: Ga door naar Stap N+1 (diepte + 1).

Inhoud van chain.nix

{ depth ? 1
, pkgs ? import <nixpkgs> { }
, bash ? pkgs.bash
, coreutils ? pkgs.coreutils
, nix ? pkgs.nixVersions.latest
, chain ? ./chain.nix
, step ? ./step.sh
}:
let
  roller = derivation {
    name = "step-${toString depth}.drv";
    system = builtins.currentSystem;
    builder = "${bash}/bin/bash";
    args = [ "-e" "${step}" ];
    DEPTH = toString depth;
    BASHPKG = "${bash}";
    COREUTILS = "${coreutils}";
    NIXPKG = "${nix}";
    CHAIN = "${chain}";
    STEP = "${step}";
    PATH = "${coreutils}/bin:${nix}/bin";
    # De builder instantiëert derivaties, dus hij heeft een store nodig om mee te communiceren.
    requiredSystemFeatures = [ "recursive-nix" ];
    # De output van deze derivation is een .drv-bestand. Dat is wat het dynamisch maakt.
    __contentAddressed = true;
    outputHashMode = "text";
    outputHashAlgo = "sha256";
  };
in
  builtins.outputOf roller.outPath "out"

Inhoud van step.sh

set -eu
export NIX_CONFIG='experimental-features = nix-command ca-derivations dynamic-derivations'
roll=$(( $(od -An -N1 -tu1 < /dev/urandom) % 6 + 1 ))
echo "depth $DEPTH rolled a $roll"
if [ "$roll" -eq 6 ]; then
# Zes. Stop. Het antwoord is hoe diep we zijn gekomen.
cat > answer.nix <<NIX
let bash = builtins.storePath $BASHPKG; in
derivation {
  name = "dice-result";
  system = builtins.currentSystem;
  builder = "\${bash}/bin/bash";
  args = [ "-c" "echo $DEPTH > \$out" ];
  __contentAddressed = true;
  outputHashMode = "recursive";
  outputHashAlgo = "sha256";
}
NIX
else
# Geen zes. Mijn antwoord is wat het volgende niveau antwoordt.
cat > answer.nix <<NIX
let
  bash = builtins.storePath $BASHPKG;
  coreutils = builtins.storePath $COREUTILS;
  # Dit is de bind. chain.nix vragen om de volgende diepte bouwt of
  # evalueert dit hier niet: het levert een placeholder op voor
  # "wat diepte $(( DEPTH + 1 )) uiteindelijk antwoordt".
  inner = import (builtins.storePath $CHAIN) {
    inherit bash coreutils;
    depth = $(( DEPTH + 1 ));
    nix = builtins.storePath $NIXPKG;
    chain = builtins.storePath $CHAIN;
    step = builtins.storePath $STEP;
  };
in
derivation {
  name = "dice-passthrough";
  system = builtins.currentSystem;
  builder = "\${bash}/bin/bash";
  args = [ "-c" "cp \$inner \$out" ];
  PATH = "\${coreutils}/bin";
  inherit inner;
  __contentAddressed = true;
  outputHashMode = "recursive";
  outputHashAlgo = "sha256";
}
NIX
fi
cp "$(nix-instantiate answer.nix)" "$out"

Het algemene idee van deze derivation is:

  1. Werp een zes en we schrijven een derivation die de diepte echo't. Gewoon, niets dynamisch daaraan. Dit beëindigt de build-graaf.
  2. Werp iets anders en we schrijven een passthrough: een derivation wiens enige taak cp $inner $out is, waarbij inner gelijk is aan import chain.nix { depth = n + 1; }.

In beide gevallen is het bestand dat in $out wordt gekopieerd een .drv, zodat builtins.outputOf op dezelfde manier werkt voor een keten die stopte als voor een keten die doorging. We hebben een depth-parameter nodig om oneindige recursie te voorkomen en zodat de store-paths van de derivaties verschillend zijn, aangezien ze content-addressed zijn.

We kunnen de build-graaf groeien terwijl de build vordert. Als we echter proberen de graaf te inspecteren met --dry-run of nix-store -q --tree, krijgen we niets. Omdat de graaf nog niet bekend is, kunnen onze tools hem niet zien.

$ nix build --store /tmp/dice -f ./default.nix --dry-run
warning: Ignoring dynamic derivation /nix/store/vnm4l32g…-step-1.drv.drv^out
while querying missing paths; not yet implemented

Dynamische derivaties introduceren een tweede graaf die pas bestaat na de build, en het ecosysteem heeft nog geen manier om deze te inspecteren.

Ik heb de build 900 keer uitgevoerd en de lengte van de keten gelogd. Het werpen van een dobbelsteen met zes zijden is een van de meest klassieke manieren om geometrisch verval te simuleren. Het gemiddelde was 6,18, de mediaan 4 en de langste keten 46. De wiskunde klopt.

Voorbij lang2nix

Elke demo van dynamische derivaties tot nu toe, inclusief die van mij, is een build-systeem geweest:

  • MakeNix voor C,
  • NpmNix voor Node,
  • cargo-dyndrv voor Rust,
  • nix-ninja voor Ninja.

Dat is een redelijk startpunt, maar het vangt niet de volledige kracht van dit primitief. Welke andere ideeën kunnen we verkennen?

  • Mario: In "Super Mario Derivations" is het attribuutpad de knopvolgorde en moet ik het aantal drukken opgeven. De dynamische versie emuleert totdat Mario sterft. De stopconditie is data die halverwege de build wordt ontdekt, en de run duurt precies zo lang als hij toevallig uitvalt.
  • Zoeken in een toestandsruimte: Vervang de dobbelsteen door een predicaat en je hebt een zoektocht waarbij elke frontier node een derivation is. Denk aan model checking, puzzeloplossers of een fuzzer die alleen inputs uitbreidt die nieuwe coverage vinden. Toestanden die je twee keer bereikt, vallen samen op één store path en overleven een herstart.
  • Crawling: Haal een pagina op, parse de links en genereer één derivation per link. De grens wordt ontdekt in plaats van gedeclareerd; de crawl gaat verder omdat de store onthoudt welke pagina's al zijn opgehaald, en de afhankelijkheidsgraaf van het resultaat is de link-graaf.

Wat zijn de grenzen van dit primitief? Ik weet het niet.

De grootte van de graaf wordt nu alleen beperkt door de vraag of Nix stopt met het genereren van opvolgers. Er is geen dieptelimiet voor de store-laag, geen equivalent van max-call-depth. Mijn langste eerlijke keten in het dobbelsteen-voorbeeld was 46 diep, maar ik had gemanipuleerde voorbeelden die tot 500 gingen. Hoe ver kan het gaan?

Ik ben zozeer gehersenspoeld om eerst een plan te maken voordat ik begin met mijn build-systemen, dat het idee om het gaandeweg te verzinnen een beetje eng is. 😨