Resolving Action Dependencies: Comparing JavaScript and Go implementations

Emmanuel QuentinAugust 22, 2014

#golang#js#oss#tutorial

While I was developing gaudi, a simple orchestrator using Docker containers, a problem quickly came up: how can a program determine the order of execution of a list of routines with dependencies on each other?

The Problem

The problem is simple. Gaudi browses a list of containers configured by the user. Each container can depend on a list of other containers. For instance, here is the description of the infrastructure for a web application using gaudi:

web_server:
    type: apache
    links: [web_app] # must be started after web_app container
    volumes:
        .: /var/www
web_app:
    type: php-fpm
    links: [database, amqp] # must be started after database and amqp containers
    volumes:
        .: /var/www
database:
    type: mysql
amqp:
    type: index
    image: toto/rabbitMQ

Before executing a task on one of the containers (e.g. start), we should check that this task has already been executed on all dependencies.

To optimize the process, tasks should run in parallel whenever it's possible.

JavaScript Implementation

In javaScript, a simple solution is to iterate on each element, and for each element, check if all dependencies are ready. If not, register another pass in the loop for the next tick.

This solution requires 2 nested loops called each time an element is started. This implementation shows a complexity of O^3.

Here is one example implementation:

var elements = {
    app1: [],
    app2: [],
    app3: ['app4'],
    app4: ['app2']
};

// initialize status
var done = starting = {};
for (var elementName in elements) {
    done[elementName]     = false;
    starting[elementName] = false;
}

function startAll() {
    for (var elementName in elements) {
        if (done[elementName]) {
        	// already started
            continue;
        }

        // check dependencies status
        var allDone = true;
        elements[elementName].forEach(function(dependency) {
        	allDone = allDone && done[dependency] === true;
        });

        if (allDone) {
        	// at least one element has no dependency and can be started
            startElement(elementName, startAll);
        }
    }
}

function startElement(elementName, callback) {
    if (starting[elementName]) {
      return;
    }

    console.debug('Starting ' + elementName + '...')
    starting[elementName] = true;

    setTimeout(function() {
      done[elementName] = true;
      console.debug(elementName + ' started');
      callback();
    }, 2000);
}

startAll();

You can test this implementation online at this Plunker.

Go Implementation

In Go, the solution is cleaner: create a map of channels for each element, and wait that each dependency is done before stating a new one.

package "main"

import "fmt"

func main () {
	// create a map for status channels
	done := make(map[string]chan bool)

	// create 4 elements with dependencies
	elements := make(map[string][]string, 4)
	elements["app1"] = []string{}
	elements["app2"] = []string{}
	elements["app3"] = []string{"app4"}
	elements["app4"] = []string{"app2"}

	// iterate over each element
	for elementName, dependencies := range elements {
		// initialize the channel of this element
		done[elementName] = make(chan bool)

		// call startElement for all elements in a go routine
		go startElement(elementName, dependencies, done)
	}

	// wait for all elements to be started
	for elementName, _ := range elements {
		<- done[elementName]
	}

	fmt.Println("Done")
}

func startElement (name string, dependencies []string, done map[string]chan bool) {
	// wait for all dependencies to be finished (i.e closed channel)
	for _, dependency := range dependencies {
		<- done[dependency]
	}

	// start the element
	fmt.Println("Starting", name)
	time.Sleep(2 * time.Second)
	fmt.Println("Started", name)

	// close the channel once finished
	close(done[name])
}

The elements variable stores a map of strings array representing dependencies. For each element, we call a go routine startElement, which waits for each dependency to finish with <-done[dependency].

When all dependencies of an element are started, we start the element and close its associated channel.

In case of dependency loop, go will throw an error: "fatal error: all goroutines are asleep - deadlock!".

You can see the result in the go playground.

This implementation only has two loops, so its complexity reaches O^2, much better than the JavaScript implementation.

Conclusion

Since it's so easy to build complex environments with gaudi (see my previous article on building a complete Magento server with 9 containers, dependency resolution needs to be extremely streamlined. I used the Go implementation described above in gaudi to resolve containers dependencies, and I find it very elegant. It's also much faster when the Go program runs on several processes.

If you're considering learning Go, now is a good time to start!

Did you like this article? Share it!