Concurrent Programming

Example with Akka.Net: create a tree and visit it using depth first search

Introduction

Akka.Net helps building asynchronous and distributed programs. This framework is based on the actor model. In this model, actors are classes that communicate with messages only, and do not share mutable variables with other actors. Therefore, actors can safely run concurrently without synchronization mechanisms. I propose to have a look at this framework by implementing an algorithm : creating a tree, and visiting it using depth first search. In this article, I will focus on running the program in a single machine, but with multiple cores (distributed programming with Akka.Net will not be discussed). After describing the algorithm and its expected behavior in Akka.Net, I will explain the implementation.

This example has been written using Akka.Net 1.1.1 and the .Net Framework 4.6.1. The complete source code can be found on github.

Specifying the algorithm

A reminder on the theory

A depth first search (DFS) of a tree consists in visiting each node of a tree, starting from its root. The search explores a path as deep as possible before backtracking. In consequence, nodes are visited in a particular order.

image1_dfs

In C#, we can represent a tree by creating a class Node containing a list of Nodes. A tree can be built from the root to the leafs. DFS can be implemented recursively in a single thread.

We can now create a tree, and visit it using DFS:

As expected the output is:

image2_onethreadoutput

Sum it up!

DFS is algorithm that explores each node of a tree once in a particular order. A DFS based on the actor model should also respect these properties.

The Akka.Net DFS

Architecture

Everything is an actor

In the actor model, everything is an actor, so let’s create them! We need two actors. The TreeActor receives messages from the client and send them to the root node. The NodeActor receives messages from the TreeActor (if it is the root), or an other NodeActor.

image3_dfs_actors

Transmissions of messages

The NodeActor and the TreeActor can both receive the same four type of messages. The AddRequest is intended to the NodeActor creating the child. The AddResult is sent back to the TreeActor by the creator of the new node.

image4_dfs_add

The VisitRequest is received once by each actor from its parent. The VisitResult is sent back to the parent when all children have been visited. Remember that the order of visit matters in DFS.

image5_dfs_visit

Identification of race conditions

Actors can compete in delivering message and it can lead to race conditions. Sending a VisitRequest to the tree, immediately followed by an AddRequest messags can result to different outcomes: the added node may or may not receive the VisitRequest. In order to avoid this confusing behavior, the program does not allow to create and visit a tree concurrently. We will implement that by keeping information about past messages in our tree actor.

Message consistency

We will also remove an other confusing behavior: adding a child to a nonexistent parent, or adding an already existing child.

Implementation

Read-only properties for messages

As it is recommended by the documentation, messages are read-only. In this implementation, public properties are only instantiated in the constructor.

An AddRequest has an instance of ICustomActorFactory which helps create the new node to add.

During unit testing, this factory is very helpful to inject a fake node actor.

For the real program, a default implementation is provided.

An AddResult is just empty.

Each VisitRequest contains the request previously sent to the parent. It helps remember the last visited node, and deduce the next node to visit: it is like a stack.

The VisitResult is sent after all children of a node (and itself) have been visited. It also helps to deduce the next node to visit by encapsulating the VisitRequest.

The TreeActor

The TreeActor is a ReceiveActor that implements IWithUnbondedStash. In the normal behavior, any message are handled. In the busy behavior, AddRequests and VisitRequests are systematically stashed.

AddRequestHandler/AddRequestHandler are (nearly) symmetrically identical to VisitRequestHandler/VisitResultHandler. A request is handle only if no other request of the other type is being processed. The request is stashed and the tree becomes busy. If all result of a type are received, all messages are unstashed and the normal behavior is restored. This security is to prevent race conditions.

The NodeActor

A NodeActor has only one behavior.

The AddRequestHandler either creates the new node (if the request is intended to this node), or delivers the message to all children in parallel.

The VisitRequestHandler immediately sends the VisitResult if the node has no child, or sends a new VisitRequest to the first child otherwise. This new VisitRequest wraps the old one to remember which node has been visited.

The VisitResultHandler calculates the next child to visit. If no child to visit remains, a VisitResult is sent back to the parent node.

Consuming actors

We can consume our actors now!

Result

We have the same result as the first version of the DFS.

image6_akkadotnetoutput

Conclusion

The real goal of this article is to test Akka.Net capabilities with an example. We have implemented a concurrent depth first search algorithm where each node can process a different request (of the same type) at a given moment. The program can run in different threads. At first, the new paradigm is not easy to deal with, but Akka.Net comes with practices that really makes concurrent programming safer: threads communicate together with immutable messages, and computing units (actors) process messages one at a time. While immutability is at the discretion of the developer, communication and message processing are provided by the framework. However, my example is not enough to fully evaluate Akka.Net capabilities in general (local or distributed), and ultimately how it may fit or may not fit a real case scenario. Other aspects have to be studied, like logging, supervision, testing, distributed programming, reactive streams and maybe more. One of these subjects may be one in my next articles.