My PhD thesis propositions and some discussion

Apart from the contents of my PhD thesis, theses at our university are usually accompanied by a list of propositions. According to our university's Doctorate regulations, they must be defendable and opposable, at least six of the propositions are not supposed to be directly related to the research subject and two of them may be slightly playful. Besides the contents of my thesis, committee members are also allowed to ask questions about the propositions.

A colleague of mine: Felienne Hermans, has covered her propositions on her blog to elaborate about them. I have decided to do the same thing, although I'm not planning to create separate blog posts for each individual proposition. Instead, I cover all of them in a single blog post.

Propositions

1. Many of the non-functional requirements of a deployed service-oriented system can be realized by selecting an appropriate software deployment system.
   
   As I have explained earlier in a blog post about software deployment complexity, systems are rarely self-contained but composed of components. An important property of a component is that it can be deployed independently, significantly complicating a software deployment process.
   
   Components of service-oriented systems are called "services". It's a bit of an open debate to exactly tell what they are, since people from industry often think in terms of web services (things that use SOAP, WSDL, UDDI), while I have also seen the description "autonomous platform independent entities that can be loosely coupled" in the academic literature.
   
   Although web services are some sort of platform independent entities, they still have implementations behind their interfaces depending on certain technology and can be deployed to various machines in a network. We have seen that deployment on a single machine is hard and that deploying components into networks of machines is even more complicated, time consuming and error prone.
   
   Besides deployment activities, there are many important non-functional requirements a system has to meet. Many of them can be achieved by designing an architecture, e.g. components, connectors and the way they interact through architectural patterns/styles. Architectural patterns (e.g. layers, pipes and filters, blackboard etc.) implement certain quality attributes.
   
   For service-oriented systems, it's required to deploy components properly into a network of machines to be able to compose systems. In other words: we have to design and implement a proper deployment architecture. This has several technical challenges, such as the fact that we have to deploy components in such a way that they exactly match the deployment architecture, the deployment activities themselves, and the fact that we have to determine whether a system is capable of running a certain component (i.e. a service using Windows technology cannot run on a Linux machine or vice-versa).
   
   In addition to technical constraints, there are also many non-functional issues related to deployment that require attention, i.e. where to place components and how to combine them to achieve certain non-functional requirements? For example, privacy could be achieved by placing services providing access to privacy-sensitive data in a restricted zone and robustness by deploying multiple redundant instances of the same service.
   
   It can also be hard to manually find a deployment architecture that satisfies all non-functional requirements. In such cases, deployment planning algorithms are very helpful. In some cases it's even too hard or impossible to find an optimal solution.
   
   Because of all these cases, an automated deployment solution taking all relevant issues into account is very helpful in achieving many non-functional requirements of a deployed service-oriented system. This is what I have been trying to do in my PhD thesis.
   
   
2. The intention of the Filesystem Hierarchy Standard (FHS) is to provide portability among Linux systems. However, due to ambiguity, over-specification, and legacy support, this standard limits adoption and innovation. This phenomenon applies to several other software standards as well.
   
   There are many standards in the software engineering domain. In fact, it's dominated by them. One standard that is particularly important in my research is the Filesystem Hierarchy Standard (FHS) defining the overall filesystem structure of Linux systems. I have written a blog post on the FHS some time ago.
   
   In short: the FHS defines the purposes of directories, it makes a distinction between static and variable parts of a system, it defines hierarchies (e.g. / is for boot/recovery, /usr is for user software and for /usr/local nobody really knows (ambiguity)). Moreover, it also defines the contents of certain directories, e.g. /bin should contain /bin/sh (over-specification).
   
   I have problems with the latter two aspects -- the hierarchies do not provide support for isolation, allowing side-effects to easily manifest themselves while deploying and enabling destructive upgrades. I also have a minor problem with strict requirements of the contents of directories, as they easily allow builds to trigger side-effects while assuming that certain tools are always present.
   
   For all these reasons, we deviate on some aspects of the FHS in NixOS. Some people consider this unacceptable, and therefore they will not be able to incorporate most of our techniques to improve the quality of deployment processes.
   
   Moreover, as the FHS itself has issues, we observe that although the filesystem structure is standardized, file system layouts in many Linux distributions are still slightly different and portability issues still arise.
   
   In other domains, I have also observed various issues with standards:
   
   
   • Operating systems: nearly every operating system is more or less forced to implement POSIX and/or the Single UNIX Specification, taking a lot of effort. Furthermore, by implementing these standards they UNIX is basically reimplemented. These standards have many strict requirements on how certain library calls should be implemented, although it also specifies undefined behaviour at the same time. Apart from the fact that it's difficult and time consuming to implement these standards, there is little room to implement an operating system that is conceptually different from UNIX as it conflicts with portability.
   • The Web (e.g. HTML, CSS, DOM etc.): First, a draft is written in a natural language (which is inherently ambiguous) and sometimes underspecified. Then vendors start implementing these drafts. As initially these standards are ambiguous and underspecified, implementations behave very differently. Slowly these implementations converge into something that is uniform by collaborating with other vendors and the W3C to improve the draft version of a standard. Some vendors intentionally or accidentally implement conformance bugs, which don't get fixed for quite some time.
     
     These buggy implementations may become the de-facto standard, which has happened in the past, e.g. with Internet Explorer 6, requiring web developers to implement quirks code. Since the release of Internet Explorer 6 in 2001, Microsoft had 95% market share and did not release a new version until 2006. This was seriously hindering innovation in web technology. It also took many years before other implementations with better web standards conformance and more features gained acceptance.

So are standards bad? Not necessarily, but I think we have to critically evaluate them and not consider them as holy books. Moreover, standards need to be developed with some formality and elegance in mind. If junk gets standardized, it will remain junk and requires everybody to cope with junk for quite some time.

One of the things that may help is using good formalisms. For example, a good one I can think of is BNF that was used in the ALGOL 60 specification.


3. To move the software engineering community as a whole forward, industry and academia should collaborate. Unfortunately, their Key Performance Indicators (KPIs) drive them apart, resulting in a prisoner's dilemma.
   
   This proposition is related to an earlier rant blog post about software engineering fractions and collaborations. If I would use stereotypes, then the primary KPI of academia are the amount of (refereed) publications and the primary KPI of industry is how much they sell.
   
   It's obvious that, if both fractions would let themselves go a bit from their KPIs, i.e. academia does a bit more in engineering tools and transferring knowledge, while industry spends some of their effort in experimenting and paying attention to "secondary tasks", that both parties would benefit. However, in practice often the opposite happens (although there are exceptions of course).
   
   This is analogous to a prisoner's dilemma, which is a peculiar phenomenon. Visualize the following situation: two prisoners have jointly committed a crime and got busted. If both confess their crime then the amount of time they have to spend in prison are five years. If one prisoner confesses while the other does not, then the prisoner that confesses goes ten years into jail and the other remains free. If none of them confess, they both have to spent twenty years in prison.
   
   In this kind of situation the (obvious) win-win situation for both criminals is that they both confess. However, because they both give priority to their self-interests, none of them confesses as they assume that they remain free. But instead, the situation has the worst outcome: both have to spent twenty years in prison.
   
   
4. In software engineering, the use of social media, such as blogging and twitter, are an effective and efficient way to strengthen collaboration between industry and academia.
   
   This proposition is related to the previous one. How can we create a win-win situation? Often I hear people saying: "Well collaboration is interesting, but it costs time and money, which we don't have right now and we have other stuff to do".
   
   I don't think the barrier has to be that high. Social media, such as blogging and twitter, can be used for free and allows one to easily share stories, thoughts, results and so on. Moreover, recipients can also share these with people they know.
   
   My blog for example, has attracted many more readers and has given me much more feedback then all my research papers combined. Moreover, I'm not limited by all kinds of contraints that program committee members impose on me.
   
   However these observations are not unique to me. Many years ago, a famous Dutch computer scientist named Edsger Dijkstra wrote many manuscripts that he sent to his peers directly. He wrote about subjects that he found relevant. His peers spread these manuscripts through their colleagues allowing him to reach a wide range of people, eventually reaching thousands of people.
   
   
5. While the vision behind the definition of free software as described by the Free Software Foundation to promote freedom is compelling, the actual definition is ambiguous and inadequately promoted.
   
   The free software definition defines four freedoms. I can rephrase them in one sentence: "Software that can be used, studied, adapted and shared for any purpose". An essential precondition for this is the availability of the source code. I think this definition is clear and makes sense.
   
   However, there is a minor issue with the definition. The word 'free' is ambiguous in English. In the definition, it refers to free as in freedom not free in price (gratis). In Dutch or French it's not a problem. In these languages free software translates to 'vrije software' and 'libre software'.
   
   Moreover, although (almost) all free software is gratis, it's also allowed to sell free software for any price, which is often misunderstood.
   
   I have seen that the ambiguity of the word free is often used as an argument why the definition is not attracting a general audience.
   
   I think there is a bigger problem: the way free software is advertised. Most advertisements are not about what's good about free software, but about what's bad about proprietary software and how evil certain practices of certain companies are.
   
   Although I don't want to say that they are not right and we should tolerate such bad practices, I think it would also help to pay more attention to the good aspects of free software. The open source definition has much more care for this. For example, being able to improve quality of software. That's something I think that would attract people from the other side, whereas negative campaigning does not.
   
   
6. Compared to the definition of free software provided by the Free Software Foundation, the definition of Open Source as provided by the Open Source Initiative, fails to improve on freedom. While it has been more effectively promoted, it lacks a vision and does not solve ambiguity.
   
   The open source definition lists ten pragmatic points with the intention of having software that is free (as in freedom), e.g. availability of source code, means to share modified versions, and so on. However, it does not explain why it's desired for others to respect these ten pragmatic points and what their rationale is (although there is an annotated definition that does).
   
   Because of these reasons, I have seen that sometimes software is incorrectly advertised as being open-source, while in reality they are not. For example, there is also software available with source code, for which it is not allowed to do commercial redistributions, such as the LCC compiler. That's not open source (nor free software). Another prominent example is Microsoft's Shared Source initiative, only allowing someone to look at code, but not to modify or redistribute it.
   
   A very useful aspect of open source is the way it's advertised. It pays a lot of attention in selling its good points. For example, that everyone is able to improve its quality, and allowed to collaborate etc. Companies (even those that sell proprietary software) acknowledge these positive aspects and are sometimes willing to work with open-source people on certain aspects or to "open-source" pieces of their proprietary products. Examples of this are the Eclipse platform and the Quake 3 arena video game.
   
   
7. Just like making music is more than translating notes and rests into tones and pauses with specific durations, developing software systems is more than implementing functional requirements. In both domains, details, collaboration and listening to others are most important.
   
   I have observed that in both domains we make estimations. In software development, we try to estimate how much effort it takes to develop something and in music we try to estimate how much effort it takes to practice and master a composition.
   
   In software development, we often look at functional requirements (describing what a system should do) to estimate. I have seen that sometimes functional requirements may look ridiculously simple, such as displaying tabular data on a web page. Nearly every software developer would say: "that's easy".
   
   But even if functional requirements are simple, certain non-functional requirements (describing how and where) could make it very difficult. For example, properly implementing security facilities, a certain quality standard (such as ISO 9126) or to provide scalability. These kind of aspects may be much more complicated than the features of a system itself.
   
   Moreover, software is often developed in a team. Good communication and being able to divide work properly is important. In practice, you will almost always see that something goes wrong with that, because people have assumptions that all details are known by others or there is no clear architecture of a system so that work can be properly divided among team members.
   
   These are all kinds of reasons that may result in development times that are significantly longer than expected and failure to properly deliver what clients have asked.
   
   In my spare time I'm a musician and in music I have observed similar things. People make effort estimations by looking at the notes written on paper. Essentially, you could see those as functional requirements as they tell you what to play.
   
   However, besides playing notes and pausing, there are many more aspects that are important, such as tempo, dynamics (sudden and gradual loudness) and articulation. You could compare these aspects to non-functional requirements in software, as they tell somebody how to play (series of) notes.
   
   Moreover, making music can also be a group effort, such as a band or an orchestra, requiring people to properly interact with each other. If others make mistakes they may confuse you as well.
   
   I vividly remember a classical composition of 15 years ago. I just joined an orchestra and we were practising: "Land of the Long White Cloud" by Philip Sparke. In the middle of the composition, there is a snare drum passage consisting of only sixteenth notes. I already learned playing patterns like these in my first drum lesson, so I thought that it would be easy.
   
   However, I had to play these notes in a very fast tempo and very quietly, which are usually conflicting constraints for percussionists. Furthermore, I had to keep up the right tempo and don't let the other members distract me. Unfortunately, I couldn't cope with all these additional constraints, and that particular passage had to be performed by somebody else. I felt like an idiot and I was very disappointed. However, we did win the contest in which we had to perform that particular composition.
   
   As a side note: "The land of the long white cloud" is also known as Aotearoa or New Zealand.
   
   
8. Multilingualism is a good quality for a software engineer as it raises awareness that in natural languages as well as in software languages and techniques, there are things that cannot be translated literally.
   
   It's well known that some words or sentences cannot be literally translated from one natural language to another. In such cases, we have to reformulate a sentence into something that has an equivalent meaning, which is not always trivial.
   
   For example, non-native English speakers, like Dutch people, tend to make (subtle) mistakes now and then, which sometimes have hilarious outcomes. Make that the cat wise is a famous website that elaborates on this, calling the Dutch variant of English: Dunglish.
   
   Although we are aware of the fact that we cannot always translate things literally in natural languages, I have observed that in the software domain the same phenomenon occurs. One particular programming language may be more useful for a certain goal, than another programming language. Eventually, code written in a programming language gets compiled into machine code or another programming language (having an equivalent reformulation in a different language) or interpreted by an interpreter.
   
   However, I have also observed that in the software engineering domain there is a lot of programming language conservatism. Most conventional programming languages used nowadays (Python, C++, Java, C# etc.) use structured and imperative programming concepts in combination with class-based OO techniques. Unconventional languages such as purely functional programming languages (Haskell) or declarative languages (Prolog, Erlang) only get little mainstream acceptance, although they have very powerful features. For example, programs implemented in a purely functional language easily scale across multiple cores/processors.
   
   Instead, many developers use conventional languages to achieve the same, imposing many additional problems that need to be solved and more chances on errors. Our research based on the purely functional deployment model also suffers from conservatism. Therefore, I think multilingualism is very powerful asset for an engineer, as he is not limited by a solution set that is too narrow.
   
   
9. Stubbornness is both a positive as well as a negative trait of a researcher.
   
   I think that when you do research and if you discover something that is uncommon, others may reject it or tell you to do something that they consider more relevant. Some researchers choose to comply and give up stuff that they think is relevant. If every scientist would do that, then I think certain things would have never been discovered. I think it's a scientist's duty to properly defend important discoveries.
   
   In the middle ages it was even worse. For example, a famous scientist named Galileo Galilei revealed that not the Earth but the Sun was the centre of our solar system. He was sentenced to house arrest for the rest of his life by the catholic church.
   
   However, stubbornness also has a negative aspect. It often comes with ignorance and sometimes that's bad. For example, I have "ignored" some advice about properly studying related work and taking evaluation seriously, resulting in a paper that was badly rejected.
   
   

Conclusion

In this blog post, I have described some thoughts on my PhD propositions. The main reason of writing this down is to prepare myself for my defence. I know this blog post is lengthy, but that's good. This will probably prevent my committee members to read all the details, so that they cannot use everything I have just written against me :-) (I'm very curious to see if anyone has notice that I just said this :P).

A Reference Architecture for Distributed Software Deployment

Today, I'm happy to announce the title and contents of my PhD dissertation on this blog!

Background

I have written many software deployment related topics on my blog. Earlier, I have explained that certain developments in software engineering, such as component-based software engineering (CBSE), have increased the quality of software systems, but also have significantly increased the complexity of deployment processes of software systems. Moreover, I have written about solutions, typically involving tools from the Nix project.

Before I started my research as PhD (and master's) student, we already had the following deployment tools in the Nix project:

• The Nix package manager for deployment of individual packages from declarative specifications.
• NixOS, a Linux distribution completely built around the Nix package manager. NixOS deploys entire system configurations from a single declarative specification.
• Hydra, formerly known as just the "Nix build farm". Hydra builds jobsets from declarative specifications.

Distributed software deployment

As you may notice, these tools all have something in common: to fully automate software deployment processes from declarative specifications, in a reliable, reproducible, generic and efficient way. Their difference is the level in which they operate.

However, to support modern generation systems, typically exposed as services through the Internet, these tools are not sufficient:

• We have to deploy multiple machines in a network, instead of a single machine.
• Components may have dependencies on other components residing on different machines in the network, as well as system configurations (called inter-dependencies in this thesis).
• Components need underlying infrastructure components, e.g. an application server or a DBMS.
• Upgrading these systems may give a large time window in which a system is inconsistent.
• We have to meet important non-functional requirements, e.g. performance, security, privacy and the license under which components are governed.

To support these new generation of systems, we have developed a collection of new tools in the Nix project:

• Disnix, to deploy services (such as web services, web applications, UNIX processes etc) inside networks of machines from declarative specifications.
• Dynamic Disnix, to automatically redeploy services through Disnix based on technical and non-functional constraints if an event occurs in the network, e.g. machine crash.
• NixOps (formerly known as Charon and nixos-deploy-network) and the NixOS test driver, to deploy and test networks of NixOS configurations from declarative specifications.
• Dysnomia, a prototype-tool to deploy mutable software components.
• grok-trace, a prototype-tool to dynamically analyze build processes to discover license constraints.

These tools solve various distributed deployment aspects having similar quality attributes as the older Nix tools and make it possible to support some important non-functional requirements.

A Reference Architecture for Distributed Software Deployment

However, to fully automate deployments of service-oriented systems, we must combine these tools implementing generic deployment aspects with components supporting important non-functional requirements of a domain, such as performance, security and privacy. However, there is no silver bullet that solves all these problems for any domain, as some non-functional requirements are more important in one domain than another, and some may conflict with each other.


Instead, we have designed a reference architecture that can be used to construct a concrete architecture for a domain-specific deployment tool, capable of fully automating a deployment process with its desired quality attributes.

My thesis gives some background information about software deployment in general and Nix, it proposes a reference architecture for distributed software deployment, it describes most of the newer Nix components, and shows how these can be applied. Finally, we reflect on how well we have achieved our desired quality attributes.

Availability

My PhD thesis can be obtained from the PhD thesis page of my homepage. Moreover, the defence will be at June 3, 2013 14:30 in the Aula Congresscentre of Delft University of Technology. If you're interested in attending my defence, please let me know!

Dynamic analysis of build processes to discover license constraints

As I have explained earlier in the blog post about software deployment complexity, software is rarely self-contained nowadays, but typically use many off the shelf components. Reuse has advantages, such as the fact that productivity increases and products can be finished more quickly. One of the disadvantages is an increasingly more complicated deployment process.

Apart from productivity and deployment aspects, the usage of components under Free and Open Source licenses is very popular. This is probably due to the fact that the source code is available, can be adapted and most software packages are available for free through the internet (free in price, a.k.a. gratis).

What a lot of vendors don't realize, is that most Free and Open-Source components are not in the public domain. They are in fact copyrighted and distributed under licenses ranging from simple permissive ones (allowing you to do almost everything you want including keeping modifications secret) to more complicated copyleft licenses imposing requirements on derived works. The GNU General Public License (GPL) is the most famous copyleft license around.

Because of the obligations that these licenses impose on users, licenses have become a very important non-functional requirement of software systems. Not obeying these licenses could result in costly lawsuits by copyright holders. Busybox is a well-know example of a software package which has been defended successfully in court several times.

Some clarification

Before you read on, I first want to give some clarification to readers unfamiliar with Free and Open Source software. I have written an earlier blog post about Free and Open-Source software explaining what it is and what it is not. In this blog post I also try to clarify a number of common misconceptions.

Most outsiders think that these lawsuits are about money, which is not true. These lawsuits are not held because people include FOSS components in their commercial products and ask money for these products. As I have explained earlier, selling free and open-source software is fine.

These lawsuits are held because some copyleft licenses require that the source code of the derived products or parts thereof are available under the conditions of the same license, which includes access to the source code. Typically, many vendors refrain from publishing source code and do not obey the obligations that these licenses specify. In many cases, vendors are unaware of this.

Background

The research I have done about this subject has a bit of history, which I'd like to explain here :-)

A couple of years ago, when I was in my first year as a PhD student, I've attended ICSE 2009 and there was one talk that I found very inspiring and gave me a lot of ideas. The paper was titled: 'License Integration Patterns: Addressing License Mismatches in Component-Based Development' and presented by Ahmed E. Hassan, which basically covered a large number of FOSS licenses and described patterns how to combine components governed under various licenses in a proper way.

Although their paper covers a great amount of license issues, they were still looking into automation of their patterns, for example to automatically verify derived works. This process turns out te be quite challenging because automating such processes require you to have powerful deployment tools and a complete notion of all dependencies involved in producing an artifact, such as a binary. Fortunately, deployment research is our expertise and our tools are designed for such purposes. For a while, I had several ideas about a possible solution in mind, but I never implemented anything.

Some time later at ASE 2010, which I also attended, there was another talk related to this subject titled: 'A sentence-matching method for automatic license identification of source code files' and given by Yuki Manabe. In this paper a tool was developed, called Ninka, which can be used to analyse sentences in comments of the source code, to determine under which license a source file is governed. I asked Yuki whether the tool was available somewhere, but unfortunately the idea quickly appeared on the bottom of my todo list and I forgot about this (which is a shame).

A while later Daniel German, who is involved in all the publications I have mentioned, was invited by Eelco Dolstra to visit our group in Delft. That visit resulted in an eventual collaboration between me, Eelco Dolstra (from our group), Daniel German, Julius Davies (from University of Victoria) and Armijn Hemel (who is from the gpl-violations.org project as well as owner of Tjaldur, a company specialised in software governance and license compliance engineering).

Motivation

In order to say something about the rights and obligations of software systems, you must know the following things:

• How are source files combined into a final executable (e.g. static linking, dynamic linking)?
• What licenses govern the (re)use of source files that were used to build the binary?
• How can we derive the license of the resulting binary from the build graph containing the source files?

We together wrote a paper to provide an answer for the first question.

Approach

To provide a good answer for that question, we have crafted a method which traces system calls of build processes (essentially the involved processes and what files go in and out) and we produce build graphs out of these traces. Furthermore, the traces of each package are stored in a central database, so that inter package-dependencies can be determined.

We have used the Nix package manager to manage all the build processes. Nix is a very convenient instrument, as it has a number of good features, such as the fact that builds are pure (so no undeclared dependencies can affect the reliability of our results), that it guarantees dependency completeness (so that we are certain that no crucial dependencies affecting the license of the result binary are missed) and because Nix stores all packages in isolation in separate directories, we can easily identify inter-package relationships by looking at absolute file names. Furthermore, the Nix expression language allows us to modify the standard builder environment, without changing any package build specifications.

Tracing system calls

We trace the following system calls:

• File related system calls, e.g. open(), execve()
• Process related system calls, e.g. fork(), clone(), vfork()

Apart from capturing traces, there were a number issues we had to deal with:

• We have to translate all relative paths to absolute paths
• In Linux, pids wrap around if they exceed 32767, so we have to use a different attribute to distinguish between processes
• Cycles appear in the graph, if files are read/written multiple times, which we have to remove
• The are coarse grained processes, such as the install process, which install multiple files in one run. In the resulting graph it looks like the resulting artifact is dependent on all other artifiacts installed by the same process, which is not true. We have to identify these processes and rewrite them.
• We don't want to know anything about the dependencies of the build tools themselves, because these are not considered derived work.

I have kept the mechanics intentionally brief here, because I don't want to explain them again here. The exact details can be found in the paper.

Build trace graphs

Below I have included a graph of cupsd, an executable belonging to the CUPS package, which we have derived with our tool:

The SVG pictures of this graph as well as several other graphs, can be found here.

By using a graph such as the one of cupsd and by using Ninka to analyse the source files in this graph, one can say something about the license under which the resulting binary is covered. In the paper, we have found an interesting problem with a well known free/open-source package, which I'm not going to reveal in this blog post :-)

Discussion

A reader with Nix experience may probably wonder why we have implemented an additional tracing approach, next to the Nix package manager. The answer is that Nix works on package level, but licenses do not always cover complete packages. There are packages in which individual files are covered under several licenses. Therefore, a more fine-grained tracing approach is required.

Unfortunately, the paper was rejected from ICSE 2012, which I was a bit disappointed about a while ago (although I'm still there anyway because I have to present another paper at HotSWUp). The fact that a paper is not "good enough" is not really what bothers me, but what bothers me is that it is a bit unclear whether this contribution is useful or useless and the fact that the solution is seen as 'too simple' (which is NOT a bad thing IMHO).

Perhaps it may indeed be too simple for a top general conference, but I also have no idea to what other type of conference or journal I could send this. And if this solution is too "practical", would it then perhaps be useful for a 'Software Engineering in Practice Track / Experience Track' at some conference? Although I have heard somebody talking about "engineering perspective", I haven't heard any reviewers suggesting about submitting to another track type.

The only thing that becomes clear to me from the reviews I have received, is that they are not really critical about the contents (although certain details can be strengthened of course), but rather about the significance of the contribution.

I have also noticed that the goal of this paper is generally misunderstood. People think that we are actually solving the complete licensing problem, but instead we provide an important ingredient, which is not there yet. Realising these build graphs, which cover complete build processes are already complicated enough, although the idea of using system call tracing for various purposes is not new. Nobody, however, has used system call tracing for this purpose yet (and therefore had to solve several problems as well). And furthermore, because we're using Nix, the process of experimenting with builds, suddenly becomes much simpler, which with conventional solutions will take significantly more effort.

If you look to the three questions I have given earlier, the paper is about the first question. The ASE 2010 paper provides a solution for the second. The third question is still future work, for an eventual license calculus. But in order to develop such a license calculus the ingredient of complete build trace graphs is required. I'm pretty sure that if I would talk to software deployment people about this, that this story will be appreciated. Unfortunately, as I have explained before, software deployment is a very cold research subject, without a real community.

I'm still thinking what to do with this paper, but I have no idea yet. Furthermore, the amount of time that I have left, is pretty limited. I have decided to put it online and announce it through this blog anyway. Normally, I always report about papers after they have been accepted, but not everything in research can be a 'success story'. Of course, I'm always open for all suggestions.

References

The paper is titled: 'Discovering Software License Constraints: Identifying a Binary's Sources by Tracing Build Processes'. As always, papers can be obtained from my publications page.

The techniques described in this blog post are becoming part of the service portfolio of Tjaldur, a company specialised in software governance. Furthermore, one day I expect that this tool is also going to be integrated in the Nix project.

UPDATE: Never give up! In the meantime, an updated version of this paper titled: "Tracing software build processes to uncover license compliance inconsistencies" has been accepted for ASE 2014! I owe a big thanks to Shane McIntosh, who did some major efforts in improving the paper, and he showed me that there are always new possibilities. Sometimes, it's good to be wrong about something! :-)

Deployment of mutable components

It's been quiet here for a while. Lately, I'm very busy with all kinds of research related things (including working on my thesis). So I thought it's time for a new research related episode here on this blog... Yesterday, a paper of mine got accepted.

Purely functional deployment

As you may know, the Nix package manager is also known as the purely functional deployment model (which happens to be the title of Eelco Dolstra's PhD thesis), because it borrows concepts from purely functional programming languages, such as Haskell. In Nix, packages are derived from purely functional build functions, also called derivations:

• The result of a derivation exclusively depends on the specified inputs of a derivation. If a dependency is not specified, it cannot be found and thus a build fails.
• In a Nix build environment, many side effects are removed. For example, most environment variables are cleared or set to non-existing values, such as HOME=/homeless-shelter. Also certain commands cannot be used because they have side effects, such as date or hostname.
• Various common build tools (e.g. GCC and binutils) have been patched to ignore impure directories, such as /usr/lib and /usr/include which may accidentally allow a build to succeed, with improper dependency specifications.
• Nix stores every component in a so-called Nix store using a special filename, such as: /nix/store/a92pq...-firefox-9.0.1 in which the former part: a92pq... is a hash code derived from all build-time dependencies. This filesystem organisation prevents that dependencies can be implicitly found unless they are explicitly specified in a build process, e.g. through configuration flags or environment variables.
• To improve purity, builds can be optionally performed in a chroot() environment.
• Nix components which have been successfully built, are made immutable by removing the write permission bits, analogous to purely functional language objects which are immutable.

As explained in many earlier blog posts, although this approach is unconventional, it has a number of distinct advantages, such as the fact that multiple versions or variants of components can be safely stored next to each other, upgrades are always safe, dependencies are always complete and so on.

Mutable components

Although Nix has several powerful features, one aspect that it is lacking is supporting the deployment of (which I call) mutable components, such as databases. Apart from the fact that the state of mutable components changes continuously (which cannot be supported in Nix, because components are made immutable), they also have several other important properties:

• Mutable components are typically hosted inside a container, such as a DBMS or application server. In order deploy a mutable component filesystem operations are not always enough; also the container must be notified.
• The state of mutable components is very often stored in an unisolated directory and in a format close to the underlying implementation of the container. In order to transfer a mutable component from one machine to another, copying state files may (in many cases) not work, because they are incompatible with the target architecture or temporarily inconsistent, because of locks and/or unfinished write operations.

Because of these issues, many containers include tools which allow you to capture state in a portable format and in a consistent manner, e.g. mysqladmin. In the paper, I call the actual files representing state, physical state whereas the dump captured by a tool, such as mysqladmin the logical representation of state.

Dysnomia

To support automated deployment of mutable components using concepts similar to Nix, I have developed a tool called Dysnomia, which originates from the Disnix activation scripts package.

Dysnomia provides a generic interface for mutable components. Basically, it's an extended version of the activation scripts, implementing a snapshot and restore operation, which capture the state of a mutable component and restores them (respectively) by invoking tools that can consistently capture state in a portable manner. Also, for certain types it supports incremental snapshots.

Apart from a generic interface to support deployment of mutable components, we also have to identify the logical representation of mutable components in a unique manner, similar to hash codes for immutable Nix components. This makes it possible to perform efficient upgrades, because components with the same name do not have to be deployed again.

In Dysnomia, we address components using the following naming convention:

/dysnomia/<type>/<container identifier>/<component name>/<generation number>

The latter component, the generation number, is derived from a container property, such as a MySQL binlog sequence number or Subversion repository number. It may also be possible to use a timestamp, although this has some practical issues.

Extending Disnix

In a few days time, I have created a very hacky version of Disnix using Dysnomia. I have adapted the deployment process of Disnix and constructed two new variants:

• The simple version. In the transition phase, we capture all state of mutable components, transfer the state and restore the state. During this phase access may be blocked and can be very expensive for large datasets.
• The optimised version. In this version, we transfer the state outside the transition phase so that the system is still accessible. After transferring the state, we enter the transition phase and we transfer an incremental dump of the mutable state components to take changes into account which have been made meanwhile. In this version, the blocking time window is reduced to a minimum reducing the costs of blocking as much as possible.

Discussion

After reading all this, you may think that the problem of dealing with state in conjunction with Nix has been solved and the world has become a much better place. Unfortunately, there are a number of drawbacks, which may be significant:

• The filesystem is used as an intermediate layer, which may be very expensive for very large databases. Database replication tools can solve these problems much more efficiently.
• It is not part of Disnix yet. I'm still thinking of integrating it, but it radically changes the behaviour of Disnix. Perhaps it may become an optional feature in the future.
• Also, the costs of managing state may be higher than the benefits that it gives.
• The number of supported mutable components is still limited, and not all types of mutable components can be efficiently snapshotted.

Where comes the name from?

One of the aspects not covered in the paper is where the name Dysnomia comes from and it probably sounds very strange to you. Unfortunately, the space in the paper is very limited to explain it :-)

This is how I came to it:

• Nix is derived from the Dutch word for nothing: 'Niks' (because if you don't specify dependencies, Nix cannot find anything) combined with UNIX, hence: Nix. Coincidentally, Nix is also a mythological figure as well as a name for a moon of the dwarf planet Pluto which is part of the Kuiper belt.
• Disnix and NixOS also use the original naming convention. For example, Disnix is DIStributed NIX.
• Hydra, our continuous integration server and Charon, our cloud deployment tool are names based on the other moons of Pluto.
• Apparently, Pluto has a fourth moon, which is recently discovered, but it does not have a name yet. Furthermore, I don't think this hacky tool is worthy to bear that new name.
• I took another dwarf planet from the Kuiper belt: Eris, which happens to be the largest dwarf planet discovered so far. Apparently it has a moon named: Dysnomia. So that explains where the name comes from. Furthermore, I also think it's better to take a moon of a different dwarf planet, because Dysnomia could also be used without Nix (and related applications).

Conclusion

Although I have a very experimental extension supporting deployment of mutable components, it has a number of drawbacks. When I started thinking about this tool, I thought it was a great idea. However, after implementing it and doing some experiments, I think that in some cases the costs are actually higher than the benefits. But nonetheless, I still think it's important to have a solution for this problem and some knowledge, which could lead to interesting discussions.

More details can be found in the paper titled: 'A Generic Approach for Deploying and Upgrading Mutable Software Components' which can be found on my publications page. As usual, my slides can be found on my talks page, once I have prepared them.

I'm going to present this paper at the HotSWUp workshop in Zurich (which is co-located with ICSE 2012). In my last blog post, I was a bit disappointed about my ICSE rejection, but it turns out that I'm going to be there anyway, just in case you want to meet up :-)

To prove once more that I have nothing against ICSE and that I actually like it, here is some shameless promotion:

Techniques and lessons for improvement of deployment processes

So far, all my software deployment related blog posts were mostly about techniques implemented in Nix, NixOS and Disnix and some general deployment information.
In my career as a Masters student and PhD student, I have written quite a number of Nix expressions for many packages and I have also "Nixified" several large code bases of commercial companies to make it possible to use the distinct features of Nix to make software deployment processes reproducible and reliable.

However, for many systems it turns out that implementing Nix support (for instance, to allow it to be deployed by our Nix-based deployment tools) is more difficult, tedious and laborious than expected. In this blog post, I'm going to describe a number of interesting techniques and lessons that could improve the deployment process of a system, based on my experience with Nix and Disnix. Second, by taking these lessons into account, it also becomes easier to adopt Nix as underlying deployment system.

1. Deal with the deployment complexity from the beginning in your development process. Although this lesson isn't technical and may sound very obvious to you, I can ensure you that if you have a codebase which grows rapidly, without properly thinking about deployment, it becomes a big burden to implement the techniques described in this blog post later in the development process. In some cases, you may even have to re-engineer specific parts of your system, which can be very expensive to do, especially if your codebase consists of millions of lines of code.
   
   
2. Make your deployment process scriptable. This lesson is also an obvious one, especially if you have adopted an agile software development process, in which you want to create value as soon as possible (without a deployed system there is no value).
   
   Although it's obvious, I have seen many cases where developers still build and package components of a software system by manually performing build and package tasks in the IDE and by doing all the installation steps by hand (with some deployment documentation). Such deployment processes typically take a lot of time and are subject to errors (because they are performed manually and humans make mistakes).
   
   Quite often these developers, who perform these manual/ad-hoc deployment processes, tell me that it's much too complicated to learn how a build system works (such as GNU Make or Apache Ant) and to maintain these build specifications.
   
   The only thing I can recommend to them is that it really is worth the effort, because it significantly reduces the time to make a new release of the product and also allows you test your software sooner and more frequently.
   
   
3. Decompose your system and their build processes. Although I have seen many software projects using some kind of automation, I have also encountered a lot of build tools which treat the the complete system as a single monolithic blob, which must be built and deployed as a whole.
   
   In my opinion it's better to decompose your system in parts which can be built separately, for the following reasons:
   
   
   • It may significantly reduce build times, because only components that have been changed have to be rebuilt. There is no need to reexamine the complete codebase for each change.
   • It increases flexibility, because it becomes easier to replace specific parts of a system with other variants.
   • It allows a better means of sharing components across systems and better integration in different environments. As I have stressed out in an earlier blog post, software nowadays is rarely self-contained and run in many types of environments.
   • It allows you to perform builds faster, because they can be performed in parallel.
     
   
   In order to decompose a system properly, you have to think early about a good architecture of your system and keep reflecting about it. As a general rule, the build process of a sub component should only depend on the source code, build script and the build results of the dependencies. It should not be necessary to have cross references between source files among components.
   
   Typically, a bad architecture for a system also implies a very complex and inefficient build process.
   
   I have encountered some extreme cases, in which the source code system is one big directory of files, containing hundreds of dependencies including third-party libraries in binary form, infrastructure components (such as the database and web servers) containing many tweaks and custom configuration files.
   
   Although such code bases can be automatically deployed, it offers almost no flexibility, because it is a big burden to replace a specific part (such as a third party library) and still ensure that the system works as expected. Also it requires the system to be deployed in a clean environment because it offers no integration. Typically these kind of systems aren't updated that frequently either.
   
   
4. Make build-time and run-time properties of components configurable. Another obvious lession, but I quite frequently encounter build processes which make implicit assumptions about the locations where specific dependencies can be found.
   
   For example, in some Linux packages, I have seen a number of Makefiles which have hardcoded references to the /usr/bin directory to find specific build tools, which I have to replace myself. Although most Linux systems have these build-time dependencies stored in this folder, there are some exceptions such as NixOS and GoboLinux.
   
   In my opinion it's better to make all locations and settings configurable, either by allowing it to be specified as a build parameter, environment variable (e.g. PATH) or stored in a configuration file, which can be easily edited.
   
   
5. Isolate your build artifacts. I have noticed that some development environments store the output of a build in separate folders (for example Eclipse Java projects) whereas others store all the build artifacts of all projects in a single folder (such as Visual Studio C# projects). Similarly, with end user installations in production environments, libraries are also stored in global directories, such as /usr/lib on Linux environments, or C:\Windows\System32 on Windows.
   
   Based on my experience with Nix, I think it's better to store the build output of every component in isolation, by storing them in separate folders. Although this makes it harder to find components, it also offers some huge benefits, such as the ability to store multiple versions next to each other. Also upgrades can be made more reliable, because you can install another version next to an existing one. Furthermore, builds can also be made more pure and reproducible, because it's required to provide the locations of these components explicitly. In global folders such as /usr/lib a dependency may still be implicitly found even if it's not specified, which cannot happen if all the dependencies are stored in separate locations. More information about isolation can be found in my blog post about NixOS and the FHS.
   
   
6. Think about a component naming convention. Apart from storing components in separate directories which offers some benefits, it's also important to think about how to name them. Typically, the most common naming scheme that's being used consists of a name and version number. This naming scheme can be insufficient in some cases, for example:
   
   
   • It does not take the architecture of the component into account. In a name-version naming scheme a 32-bit variant and a 64-bit variant are considered the same, while they may not be compatible with another component.
   • It does not take the optional features into account. For example, another component may require certain optional features enabled in order to work. It may be possible that a program incorrectly uses a component which does not support a required optional feature.
   
   I recommend you to also take relevant build-time properties into account when naming a component. In Nix you get such a naming convention for free, although the naming convention is also very strict. Nix hashes all the build-time dependencies, such as the source code, libraries, compilers and build scripts and makes this hash code part of the component name, for example: /nix/store/r8vvq9kq18pz08v24918my6r9vs7s0n3-firefox-8.0.1. Because of this naming scheme, different variants of a component, which are (for example) compiled with another version of a compiler of for a different system architecture do not share the same name.
   
   In some cases, it may not be necessary to adopt such a strict naming scheme, because the underlying component technology used is robust enough to offer enough flexibility. In one of my case studies covering Visual Studio projects, we only distinguish between variants of component by taking the name, version, interface and architectures into account. because they have no optional features and we assume the .NET framework is always compatible. We organize the filesystem in such a way that 32-bit and 64-bit variants are stored in separate directories. Although a naming scheme like this is less powerful than Nix's, it already offers huge benefits compared to traditional deployment approaches.
   
   Another example of a more strictly named component store is the .NET Global Assembly Cache (GAC), which makes a distinction between components based on the name, version, culture and a cryptographic key. However, the GAC is only suitable for .NET library assemblies and not for other types of components and cannot take other build properties into account.
   
   
7. Think about component composition. A system must be able to find its dependencies at build-time and run-time. If the components are stored in a separate folders, you need to take extra effort in order to compose them. Some methods of addressing dependencies are:
   
   
   • Modify the environment. Most platforms use environment variables to address components, such as PATH for looking up executables, CLASSPATH for looking up Java class files, PERL5LIB for addressing Perl libraries. In order to perform a build these environment variables must be adapted to contain all the dependencies. In order to run the executable, the executable needs to be wrapped in a process, which sets these environment variables. Essentially, this method binds dependencies statically to another component.
   • Composing symlink trees. You can also provide a means of looking up components from a single location by composing the contents of the required dependencies in a symlink tree and by referring to its contents. In conjunction with a chroot environment, and a bind mount of the component directory, you can make builds pure. Because of this dynamic binding approach, you can replace dependencies, without a rebuild/reconfiguration, but you cannot easily run one executable that uses a particular variant of a library, while another runs another variant. This method of addressing components is used by GoboLinux.
   • Copy everything into a single folder. This is a solution which always work, however it is also a very inefficient as you cannot share components.
   
   Each composition approach has its own pros and cons. The Nix package manager supports all three approaches, however the first approach is mostly used for builds as its the most reliable one, because static binding always ensures that the dependencies are present and correct and that you can safely run multiple variants of compositions simultaneously. The second approach is used by Nix for creating Nix profiles, which end users can use to conveniently access their installed programs.
   
   
8. Granularity of dependencies. This lesson is very important while deploying service-oriented systems in a distributed environment. If service components have dependencies on components with a large level of granularity, upgrades may become very expensive because some components are unnecessarily reconfigured/rebuilt.
   
   I have encountered a case in which a single configuration file was used to specify the locations of all service components of a system. When the location of a particular service component changes, every service component had to be reconfigured (even services that did not need access to that particular service component) which is very expensive.
   
   It's better to design these configuration files in such a way that they only contain properties that a service components need to know.
   
   

Conclusion

In this blog post I have listed some interesting lessons to improve the deployment process of complex systems based on my experience with Nix and related tools. These can be implemented in various deployment processes and tools. Furthermore, it becomes easier to adopt Nix related tooling by taking these lessons into account.

I also have to remark that it is not always obvious to implement all these lessons. For example, it is hard to integrate Visual Studio C# projects in a stricter deployment model supporting isolation, because the .NET runtime has no convenient way to address run-time dependencies in arbitrary locations. However, there is a solution for this particular problem, which I have described in an earlier blog post about .NET deployment with Nix.

UPDATE: I have given a presentation about this subject at Philips recently. As usual, the slides can be obtained from the talks page of my homepage.

An evaluation and comparison of GoboLinux

In this blog post, I'm going to evaluate deployment properties of GoboLinux and compare it with NixOS. Both Linux distributions are unconventional because they deviate from the Filesystem Hierarchy Standard (FHS). Apart from this, GoboLinux shares the same idea that the filesystem can be used to organize the management of packages and other system components, instead of relying on databases.

The purpose of this blog post is not to argue which distribution is better, but to see how this distribution achieves certain deployment properties, what some differences are compared to NixOS and what we can learn from it.

Filesystem organization

Unlike NixOS, which only deviates from the FHS where necessary, GoboLinux has a filesystem tree which completely deviates from the FHS, as shown below:

GoboLinux stores static parts of programs in isolation in the /Programs folder. The /System folder is used to compose the system, to store system configuration settings and variable data. /Files is used for storing data not belonging to any program. /Mount is used for accessing external devices such as DVD-ROM drives. The /Users folder contains home directories. /Depot is a directory without a predefined structure, which can be organized by the user.

GoboLinux also provides compatibility with the FHS. For example, the /usr and /bin directories are actually also present, but not visible. These directories are in fact symlinks trees referring to files in the /System directory (as you may see in the picture above). They are made invisible to end-users by a special kernel module called GoboHide.

Package organization

Like NixOS, GoboLinux stores each package in a seperate directories, which do not change after they have been built. However, GoboLinux uses a different naming convention compared to NixOS. In GoboLinux every package uses the /Program/<Name>/<Version> naming convention, such as: /Programs/Bzip2/1.0.4 or /Programs/LibOGG/1.1.3. Furthermore, each program directory contains a Current symlink which points to the version of the component, that is actually in use. Some program directories also have a Settings/ directory containing system configuration files for the given package.

The use of isolated directories offers a number of benefits like NixOS:

• Because every version is stored in its own directory, we can safely store multiple versions next to each other, without having to worry that a file of another version gets overwritten.
• By using a symlink, pointing to the current version, we can atomically switch between versions by flipping the symlink (also used by Nix to switch Nix profiles), which ensures that there is no situation in which a package contains both files of the old version and new version.

In contrast to NixOS, GoboLinux uses a nominal naming convention and dependency specifications, which are based on the name of the package and version number. With a nominal naming convention, it cannot make a distinction between several variants of components, for example:

• It does not reflect which optional features are enabled in a package. For example, many libraries and programs have optional dependencies on other libraries. Some programs may require a particular variant of a library with a specific option enabled.
• It does not take the build-time dependencies, such as build tools or library versions into account, such as the version of GCC or glibc. Older versions may have ABI incompatibilities with newer versions.
  
• It does not take the architecture of the binaries into account. Using this naming scheme, it is harder to store 32-bit and 64-bit binaries safely next to each other.
  

In NixOS, however, every package name is an exact specification, because the component name contains an hash-code derived from all build-time dependencies to build the package, such as the compiler version, libraries and build scripts.

For example, in NixOS bzip2 may be stored under the following path: /nix/store/6iyhp953ay3c0f9mmvw2xwvrxzr0kap5-bzip2-1.0.5. If bzip2 is compiled with a different version of GCC or linked to a different version of glibc, it gets a different hash-code and thus another filename. Because no component shares the same name, it can be safely stored next to other variants.

Another advantage of the Nix naming convention is that unprivileged users can also build and install software without interfering with other users. If for example, a user injects a trojan horse in a particular package, the resulting component is stored in a different Nix store path and will not affect other users.

However, because of these exact dependency specifications, upgrades in NixOS may be more expensive. In order to link a particular program to a new version of a library, it must be rebuild, while in GoboLinux the library dependency can be replaced without rebuilding (although it may not guarantee that the upgraded version will work).

System composition

Of course, storing packages in separate directories does not immediately result in a working system. In GoboLinux, the system configuration and structure is composed in the /System directory.

The /System directory contains the following directories:

• Kernel/, contains everything related to the Linux kernel, such as Boot/ storing kernel images, Modules/ storing kernel modules and Objects/ storing device files.
  
• Links/, is a big symlink tree composing the contents of all packages that are currently in use. This symlink tree makes it possible to refer to executables in Executables/, libraries in Libraries/ and other files from a single location. The Environment/ directory is used to set essential environment variables for the installed programs.
• Settings/ contains configuration files, which in other distributions are commonly found in /etc. Almost all files are symlinks to the Settings/ folder included in each program directory.
• Variable/ contains all non-static (variable) data, such as cache and log files. In conventional distributions these files are stored in /var.

Like NixOS, GoboLinux uses symlink trees to compose a system and to make the contents of packages accessible to end users.

Recipes

Like NixOS, GoboLinux uses declarative specifications to build packages. GoboLinux calls these specifications recipes. Each recipe directory contains a file called Recipe which describes how to build a package from source code and a folder Resources/ defining various other package properties, such as a description and a specification of build-time and run-time dependencies.

compile_version=1.8.2
url="$httpSourceforge/lesstif/lesstif-0.95.2.tar.bz2"
file_size=2481073
file_md5=754187dbac09fcf5d18296437e72a32f
recipe_type=configure
make_variables=(
   "ACLOCALDIR=$target/Shared/aclocal"
   "aclocaldir=$target/Shared/aclocal"
)

An example of a recipe, describing how to build Lesstif, is shown above. Basically, for autotools based projects, you only need to specify the location where the source code tarball can be obtained, and some optional parameters. From this recipe, the tarball is download from the sourceforge web server and the standard autotools build procedure is performed (i.e. ./configure; make; make install) with the given parameters.

In the Resources/Dependencies run-time dependencies can be specified and in Resource/BuildDependencies build-time dependencies can be specified. The dependencies are specified by giving a name and an optional version number or version number range.

GoboLinux recipes and Nix expressions both offer abstractions to declaratively specify build actions. A big difference between those specifications, is the way dependencies are specified. In GoboLinux only nominal dependency specifications are used, which may not be complete enough, as explained earlier. In Nix expressions, you refer to build functions that build these dependencies from source-code and their build-time dependencies, which are stored in isolation in the Nix store using hash codes.

Furthermore, in Nix expressions run-time and build-time dependencies are not separately specified. In Nix, every run-time dependency is specified as build-time dependency. After a build has been performed, Nix conservatively scans for hash occurrences of build-time dependencies inside a realized component to identify them as run-time dependencies. Although this sounds risky, it works extremely well, because chances are very slim that an exact occurrence of a hash code represents something else.

Building packages

In GoboLinux, the Compile tool can be used to build a package from a recipe. Builds performed by this tool are not entirely pure, because it looks for dependencies in the /System/Links directory. Because this directory contains all the installed packages on the system, it may be possible that the build of a recipe may accidentally succeed when a dependency is not specified, because it can be implicitly found.

In order to make builds pure, GoboLinux provides the ChrootCompile extension, which performs builds in a chroot environment. ChrootCompile tool bind mounts the /Program directory in the chroot environment and creates a small /System only containing symlinks to the dependencies that are specified in the recipe. Because only the specified dependencies can be found in /System/Links directory, a build cannot accidentally succeed if a dependency has been omitted.

Both Nix and ChrootCompile have the ability to prevent undeclared dependencies to accidentally succeed a build, which improves reproducibility. In Nix, this goal is achieved differently. In Nix, the environment variables in which a build is performed are completely cleared (well not completely, but almost :-) ), and dependencies which are specified are added to the PATH and other environment variables, which allow build tools to find the dependencies.

Nix builds can be optionally performed in a chroot environment, but this is not mandatory. In NixOS, the traditional FHS directories, such as /usr don't exist and cannot make a build impure. Furthermore, common utilities such as GCC have been patched so that they ignore standard directories, such as /usr/include, removing many impurities.

Furthermore, Nix also binds dependency relationships statically to the executables (e.g. by modifying the RPATH header in an ELF binary), instead of allowing binaries to look in global directories like: /System/Links, which GoboLinux executables do. Although, GoboLinux builds are pure inside a chroot environment, their run-time behaviour may be different when a user decides to upgrade a version of its dependency.

Conclusion

In this blog post I did an evaluation of GoboLinux and I compared some features with NixOS. In my opinion, evaluating GoboLinux shows a number of interesting lessons:

• There are many deployment related aspects (and perhaps other aspects as well) that can be solved and improved by just using the filesystem. I often see that people write additional utilities, abstraction layers and databases to perform similar things, while you can also use symlink trees and bind mounts to provide abstractions and compositions. Additionally, this also shows that the filesystem, which is an essential key component for UNIX-like systems, is still important and very powerful.
• Storing packages in separate directories is a simple way to manage their contents, store multiple versions safely next to each other and to make upgrades more reliable.

GoboLinux and NixOS have a number of similar deployment properties, because of their unorthodox filesystem organization, but also some differences and limitations. The following table summarizes the differences covered in this blog post:

	GoboLinux	NixOS
FHS compatibility	Yes (through hidden symlink trees)	No (deviates on some FHS aspects)
Component naming	Nominal (name-version)	Exact (hash-name-version)
Component binding	Dynamic (dependency can be replaced without rebuild)	Static (rebuild required if a dependency changes)
Granularity of component isolation	Only between versions	Between all build-time dependencies (including version)
Unprivileged user installations	No	Yes
Build specifications	Stand-alone recipes	Nix expressions which need to refer to all dependency expressions
Build-time dependency addressing	/System/Links symlink tree in chroot environment	Setting environment variables + modified tools + optional chroot environment
Run-time dependencies	Specified manually	Extracted by scanning for hash occurrences
Run-time dependency resolving	Dynamic, by looking in /System/Links	Static (e.g. encoded in RPATH)

The general conclusion of this blog post is that both distributions achieve better deployment properties compared to conventional Linux distributions, by their unorthodox filesystem organisation. Because of the purely functional deployment model of the Nix package manager, NixOS is more powerful (and strict) than GoboLinux when it comes to reliability, although this comes at the expense of extra rebuild times and additional disk space.

The only bad thing I can say about GoboLinux is that the latest 014.01 release is outdated (2008) and it looks like 015 is in progress for almost three years... I'm not sure if there will be a new release soon, which is a pity.

And of course, apart from these deployment properties, there are many other differences I haven't covered here, but that's up to the reader to make a decision.

I'm planning to use these lessons for a future blog post, which elaborates more on techniques for making software deployment processes more reliable.

On Nix, NixOS and the Filesystem Hierarchy Standard (FHS)

Our work on NixOS has been topic of discussion within various free software/open source projects and websites. For example, we have been discussed on the Debian mailing list and on Linux Weekly News.

One of the criticisms I often receive is that we don't comply with the Filesystem Hierarchy Standard (FHS). In this blog post, I'd like to give a response on the FHS and why NixOS deviates from it.

What is the Filesystem Hierarchy Standard?

The purpose of the Filesystem Hierarchy Standard (FHS) is to define the main directories and their contents in Linux operating systems. More specifically:

• It defines directory names and their purposes. For example, the bin directory is for storing executable binaries, sbin is for storing executable binaries only accessible by the super-user, lib is for storing libraries.
• It defines several hierarchies within the filesystem, which have separate purposes:
  
  The primary / hierarchy contains essential components for the boot process and system recovery. The secondary hierarchy: /usr contains components not relevant for booting and recovery. Moreover, files in this directory should be shareable across multiple machines, e.g. through a network filesystem. The tertiary hierarchy: /usr/local is for the system administrator to install software locally.
  
  Hierarchies and special purpose directories are usually combined. For example, the /bin directory contains executable binaries relevant for booting and recovery which can be used by anyone. The /usr/bin directory contains executable binaries not relevant for booting or recovery, such as a web browser, which can be shared across multiple machines. The /usr/local/bin directory contains local executables installed by the system administrator.
  
  The FHS also defines the /opt directory for installing add-on application software packages. This directory can also be considered a separate hierarchy, although it is not defined as such in the standard. This directory also contains the same special purpose directories, such as bin and lib like the primary, secondary and tertiary hierarchies. Furthermore, also the /opt/<package name> convention may be used, which stores files specific to a particular application in a single folder.
  
• It also makes a distinction between static and variable parts of a system. For example, the contents of the secondary hierarchy /usr are static and could be stored on a read-only mounted partition. However, many programs need to modify their state at runtime and store files on disks, such as cache and log files. These files are stored in variable storage directories, such as /var and /tmp.
  
• It defines what the contents of some folders should look like. For example, a list of binaries which should reside in /bin, such as a Bourne compatible shell.
  
• The standard has some practical problems. Some aspects of the filesystem are undefined and need clarification, such as a convention to store cross compiling libraries. Furthermore, the standard is quite old and newer Linux features such as the /sys directory are not defined in the standard. To cope with these issues, many distributions have additional clarifications and policies, such as the Debian FHS policy.

Linux Standard Base

The Filesystem Hierarchy Standard (FHS) is part of another standard: The Linux Standard Base (LSB), which incorporates and extends several other standards, such as POSIX and the Single UNIX specification.

The LSB standard has been developed, because there are many Linux based systems out there. What they all have in common is that they run the Linux kernel, and quite often a set of GNU utilities (that's why the free software foundation advocates GNU/Linux as the official name for these kind of systems).

Apart from some similarities, there are many ways in which these systems differ from each other, such as the package manager which is being used, the way the file system is organized, the software which is supported etc.

Because there are many Linux systems available, the Linux Standards Base is designed to increase compatibility among these Linux distributions, so that it becomes easier for software vendors to ship and run Linux software, even in binary form. Many of the common Linux distributions such as Debian, SuSE and Fedora try to implement this standard, although it has several issues and criticisms.

NixOS and the FHS

In NixOS, we have an informal policy to follow the FHS as closely as possible, but to deviate from it where necessary. An important aspect is that we can't follow the structure of the primary /, secondary /usr and tertiary hierarchies: /usr/local.

The main reason to refrain from using these hierarchies is that they don't provide isolation. For example the /usr/lib directory contains a wide collection of shared libraries belonging to many packages. To determine to which package a particular library belongs, you need to have a look in the database of the package manager. Because most libraries can be found in the same location, e.g. /usr/lib, it is very tempting to forget specifying a dependency, because they can still be implicitly found.

The purpose of the Nix package manager is to achieve purity, which means that the build result of a package should exclusively depends on the source code and input parameters. Purity ensures that the build of a package can be reproduced anywhere and that a package can be transferred to any machine we want, with the guarantee that the dependencies are present and correct.

Nix achieves purity by using the filesystem as a database and to store packages in isolation in a special directory called the Nix store. For example:

/nix/store/r8vvq9kq18pz08v249h8my6r9vs7s0n3-firefox-8.0.1

The path above refers to the Mozilla Firefox web browser. The first part of the directory name: r8vvq9kq18pz08v249h8my6r9vs7s0n3 is a hash-code derived from all build time dependencies. By using this naming convention, components can be stored safely in isolation from each other, because no component shares the same name. If Firefox is compiled with a different version of GCC or linked to a different version of the GTK+ library, the hash code will differ and thus not interfere with another variant.

Because of the naming scheme of the Nix store and the fact that we don't use global directories to store binaries and libraries, the build of a Nix package will typically fail if a required build time dependency is omitted. Furthermore, it also restricts undeclared dependencies which may allow a build to accidentally succeed (and therefore also prevents incomplete dependency specifications).

Another deviation of the FHS, is not following the list of required binaries and libraries in the /bin, /lib etc. directories. For example, the FHS requires a Bourne compatible shell in /bin/sh, some mkfs.* utilities in /sbin and for historic reasons, a sendmail executable in /usr/lib.

In NixOS, apart from the /bin/sh executable (which is a symlink to the bash shell in the Nix store), we don't store any binaries in these mandatory locations because it is not necessary and it also makes builds impure.

Discussion

Now that I have explained why we deviate from the FHS on some points, you probably may wonder, how we achieve certain properties defined in the FHS in NixOS:

• How to determine files for the boot process and recovery? Because we don't use hierarchies, files relevant for the boot process can't be found in /bin and /lib. In NixOS, we basically generate a small base system as a Nix component serving this purpose, which is stored as a single component in the Nix store.
  
• How to share components? Because we have no secondary hierarchy, you can't share components by storing the /usr directory on a network file system. In Nix, however, the entire Nix store is static and shareable. Furthermore, it's even more powerful, because the hash codes inside the component names prevent different variants of NixOS to use the incorrect versions of a component. For example, you can safely share the same Nix store across 32-bit and 64-bit machines, because this parameter is reflected in the hash.
  
  In fact, we already use sharing extensively in our build farm, to generate virtual machines to perform testcases. Apart from a Linux kernel image and an initial RAM disk, the components of the entire virtual network are shared through the host system's Nix store, which is mounted as a network file system.
• How to find dependencies? Because we store all software packages in the Nix store, it is harder to address components in e.g. scripts and configuration files, because all these components are stored in separate directories, and aren't necessarily in the user's PATH.
  
  I have to admit that this is inconvenient in some cases, however in NixOS we usually don't manually edit configuration files and write scripts.
  NixOS is a distribution that is unconventional in this sense, because its goal is to make the entire deployment process model-driven. Instead of manually installing packages and adapting configuration files in e.g. /etc. In NixOS, we generate all the static parts of a system from Nix expressions, including all configuration files and scripts. The Nix expression language provides the paths to the components.

Improvements

Although we have to deviate from the FHS for a number of reasons, there are also a few improvements we could make in the organization of the filesystem:

• The directory names and purposes within the hierarchies can be more consistently used within Nix packages. Essentially, you could say that every component in the Nix store is a separate hierarchy.
  
  For example, I think it's a good thing to use /nix/store/<package>/bin for storing binaries, and /nix/store/<package>/lib for libraries. Sometimes installation scripts of packages do not completely adhere to the FHS and need some fixing. For example, some packages install libraries in the libexec directory, which is not defined by the FHS.
  
  We could make an additional check in the generic builder of Nixpkgs, checking the structure of a package and to report inconsistencies.
  
• For the variable parts of the system, we can adhere better to the FHS. For example, the current version of the FHS defines the /srv directory used for serving files to end-users, through a service (e.g. a web server). In NixOS, this directory is not used.
• Because the FHS standard has some gaps, we could also define some additional clarification, like other Linux distributions do.

Conclusion

In this blog post I've explained the idea behind the Filesystem Hierarchy Standard (FHS) and I have explained why we deviate from it in NixOS. The main reason is that the organization of specific parts of the file system, conflict with important aspects of the Nix package manager, such as the ability to store components isolation and to guarantee correct and complete dependencies.

Furthermore, apart from the FHS, NixOS cannot completely implement other parts of the LSB either. For example, in the LSB a subset of the RPM package manager is defined as default package manager, which imperatively modifies the state of a system.

If we would implement this in NixOS, we can no longer ensure that the deployment of a system is pure and reproducible. Therefore, we sometimes have to break from the traditional organization and management of Linux systems. However, sometimes I get the impression that the FHS is considered a holy book and by breaking from it, we are considered heretics.

Related work

• GoboLinux is also a Linux distribution not obeying the FHS, with a custom filesystem organization. They also have the vision that the filesystem can act as a database for organizing packages.
• The Mancoosi project is also a research project investigating package management related problems, like we do. Their research differs from us, because they don't break away from the traditional filesystem organization and management of Linux systems. For example, a lot of their research deals with maintainer scripts of packages, which goal is to "glue" files from a package to files on the system, e.g. by imperatively modifying configuration files.
  
  By keeping the traditional management intact, this introduces a whole bunch of challenges to make deployment efficient, reliable and reproducible. For example, they have investigated modeling techniques for maintainer scripts and system configurations, to simulate whether an upgrade succeed and to determine inverse operations to perform rollbacks.
  
  In our research, we achieve more reliable deployment by breaking from the traditional model.