do you work on a fast HTTP router implementation?

[BurntSushi]

If so, I'd like to hear from you. For context, I'm investigating the feasibility of using regexes in this particular domain. It seems like they could be a good fit (and I say that without any particularly relevant experience with the HTTP router domain), and I wonder whether folks are actually using them. So if you do work on an HTTP router, and you'd be willing to lend some of your time, I'd appreciate if you could take a stab at the following questions:

1. Is there a link your router implementation where I can read the code? Similarly, a link to the API docs would be great if they exist.
2. Are there benchmarks for your router? If so, could you share instructions for how to run them?
3. Do you use the regex crate in your implementation? If not, why not?
4. Similarly, do you use RegexSet from the regex crate? If not, why not?

(For the "why not" questions, I'm not necessarily looking for a novel or anything. Answers like "I didn't know about it" or "I tried but it ended up being really slow" are totally fine.)

EDIT: To be clear, I am not looking to build a router myself. I am looking to use HTTP routers as a real world use case driving optimizations inside the regex crate.

[BurntSushi]

Someone on Twitter pointed out the router inside of actix-web has benchmarks and it includes a benchmark using RegexSet: https://github.com/actix/actix-web/blob/8759d79b03510f0cae2aac1cb459e79802c85fc6/actix-router/benches/router.rs#L182

(I haven't run them yet though.)

[BurntSushi]

3. I don't use the regex crate because it was very slow for this specific usecase.

Yeah, this is what I suspected to be the case and was why I opened this issue. I wanted to get a sense of what was out there.

Also, in case you didn't see my edit, I have no plans of building a router. What I'd like to do is explore whether using regex as an implementation strategy is viable, and possibly, have it serve as a real world use case to drive optimizations inside of the regex crate.

[adriangb]

Hi @BurntSushi sorry to bother you with general regex/automata questions, but I’m wondering if you could help me understand (reading material is fine) the difference between the NFAs that a regex engine would build for a RegexSet and the structures that routers like matchit and pathtree use. To (someone with no formal computer science education) it seems like a trie is just a special case of an NFA. If so, what would make a RegexSet considerably slower than these other routers? Shouldn’t the automaton built in the RegexSet be pretty much identical to the trie a router crate might build?

[BurntSushi]

Good question. I haven't done an investigation of the router implementations yet. Your question is kind of the point of me asking for router impls in the first place, so I could investigate and answer it.

Of course I have some ideas as to why. The main idea is that not all NFAs are created equal, just because they have the same expressive power. It's kind of like saying, "Rust and Python are both Turing complete, so why is Rust so much faster?"

And of course there are good reasons why.

Anyway, once I do my investigation I'll share what I learn.

[adriangb]

Makes sense, I look forward to the results of your investigation!

[adriangb]

This is linked to elsewhere but this article of Andrew’s is absurdly good: https://blog.burntsushi.net/transducers

I learned a lot (and still have a lot to learn, I expect I’ll need several reads to digest). It at least confirmed my thought that Tries are simply a special case of an automata (noncyclical, compressed since a node can represent more than one character, etc).

Most routers restrict parameters/wildcards to be within two / and only allow “catch all” routes at the end of the path. I think this and other assumptions about the nature of HTTP paths let’s them be more efficient than an automata that can’t make assumptions about the input string. If you don’t allow “one or more”/“zero or more” type modifiers I think you naturally end up with a minimal DFA that is unique (so you can detect ambiguous paths like https://github.com/julienschmidt/httprouter does). Once you start adding more advanced features (even parameters that must match a regex, which some routers do!) you just move the implementation right along the spectrum from “simple compressed trie” to “custom regular language that compiles into some sort of DFA/NFA”. Both are possible, so it becomes a problem of API design for the router. Some routers allow routing based on headers or applying arbitrary functions as filters, which could theoretically injected into the automaton or could be applied at the end to every matched route in simpler but less efficient implementations.

I think an ideal router implementation will have to balance these API concerns in a way where simple cases are easy to understand and performant but more complex cases are still possible, even if they result in lower performance for requests that traverse those routes.

[Geal]

I explored this in sozu a few years ago, and there's a benchmark repository you can explore.
In sozu's context, the time spent building the router data structure was critical, as this is something that blocked the event loop and could happen often (I think now I'd do things differently to build the structure off of the event loop). The RegexSet based approach was too slow (on building and lookup), but fst was competitive.

I ended up with a tradeoff where routing was done with a trie for the hostname, possibly handling a glob pattern, and then for the URL testing for equality or regular expressions. I'd love to see something that is more flexible and could hande different patterns for the hostname and that could manage both hostname and URL in the same structure.

[Geal]

An additional point here: the base use case for sozu is routing for tens of thousands of applications, some of them serving a large number of domains, so this could result in hundreds of thousands of routes

[ibraheemdev]

Oh that's a super interesting use case! I can't imagine anything doing better than a trie at that point (for lookups), but creation speed is an added challenge.

[Geal]

Honestly a stack of hashmaps can work extremely well 😁

[joshtriplett]

cc @jbr

[jbr]

@BurntSushi Take a look at routefinder, which takes the interface of route-recognizer but drops the awkward nfa description and improves the performance by around an order of magnitude. I'd be excited to extend the route description specification to include additional components like grouped and optional path segments, as well as constraints on captures, and intend it to be extensible for a variety of use cases.

I did not use regexes at all, but instead have a purpose-built route specification "language" and parser that also includes route prioritization for when there are multiple matches. I don't see what would be gained by using regexes, and would have to compile one string format to another string format and have an intermediate representation that does not closely describe the path components. I did not look into using building blocks from the regex crate, if they are available, but most path matching is either "exact string match" or "capture everything up to a slash character," for which regexes seem like overkill.

Criterion benchmarks are available in the repo, executable with cargo bench. It should be fairly easy to modify the benchmarks to conform to a standard benchmark case. I would say that "finding the best matching route for a given input and a set of routes" is routefinder's strong suit, not necessarily "matching a single route," and that the larger the set of routes the better routefinder will perform compared to other routers.

Current users of routefinder: tide, summmeros, trillium.rs (mine)

[ibraheemdev]

takes the interface of route-recognizer but drops the awkward nfa description and improves the performance by around an order of magnitude.

I added routefinder to matchits benchmarks, and interestingly it seems to do worse than route-recognizer:

Compare Routers/matchit 
time:   [197.57 ns 198.74 ns 199.83 ns]

Compare Routers/route-recognizer
time:   [3.7552 us 3.7732 us 3.8027 us]

Compare Routers/routefinder
time:   [5.7313 us 5.7405 us 5.7514 us]

Your benchmarks are based off a much smaller dataset than mine (Github's API has over 100 routes), which could by why your results look different.

[jbr]

Interesting! I'll take a look at profiling that difference! That small directional difference in fact is what I expected when first writing routefinder (trading off performance for ease of use and extensibility) and instead found meaningful performance gains vs route recognizer.

[gsquire]

I wrote a simple router a while back here. It's very rudimentary. I'm not sure how helpful it would be but figured I'd share. The crate could use some polish for sure.

[fundon]

path-tree is a very small implementation. The benchmarks is here.

Plan: redesign it, add regex for more cases. viz-rs/path-tree#18

[v1gnesh]

Hello,

This one's not exactly a HTTP router, more from the observability & logging arena.
https://github.com/vectordotdev/vector#performance

It may be quite a drift away from the exact think you're looking for, but seems like a similar situation.
That is, a place where performant regex parsing could help.

1. Is there a link your router implementation where I can read the code? Similarly, a link to the API docs would be great if they exist.
   It's a huge project; might need some looking - https://github.com/vectordotdev/vector/

2. Are there benchmarks for your router? If so, could you share instructions for how to run them?
   https://github.com/vectordotdev/vector-test-harness/tree/master/cases/regex_parsing_performance

3. Do you use the regex crate in your implementation? If not, why not? Similarly, do you use RegexSet from the regex crate? If not, why not?
   Both regex and RegexSet are used.
   Here's the PR that brought in RegexSet

[BurntSushi]

This is great, thank you!

[v1gnesh]

You may also be interested in MeiliSearch's use of Regex.

[BurntSushi]

Yeah I don't want to turn this issue into a "every project that uses regex" sort of thing. Would like to stay focused on the domain of HTTP routers. :-)

[v1gnesh]

Well, sure, I only mention it as it's a project where improvements in its use of regex could yield noticable benefits to end users & increase visibility/adoption.