[Distributed] Message Routing

Message Routing

Message routing inside the graph depends on the configuration used to partition the graph between the cluster nodes and thus the resulting hierarchy. Two use cases influence how the communication is done inside the graph:

• The graph processing is running in parallel on a single node.
• The graph processing is distributed over several nodes.

Message Types

Several message types are used during the graph processing:

• Explicit messages used by the vertices to communicate between each other between two substeps (supersteps).
• Implicit messages used during crunch steps.
• Internal messages used by the workers, foremen and the graph for control and synchronization.

Routes

Substeps Messages

Substeps messages are sent by one vertex (sender) at the end of a substep and will be received by another vertex (recipient) at the beginning of the next substep. The routing of those messages is transparent to the vertices and they only know the sender and receiver of those messages.

Messages between the vertices are always passing through their corresponding workers which are in charge of dispatching them to the workers of the messages' recipients. The way messages are handled between workers depends on the configuration of the graph internal hierarchy.

Messages between vertices managed by the same worker

When a worker routes a message sent to a vertex that it manages, it simply adds the message to its own mailbox.

Messages between vertices managed by separate workers

When a worker routes a message sent to a vertex managed by another worker, it directly sends the message to the worker. This is done without taking into account if the worker is local to the node or if it is on a remote node.

Some tests should be done to measure the difference of performance between a routing protocol that sends atomic messages directly to the worker and a routing protocol that passes through the foremen for inter-node communication, aggregating the messages.

Crunchsteps Messages

A crunchstep consists of taking the values of all the vertices and perform a reduction on them. The result of that reduction is then sent to all the vertices of the graph. This operation implies vertical communication between the vertices and the graph. The reduction is completed by the graph which sends the result back to the vertices.

The exact vertical communication depends on the internal hierarchy of the graph, but it follows some general rules. Each worker first perform the reduction on the values of its own vertices and sends the result to its parent (the graph for a local processing in parallel or a foreman for a distributed processing on a cluster). The parent then performs the reduction on the results it received from its children and sends the result to its own parent (and so on) until it reaches the graph. The graph then performs the final reduction and sends the result to its children (and so on) until it reaches the workers that can execute the next substep on the vertices.

Internal Messages

Internal messages are used to vertically control the execution and synchronization of the substeps. They are used in the communication between the workers and the graph, with the foreman reducing/distributing and relaying them along the way.

Next message

Sent by the graph to the workers, this message signals the worker to launch their next substep.

Stop message

When the message is received by the graph from a worker, it stops the current processing of the graph. When the message is received by the workers from the graph, the worker actor is stopped.

Done message

This message is sent by the workers to the graph to indicate that all of their vertices reached the end of their current (non-crunch) substep. The graph initiate the next step once it has received a Done from all of its children.

Halt message

This message is sent by the workers to the graph to indicate that they don't have any more processing to do. If the graph receives a Halt from all of its children, it means that there is no more processing to do and the graph can stop.

Message Priorities

Some type of messages can take priority on other type of messages, meaning that when they are received on one end, the other messages are ignored. This also allows for simplifications in the vertical communication and reduction of the outgoing messages.

Received by the graph

1. Stop
2. Done ou Crunch
3. Halt

Received by the workers

1. Stop
2. Next ou CrunchResult
3. Message (messages of the previous superstep should be discarded)