Design of a Router/UrlMatcher

Question

Note: I am not sure if the question belongs to this particular stackexchange . If it does not, please let me know and I will delete it here and post it on the relevant exchange. Though it seemed more suited to this exchange than StackOverflow.

I am trying to create a REST server. My problem is to optimise a router/route multiplexer(mux for short)

The use case is as follows :

At the start , I register multiple routes , example - /route/v1/{someParam}/end and /route/v2/{someParam}/notEnd/somethingElse , For each route we have a corresponding callback function that we can call . In the case of any new request, we get a new URI and find out which route it matches and call the corresponding callback function. So the code will look like

auto Callback = match(URIFromRequest) 
Callback() // Called in a separate  thread . Not our concern now

Please keep in mind that {someParam} in the route is a path parameter so the URIFromRequest /route/v1/randomValue/end matches /route/v1/{someParam}/end .

My goal is to create a Data Structure of the routes and their corresponding callback such that the match function is as fast as possible. Please Note that the total number of routes registered will be only around 30-50.

Right now I am planning to convert each registered route to regex. For example ,the /route/v1/{someParam}/end gets converted to regex like ^/route/v1/[^/]+/end$. Now, all these regexes and corresponding callbacks are stored in a map-like structure. Whenever I get a new request, I iterate through the map. If the URI, matches any request, I return its callback function.

This seems terribly inefficient, however, I cannot think of any other solution that also supports path-parameters(i.e the {someParam} part). Does anyone have any idea on what should be a more efficient solution?

Answer 1

If I understand correctly, your problem is directly solved by Knuth Morris Pratt algorithm for pattern matching; way more efficient than regex processing, with the additional advantage that you can precalculate the matching table for all possible routes.

https://en.wikipedia.org/wiki/Knuth–Morris–Pratt_algorithm

Answer 2

It appears your "routes" have 3 things in common which can help accelerate the search. They all have

1. A fixed prefix, of known length
2. A fixed suffix, of known length
3. A minimum length, which is at least as long as the prefix and suffix lengths together.

This gives us a first rapid check: For short inputs, you can disregard long patterns, without doing the actual match.

The second observation is that this length check allows us to check substrings without worrying about buffer overruns. When matching URI against /route/v1/{someParam}/end, you know the minimal length of URI has to be 14, so you can safely compare the first 10 characters against /route/v1/ and the last against /end.

Your URI design appears to also contain common prefixes, which can accelerate testing even further. A somewhat heavy-weight solution is a prefix tree, but for your example you could restrict it to one special /route/v prefix. This would partition your pattern set in 2: those that start with that prefix and those that do not.

Answer 3

While written around PHP (i.e. the Symfony framework), Nicolas Grekas has written up an article on how they made their routing component 77.7x faster.

Part 1: https://nicolas-grekas.medium.com/making-symfonys-router-77-7x-faster-1-2-958e3754f0e1

Part 2:https://nicolas-grekas.medium.com/making-symfony-router-lightning-fast-2-2-19281dcd245b

The articles are definitely worth reading,but to summarize:

Try combining as many routes as possible into a single Regular expression.

You can easily fit a few dozen route patterns into a single, large regular expression. If your RE dialect offers an easy way to define which route was matched (like PCRE's MARK feature), you can build a static map with your callbacks, and have the regexp return which index in the map to call.