When and Where Order Matters

Recently I have been hearing the resurfacing of an old debate: whether order matters in the execution of configuration management policy. The debate started years ago when CFEngine introduced a declarative approach to configuration in order to separate the WHAT from the HOW -- and move to a more knowledge-oriented form of management. Alva Couch, my friend and colleague, likened CFEngine to Prolog.

Declaration seems to make people uncomfortable. Unless you are trained in management, it feels wrong to simply declare what you want, without explaining how to get it. In the words of Rich Hickey, engineers are trained to `complect' WHAT we want with HOW we get it -- muddling things up. We do not learn declarative methods in college. We learn imperative methods -- flow charts and assembly-line thinking: we are all children of the Tofflers' Second Wave industrialization. But the time for factories and making humans work like machines is over. The future lies in knowledge-oriented systems.

Putting order in order

In CFEngine, the natural thing to do was to compute an optimum approach to processing configuration declarations that was not the order in which they were written, but grouped into bulk items that could be handled efficiently. This was not necessarily intuitive, as it did not necessarily follow the order in which the declarations were made -- as we all learnt in school.

In 2001-2002, Steve Traugott rebelled against this idea, insisting that the only correct way to ensure predictability was to baseline a system and reconstruct it along a unique path, using a unique set of commands. He called this congruence, as an antidote to convergence. He used the phase: Why Order Matters. His argument, while not incorrect, missed some obvious points, and he arrived at an exaggerated conclusion.

Does order matter? Of course it does. Chomsky proved it. CFEngine never claimed that order doesn't matter, only that there is more than one correct order, and that the best order might not be the one you first think of. What CFEngine did prove was that it is NOT necessary to erase, or baseline a system and reconstruct it using a unique set of commands. That is what Alva Couch called the nuclear approach configuration management.

The invention of zero

Let's examine when order matters. First let's see why you don't have to start from a known state to get to a known state.

This has a simple analogue in mathematics: zero. Indeed, baselining is a perfect example of this: no matter what state you start with, you can set it to zero.

   1 * 0 -> 0
   2 * 0 -> 0
   3 * 0 -> 0

   4 * 0 + x -> x
   5 * 0 + x -> x

   etc..

Convergent operations, in CFEngine are just renormalized zero operations, as in the last lines. Starting from any initial state, we can get any predictable outcome. As long as the operations are sufficiently atomic (no dependencies to introduce fragility), we can always arrange this robust predictability. This is why CFEngine's core language is built as a low level `assembler language' for infrastructure -- each statement is a robust, autonomously healing entity, that can be combined in any order to make parallelizable or serial processes, as you like.

When order matters

Let's see under what circumstances a particular order needs to be preserved. Order matters when:

  • Copying an existing pattern with fidelity (preservation of order).
  • When optimizing for compression (computing optimum order).

For example, copying of DNA is an example of the former. A change in DNA ordering is called a mutation, and it usually results in the death of a cell, although it occasionally results in marvellous adaptations. Parallel processing is an example of the second of these. By breaking up computations into minimally dependent sections, you can parallelize code and alter the order of the computation to make it vastly more efficient. It might not be the naive ordering that you first thought of in an assembly line logic, but it is possible to prove that the result is correct. All of High Performance Computing is based on this idea. In cooking too, a smart Chef will prepare different ingredients in parallel, as separate processes to optimize the eventual result.

So, we don't have to execute operations in the naive ordering to necessarily get the right result. It is not even true that it will be faster if we do this, as there are many efficiencies to be gained by optimal scheduling, as any multitasking system knows. We know, for instance, that CFEngine's scheduling runs orders of magnitude faster than other Ruby-based tools (see for example this), and this cannot only be put down to the inefficiencies of Ruby.

In declarative languages like Prolog, order is completely out of the hands of the `programmer' or `declarer'. Prolog can compute a result because its facts and assumptions are all constant and deterministic. In configuration reasoning, that is not true. The very act of making changes to an environment we do not fully control means that the assumptions and facts change in real time -- so we always have a situation of uncertain, incomplete information. The `clever' aspect of CFEngine is to find an approximation to determinism within a framework of incomplete certainty. That is non-trivial, but this is what brings robustness (if a few cognitive headaches) to its users.

Order belongs to pattern or grammar

The Chomsky hierarchy is a classification of patterns in which ordering matters in varying degrees. The term grammar is used for a pattern constructed from a symbolic alphabet, in linguistics and computer science. Chomsky showed that there are four levels of grammar starting from regular languages, where order is weakly important, to context free languages and recursively enumerable grammars. All of these automata can be computed by different kinds of state machine. The regular languages can be handled by simple finite state machines, and at the other end of the complexity a full Turing machine is needed to model the grammar. The role of order in each of these languages depends on the underlying language.

We tend to confuse the fact that we read linearly with the uniqueness of a particular order. Consider this bit of XML.

<books>
 <book isbn="123456">
   <title>Great Expectations</title>
    <author>Charles Dickens</author>
 </book>

 <book isbn="1234567">
   <title>I, Robot</title>
    <author>Isaac Asimov</author>
 </book>

 <book isbn="1234568">
   <title>The fountainhead</title>
    <author>Ayn Rand</author>
 </book>
</books>

The linear structure of this language represents nothing real about the data. The books were not written in this order, they do not have to read in this order, and they would not appear in this order on the shelf. Why are they ordered at all? This is an artifact. We wrapped this order independent pattern (a regular language) into an order-dependent one (a context free language) in order to facilitate processing in an imperative (context free) language framework. In other words, it was the tool the tricked us into an optical illusion, not the problem's inherent nature. We have to preserve order within the stanzas of the XML wrapping (because it is that kind of language), but outside this, order means nothing.

In calculus, or finite difference methods, we solve an equation of a single variable in a serial manner starting from an initial (boundary) value, and generating a chain of values that add up to the result. That is because difference methods are relative methods. About this we can say the following: if you have multivariate problems, the sequential approach rapidly needs to be parallelized; moreover, to bring predictability to solutions, we need absolute methods, not relative ones: the method of fixed points -- which is where CFEngine's convergence comes in.

Robustness and fragility

Order matters when there are strong dependencies between the steps in a problem, i.e. when there is no atomic change operation that will resolve the configuration. In the late 1990s, I proved that if you continuously loop around a test for ideal state, in which you try to set dependent policies in a random order, they will resolve each other after a couple of iterations. It took four years to publish this result, such was the horror amongst computer scientists. Alva Couch (who is a lot quicker to `get' these unconventional ideas) generalized this idea to arbitrary dependencies in his Maelstrom paper. We now know that a wide class of problems can be immunized against strong ordering in a self-healing framework that is robust to errors.


  A -> B -> C ->  BREAK!  -> D

Schemes based on a rigid ordering are maximally fragile structures: in a chain, every link is a single point of failure, and the only remedy is to erase and start again. CFEngine does not encourage linear sequences; nevertheless, today, a chain forcefully coded in CFEngine can heal from any point of failure without a total destructive reset of the system. This is the way to make infrastructure become reliable to the point where we can move on to more pressing challenges, like using the reliable infrastructure to build value for society.

The attempts to discredit non-intuitive ordering have been of the form: `I don't get it, so it can't be true'. That might be good enough for yesterday's junior system administrators, but tomorrow's IT infrastructure engineers need to get educated to stay in the game. CFEngine is still ahead of this game, enabling robust self-healing in cases where other tools merely stop and cry havoc.

See also: Configuration Management: Models and Myths