Friday, November 2, 2012

An alternative explanation of the Nix package manager

As I have explained in my previous blog post, I started working at a new company as a software architect. One of the things I'm working on is (obviously) deployment.

Recently, I had to give my new employer some background information about my past experience and the Nix package manager. I have frequently presented Nix and related subjects to various kind of audiences. However, I nearly always use a standard explanation recipe, that is somewhat similar to what I have described in an old blog post about the Nix package manager.

This time, I have decided to give an alternative explanation, which I will describe in this blog post.

The Nix package manager


In short: Nix is a package manager, which is a collection of software tools to automate the process of installing, upgrading, configuring, and removing software packages. Nix is different compared to conventional package managers, because it borrows concepts from purely functional programming languages to make deployment reliable, reproducible and efficient. The Nix project has been initiated by Eelco Dolstra as part of his PhD research.

Purely functional programming languages


So, what are purely functional programming languages?

Many programming languages that are in use nowadays support functions. Functions in mathematics are an early inspiration source for "building bricks" in higher level languages.

For example, if we would have sticked ourselves to machine language or assembly, implementing and calling functions is not very obvious -- developers have to follow a function calling convention, that sets the function argument values in the right memory locations, pushes/pops memory addresses onto/from the stack, jumps from one memory location to another etc. For example, the following Intel assembly code fragment, shows how a function invocation can be implemented, using a certain calling convention:

.486
.MODEL FLAT
.CODE
PUBLIC _myFunc
_myFunc PROC
  ; Subroutine Prologue
  push ebp     ; Save the old base pointer value.
  mov ebp, esp ; Set the new base pointer value.
  sub esp, 4   ; Make room for one 4-byte local variable.
  push edi     ; Save the values of registers that the function
  push esi     ; will modify. This function uses EDI and ESI.
  ; (no need to save EBX, EBP, or ESP)

  ; Subroutine Body
  mov eax, [ebp+8]   ; Move value of parameter 1 into EAX
  mov esi, [ebp+12]  ; Move value of parameter 2 into ESI
  mov edi, [ebp+16]  ; Move value of parameter 3 into EDI

  mov [ebp-4], edi   ; Move EDI into the local variable
  add [ebp-4], esi   ; Add ESI into the local variable
  add eax, [ebp-4]   ; Add the contents of the local variable
                     ; into EAX (final result)

  ; Subroutine Epilogue 
  pop esi      ; Recover register values
  pop  edi
  mov esp, ebp ; Deallocate local variables
  pop ebp ; Restore the caller's base pointer value
  ret
_myFunc ENDP
END
I don't expect anyone to understand this code fragment, but it's pretty obvious that something as simple as invoking a function, is very complicated on machine level, as opposed to the following code fragment, written in the C programming language that defines a sum function that adds two integers to each other:

int sum(int a, int b)
{
    return a + b;
}

int main()
{
    return sum(1, 2);
}

Although many programming languages support functions, these are not the same as functions in mathematics. Consider the following mathematical theorem, known as Leibniz' Principle:
x = y => f(x) = f(y)
The above theorem states that if two function arguments are identical, the result of their function applications are identical as well, something which looks very obvious and makes sense. However, in most programming languages, this is not always the case, such as the C programming language. Consider the following C code example:
int v = 0;

int add(int a)
{
    v = v + a;
    return v;
}

int main()
{
    int p = add(1); /* 1 */
    int q = add(1); /* 2 */
}
The add function is called twice in this program with the same function argument. However, each function invocation yields a different result. The reason that this happens is because we have a global variable v that is accessed and overwritten in each function invocation to add.

There are many causes why function invocations with the same parameters yield different results, such as functions returning time-stamps, generating random numbers, performing I/O, accessing global variables. These causes are called side-effects in the functional programming community.

Because C (and many other commonly used programming languages) allow these side-effects to be programmed, they lack referential transparency, meaning that functions cannot be replaced by its value without changing the behaviour of a program.

Purely functional languages are an exception. In purely functional programming languages the result of a function invocation exclusively depends on the definition of the function itself and their parameters, as they do not allow side-effects to be programmed and they exclude destructive updates, such as having a global variable that can be updated. Purely functional programming languages have no variables, but identifiers that are bound to immutable objects. As a consequence, functions in these language support referential transparency.

Another characteristic of functional programming languages is that they often use lazy evaluation, which means that an expression only gets evaluated when it's really needed. A well known purely functional programming language is Haskell.

Because of these properties, purely functional programming languages, such as Haskell, have a number of interesting benefits -- thanks to the fact that functions always yield the same result based on their definition and their arguments, we can cache evaluation results, so that they only have to be executed once, improving efficiency. Laziness offers the advantage that a particular function only has to be evaluated when it's needed, improving efficiency even more. Because of referential transparency and the closures of the functions are known, we can also easily divide function execution over multiple cores/CPUs improving execution speed.

Although purely functional languages have some benefits, they also have some drawbacks. For example, the laziness and caching properties conflict with time predictability, which makes it very hard to develop real-time systems. Moreover, programs written in purely functional languages are much harder to debug.

Purely functional package management


Now I'm trying to draw an analogy to package management: What if we treat the deployment process of a package as a function in programming languages (consisting of steps, such as configuring, building from source, installing and/or upgrading)? In conventional package managers like RPM, such "functions" look very much like functions in imperative programming languages, such as C.

For example, most packages that are in use today, are rarely self contained -- they usually depend on other components that are needed during build-time, such as a compiler, and at run-time, such as libraries. Dependencies can be considered function arguments to a function that deploys a specific package.

However, conventional package managers, have a number of drawbacks. For example, while executing a function (i.e. deploying a package), we are often capable of destructively modifying other packages, by overwriting or removing files belonging to another package. Although it may look obvious now that these properties have drawbacks, it's very common that such operations happen. Especially upgrades are destructive and may result in problems, such as the "DLL hell", because after an upgrade, a program may utilise a library that is incompatible or does not work properly.

Furthermore, files belonging to packages are often stored in global locations, such as /usr/lib on Linux, or C:\WINDOWS\System32 on Windows, allowing packages to find their dependencies even if they are not declared (you could see these implicit dependencies as global variables in a programming language). These factors limit reproducibility. For example, if we would run the same function on another machine, the deployment may fail, because the undeclared dependency is not present.

Because the contents of packages deployed by conventional package managers are often installed in global locations, it's hard to allow multiple versions or variants to safely co-exist, unless the packager has manually checked that there is no file that shares the same name with another package.

The Nix package manager is designed to overcome these drawbacks, by borrowing concepts from purely functional programming languages. In Nix, we describe the build recipes of packages in a domain-specific language called the Nix expression language and every build is modeled after a function that describes the build and a function invocation that builds the package with its required dependencies.

The following example shows a Nix expression that describes how to build the GNU Hello package:
{stdenv, fetchurl}:

stdenv.mkDerivation {
  name = "hello-2.6";
  
  src = fetchurl {
    url = ftp://ftp.gnu.org/gnu/hello/hello-2.6.tar.gz;
    sha256 = "1h6fjkkwr7kxv0rl5l61ya0b49imzfaspy7jk9jas1fil31sjykl";
  };

  meta = {
    homepage = http://www.gnu.org/software/hello/manual/;
    license = "GPLv3+";
  };
}
The expression shown above defines a function that takes two arguments: the stdenv component is the standard environment providing common UNIX utilities, (such as cat and ls), GNU Make and GCC, fetchurl is a function that downloads a file from an external source.

In the remainder of the function definition, we invoke the stdenv.mkDerivation function that is used to build a package from source, its dependencies (which are passed as function arguments) and a specified build recipe. In our example, we have omitted the build recipe. If no build procedure is specified, the standard Autotools build procedure: ./configure; make; make install is executed.

The earlier code fragment only defines a function, but in order to build a package we need to compose it, by calling it with the right function arguments, which is done in the following expression:
rec {
  stdenv = ...;

  fetchurl = import ../build-support/fetchurl {
    inherit stdenv curl;
  };

  hello = import ../applications/misc/hello {
    inherit stdenv fetchurl;
  }

  ...
}
Here, the hello attribute is bound to the function defined in the earlier expression and invoked with the right function arguments. The dependencies of GNU Hello are also defined and composed in the above expression.

The derivation functions used to build packages as well as the Nix expression language itself are purely functional -- the build result of a package exclusively depends on the function definition and its given arguments, files belonging to another package are never overwritten or removed, dependencies can only be found if they are specified, and we can easily divide derivations over multiple CPUs, cores or machines to improve scalability.

As may become evident now, applying purely functional concepts in package management makes deployment of packages reliable, reproducible, scalable and efficient.

The remaining open question is how Nix achieves these purely functional properties:

  • To ensure that packages cannot be overridden or removed by build functions of other packages, we store the result of each build in a separate location on the filesystem, in directories that are made immutable (by removing write permission bits), so that they cannot be changed. To create, such a unique location, we store component in a store called the Nix store and we use hashing (derived from all inputs to the function, such as their dependencies, sources and build scripts) to generate a unique directory name, e.g. /nix/store/xq2bfcqdsbrmfr8h5ibv7n1qb8xs5s79-openssl-1.0.0c. If we, for example, change any of its build parameters, such as the used compiler, the hash will differ and thus its safe to allow multiple variants to coexist as they never share the same name.
  • By using the Nix store concept, we get another important property "for free" -- because every package variant is stored in a unique location, as opposed to global locations, such as /usr/lib, we have stricter guarantees that dependency specifications are complete, as they cannot be implicitly found. In order to allow a dependency to be found we have to explicitly specify it, for example, by adding it to the PATH environment variable.
  • To reduce the chances on side effects even more, we run build scripts in isolated environments with unprivileged user rights and we can optionally use a chroot() environment to limit access to the host filesystem even more.
  • We have also patched several common UNIX utilities, such as gcc and ld to ignore global locations, such as /usr/lib.

Nix applications


Apart from package management, Nix has been used for a number of other applications:
  • NixOS is a GNU/Linux distribution completely built around the Nix package manager. Apart from the fact that every component (including the Linux kernel and configuration files) are managed by Nix, it is also used to deploy entire system configurations from declarative specifications.
  • Disnix is an extension to Nix developed by me to automatically deploy service-oriented systems composed of distributable components, in networks of machines.
  • Hydra is a continuous build and integration server, built around Nix and using the Nix expression language to define build and test jobs.

Why am I writing this blog post?


As I have explained Nix on my blog before, you may probably wonder why I'm doing it again? It's not that since I have switched jobs, that I wanted to reboot my blog :-)

At my new working spot, my colleagues are not system administrators or packagers, but people with programming language experience, including functional languages, such as Lisp. Therefore, I have decided to give them an alternative explanation, instead of the traditional one.

In the past, I sometimes had some trouble properly explaining the Nix concepts to certain kind of audiences. In many ways I think this alternative explanation is better than the traditional one, albeit it's also a bit longer, but oh well... :-)

In the traditional explanation, I start explaining conventional package managers (and their drawbacks) and showing the Nix store concept and the hash-codes in the path name. Usually when people see this, they initially have a weird feeling. Some even think that we're crazy.

Then we show more stuff, such as how to write Nix expressions specifying how to build packages, increasing the confusion a bit more. Then we have to put some effort in 'justifying' this means. Quite often, after some confusion people see the point and understand some of the benefits. Some of them, however, have already lost interest by then.

Furthermore, we often avoid the term 'purely functional', because it causes extra confusion. In this alternative explanation, I do not omit the term 'purely functional'. The described means (such as the Nix store paths with hash codes) make sense in this explanation, as they are a direct consequence of mapping the goal of purely functional languages to the deployment of packages.

Downsides of this alternative explanation


Although I find this explanation better, there are also some drawbacks. In this explanation, programming languages are the main focus point. Usually our intended audience consists of system administrators, system engineers, packagers and (of course) researchers. Most of them are often not programmers, and have no affinity with programming language research concepts. Especially uncommon languages, such as purely functional ones (including the term: purely functional).

I have especially suffered from this while trying to publish papers in the systems community. They often slam our papers, because "their event is not about programming languages" and we never receive any valuable feedback from them either, even though I have always used the traditional explanation instead of this one.

Conclusion


In this blog post, I have given an alternative explanation of the Nix package manager, using programming languages as a basis concept. In many ways, I find this explanation better than the older/traditional explanation, although it also has its drawbacks. I think properly explaining Nix without any confusion is still an open challenge.

References

3 comments:

  1. Good post. The analogy to functional programming extends all the way to its biggest drawback: people just don't get it yet. And we're left with a small minority of people in the functional world saying, "why isn't everyone doing this? this is obviously better." Hopefully the recent uptick in functional programming will give nix a boost.

    ReplyDelete
  2. I think an important reason why people don't get it, is because they don't want to :-)

    They think maths is too theoretical and that they have enough tools available, which can do the job. So why bother looking/thinking about something else, or at least to have a critical look at their current development practices?

    I hope this blog post at least contributes to the latter aspect, so that we won't get slammed again, when we're trying to reach a particular audience.

    ReplyDelete