Luận án Tiến sĩ về mô hình triển khai phần mềm thuần hàm của Eelco Dolstra

The Purely Functional Software Deployment Model Het puur functionele softwaredeploymentmodel (met een samenvatting in het Nederlands) Proefschrift ter verkrijging van de graad van doctor aan de Universiteit Utrecht op gezag van de Rector Magnificus, Prof. Gispen, ingevolge het besluit van het College voor Promoties in het openbaar te verdedigen op woensdag 18 januari 2006 des middags te 12.45 uur door Eelco Dolstra geboren op 18 augustus 1978, te Wageningen Promotor: Prof. Doaitse Swierstra, Universiteit Utrecht Copromotor: Dr. Eelco Visser, Universiteit Utrecht The work in this thesis has been carried out under the auspices of the research school IPA (Institute for Programming research and Algorithmics).

Dit proefschrift werd mogelijk gemaakt met financiële steun van CIBIT|SERC ICT Adviseurs. Cover illustration: Arthur Rackham (1867–1939), The Rhinegold & The Valkyrie (1910), illustrations for Richard Wagner’s Der Ring des Nibelungen: the gods enter Walhalla as the Rhinemaidens lament the loss of their gold. ISBN 90-393-4130-3 Acknowledgements This thesis could not have come about without the help of many individuals. Foremost I wish to thank my supervisor and copromotor Eelco Visser.

He was also my master’s thesis supervisor, and I was quite happy that we were able to continue to work together on the Variability/TraCE project. He shared my eventual interest in configuration management- related issues, and package management in particular. His insights have improved this research and this thesis at every point. The Software Engineering Research Center (SERC), now known as CIBIT|SERC ICT Adviseurs, funded my PhD position.

Gert Florijn initiated the variability project and the discussions with him were a valuable source of insights. The results of the present thesis are probably not what any of us had expected at the start; but then again, the nice thing about a term like “variability” is that it can take you in so many directions. My promotor Doaitse Swierstra gave lots of good advice—but I ended up not imple- menting his advice to keep this thesis short. I am grateful to the members of the reading committee—Jörgen van den Berg, Sjaak Brinkkemper, Paul Klint, Alexander Wolf and Andreas Zeller—for taking the time and effort to go through this book.

Karl Trygve Kalle- berg, Armijn Hemel, Arthur van Dam and Martin Bravenboer gave helpful comments. Several people have made important contributions to Nix. Notorious workaholic Martin Bravenboer in particular was an early adopter who contributed to almost every aspect of the system. Armijn Hemel (“I am the itch programmers like to scratch”) contributed to Nixpkgs and initiated the NixOS, which will surely conquer the world.

René de Groot coined the marketing slogan for NixOS—“Nix moet, alles kan!” Roy van den Broek has replaced my hacky build farm supervisor with something much nicer (and Web 2. Eelco Visser, Rob Vermaas and Merijn de Jonge also contributed to Nixpkgs and the build farm. In addition, it is hard to overestimate the importance of the work done by the free and open source software community in providing a large body of non-trivial modular components suitable for validation. Thanks! The Software Technology group is a very pleasant work environment, and I thank all my current and former colleagues for that.

I especially thank my roommates Dave Clarke (“The cause of the software crisis is software”), Frank Atanassow (who demanded “pointable research”), Merijn de Jonge, Martin Bravenboer, Rob Vermaas and Stefan Hold- ermans. Andres Löh, Bastiaan Heeren, Arthur Baars, Karina Olmos and Alexey Rodriguez were more than just good colleagues. Daan Leijen insisted on doing things the right way. The #klaplopers provided a nice work environment in virtual space—though whether IRC is a medium that increases productivity remains an unanswered empirical question.

Arthur van Dam and Piet van Oostrum provided valuable assistance in wrestling with TEX. Atze Dijkstra, Bastiaan Heeren and Andres Löh had helpful advice (and code!) for the preparation of this thesis. And finally I would like to thank my family—Mom, Dad, Jitske and Menno—for their support and love through all these years. iii iv Contents I.

The state of the art. The Nix deployment system. Outline of this thesis. An Overview of Nix 19 2.

The Nix store. Transparent source/binary deployment. Deployment as Memory Management 49 3. What is a component?.

The file system as memory. The Nix Expression Language 61 4. Context-free syntax. The Extensional Model 87 5.

The Nix store. File system objects. Path validity and the closure invariant. Translating Nix expressions to store derivations.

Fixed-output derivations. Building store derivations. The simple build algorithm. The parallel build algorithm.

Garbage collection roots. Stop-the-world garbage collection. Concurrent garbage collection. The Intensional Model 135 6.

A content-addressable store. The hash invariant. Equivalence class collisions. Adding store objects.

Building store derivations. Assumptions about components. Applications 165 vi Contents 7. The Nix Packages collection.

The standard environment. Supporting third-party binary components. Binary patch creation. Continuous Integration and Release Management 209 8.

The Nix build farm. Discussion and related work. Service configuration and deployment. Capturing component compositions with Nix expressions.

Maintaining the service. Composition of services. Variability and crosscutting configuration choices. Low-level build management using Nix.

247 vii Contents viii Part I. Introduction This thesis is about getting computer programs from one machine to another—and having them still work when they get there. This is the problem of software deployment. Though it is a part of the field of Software Configuration Management (SCM), it has not been a subject of academic study until quite recently [169].

The development of principles and tools to support the deployment process has largely been relegated to industry, system administrators, and Unix hackers. This has resulted in a large number of often ad hoc tools that typically automate manual practices but do not address fundamental issues in a systematic and disciplined way. This is evidenced by the huge number of mailing list and forum postings about de- ployment failures, ranging from applications not working due to missing dependencies, to subtle malfunctions caused by incompatible components. Deployment problems also seem curiously resistant to automation: the same concrete problems appear time and again.

De- ployment is especially difficult in heavily component-based systems—such as Unix-based open source software—because the effort of dealing with the dependencies can increase super-linearly with each additional dependency. This thesis describes a system for software deployment called Nix that addresses many of the problems that plague existing deployment systems. In this introductory chapter I describe the problem of software deployment, give an overview of existing systems and the limitations that motivated this research, summarise its main contributions, and outline the structure of this thesis. Software deployment Software deployment is the problem of managing the distribution of software to end-user machines.

That is, a developer has created some piece of software, and this ultimately has to end up on the machines of end-users. After the initial installation of the software, it might need to be upgraded or uninstalled. Presumably, the developer has tested the software and found it to work sufficiently well, so the challenge is to make sure that the software works just as well, i., the same, on the end-user machines. I will informally refer to this as correct deployment: given identical inputs, the software should behave the same on an end-user machine as on the developer machine1.

This should be a simple problem. For instance, if the software consists of a set of files, then deployment should be a simple matter of copying those to the target machines. In 1 I’m making several gross simplifications, of course. First, in general there is no single “developer”.

Second, there are usually several intermediaries between the developer and the end-user, such as a system administra- tor. However, for a discussion of the main issues this will suffice. Introduction practice, deployment turns out to be much harder. This has a number of causes.

These fall into two broad categories: environment issues and manageability issues. Environment issues The first category is essentially about correctness. The software might make all sorts of demands about the environment in which it executes: that certain other software components are present in the system, that certain configuration files exist, that certain modifications were made to the Windows registry, and so on. If any of those environmental characteristics does not hold, then there is a possibility that the software does not work the same as it did on the developer machine.

Some concrete issues are the following: • A software component is almost never self-contained; rather, it depends on other components to do some work on its behalf. These are its dependencies. For correct deployment, it is necessary that all dependencies are identified. This identification is quite hard, however, as it is often difficult to test whether the dependency specifi- cation is complete.

After all, if we forget to specify a dependency, we don’t discover that fact if the machine on which we are testing already happens to have the depen- dency installed. • Dependencies are not just a runtime issue. To build a component in the first place we need certain dependencies (such as compilers), and these need not be the same as the runtime dependencies, although there may be some overlap. In general, deployment of the build-time dependencies is not an end-user issue, but it might be in source- based deployment scenarios; that is, when a component is deployed in source form.

This is common in the open source world. • Dependencies also need to be compatible with what is expected by the referring component. In general, not all versions of a component will work. This is the case even in the presence of type-checked interfaces, since interfaces never give a full specification of the observable behaviour of a component.

Also, components often exhibit build-time variability, meaning that they can be built with or without certain optional features, or with other parameters selected at build time. Even worse, the component might be dependent on a specific compiler, or on specific compilation options being used for its dependencies (e., for Application Binary Interface (ABI) compatibility). • Even if all required dependencies are present, our component still has to find them, in order to actually establish a concrete composition of components. This is often a rather labour-intensive part of the deployment process.

Examples include setting up the dynamic linker search path on Unix systems [160], or the CLASSPATH in the Java environment. • Components can depend on non-software artifacts, such as configuration files, user accounts, and so on. For instance, a component might keep state in a database that has to be initialised prior to its first use. Software deployment • Components can require certain hardware characteristics, such as a specific proces- sor type or a video card.

These are somewhat outside the scope of software deploy- ment, since we can at most check for such properties, not realise them if they are missing. • Finally, deployment can be a distributed problem. A component can depend on other components running on remote machines or as separate processes on the same machine. For instance, a typical multi-tier web service consists of an HTTP server, a server implementing the business logic, and a database server, possibly all running on different machines.

So we have two problems in deployment: we must identify what our component’s re- quirements on the environment are, and we must somehow realise those requirements in the target environment. Realisation might consist of installing dependencies, creating or modifying configuration files, starting remote processes, and so on. Manageability issues The second category is about our ability to properly manage the deployment process. There are all kinds of operations that we need to be able to perform, such as packaging, transferring, installing, upgrading, uninstalling, and answering various queries; i., we have to be able to support the evolution of a software system.