Graph Based Routing

Preamble

I’d like to share with you a concept that I’ve been working on for some time. I’ve yet to decide on a good name for yet, but at the moment I call it ‘State MachineGraph based routing‘.

Routing is important… no vital to most web applications. Whether it’s client side or server side, C# or Node.js, nothing (sensible) can happen without some kind of routing. Yet despite this, it’s usually treated as a secondary aspect of the development process… a mere peasant in your chosen web stack. Routing is a dull, unintelligent series of pattern matches and parameter capture.

This is an outdated view. Routes in a contemporary web app are complex, often hierarchical beasts. Routes such as these can be prohibitively costly both to maintain and to execute and as such we are prevented from making the most of things. Enter Graph based Routing.

Aims and Overview

Graph based routing is designed to improve upon traditional routing strategies in terms of route definition, performance and flexibility. As the name suggests, defined routes are stored in a graph structure… each node representing a URI segment. Edges in the graph then represent links to the segments that follow e.g:

Definition for routes:
    /api/products/{id}

It becomes clear why this is a good way of representing routes when you introduce slightly more complexity:

Definition for routes:
    /api/products/{id}
    /api/products/bestsellers
    /api/customers/{id}

Instead of having to store each route separately and in it’s entirety, we create links between segments that have a common predecessor.

The route matching algorithm no longer needs to scan (potentially) the whole route table for matches… just consider the next segment and then choose only between those possibilities represented by the graph edges.

Route definition

The benefits extend to route definition and maintenance too. Consider a theoretical DSL with special ‘/’ and ‘|’ (or) operators to define the above routes as a graph:

   routes = "api" / (
         "products" / ( "bestsellers" | "id )
       | "categories" / "id"
   )

Even with such a small number of routes, it’s possible to see an improvement in readability and a reduction in redundant code. Because routes are broken down into objects, we can re-use parts of them and even define complex routes programatically or by convention.

These routes are all in one place… but that’s not to say this couldn’t be extended to cater for a definition that involves placing routes near to where they are handled. In the case of Asp.Net/C# we could assign parts of routes to static variables and (thread safely) attach more routes to them from anywhere else in our code, use lambdas in controllers, or a myriad of other techniques.

Parsing Strategy

Implementing a graph based routing engine dictates that we parse URIs by traversing the graph of route definitions in a particular way. In traditional routing we can make use of pattern matching and constraints in order to decide how to interpret segments, but we cannot easily use this information to make choices.

With graph based routing this becomes easy by defining an Activation function for each graph edge. Rather than being limited to pattern matching, an activation function contains arbitrary code that must return true or false (matched or not matched) based on the value of the current URI segment.

If an edge is matched, we transition to the succeeding graph node which can then execute an Action function. If an edge is not matched, we move on to the next edge in the sequence until we either have a match or run out of options.

Once route parsing is complete, the Final function of the last node is executed. If the last node does not provide one, the engine must execute the final function of the last travelled node that did.

State machine

In effect, a graph based routing engine is a finite state machine with the URI as input. In order to understand the purpose of the Activation and Action functions, lets look at a real world example:

Default Web API routing case:
    /api/{controller}/{id} - (optional)

We can see how our graph has produced a very simple state machine, with only one valid transition at each state apart from the optional nature of the id parameter. Pseudo code for each activation function can be seen above each transition line, and a summary of the action function inside each circle.

See also that the optional nature of our Id parameter has created a transition that ‘jumps’ over the Set Id node if a value is not present. Two other things to note here:

• The final state of the machine is not directly mapped to a graph node, instead this is a result of executing the Final Function.
• If at any point we fail to find a match for the next URI segment, we transition to an error state and execute an Error Function.

Flexibility

Through this use of Activation, Action & Final functions, we can reproduce all the functionality of traditional routing mechanisms, while at the same time opening providing developers with the ability to execute whatever code they like at each stage of the process. You could view each graph node as a miniature piece of middleware.

The routing engine must provide a mechanism for storing ‘state’ while the FSM is running, in order to store things like target controller/action names, parameter values or anything else that the developer needs to implement their node functions. It must also allow nodes to access information about the current Http request/response.

At a basic level, we could implement easily implement custom model binding, deserialization, or logging as part of our custom actions functions. If we take this further we can some do very cool things… consider an implementation for a Javascript app in which certain actions cause nested elements to open. For certain routes we could show, hide or create DOM elements per segment in order to reconstruct the UI state after a full page load.

If we so desired, we could code our activation functions so that our API routing would make different choices based on the user that was currently logged in, or even the time of day. Routing also no longer needs to be linear… by storing state we can even defer making a decision about what to do with our route segments until we execute the final function so we can use all the information available to us.

Summary

With graph based routing, you can make routing a first class citizen in your web application. Although we talked a lot about analogues with Asp.Net / Web API routing, the concept is totally platform independant.

Whats really cool when applying this server side is that you don’t even really need a web framework, so long as your action/final functions are able to send http responses. Alternatively you could even choose which framework you wish to service your request, which brings me onto another point… now that we are moving towards the OWIN based future, routing should become a middleware concern! But that’s a topic for another post.

All this may have been theoretical, but I am working on implementations for Javascript, Web API and OWIN which are all at various stages of development. I hope to have some more news on this in the next few weeks, so stay tuned and please let me have your thoughts and feedback. This is a brand new concept and any contributions will be gladly received.

Pete

Appendix – Glossary

• Route – A potentially valid URL route made up of nodes, transitions & actions.
• Segment – Part of a URL separated by ‘/’
• Graph – The representation of all routes for an application
• Node – A node in the route graph – typically representing a potential route segment match.
• Base Node – The common root node of every route, and the starting point for route parsing.
• Error Node – A node that is reached when an error occurs.
• Transition – A link between two nodes by which we can transition from one to another.
• Activation function – Determines whether or not a transition can be made.
• Action function – Executed after a transition has successfully occurred.
• Final function – Executed by a node *only* if it is the last node in the route.