1

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?

3
  • 3
    The most common approach is to have the user specify the precedence of the match, and iterate through the specs. If there are a lot of URL specs to work through, that's technically the fault of the user. It's also why the now common approach of /{controller}/{id} is so common. It hits so many URL patterns for REST services that you don't need many other specs. Dec 27, 2019 at 21:34
  • @BerinLoritsch Thanks, Mate. Unfortunately, the routes are pre-decided . I cannot change them. Dec 28, 2019 at 6:11
  • 2
    Only thing I can think of is to tokenize the URL bits putting them into a tree structure, and walk tree based on the URL you receive. Dec 28, 2019 at 12:18

3 Answers 3

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

1

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.

1

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.