#4: Race to the finish: cache or check?
Parallelizing workflow outcomes
In post #3, we looked at how make creates stability of outcomes, compared to a sequences of weakly defined outcomes, with the notion of a desired end state. Moreover, it builds artifacts that can be kept (cached) along the way to avoid repetition of work. That’s a powerful improvement over simple runbook-oriented scripting, but it depends on synchronization based on trusting clocks and timestamps. Before we leave ‘make’, let’s take a moment to think about how its simple behavior could be improved upon.
The semi-realistic example in our previous post, implemented as a Makefile, relied on the synchronization of clocks, which is a highly complex and interesting problem in distributed systems. No two independent machines have the same clock or tell the same time, so timestamps belonging to different machines are not exactly comparable. Of course we can work around this approximately with services like NTP that keep clock times close together — but this is not foolproof.
The previous ‘make’ example was also devoid of features for building workflows across multiple machines. Some kind of interprocess communication, or shared state seems to be in order... A runbook approach would try to push event notifications between stages to manage this, without a clear promise about what the outcome might be. A Makefile improves on this by fetching what it needs from dependencies only when it needs to produce a policy sanctioned output. This leads to greater stability and quality control. The main problem in translating this for distributed systems is that we have to deal with multiple clocks, and multiple (independent) measures of time that can only be approximately synchronized.
If we use persistent storage (something like a SAN service, for instance) then this problem might be avoided, depending a bit on the semantics of the filesystem: if a storage service has a single clock that determines relative times for all parties, then all file times would be automatically calibrated by virtue of their arriving at a single service point. This might no longer be true if there are multiple volumes with sharded servers. If tampering in the pipeline’s interior states were possible, including clock errors, the Makefile approach is vulnerable to faulty blocking, as long as we rely on update times.
In an actual build system, a polled recomputation of a file hash, or binary comparison would avoid this possible uncertainty at the expense of additional computation. This is a small price to pay for small data files, and can be optimized for large data (cryptohashes would be overkill). So we can make subroutine pipelines (see the figure below) with encapsulated outcomes that keep clear promises:
# Makefile for helloworld.cend_state: exec_hello exec_world inputs
cat hello_stage world_stage inputs > end_stateexec_hello: hello exec_hello.sh
./exec_hello.sh > hello_stage
exec_world: world exec_world.sh
./exec_world.sh > world_stagehello.o: hello.c compile_hello.sh
./compile_hello.sh
world.o: world.c compile_world.sh
./compile_world.shhello: hello.o
./link_hello.sh
world: world.o
./link_world.sh
The dangling reference to “inputs” can refer to any pure data file, such as a version declaration, or license text, that lives in the build area, and is captured in the dependencies so that a change will trigger a new build.
The end state promises are now explicitly dependent on the promises of the parallel sub-pipelines as integral artifacts, and each sub-level can be cached in terms of these artifacts.
The result is now that any change to the sources, or the transformations, will always lead to the correct convergent outcome, with only necessary and sufficient work.
So, the key to efficient execution and separation of concerns is containment.
Parallel sequences
Even within the scope of make, we can explore running this in parallel, say with GNU make, on multicore processors, to simulate the effect of parallelism at the the container/binary level:
make -j3With parallelism, we have to be clear about which promised outcomes depend on which prior promises of intermediate desired states. The `hello’ and `world’ containers have to be built internally in their normal order, just like Docker containers, but their relative scheduling order is irrelevant, because a third final aggregator container, responsible to building the desired end-state (an orchestrator), pulls the results in the order defined by its own promised outcome. The result is now a confluence of pipes from a tributary structure.
There are interior embedded pipelines within the `hello’ and `world’ build services, but the scaled effect of each is to promise a service — a service that acts like a single component to build a tributary servicing the main flow. The desired end-state acts as a final compositor, arranging these framed outcomes from persistent storage and outputs them in a ordered arrangement, with full documentation of dependencies.
In our next post, we will explore these concepts in more depth in the context of our historical experiences with CFEngine, the first declarative configuration management language and system implemented and deployed at scale across millions of machines.
