In this post I’ll demonstrate my new fast-downward library and show how it can be used to solve planning problems. The name comes from the use of the backend solver - Fast Downward. But what’s a planning problem?

Roughly speaking, planning problems are a subclass of AI problems where we need to work out a plan that moves us from an initial state to some goal state. Typically, we have:

• A known starting state - information about the world we know to be true right now.
• A set of possible effects - deterministic ways we can change the world.
• A goal state that we wish to reach.

With this, we need to find a plan:

• A solution to a planning problem is a plan - a totally ordered sequence of steps that converge the starting state into the goal state.

Planning problems are essentially state space search problems, and crop up in all sorts of places. The common examples are that of moving a robot around, planning logistics problems, and so on, but they can be used for plenty more! For example, the Beam library uses state space search to work out how to converge a database from one state to another (automatic migrations) by adding/removing columns.

State space search is an intuitive approach - simply build a graph where nodes are states and edges are state transitions (effects), and find a path (possibly shortest) that gets you from the starting state to a state that satisfies some predicates. However, naive enumeration of all states rapidly grinds to a halt. Forming optimal plans (least cost, least steps, etc) is an extremely difficult problem, and there is a lot of literature on the topic (see ICAPS - the International Conference on Automated Planning and Scheduling and recent International Planning Competitions for an idea of the state of the art). The fast-downward library uses the state of the art Fast Downward solver and provides a small DSL to interface to it with Haskell.

In this post, we’ll look at using fast-downward in the context of solving a small planning problem - moving balls between rooms via a robot. This post is literate Haskell, here’s the context we’ll be working in:

{-# language DisambiguateRecordFields #-}

module FastDownward.Examples.Gripper where

import Control.Monad
import qualified FastDownward.Exec as Exec
import FastDownward.Problem

If you’d rather see the Haskell in it’s entirety without comments, simply head to the end of this post.

Modelling The Problem

Defining the Domain

As mentioned, in this example, we’ll consider the problem of transporting balls between rooms via a robot. The robot has two grippers and can move between rooms. Each gripper can hold zero or one balls. Our initial state is that everything is in room A, and our goal is to move all balls to room B.

First, we’ll introduce some domain specific types and functions to help model the problem. The fast-downward DSL can work with any type that is an instance of Ord.

data Room = RoomA | RoomB
  deriving (Eq, Ord, Show)

adjacent :: Room -> Room
adjacent RoomA = RoomB
adjacent RoomB = RoomA

data BallLocation = InRoom Room | InGripper
  deriving (Eq, Ord, Show)

data GripperState = Empty | HoldingBall
  deriving (Eq, Ord, Show)

A ball in our model is modelled by its current location. As this changes over time, it is a Var - a state variable.

type Ball = Var BallLocation

A gripper in our model is modelled by its state - whether or not it’s holding a ball.

type Gripper = Var GripperState

Finally, we’ll introduce a type of all possible actions that can be taken:

data Action = PickUpBall | SwitchRooms | DropBall
  deriving (Show)

With this, we can now begin modelling the specific instance of the problem. We do this by working in the Problem monad, which lets us introduce variables (Vars) and specify their initial state.

Setting the Initial State

problem :: Problem (SolveResult Action)
problem = do

First, we introduce a state variable for each of the 4 balls. As in the problem description, all balls are initially in room A.

  balls <- replicateM 4 (newVar (InRoom RoomA))

Next, introduce a variable for the room the robot is in - which also begins in room A.

  robotLocation <- newVar RoomA

We also introduce variables to track the state of each gripper.

  grippers <- replicateM 2 (newVar Empty)

This is sufficient to model our problem. Next, we’ll define some effects to change the state of the world.

Defining Effects

Effects are computations in the Effect monad - a monad that allows us to read and write to variables, and also fail (via MonadPlus). We could define these effects as top-level definitions (which might be better if we were writing a library), but here I’ll just define them inline so they can easily access the above state variables.

Effects may be used at any time by the solver. Indeed, that’s what solving planning problems is all about! The hard part is choosing effects intelligently, rather than blindly trying everything. Fortunately, you don’t need to worry about that - Fast Downward will take care of that for you!

  let

Picking Up Balls

The first effect takes a ball and a gripper, and attempts to pick up that ball with that gripper.

    pickUpBallWithGripper :: Ball -> Gripper -> Effect Action
    pickUpBallWithGripper b gripper = do
      Empty <- readVar gripper                  -- (1)

      robotRoom <- readVar robotLocation        -- (2)
      ballLocation <- readVar b
      guard (ballLocation == InRoom robotRoom)  -- (3)

      writeVar b InGripper                      -- (4)
      writeVar gripper HoldingBall

      return PickUpBall                         -- (5)

1. First we check that the gripper is empty. This can be done concisely by using an incomplete pattern match. do notation desugars incomplete pattern matches to a call to fail, which in the Effect monad simply means “this effect can’t currently be used”.

2. Next, we check where the ball and robot are, and make sure they are both in the same room.

3. Here we couldn’t choose a particular pattern match to use, because picking up a ball should be possible in either room. Instead, we simply observe the location of both the ball and the robot, and use an equality test with guard to make sure they match.

4. If we got this far then we can pick up the ball. The act of picking up the ball is to say that the ball is now in a gripper, and that the gripper is now holding a ball.

5. Finally, we return some domain specific information to use if the solver chooses this effect. This has no impact on the final plan, but it’s information we can use to execute the plan in the real world (e.g., sending actual commands to the robot).

Moving Between Rooms

This effect moves the robot to the room adjacent to its current location.

    moveRobotToAdjacentRoom :: Effect Action
    moveRobotToAdjacentRoom = do
      modifyVar robotLocation adjacent

      return SwitchRooms

This is an “unconditional” effect as we don’t have any explicit guards or pattern matches. We simply flip the current location by an adjacency function.

Again, we finish by returning some information to use when this effect is chosen.

Dropping Balls

Finally, we have an effect to drop a ball from a gripper.

    dropBall :: Ball -> Gripper -> Effect Action
    dropBall b gripper = do
      HoldingBall <- readVar gripper     -- (1)
      InGripper <- readVar b

      robotRoom <- readVar robotLocation -- (2)
      writeVar gripper Empty             -- (3)
      writeVar b (InRoom robotRoom)      -- (4)

      return DropBall                    -- (5)

1. First we check that the given gripper is holding a ball, and the given ball is in a gripper.

2. If we got here then those assumptions hold. We’ll update the location of the ball to be the location of the robot, so first read out the robot’s location.

3. Empty the gripper

4. Move the ball.

5. And we’re done! We’ll just return a tag to indicate that this effect was chosen.

Solving Problems

With our problem modelled, we can now attempt to solve it. We invoke solve with a particular search engine (in this case A* with landmark counting heuristics). We give the solver two bits of information:

1. A list of all effects - all possible actions the solver can use. These are precisely the effects we defined above, but instantiated for all balls and grippers.
2. A goal state. Here we’re using a list comprehension which enumerates all balls, adding the condition that the ball location must be InRoom RoomB.

  solve
    cfg
    ( [ pickUpBallWithGripper b g | b <- balls, g <- grippers ]
        ++ [ dropBall b g | b <- balls, g <- grippers ]
        ++ [ moveRobotToAdjacentRoom ]
    )
    [ b ?= InRoom RoomB | b <- balls ]

So far we’ve been working in the Problem monad. We can escape this monad by using runProblem :: Problem a -> IO a. In our case, a is SolveResult Action, so running the problem might give us a plan (courtesy of solve). If it did, we’ll print the plan.

main :: IO ()
main = do
  res <- runProblem problem
  case res of
    Solved plan -> do
      putStrLn "Found a plan!"
      zipWithM_ 
        ( \i step -> putStrLn ( show i ++ ": " ++ show step ) ) 
        [ 1::Int .. ] 
        ( totallyOrderedPlan plan )

    _ ->
      putStrLn "Couldn't find a plan!"

fast-downward allows you to extract a totally ordered plan from a solution, but can also provide a partiallyOrderedPlan. This type of plan is a graph (partial order) rather than a list (total order), and attempts to recover some concurrency. For example, if two effects do not interact with each other, they will be scheduled in parallel.

Well, Did it Work?!

All that’s left is to run the problem!

> main
Found a plan!
1: PickUpBall
2: PickUpBall
3: SwitchRooms
4: DropBall
5: DropBall
6: SwitchRooms
7: PickUpBall
8: PickUpBall
9: SwitchRooms
10: DropBall
11: DropBall

Woohoo! Not bad for 0.02 secs, too :)

Behind The Scenes

It might be interesting to some readers to understand what’s going on behind the scenes. Fast Downward is a C++ program, yet somehow it seems to be running Haskell code with nothing but an Ord instance - there are no marshalling types involved!

First, let’s understand the input to Fast Downward. Fast Downward requires an encoding in its own SAS format. This format has a list of variables, where each variable contains a list of values. The contents of the values aren’t actually used by the solver, rather it just works with indices into the list of values for a variable. This observations means we can just invent values on the Haskell side and careful manage mapping indices back and forward.

Next, Fast Downward needs a list of operators which are ground instantiations of our effects above. Ground instantiations of operators mention exact values of variables. Recounting our gripper example, pickUpBallWithGripper b gripper actually produces 2 operators - one for each room. However, we didn’t have to be this specific in the Haskell code, so how are we going to recover this information?

fast-downward actually performs expansion on the given effects to find out all possible ways they could be called, by non-deterministically evaluating them to find a fixed point.

A small example can be seen in the moveRobotToAdjacentRoom Effect. This will actually produce two operators - one to move from room A to room B, and one to move from room B to room A. The body of this Effect is (once we inline the definition of modifyVar)

  readVar robotLocation >>= writeVar robotLocation . adjacent

Initially, we only know that robotLocation can take the value RoomA, as that is what the variable was initialised with. So we pass this in, and see what the rest of the computation produces. This means we evaluate adjacent RoomA to yield RoomB, and write RoomB into robotLocation. We’re done for the first pass through this effect, but we gained new information - namely that robotLocation might at some point contain RoomB. Knowing this, we then rerun the effect, but the first readVar gives us two paths:

readVar robotLocation 
  >>= \RoomA -> writeVar robotLocation RoomB                     -- If we read RoomA
  >>= \RoomB -> writeVar robotLocation (adjacent RoomB -> RoomA) -- If we read RoomB

This shows us that robotLocation might also be set to RoomA. However, we already knew this, so at this point we’ve reached a fixed point.

In practice, this process is ran over all Effects at the same time because they may interact - a change in one Effect might cause new paths to be found in another Effect. However, because fast-downward only works with finite domain representations, this algorithm always terminates. Unfortunately, I have no way of enforcing this that I can see, which means a user could infinitely loop this normalisation process by writing modifyVar v succ, which would produce an infinite number of variable assignments.

Conclusion

CircuitHub are using this in production (and I mean real, physical production!) to coordinate activities in its factories. By using AI, we have a declarative interface to the production process – rather than saying what steps are to be performed, we can instead say what state we want to end up in and we can trust the planner to find a suitable way to make it so.

Haskell really shines here, giving a very powerful way to present problems to the solver. The industry standard is PDDL, a Lisp-like language that I’ve found in practice is less than ideal to actually encode problems. By using Haskell, we:

• Can easily feed the results of the planner into a scheduler to execute the plan, with no messy marshalling.
• Use well known means of abstraction to organise the problem. For example, in the above we use Haskell as a type of macro language – using do notation to help us succinctly formulate the problem.
• Abstract out the details of planning problems so the rest of the team can focus on the domain specific details – i.e., what options are available to the solver, and the domain specific constraints they are subject to.

fast-downward is available on Hackage now, and I’d like to express a huge thank you to CircuitHub for giving me the time to explore this large space and to refine my work into the best solution I could think of. This work is the result of numerous iterations, but I think it was worth the wait!

Appendix: Code Without Comments

Here is the complete example, as a single Haskell block:

{-# language DisambiguateRecordFields #-}

module FastDownward.Examples.Gripper where

import Control.Monad
import qualified FastDownward.Exec as Exec
import FastDownward.Problem


data Room = RoomA | RoomB
  deriving (Eq, Ord, Show)


adjacent :: Room -> Room
adjacent RoomA = RoomB
adjacent RoomB = RoomA


data BallLocation = InRoom Room | InGripper
  deriving (Eq, Ord, Show)


data GripperState = Empty | HoldingBall
  deriving (Eq, Ord, Show)


type Ball = Var BallLocation


type Gripper = Var GripperState

  
data Action = PickUpBall | SwitchRooms | DropBall
  deriving (Show)


problem :: Problem (Maybe [Action])
problem = do
  balls <- replicateM 4 (newVar (InRoom RoomA))
  robotLocation <- newVar RoomA
  grippers <- replicateM 2 (newVar Empty)

  let
    pickUpBallWithGripper :: Ball -> Gripper -> Effect Action
    pickUpBallWithGripper b gripper = do
      Empty <- readVar gripper
  
      robotRoom <- readVar robotLocation
      ballLocation <- readVar b
      guard (ballLocation == InRoom robotRoom)
  
      writeVar b InGripper
      writeVar gripper HoldingBall
  
      return PickUpBall


    moveRobotToAdjacentRoom :: Effect Action
    moveRobotToAdjacentRoom = do
      modifyVar robotLocation adjacent
      return SwitchRooms


    dropBall :: Ball -> Gripper -> Effect Action
    dropBall b gripper = do
      HoldingBall <- readVar gripper
      InGripper <- readVar b
  
      robotRoom <- readVar robotLocation
      writeVar b (InRoom robotRoom)
  
      writeVar gripper Empty
  
      return DropBall

  
  solve
    cfg
    ( [ pickUpBallWithGripper b g | b <- balls, g <- grippers ]
        ++ [ dropBall b g | b <- balls, g <- grippers ]
        ++ [ moveRobotToAdjacentRoom ]
    )
    [ b ?= InRoom RoomB | b <- balls ]

  
main :: IO ()
main = do
  plan <- runProblem problem
  case plan of
    Nothing ->
      putStrLn "Couldn't find a plan!"

    Just steps -> do
      putStrLn "Found a plan!"
      zipWithM_ (\i step -> putStrLn $ show i ++ ": " ++ show step) [1::Int ..] steps


cfg :: Exec.SearchEngine
cfg =
  Exec.AStar Exec.AStarConfiguration
    { evaluator =
        Exec.LMCount Exec.LMCountConfiguration
          { lmFactory =
              Exec.LMExhaust Exec.LMExhaustConfiguration
                { reasonableOrders = False
                , onlyCausalLandmarks = False
                , disjunctiveLandmarks = True
                , conjunctiveLandmarks = True
                , noOrders = False
                }
          , admissible = False
          , optimal = False
          , pref = True
          , alm = True
          , lpSolver = Exec.CPLEX
          , transform = Exec.NoTransform
          , cacheEstimates = True
          }
    , lazyEvaluator = Nothing
    , pruning = Exec.Null
    , costType = Exec.Normal
    , bound = Nothing
    , maxTime = Nothing
    }

• The Nix expression language computes the Nix store paths for the required packages. By simply referring to the variable that contains the build result, you can obtain the Nix store path of the package, without having to remember them yourself.
• Nix statically binds shared libraries to ELF binaries by modifying the binary's RPATH field. As a result, binaries no longer rely on the presence of their library dependencies in global locations (such as /lib), but use the libraries stored in isolation in the Nix store.
• The GNU linker (the ld command) has been wrapped to transparently add the paths of all the library package to the RPATH field of the ELF binary, whenever a dynamic library is provided.

• ELF executables require the presence of an ELF interpreter in /lib/ld-linux.so.2 (on x86) and /lib/ld-linux-x86-64.so.2 (on x86-64), which is impure and does not exist in NixOS.
• ELF binaries produced by conventional means typically have no RPATH configured. As a result, they expect libraries to be present in global namespaces, such as /lib. Since these directories do not exist in NixOS an executable will typically fail to work.

Automatic searching for library locations

$ patchelf --print-needed ./zipmix
libm.so.6
libc.so.6

$ export libs=/nix/store/7y10kn6791h88vmykdrddb178pjid5bv-glibc-2.27/lib:/nix/store/xh42vn6irgl1cwhyzyq1a0jyd9aiwqnf-zlib-1.2.11/lib

$ patchelf --print-interpreter ./zipmix
/lib64/ld-linux-x86-64.so.2

Dealing with multiple architectures

$ readelf -h ./zipmix
ELF Header:
  Magic:   7f 45 4c 46 02 01 01 00 00 00 00 00 00 00 00 00
  Class:                             ELF64
  Data:                              2's complement, little endian
  Version:                           1 (current)
  OS/ABI:                            UNIX - System V
  ABI Version:                       0
  Type:                              EXEC (Executable file)
  Machine:                           Advanced Micro Devices X86-64

Patching collections of binaries

$ autopatchelf ./bin

$ autopatchelf --no-recurse ./bin

$ autopatchelf ./zipmix

The result

{stdenv, fetchurl, autopatchelf, glibc}:

stdenv.mkDerivation {
  name = "kzipmix-20150319";
  src = fetchurl {
    url = http://static.jonof.id.au/dl/kenutils/kzipmix-20150319-linux.tar.gz;
    sha256 = "0fv3zxhmwc3p34larp2d6rwmf4cxxwi71nif4qm96firawzzsf94";
  };
  buildInputs = [ autopatchelf ];
  libs = stdenv.lib.makeLibraryPath [ glibc ];
  installPhase = ''
    ${if stdenv.system == "i686-linux" then "cd i686"
    else if stdenv.system == "x86_64-linux" then "cd x86_64"
    else throw "Unsupported system architecture: ${stdenv.system}"}
    mkdir -p $out/bin
    cp zipmix kzip $out/bin
    autopatchelf $out/bin
  '';
}

{stdenv, fetchurl, glibc, SDL, xlibs}:

stdenv.mkDerivation {
  name = "quake4-demo-1.0";
  src = fetchurl {
    url = ftp://ftp.idsoftware.com/idstuff/quake4/demo/quake4-linux-1.0-demo.x86.run;
    sha256 = "0wxw2iw84x92qxjbl2kp5rn52p6k8kr67p4qrimlkl9dna69xrk9";
  };
  buildInputs = [ autopatchelf ];
  libs = stdenv.lib.makeLibraryPath [ glibc SDL xlibs.libX11 xlibs.libXext ];

  buildCommand = ''
    # Extract files from the installer
    cp $src quake4-linux-1.0-demo.x86.run
    bash ./quake4-linux-1.0-demo.x86.run --noexec --keep
    # Move extracted files into the Nix store
    mkdir -p $out/libexec
    mv quake4-linux-1.0-demo $out/libexec
    cd $out/libexec/quake4-linux-1.0-demo
    # Remove obsolete setup files
    rm -rf setup.data
    # Patch ELF binaries
    autopatchelf .
    # Remove libgcc_s.so.1 that conflicts with Mesa3D's libGL.so
    rm ./bin/Linux/x86/libgcc_s.so.1
    # Create wrappers for the executables and ensure that they are executable
    for i in q4ded quake4
    do
        mkdir -p $out/bin
        cat > $out/bin/$i <<EOF
    #! ${stdenv.shell} -e
    cd $out/libexec/quake4-linux-1.0-demo
    ./bin/Linux/x86/$i.x86 "\$@"
    EOF
        chmod +x $out/libexec/quake4-linux-1.0-demo/bin/Linux/x86/$i.x86
        chmod +x $out/bin/$i
    done
  '';
}

{deployAndroidPackage, lib, package, os, autopatchelf, makeWrapper, pkgs, pkgs_i686}:

deployAndroidPackage {
  inherit package os;
  buildInputs = [ autopatchelf makeWrapper ];

  libs_x86_64 = lib.optionalString (os == "linux")
    (lib.makeLibraryPath [ pkgs.glibc pkgs.zlib pkgs.ncurses5 ]);
  libs_i386 = lib.optionalString (os == "linux")
    (lib.makeLibraryPath [ pkgs_i686.glibc pkgs_i686.zlib pkgs_i686.ncurses5 ]);

  patchInstructions = ''
    ${lib.optionalString (os == "linux") ''
      export libs_i386=$packageBaseDir/lib:$libs_i386
      export libs_x86_64=$packageBaseDir/lib64:$libs_x86_64
      autopatchelf $packageBaseDir/lib64 libs --no-recurse
      autopatchelf $packageBaseDir libs --no-recurse
    ''}

    wrapProgram $PWD/mainDexClasses \
      --prefix PATH : ${pkgs.jdk8}/bin
  '';
  noAuditTmpdir = true;
}

Discussion

Availability

Follow up

{deployAndroidPackage, lib, package, os, autoPatchelfHook, makeWrapper, pkgs, pkgs_i686}:

deployAndroidPackage {
  inherit package os;
  buildInputs = [ autoPatchelfHook makeWrapper ]
    ++ lib.optionalString (os == "linux") [ pkgs.glibc pkgs.zlib pkgs.ncurses5 pkgs_i686.glibc pkgs_i686.zlib pkgs_i686.ncurses5 ];

  patchInstructions = ''
    ${lib.optionalString (os == "linux") ''
      addAutoPatchelfSearchPath $packageBaseDir/lib
      addAutoPatchelfSearchPath $packageBaseDir/lib64
      autoPatchelf --no-recurse $packageBaseDir/lib64
      autoPatchelf --no-recurse $packageBaseDir
    ''}

    wrapProgram $PWD/mainDexClasses \
      --prefix PATH : ${pkgs.jdk8}/bin
  '';
  noAuditTmpdir = true;
}

• By adding the autoPatchelfHook package as a buildInput, we can invoke the autoPatchelf function in the builder environment and use it in any phase of a build process. To prevent the fixup hook from doing any work (that generalizes the patch process and makes the wrong assumptions for the Android SDK), the deployAndroidPackage function propagates the dontAutoPatchelf = true; parameter to the generic builder so that this fixup step will be skipped.
• The autopatchelf hook uses the packages that are specified as buildInputs to find the libraries it needs, whereas my implementation uses libs, libs_i386 or libs_x86_64 (or any other environment variable that is specified as a command-line parameter). It is robust enough to skip incompatible libraries, e.g. x86 libraries for x86-64 executables.
• My implementation works with colon separated library paths whereas autopatchelf hook works with Nix store paths making the assumption that there is a lib/ sub folder in which the libraries can be found that it needs. As a result, I no longer use the lib.makeLibraryPath function.
• In some cases, we also want the autopatchelf hook to inspect non-standardized directories, such as uncommon directories in the same package. To make this work, we can add additional paths to the search cache by invoking the addAutoPatchelfSearchPath function.

Nix users value its isolated, repeatable builds and simple sharing of development environments. Nix makes it easy to go back in time and rebuild software from years ago without issue.

At the same time, the value of the container ecosystem is huge. Tying in to the schedulers, orchestration, and monitoring is very valuable.

Nix has been able to generate Docker images for several years now, however the typical approach to layering with Nix is to generate one fat image with all of the dependencies. This fat image offers no sharing, is slow to build, upload, and download.

In this post I talk about how I fix this problem and use Nix to automatically create multi-layered Docker images, allowing a high amount of caching between images.

Docker uses layers

Docker’s use of layering is well known, and its benefits are undeniable: sharing a “base” system is a simple abstraction which allows extending a well known image with your own code.

A Docker image is a sequence of layers, where each member is a filesystem diff, adding and removing files from its parent member:

Efficient layering is hard because there are no rules

When there are no restrictions on what a command will do, the only way to fully capture its effects is to snapshot the full filesystem.

Most package managers will write files to shared global directories like /usr, /bin, and /etc.

This means that the only way to represent the changes between installing package A and installing package B is to take a full snapshot of the filesystem.

As a user you might manually create rules to improve the behavior of the cache: add your code towards the end of a Dockerfile, or install common libraries in a single RUN instruction, even if you don’t want them all.

These rules make sense: If a Dockerfile adds code and then installs packages, Docker can’t cache the installation because it can’t know that the package installation isn’t influenced by the code addition. Docker also can’t know that installing package A has nothing to do with package B and the changes are separately cachable.

With restrictions, we can make better optimisations

Nix does have rules.

The most important and relevant rule when considering distribution and Docker layers is:

A package build can’t write to arbitrary places on the disk.

A build can only write to a specific directory known as $out, like /nix/store/ibfx7ryqnqf01qfzj4v7qhzhkd2v9mm7-file-5.34. When you add a new package to your system, you know it didn’t modify /etc or /bin.

How does file find its dependencies? It doesn’t – they are hard-coded:

$ ldd /nix/store/ibfx7ryqnqf01qfzj4v7qhzhkd2v9mm7-file-5.34/bin/file
	linux-vdso.so.1
	/nix/store/ibfx7ryqnqf01qfzj4v7qhzhkd2v9mm7-file-5.34/lib/libmagic.so.1
	/nix/store/bv6znzsv2qkbcwwa251dx7n5dshz3nr3-zlib-1.2.11/lib/libz.so.1
	/nix/store/fg4yq8i8wd08xg3fy58l6q73cjy8hjr2-glibc-2.27/lib/libc.so.6
	/nix/store/fg4yq8i8wd08xg3fy58l6q73cjy8hjr2-glibc-2.27/lib/ld-linux-x86-64.so.2

This provides great, cache-friendly properties:

1. You know exactly what path changed when you added file.
2. You know exactly what paths file depends on.
3. Once a path is created, it will never change again.

Think graphs, not layers

If you consider the properties Nix provides, you can see it already constructs a graph internally to represent software and its dependencies: it natively has a better understanding of the software than Docker is interested in.

Specifically, Nix uses a Directed Acyclic Graph to store build output, where each node is a specific, unique, and immutable path in /nix/store:

Or to use a real example, Nix itself can render a graph of a package’s dependencies:

Flattening Graphs to Layers

In a naive world we can simply walk the tree and create a layer out of each path:

and this image is valid: if you pulled any of these layers, you would automatically get all the layers below it, resulting in a complete set of dependencies.

Things get a bit more complicated for a graph with a wider graph, how do you flatten something like Bash:

If we had to flatten this to an ordered sequence, obviously bash-interactive-4.4-p23 is at the top, but does readline-7.0p5 come next? Why not bash-4.4p23?

It turns out we don’t have to solve this problem exactly, because I lied about how Docker represents layers.

How Docker really represents an Image

Docker’s layers are content addressable and aren’t required to explicitly reference a parent layer. This means a layer for readline-7.0p5 doesn’t have to mention that it has any relationship to ncurses-6.1 or glibc-2.27 at all.

Instead each image has a manifest which defines the order:

{
  "Layers": [
    "bash-interactive-4.4-p23",
    "bash-4.4p23",
    "readline-7.0p5",
     ...
  ]
}

If you have only built Docker images using a Dockerfile, then you would expect the way we flatten our graph to be critically important. If we sometimes picked readline-7.0p5 to come first and other times picked bash-4.4p23 then we may never make cache hits.

However since the Image defines the order, we don’t have to solve this impossible problem: we can order the layers in any way we want and the layer cache will always hit.

Docker doesn’t support an infinite number of layers

Docker has a limit of 125 layers, but big packages with lots of dependencies can easily have more than 125 store paths.

It is important that we still successfully build an image if we go over this limit, but what do we do with the extra layers?

In the interest of shortness, let’s pretend Docker only lets you have four layers, and we want to fit five. Out of the Bash example, which two paths do we combine in to one layer?

• bash-interactive-4.4-p23
• bash-4.4p23
• readline-7.0p5
• ncurses-6.1
• glibc-2.27

Smushing Layers

I decided the best solution is to combine the layers which are less likely to be a cache hit with other software. Picking the most low level, fundamental paths and making them a separate layer means my next image will most likely also share some of those layers too.

Ideally it would end up with at least glibc, and ncurses in separate layers. Visually, it is hard to tell if either readline or bash-4.4p23 would be better served as an individual layer. One of them should be, certainly.

My actual solution

My prioritization algorithm is a simple graph-based popularity contest. The idea is to weight each node more heavily the deeper and more references they have.

Starting with the dependency graph of Bash from before,

we first duplicate nodes in the graph so each node is only pointed to once:

we then replace each leaf node with a counter, starting at 1:

each node whose only children are counters are then combined with their children, and their children’s counters summed, then incremented:

we then repeat the process:

we repeat this process until there is only one node:

and finally we sort the paths in each popularity bucket by name to ensure the list is consistently generated to get the paths ordered by cachability:

• glibc-2.27: 10
• ncurses-6.1: 4
• bash-4.4-p23: 2
• readline-7.0p5: 2
• bash-interactive-4.4-p23: 1

This solution has properly put foundational paths which are most commonly referred to at the top, improving its chances of cache hit. The algorithm has also put the likely-to-change application right at the bottom in case the last layers need to be combined.

Let’s consider a much larger image. In this image, we set the maximum number of layers to 120, but the image has 200 store paths. Under this design the 119 most fundamental store paths will have their own layers, and we store the remaining 81 paths together in the 120th layer.

With this new approach of automatically layering store paths I can now generate images with very efficient caching between different images.

For a practical example of a PHP application with a MySQL database.

First we build a MySQL image:

# mysql.nix
let
  pkgs = import (builtins.fetchTarball {
    url = "https://github.com/grahamc/nixpkgs/archive/layered-docker-images.tar.gz";
    sha256 = "05a3jjcqvcrylyy8gc79hlcp9ik9ljdbwf78hymi5b12zj2vyfh6";
  }) {};
in pkgs.dockerTools.buildLayeredImage {
  name = "mysql";
  tag = "latest";
  config.Cmd = [ "${pkgs.mysql}/bin/mysqld" ];
  maxLayers = 120;
}

$ nix-build ./mysql.nix
$ docker load < ./result

Then we build a PHP image:

# php.nix
let
  pkgs = import (builtins.fetchTarball {
    url = "https://github.com/grahamc/nixpkgs/archive/layered-docker-images.tar.gz";
    sha256 = "05a3jjcqvcrylyy8gc79hlcp9ik9ljdbwf78hymi5b12zj2vyfh6";
  }) {};
in pkgs.dockerTools.buildLayeredImage {
  name = "grahamc/php";
  tag = "latest";
  config.Cmd = [ "${pkgs.php}/bin/php" ];
  maxLayers = 120;
}

$ nix-build ./php.nix
$ docker load < ./result

and export the two image layers:

$ docker inspect mysql | jq -r '.[] | .RootFS.Layers | .[]' | sort > mysql
$ docker inspect php | jq -r '.[] | .RootFS.Layers | .[]' | sort > php

and look at this, the PHP and MySQL images share twenty layers:

$ comm -1 -2 php mysql
sha256:0296e7b7d4b7d593fc533f06c5cc22f56c99c8ab0ed4301a6c7829ce8b18c6fa
sha256:1114fa18ba6be7e5db7728ae747a6bf0aab48fedf3ed9e95aff1f9ce51903698
sha256:181ca82fe4d920b46488d29b507d432dd121d9b2842cf8c720c0939e03e4d6a0
sha256:190b2db337109cb9692cd004aeed4b06fef0c10c700a9ba7939d73e697e3bbcc
sha256:1c4afa44a489abf7c7fe8fa642647a8a2786bf7581486e6a308e1078484784e6
sha256:424ad95540cb66adb9e16d768ccc7010923a9ca09dda1f56e4a08804c2de12e6
sha256:537b4796037a46b64fa39c42f642925704abbaab475e5c72a8fc15c258dc1e85
sha256:69bf797b6b6763938b98139814d8be884693806e0e5a50ac4fbbf11eb45f4f27
sha256:6c7f6a555dee6eebfc5497e84b1cacb4fff035e2101d8421768c0c2db54e8da2
sha256:7dcff293e9f411c63d6f1365795a89ac0058995de0f192ad9fb103ab56533ed3
sha256:86b1c4990ca1c80ad5dc0977fe37ab0f80e0f95e03fe79769b451d97e9f7a8f3
sha256:9d8278ca2542af2ff9cf2d8de439758f6b3bbb84bbe6b7a44edf8080b73d2949
sha256:a5c8632ba0135b465956281008a4f9c2263232d92c020b56e1d839aaa4b74834
sha256:b9fe88bf1364613ec01968480d7cb305d69e3de78bb4a56e3448298ffcc25139
sha256:c0c9c2eaa522dd31901c49a40577a68e3ae02cc75226a248813134046b299099
sha256:c2f4e79836f999ff389b82b8636b807c2baa5b702509b2991e651508519857d5
sha256:cdfb1dfb3ca2f8df9e87e5fa33b91a402a8b4ad0ede164dbdf4c25aded618ed3
sha256:ffd8e3d222cb85f642677642037a0e7886a565babdc0e229cc83147895a8ed2c
sha256:ffecd238fa95b110a1b5f71034b2bd358358758abb52fd098241200d94111979

Where before you wouldn’t bother trying to have your application and database images share layers, with Nix the layer sharing is completely automatic.

The automatic splitting and prioritization has improved image push and fetch times by an order of magnitude. Having multiple images allows Docker to request more than one at a time.

Thank you Target for having sponsored this work with Tweag in NixOS/nixpkgs#47411.

{stdenv, foo, bar}:
{name, buildInputs ? [], ...}@args:

let
  extraArgs = removeAttrs args [ "name" "buildInputs" ];
in
stdenv.someBuildFunction ({
  name = "mypackage-"+name;
  buildInputs = [ foo bar ] ++ buildInputs;
} // extraArgs)

• The outer function header (first line) specifies all common build-time dependencies required to build a project. For example, if we want to build a function abstraction for Python projects, then python is such a common build-time dependency.
• The inner function header specifies all relevant build parameters and accepts an arbitrary number of arguments. Some arguments have a specific purpose for the kind of software project that we want to build (e.g. name and buildInputs) while other arguments can be passed verbatim to the build function abstraction that we use as a basis.
• In the body, we invoke a function abstraction (quite frequently stdenv.mkDerivation {}) that builds the project. We use the build parameters that have a specific meaning to configure specialized build properties and we pass all remaining build parameters that are not conflicting verbatim to the build function that we use a basis.
  
  A subset of these arguments have no specific meaning and are simply exposed as environment variables in the builder environment.
  
  Because some parameters are already being used for a specific purpose and others may be incompatible with the build function that we invoke in the body, we compose a variable named: extraArgs in which we remove the conflicting arguments.

• A build procedure is extendable/tweakable -- we can adjust the build procedure by adding or changing the build phases, and tweak them by providing build hooks (that execute arbitrary command-line instructions before or after the execution of a phase). This is particularly useful to build additional abstractions around it for more specialized deployment procedures.
• Because an arbitrary number of arguments can be propagated (that can be exposed as environment variables in the build environment), we have more configuration flexibility.

Deploying SDKs

with import <nixpkgs> {};

let
  androidComposition = androidenv.composeAndroidPackages {
    toolsVersion = "25.2.5";
    platformToolsVersion = "27.0.1";
    buildToolsVersions = [ "27.0.3" ];
    includeEmulator = true;
    emulatorVersion = "27.2.0";
  };
in
androidComposition.androidsdk

$ nix-build
/nix/store/zvailnl4f1261cn87s9n29lhj9i7y7iy-androidsdk

Writing build function abstractions for SDKs

{composeMySDK, stdenv}:
{foo, bar, ...}@args:

let
  mySDKFormalArgs = builtins.functionArgs composeMySDK;
  mySDKArgs = builtins.intersectAttrs mySDKFormalArgs args;
  mySDK = composeMySDK mySDKArgs;
  extraArgs = removeAttrs args ([ "foo" "bar" ]
    ++ builtins.attrNames mySDKFormalArgs);
in
stdenv.mkDerivation ({
  buildInputs = [ mySDK ];
  buildPhase = ''
    ${mySDK}/bin/build
  '';
} // extraArgs)

• First, we dynamically extract the formal arguments of the function that composes the SDK (mySDKFormalArgs).
• Then, we compute the intersection of the formal arguments of the composition function and the actual arguments from the build function arguments set (args). The resulting attribute set (mySDKArgs) are the actual arguments we need to propagate to the SDK composition function.
• The next step is to deploy the SDK with all its plugins by propagating the SDK arguments set as function parameters to the SDK composition function (mySDK).
• Finally, we remove the arguments that we have passed to the SDK composition function from the extra arguments set (extraArgs), because these parameters have no specific meaning for the build procedure.

{androidenv}:

androidenv.buildApp {
  # Build parameters
  name = "MyFirstApp";
  src = ../../src/myfirstapp
  antFlags = "-Dtarget=android-16";

  # SDK composition parameters
  platformVersions = [ 16 ];
  toolsVersion = "25.2.5";
  platformToolsVersion = "27.0.1";
  buildToolsVersions = [ "27.0.3" ];
}

• The above function invocation propagates three build parameters: name referring to the name of the Nix package, src referring to a filesystem location that contains the source code of an Android project, and antFlags that contains command-line arguments that are passed to the Apache Ant build tool.
• It propagates four SDK composition parameters: platformVersions referring to the platform SDKs that must be installed, toolsVersion to the version of the tools package, platformToolsVersion to the platform-tools package and buildToolsVersion to the build-tool packages.

Availability

Munich NixOS Meetup

There are no talks or specific topics planned for now.

If you are interested in giving a talk, feel free to ask us, otherwise we will have a casual discussion session, help each other on issues and hack away at bugs we find or features we'd like!

Anyone is welcome, no matter if you haven't started using Nix(OS), yet or are using it in production!

Drinks and food will be provided.

München - Germany

Thursday, September 20 at 7:00 PM

17

https://www.meetup.com/Munich-NixOS-Meetup/events/254554928/

Cachix - Nix binary cache as a service was down:

• On Aug 22nd from 16:55 until 18:55 UTC (120 minutes)
• On Aug 23rd from 20:01 until 20:09 UTC (8 minutes)

On the 22nd there was no action from my side; the service recovered itself. I did have monitoring configured and I received email alerts, but I have not noticed them.

I have spent most of the 23rd gathering data and evidence on what went wrong. Just before monitoring stopped receiving data at 16:58 UTC, white-box system monitoring revealed:

• Outgoing bandwidth skyrocketed to 23MB/s
• Resident memory went through the roof to ~90%

On 23rd I have immediately seen the service was down and I've rebooted the machine.

I have spent a significant amount of time trying to determine if a specific request caused this, but it seems likely that it was just an overload, although I have not proved this theory.

Countermeasures taken

a) Server-side is implemented in GHC Haskell, so I have enabled -O2. Although GHC wiki on Performance says it is indistinguishable from -O1, in the last week I've seen an approximately 10% reduction of resident memory and most importantly, fewer memory spikes. Again, no hard evidence, time will tell.

b) Most importantly, production now runs with GHCRTS='-M2G' flag, limiting overall heap to 2G of memory, so we are not depending on the Linux OOM killer to handle out of memory situations. It is not entirely clear to me why the machine was unresponsive for two hours since OOM should have kicked in, but during that period there was not a single monitoring datapoint sent.

c) I have configured EKG to send GC stats to datadog so if it happens again, that should provide better insight into what is going on with memory consumption.

Countermeasures to be taken

1) Use a service like Pagerduty to be alerted immediately on the phone

2) Upgrade Datadog agent to version 6, which allows more precise per process monitoring

So far I am quite happy how Haskell works in production. I have taken Well-Typed training on GHC performance and if this turns out to be a space leak, I am confident that I will find it.

The only thing that saddens me, coming from Python, is that GHC has poor profiling options for long-running programs. Compiling GHC with profiling options significantly slows the performance. There is unmerged work making the GHC eventlog useful for such cases, but the state of this work is unclear.

Looking forward

So there it is, the first operational issue with Cachix. Despite this issue, I am happy to have made the choices that both allow me to respond quickly to the needs of Nix community, yet still allow me to further improve and stabilize the code with confidence as the product matures.

Speaking of maturing the product, I will share another announcement soon!

• Making sure that all dependencies of an app are present, such as a database for storage.
• Executing all relevant deployment activities to make an app available for use.
• Upgrading is risky and difficult -- it may break the application and introduce downtime.

Using tools from the Nix project

Automating Mendix application deployments with Nix

• We must obtain the Mendix runtime that interprets the Mendix models. Packaging the Mendix runtime in Nix is fairly straight forward -- simply unzipping the distribution, and moving the package contents into the Nix store, and adding a wrapper script launches the runtime suffices.
• We must produce a Mendix Deployment Archive (MDA file) that creates a Zip container with all artifacts required to run a Mendix app by the runtime. An MDA file can be produced from a Mendix project by invoking the MxBuild tool. Since MxBuild is required for this, I had to package it as well. Packaging mxbuild is a bit trickier, as it requires mono and Node.js.

Building an MDA file with Nix

{stdenv, mxbuild, jdk, nodejs}:
{name, mendixVersion, looseVersionCheck ? false, buildInputs ? [], ...}@args:

let
  mxbuildPkg = mxbuild."${mendixVersion}";
  extraArgs = removeAttrs args [ "buildInputs" ];
in
stdenv.mkDerivation ({
  buildInputs = [ mxbuildPkg nodejs ] ++ buildInputs;
  installPhase = ''
    mkdir -p $out
    mxbuild --target=package \
      --output=$out/${name}.mda \
      --java-home ${jdk} \
      --java-exe-path ${jdk}/bin/java \
      ${stdenv.lib.optionalString looseVersionCheck "--loose-version-check"} \
      "$(echo *.mpr)"
    mkdir -p $out/nix-support
    echo "file binary-dist \"$(echo $out/*.mda)\"" > $out/nix-support/hydra-build-products
  '';
} // extraArgs)

{ pkgs ? import  { inherit system; }                                                                                                                             
, system ? builtins.currentSystem
}:

let
  mendixPkgs = import ./nixpkgs-mendix/top-level/all-packages.nix {
    inherit pkgs system;
  };
in
mendixPkgs.packageMendixApp {
  name = "conferenceschedule";
  src = /home/sander/SharedWindowsFolder/ConferenceSchedule-main;
  mendixVersion = "7.13.1";
}

$ nix-build conferenceschedule.nix 
/nix/store/nbaa7fnzi0xw9nkf27mixyr9awnbj16i-conferenceschedule
$ ls /nix/store/nbaa7fnzi0xw9nkf27mixyr9awnbj16i-conferenceschedule
conferenceschedule.mda  nix-support

Running a Mendix application

• We must unzip the MDA file into a directory with write permissions.
• We must create writable state sub directories, e.g. data/tmp, data/files.
• After starting the runtime, we must configure the admin interface, to send instructions to the runtime to initialize the database and start the app:
  

  
  $ export M2EE_ADMIN_PORT=9000
  $ export M2EE_ADMIN_PASS=secret
  

• Finally, we must communicate over the admin interface to configure, initialize the database and start the app:
  

  
  curlCmd="curl -X POST http://localhost:$M2EE_ADMIN_PORT \
  -H 'Content-Type: application/json' \
  -H 'X-M2EE-Authentication: $(echo -n "$M2EE_ADMIN_PASS" | base64)' \
  -H 'Connection: close'"
  $curlCmd -d '{ "action": "update_appcontainer_configuration", "params": { "runtime_port": 8080 } }'
  $curlCmd -d '{ "action": "update_configuration", "params": { "DatabaseType": "HSQLDB", "DatabaseName": "myappdb", "DTAPMode": "D" } }'
  $curlCmd -d '{ "action": "execute_ddl_commands" }'
  $curlCmd -d '{ "action": "start" }'
  

NixOS integration

{pkgs, ...}:

{
  ...

  systemd.services.mendixappcontainer =
    let
      runScripts = ...
      appContainerConfigJSON = ...
      configJSON = ...
    in {
      enable = true;
      description = "My Mendix App";
      wantedBy = [ "multi-user.target" ];
      environment = {
        M2EE_ADMIN_PASS = "secret";
        M2EE_ADMIN_PORT = "9000";
        MENDIX_STATE_DIR = "/home/mendix";
      };
      serviceConfig = {
        ExecStartPre = "${runScripts}/bin/undeploy-app";
        ExecStart = "${runScripts}/bin/start-appcontainer";
        ExecStartPost = "${runScripts}/bin/configure-appcontainer ${appContainerConfigJSON} ${configJSON}";
      };
    };

• The undeploy-app script removes all non-state artefacts from the working directory.
• The start-appcontainer script starts the Mendix runtime.
• The configure-appcontainer script configures the runtime, such as the embedded Jetty server and the database, and starts the application.

{pkgs, ...}:

{
  require = [ ../nixpkgs-mendix/nixos/modules/mendixappcontainer.nix ];

  services = {
    openssh.enable = true;

     mendixAppContainer = {
       enable = true;
       adminPassword = "secret";
       databaseType = "HSQLDB";
       databaseName = "myappdb";
       DTAPMode = "D";
       app = import ../../conferenceschedule.nix {
         inherit pkgs;
         inherit (pkgs.stdenv) system;
      };
    };
  };

  networking.firewall.allowedTCPPorts = [ 8080 ];
}

• The password for communicating over the admin interface.
• The type of database we want to use (in this particular case an in memory HSQLDB instance) and the name of the database.
• Whether we want to use the application in development (D), test (T), acceptance (A) or production (P) mode.
• A reference to the MDA that we want to deploy (deployed by a Nix expression that invokes the Mendix build function abstraction shown earlier).

$ nixos-rebuild switch

Conclusion

• A Nix function that can be used to compile an MDA file from a Mendix project.
• Generated scripts that configure and launch the runtime and the application.
• A NixOS module that can be used to deploy a running Mendix app as part of a NixOS machine configuration.

Future work

Availability

Acknowledgements

EPYC vs m1.xlarge.x86

Nix is a powerful package manager for Linux and other Unix systems that makes package management reliable and reproducible. It provides atomic upgrades and rollbacks, side-by-side installation of multiple versions of a package, multi-user package management and easy setup of build environments.

The Nix community has collected and curated build instructions (expressions) for many thousands of packages in the Nix package collection, Nixpkgs. The collection is a large GitHub repository, which receives over a thousand pull requests each month. Some of these changes can sometimes cause all of the packages to rebuild.

To test changes to Nixpkgs and release updates for Nix and NixOS, we necessarily created our own build infrastructure. This allows us to give better quality guarantees to our users.

The NixOS infrastructure team runs several types of servers: VMs on AWS, bare metal, macOS systems, among others. We build thousands of packages a day, sometimes reaching many tens of thousands per day.

Some of our builds depend on unique features like KVM which are only available by using bare metal servers, and all of them benefit from numerous, powerful cores.

For over a year now, Packet.net (where you can natively deploy NixOS by the way!) has been generously providing bare metal hardware build resources for the NixOS build farm, and together we were curious how the new EPYC from AMD would compare to the hardware we were already using.

For this benchmark we are comparing Packet’s m1.xlarge.x86 against Packet’s first EPYC machine, c2.medium.x86. Hydra already runs a m1.xlarge.x86 build machine, so the comparison will be helpful in deciding if we should replace it with EPYC hardware.

AMD EPYC has the chance to reduce our hardware footprint, reduce our need for our AWS scale-out, and improve our turnaround time for time-sensitive security patches.

System Comparison:

Benchmark Methods

All of these tests were run on a fresh Packet.net server running NixOS 18.03 and building Nixpkgs revision 49a6964a425.

For each test, I ran each build five times on each machine with --check which forces a local rebuild:

checkM() {
  nix-build . -A "$1"
  for i in $(seq 1 5); do
    rm result
    nix-collect-garbage
    /run/current-system/sw/bin/time -ao "./time-$1" \
      nix-build . -A "$1" --check
  done
}

Benchmark Results

Kernel Builds

NixOS builds a generously featureful kernel by default, and the build can take some time. However, the compilation is easy to spread across multiple cores. In what we will further see is a theme, the EPYC beat the Intel CPU with by about five minutes, or about 35% speed-up.

nix-build '<nixpkgs>' -A linuxPackages.kernel

NixOS Tests

The NixOS release process is novel in that package updates happen automatically as an entire cohesive set. We of course test that specific software compiles properly, but we are also able to perform fully automatic integration tests. We test that the operating system can boot, desktop environments work, and even server tests like validating that our MySQL server replication is still working. These tests happen automatically on every release and is a unique benefit to the Nix build system being applied to an operating system.

These tests use QEMU and KVM, and spawn one or more virtual machines running NixOS.

Plasma5 and KDE

The Plasma5 test looks like the following:

1. First launches a NixOS VM configured to run the Plasma5 desktop manager.

2. Uses Optical Character Recognition to wait until it sees the system is ready for Alice to log in and then types in her password:

   $machine->waitForText(qr/Alice Foobar/);
   $machine->sendChars("foobar\n");
   

3. Waits for the Desktop to be showing, which reliably indicates she has finished logging in:

   $machine->waitForWindow("^Desktop ");
   

4. Launches Dolphin, Konsole, and Settings and waits for each window to appear before continuing:

   $machine->execute("su - alice -c 'dolphin &'");
   $machine->waitForWindow(" Dolphin");
   $machine->execute("su - alice -c 'konsole &'");
   $machine->waitForWindow("Konsole");
   $machine->execute("su - alice -c 'systemsettings5 &'");
   $machine->waitForWindow("Settings");
   

5. If all of these work correctly, the VM shuts down and the tests pass.

Better than the kernel tests, we’re pushing a 40% improvement.

nix-build '<nixpkgs/nixos/tests/plasma5.nix>'

MySQL Replication

The MySQL replication test launches a MySQL master and two slaves, and runs some basic replication tests. NixOS allows you to define replication as part of the regular configuration management, so I will start by showing the machine configuration of a slave:

    {
      services.mysql.replication.role = "slave";
      services.mysql.replication.serverId = 2;
      services.mysql.replication.masterHost = "master";
      services.mysql.replication.masterUser = "replicate";
      services.mysql.replication.masterPassword = "secret";
    }

1. This test starts by starting the $master and waiting for MySQL to be healthy:

   $master->start;
   $master->waitForUnit("mysql");
   $master->waitForOpenPort(3306);
   

2. Continues to start $slave1 and $slave2 and wait for them to be up:

   $slave1->start;
   $slave2->start;
   $slave1->waitForUnit("mysql");
   $slave2->waitForUnit("mysql");
   $slave1->waitForOpenPort(3306);
   $slave2->waitForOpenPort(3306);
   

3. It then validates some of the scratch data loaded in to the $master has replicated properly to $slave2:

   $slave2->succeed("
        echo 'use testdb; select * from tests' \
            | mysql -u root -N | grep 4
   ");
   

4. Then shuts down $slave2:

   $slave2->succeed("systemctl stop mysql");
   

5. Writes some data to the $master:

   $master->succeed("
        echo 'insert into testdb.tests values (123, 456);' \
            | mysql -u root -N
   ");
   

6. Starts $slave2, and verifies the queries properly replicated from the $master to the slave:

   $slave2->succeed("systemctl start mysql");
   $slave2->waitForUnit("mysql");
   $slave2->waitForOpenPort(3306);
   $slave2->succeed("
        echo 'select * from testdb.tests where Id = 123;' \
            | mysql -u root -N | grep 456
   ");
   

Due to the multiple VM nature, and increased coordination between the nodes, we saw a 30% increase.

nix-build '<nixpkgs/nixos/tests/mysql-replication.nix>'

BitTorrent

The BitTorrent test follows the same pattern of starting and stopping a NixOS VM, but this test takes it a step further and tests with four VMs which talk to each other. I could do a whole post just on this test, but in short:

• a machine serving as the tracker, named $tracker.
• a client machine, $client1
• another client machine, $client2
• a router which facilitates some of the incredible things this test is actually doing.

I’m going to gloss over the details here, but:

1. The $tracker starts seeding a file:

   $tracker->succeed("opentracker -p 6969 &");
   $tracker->waitForOpenPort(6969);
   my $pid = $tracker->succeed("transmission-cli \
        /tmp/test.torrent -M -w /tmp/data");
   

2. $client1 fetches the file from the tracker:

   $client1->succeed("transmission-cli \
        http://tracker/test.torrent -w /tmp &");
   

3. Kills the seeding process on tracker so now only $client1 is able to serve the file:

   $tracker->succeed("kill -9 $pid");
   

4. $client2 fetches the file from $client1:

   $client2->succeed("transmission-cli \
        http://tracker/test.torrent -M -w /tmp &");
   

If both $client1 and $client2 receive the file intact, the test passes.

This test sees a much lower performance improvement, largely due to the networked coordination across four VMs.

nix-build '<nixpkgs/nixos/tests/bittorrent.nix>'

The remarkable part I left out is Client1 uses UPnP to open a port of the firewall of the router which Client2 uses to read from Client1.

Standard Environment

Our standard build environment, stdenv, is at the deepest part of this tree and almost nothing can be built until after it is completed. stdenv is like build-essential on Ubuntu.

This is an important part of the performance story for us: Nix builds are represented by a tree, where Nix will schedule as many parallel builds as possible as long as its parents are done building. Single core performance is the primary factor impacting how long these builds take. Shaving off even a few minutes means our entire build cluster is able to get to share the work sooner.

For this reason, the stdenv test is the one exception to the methodology. I wanted to test a full build from bootstrap to a working standard build environment. To force this, I changed the very root build causing everything “beneath” it to require a rebuild by applying the following patch:

diff --git a/pkgs/stdenv/linux/default.nix b/pkgs/stdenv/linux/default.nix
index 63b4c8ecc24..1cd27f216f9 100644
--- a/pkgs/stdenv/linux/default.nix
+++ b/pkgs/stdenv/linux/default.nix
@@ -37,6 +37,7 @@ let

   commonPreHook =
     ''
+
       export NIX_ENFORCE_PURITY="''${NIX_ENFORCE_PURITY-1}"
       export NIX_ENFORCE_NO_NATIVE="''${NIX_ENFORCE_NO_NATIVE-1}"
       ${if system == "x86_64-linux" then "NIX_LIB64_IN_SELF_RPATH=1" else ""}

The impact on build time here is stunning and makes an enormous difference: almost a full 20 minutes shaved off the bootstrapping time.

nix-build '<nixpkgs>' -A stdenv

Conclusion

This EPYC machine has made a remarkable improvement in our build times and is helping the NixOS community push timely security updates and software updates to users and businesses alike. We look forward to expanding our footprint to keep up with the incredible growth of the Nix project.

Thank you to Packet.net for providing this hardware free of charge for this test through their EPYC Challenge.

and thank you Gustav, Daiderd, Andi, and zimbatm for their help with this article

with import <nixpkgs> {};

stdenv.mkDerivation {
  name = "hello-2.10";

  src = fetchurl {
    url = mirror://gnu/hello/hello-2.10.tar.gz;
    sha256 = "0ssi1wpaf7plaswqqjwigppsg5fyh99vdlb9kzl7c9lng89ndq1i";
  };

  meta = {
    description = "A program that produces a familiar, friendly greeting";
    longDescription = ''
      GNU Hello is a program that prints "Hello, world!" when you run it.
      It is fully customizable.
    '';
    homepage = http://www.gnu.org/software/hello/manual/;
    license = "GPLv3+";
  };
}

$ nix-build
/nix/store/188avy0j39h7iiw3y7fazgh7wk43diz1-hello-2.10

• Build scripts can only write to designated output directories and temp directories. They are restricted from writing to any other file system location.
• All environment variables are cleared and some of them are set to default or dummy values, such as search path environment variables (e.g. PATH).
• All build results are made immutable by removing the write permission bits and their timestamps are reset to one second after the epoch.
• Running builds as unprivileged users.
• Optionally, builds run in a chroot environment and use namespaces to restrict access to the host filesystem and the network as much as possible.

Writing "raw" derivations

derivation {
  name = "test";
  builder = ./test.sh;
  system = "x86_64-linux";
  person = "Sander";
}

• The name attribute specifies the name of the package, that should appear in the resulting Nix store path.
• The builder attribute specifies that the test.sh executable should be run inside the pure build environment.
• The system attribute is used to tell Nix that this build should be carried out for x86-64 Linux systems. When Nix is unable to build the package for the requested system architecture, it can also delegate a build to a remote machine that is capable.
• All attributes (including the attributes described earlier) are converted to environment variables (e.g. strings, numbers and URLs are converted to strings and the boolean value: 'true' is converted to '1') and can be used by the builder process for a variety of reasons.

#!/bin/sh -e

echo "Hello $person" > $out

$ nix-build
/nix/store/7j4y5d8rx1vah5v64bpqd5dskhwx5105-test
$ cat result
Hello Sander

$ nix repl
Welcome to Nix version 2.0.4. Type :? for help.

nix-repl> test = import ./default.nix

nix-repl> :t test
a set

nix-repl> builtins.attrNames test
[ "all" "builder" "drvAttrs" "drvPath" "name" "out" "outPath" "outputName" "person" "system" "type" ]

• The type attribute that refers to the string: "derivation".
• The drvAttrs attribute refers to an attribute set containing the original parameters passed to derivation {}.
• drvPath and outPath refer to the Nix store paths of the store derivation file and output of the build. A side effect of requesting these members is that the expression gets evaluated or built.
• The out attribute is a reference to the derivation producing the out result, all is a list of derivations of all outputs produced (Nix derivations can also produce multiple output paths in the Nix store).
• In case there are multiple outputs, the outputName determines the name of the output path that is the default.

Providing basic dependencies

{bash, basePackages, system}:

let
  shell = "${bash}/bin/sh";
in
derivation {
  name = "stdenv";
  inherit shell basePackages system;
  builder = shell;
  args = [ "-e" ./builder.sh ];
}

set -e

# Setup PATH for base packages
for i in $basePackages
do
    basePackagesPath="$basePackagesPath${basePackagesPath:+:}$i/bin"
done

export PATH="$basePackagesPath"

# Create setup script
mkdir $out
cat > $out/setup <<EOF
export SHELL=$shell
export PATH="$basePackagesPath"
EOF

# Allow the user to install stdenv using nix-env and get the packages
# in stdenv.
mkdir $out/nix-support
echo "$basePackages" > $out/nix-support/propagated-user-env-packages

{stdenv}:

derivation {
  name = "hello";
  inherit stdenv;
  builder = ./builder.sh;
  system = "x86_64-linux";
}

#!/bin/sh -e
source $stdenv/setup

mkdir -p $out/bin

cat > $out/bin/hello <<EOF
#!$SHELL -e

echo "Hello"
EOF

chmod +x $out/bin/hello

Writing more simple derivations

{stdenv, system, shell}:
{builder, ...}@args:

let
  extraArgs = removeAttrs args [ "builder" "meta" ];

  buildResult = derivation ({
    inherit system stdenv;
    builder = shell; # Make bash the default builder
    args = [ "-e" builder ]; # Pass builder executable as parameter to bash
    setupSimpleDerivation = ./setup.sh;
  } // extraArgs);
in
buildResult //
# Readd the meta attribute to the resulting attribute set
(if args ? meta then { inherit (args) meta; } else {})

{stdenv}:

stdenv.simpleDerivation {
  name = "hello";
  builder = ./builder.sh;
  meta = {
    description = "This is a simple testcase";
  };
}

{stdenv, fetchurl, gnumake, gnutar, gzip, gcc, binutils}:

stdenv.simpleDerivation {
  name = "hello-2.10";
  src = fetchurl {
    url = mirror://gnu/hello/hello-2.10.tar.gz;
    sha256 = "0ssi1wpaf7plaswqqjwigppsg5fyh99vdlb9kzl7c9lng89ndq1i";
  };
  inherit stdenv gnumake gnutar gzip gcc binutils;
  builder = ./builder.sh;
}

source $setupSimpleDerivation

export PATH=$PATH:$gnumake/bin:$gnutar/bin:$gzip/bin:$gcc/bin:$binutils/bin

tar xfv $src
cd hello-2.10
./configure --prefix=$out
make
make install

The run command abstraction

{stdenv}:

stdenv.runCommand {
  name = "hello";
  buildCommand = ''
    mkdir -p $out/bin
    cat > $out/bin/hello <<EOF
    #! ${stdenv.shell} -e

    echo "Test"
    EOF
    chmod +x $out/bin/hello
  '';
}

{stdenv, ...}:

stdenv.mkDerivation {
  name = "perl";
  ...
  setupHook = ./setup-hook.sh
}

addPerlLibPath()
{
    addToSearchPath PERL5LIB $1/lib/perl5/site_perl
}

envHooks+=(addPerlLibPath)

{stdenv, fetchurl, gnumake, gnutar, gzip, gcc, binutils}:

stdenv.runCommand {
  name = "hello-2.10";
  src = fetchurl {
    url = mirror://gnu/hello/hello-2.10.tar.gz;
    sha256 = "0ssi1wpaf7plaswqqjwigppsg5fyh99vdlb9kzl7c9lng89ndq1i";
  };
  buildInputs = [ gnumake gnutar gzip gcc binutils ];
  buildCommand = ''
    tar xfv $srcb
    cd hello-2.10
    ./configure --prefix=$out
    make
    make install
  '';
}

The run phases abstraction

{stdenv}:

stdenv.runPhases {
  name = "hello";
  phases = [ "build" "install" ];
  buildPhase = ''
    cat > hello <<EOF
    #! ${stdenv.shell} -e
    echo "Hello"
    EOF
    chmod +x hello
  '';
  installPhase = ''
    mkdir -p $out/bin
    mv hello $out/bin
  '';
}

{stdenv}:

stdenv.runPhases {
  name = "hello2";
  builder = ./builder.sh;
}

source $setupRunPhases

phases="build install"

buildPhase()
{
    cat > hello <<EOF
#! $SHELL -e
echo "Hello"
EOF
    chmod +x hello
}

installPhase()
{
    mkdir -p $out/bin
    mv hello $out/bin
}

genericBuild

The generic build abstraction

• The unpack phase generically unpacks the provided sources, makes it content writable and opens the source directory. The unpack command is determined by the unpack hook that each potential unpacker provides -- for example, the GNU tar package includes a setup hook that untars the file if it looks like a tarball or compressed tarball:
  
  

  
  _tryUntar()
  {
      case "$1" in
          *.tar|*.tar.gz|*.tar.bz2|*.tar.lzma|*.tar.xz)
              tar xfv "$1"
              ;;
          *)
              return 1
              ;;
      esac
  }
  
  unpackHooks+=(_tryUntar)
  

• The patch phase applies any patch that is provided by the patches parameter uncompressing them when necessary. The uncompress file operation also works with setup hooks -- uncompressor packages (such as gzip and bzip2) provide a setup hook that uncompresses the file if it is of the right filetype.
• The strip phase processes all sub directories containing ELF binaries (e.g. bin/ and lib/) and strips their debugging symbols. This reduces the size of the binaries and removes non-deterministic timestamps.
• The patchShebangs phase processes all scripts with a shebang line and changes it to correspond to a path in the Nix store.
• The compressManPages phase compresses all manual pages with gzip.

{stdenv, fetchurl, gnumake, gnutar, gzip, gcc, binutils}:

stdenv.genericBuild {
  name = "hello-2.10";
  src = fetchurl {
    url = mirror://gnu/hello/hello-2.10.tar.gz;
    sha256 = "0ssi1wpaf7plaswqqjwigppsg5fyh99vdlb9kzl7c9lng89ndq1i";
  };
  buildInputs = [ gnumake gnutar gzip gcc binutils ];
  buildCommandPhase = ''
    ./configure --prefix=$out
    make
    make install
  '';
}

GNU Make/GNU Autotools abstraction

{stdenv, fetchurl}:

stdenv.mkDerivation {
  name = "hello-2.10";
  src = fetchurl {
    url = mirror://gnu/hello/hello-2.10.tar.gz;
    sha256 = "0ssi1wpaf7plaswqqjwigppsg5fyh99vdlb9kzl7c9lng89ndq1i";
  };
}

Composing custom function abstractions

{stdenv}:

{ name # the name of the derivation
, text
, executable ? false # run chmod +x ?
, destination ? ""   # relative path appended to $out eg "/bin/foo"
, checkPhase ? ""    # syntax checks, e.g. for scripts
}:

stdenv.runCommand {
  inherit name text executable;
  passAsFile = [ "text" ];

  # Pointless to do this on a remote machine.
  preferLocalBuild = true;
  allowSubstitutes = false;

  buildCommand = ''
    target=$out${destination}
    mkdir -p "$(dirname "$target")"

    if [ -e "$textPath" ]
    then
        mv "$textPath" "$target"
    else
        echo -n "$text" > "$target"
    fi

    [ "$executable" = "1" ] && chmod +x "$target" || true
  '';
}

{stdenv, foo, bar}:
{name, buildInputs ? [], ...}@args:

let
  extraArgs = removeAttrs args [ "name" "buildInputs" ];
in
stdenv.someBuildFunction ({
  name = "mypackage-"+name;
  buildInputs = [ foo bar ] ++ buildInputs;
} // extraArgs)

• A build function is a nested function in which the first line is a function header that captures the common build-time dependencies required to build a package. For example, when we want to build Perl packages, then perl is such a common dependency.
• The second line is the inner function header that captures the parameters that should be passed to the build function. The notation allows an arbitrary number of parameters. The parameters in the { } block (name, buildInputs) are considered to have a specific use in the body of the function. The remainder of parameters are non-essential -- they are used as environment variables in the builder environment or they can be propagated to other functions.
• We compose an extraArgs variable that contains all non-essential arguments that we can propagate to the build function. Basically, all function arguments that are used in the body need to be removed and function arguments that are attribute sets, because they cannot be converted to strings.
• In the body of the function, we set up important aspects of the build environment, such as the mandatory build parameters, and we propagate the remaining function arguments to the builder abstraction function.

Discussion

0. "Raw" derivations
1. The setup script ($stdenv/setup)
2. Simple derivation (stdenv.simpleDerivation)
3. The run command abstraction (stdenv.runCommand)
4. The run phases abstraction (stdenv.runPhases)
5. The generic build abstraction (stdenv.genericBuild)
6. The GNU Make/GNU Autotools abstraction (stdenv.mkDerivation)

• We could also split the implementation of stdenv.mkDerivation and the corresponding setup.sh script into layered sub functions. Currently, the setup.sh script is huge (e.g. over 1200 LOC) and has many responsibilities (perhaps too many). By splitting the build abstraction functions and their corresponding setup scripts, we can separate concerns better and reduce the size of the script so that it becomes more readable and better maintainable.
• In the Nixpkgs implementation, the phases that the generic builder executes are built for GNU Make/GNU Autotools specifically. Furthermore, the invocation of pre and post hooks and do and dont flags are all hand coded for every phase (there is no generic mechanism that deals with them). As a result, when you define a new custom phase, you need to reimplement the same aspects over and over again. In my implementation, you only have to define phases -- the generic builder automatically executes the coresponding pre and post hooks and evaluates the do and dont flags.
• In the Nixpkgs implementation there is no uncompressHook -- as a result, the decompression of patch files is completely handcoded for every uncompressor, e.g. gzip, bzip2, xz etc. In my implementation, we can delegate this responsibility to any potential uncompressor package.
• In my implementation, I turned some of the phases of the generic builder into command-line tools that can be invoked outside the build environment (e.g. patch-shebangs, compress-man). This makes it easier to experiment with these tools and to make adjustments.

Availability

I’m delighted to be able to announce that users all around the world will now have a great experience when fetching from the NixOS cache.

I heard several times from users in Hong Kong and Singapore that the cache was “slow”, but I didn’t know it was this slow! After working closely with a team of Nix users in Bangalore, I experienced first-hand just how eye-wateringly slow it could be.

The NixOS cache is now being served from all of AWS CloudFront edge locations, significantly reducing latency for users in Asia, Africa, South America, and Oceania.

By expanding the cache’s distribution settings to include all of the edge locations, performance has been substantially improved build time:

Experiments in Tokyo and Hong Kong produced similar results.

NixOS’s cache is stored in AWS S3, and distributed using AWS CloudFront. This combination gives us the excellent durability guarantees of S3 combined with the large geographical distribution of CloudFront.

Until today, the NixOS cache was only served through edge nodes in the United States, Canada, and Europe.

A big thank-you to Amine Chikhaoui, and Eelco Dolstra for their help in researching this change and turning on such a massive improvement.