Trie-based Routing

In my previous post, I discussed the cost of routing in MVC vs. our own implementation. The MVC routing / infrastructure consumed about 90% of the time, while the code that actually does stuff is left with less than 10%. In our implementation, the actual request handling code gets about 85% of the time, while all the infrastructure is handled in the other 15%.

Of that, a large portion of that time is actually spent on routing. In our tests, we saw something like 40% of the time spent in selecting the right controller action to execute, this is when there is just one such action that can be run. Now, to be fair, this is a scenario where we don’t actually have any meaningful logic. We are just saying "hello world" over and over again, so the infrastructure costs are really noticeable in this benchmark. But that is the point, we want to see what the fixed costs are of the infrastructure we use.

Now, in RavenDB, we have several hundreds of routes (last count was something upward of 400), and we noticed that routing takes a lot of time to select the right action to run. We optimized the hell out of that to the point by specializing that to our own situation and based on our own knowledge. But, when we started to look at moving our code to Kestrel, we took the time to move to a system that is a better fit for us.

The major reason routing is such an expensive issue in MVC is that it does quite a lot. It needs to handle route selection, capturing values, coercing data to the right types, and a lot more. All of that takes time, memory, and CPU cycles. But as it turns out, we don’t really need all of that. We have relatively simple routing needs.

Here are a few examples of RavenDB routes:

• /admin/stats
• /databases/{databaseName}/docs
• /databases/{databaseName}/indexes/{*id}

So, we have the fixed routes, like /admin/stats. We have routes that contain a database name in the middle. And, we have routes with a suffix. We can take advantage of that to create an optimal solution.

In our case, we used a trie:

In computer science, a trie, also called digital tree and sometimes radix tree or prefix tree (as they can be searched by prefixes), is an ordered tree data structure that is used to store a dynamic set or associative array where the keys are usually strings.

The cost of querying a trie is O(L), where L is the length of the key that we are querying. Here is how a very small trie looks in our tests.

We start from the route, matching each character against the trie node key. Once we have consumed the full key, we check if it has any children starting with the next character in the URL. Note that the Children array here is of size 127. This allows us to index directly into the array (at a cost of O(1)) to find the next trie node. We didn’t want to use a dictionary here because of its size and its cost relative to an array access.

This has some interesting implications:

• The route definition is limited to ASCII characters (but the actual URLs are not, mind).
• Regardless of the number of routes, we are ensured of reliable performance.

But, that still doesn’t let us handle routes like the ones above. In order to do that, we had to extend the syntax a bit.

/admin/stats would match exactly. That is easiest.

/databases/*/docs is a route that has a capture. The * symbol says "matches anything but /", so we can get the database name captured without complex matching. Note that by capture, I mean just record the start position and length, we don’t want to pull a substring out of that and pay for an extra allocation.

/databases/*/indexes/$ is another route that has special meaning. The $ symbol says "the match is done, even if the URL has additional characters". That way we can capture embedded ids easily (again, no allocations).

The end result?

Or roughly, a route match in 0.9 μs. Pretty good, even if I say so myself.