DAG Management in Elixir

The other day I was talking to a friend, he was relating the difficulty he was having managing background job pipelines in his Rails application. The biggest issue was tracking and acting on the success/failure states from outside Sidekick while preserving the dependency structure of the DAG.

He was describing the work he’d done simplifying the graph into an algebra to help with the priority and status and I couldn’t help but think this would be a super simple to do in Elixir, it felt like such a natural fit for the language, enter Assembly Line.

Keep in mind this post is only concerned with simple DAGs. AssemblyLine doesn’t yet handle anything with branches or sub-graphs in it, although that is planned for the future.

Today lets talk about a strategy for managing the DAG itself. While the pipeline can be large and complex, we are really only concerned with the current level. Which means that with the proper data structure managing the graph should be relatively simple. In its simplest form the DAG should be representable as a stack, for example given the following Graph:

    A--------|
             |------------> C ----------> D
    B--------|

This could be represented thusly: [[A, B], C, D] where the group A, B are required before executing C but neither A nor B depend on each other in any way.

The list structure gives us two benefits: First, it clearly defines the scope of our parallel execution, all the tasks in a sublist can be performed asynchronously. Second, it provides a clear dependency state as well, we never want to work on anything that isn’t at the head of the list.

This gives us a fairly simple Server implementation:

• next_set
• complete_current_set
• complete

We have two main behaviors here, getting the work that should currently be performed (next_set) and tracking completion (complete and complete_current_set). The only operations which modify the Graph are the two complete operations. These operations remove a job or set of jobs from the front of the list.

You may be asking yourself, why two complete behaviors? This is to preserve the state for partially complete sublists. Basically if you are executing A and B at the same time but A fails B is still recorded as complete and won’t be executed again.

Next time I’ll give an idea of how to actually use the AssemblyLine application to process jobs from a queue. Both for a native Elixir application and for a Rails application using Sidekick.