Trie-based routing with Mustermann

proposals
1

Not sure if this is the right place.

I saw some discussion on moving hanami-router to be trie-based. This is something I’ve been considering for Mustermann back when I first implemented it… 13 years ago. Wow, time flies.

I’ve implemented a proof of concept for Mustermann and wanted to see whether there is interest on Hanami’s side, or if the plan would instead be to move away from Mustermann (or leave things as they are).

This does further increase compilation time. I’m happy to look into this, though. It should at least be possible to eliminate the need to compile the individual patterns.

I’m also not sure where your pain points are and what realistic route sets are like. Compiling 10k routes with four levels of nesting (each nesting level being one static and one dynamic segment) takes 3.5s on my machine. However, matching against these only takes 4.9μs (vs 0.7s when matching in a linear fashion). The break-even point seems to be around 50 routes; anything below that performs worse with the trie-based approach. Could also implement both a linear and a trie-based route-set matcher and switch between them automatically based on either a hard-coded value or some match simulation (thinking RouteSet#optimize), though that might be a bit much.

Anyway, if this is interesting to you, then I’ll work on finishing the Mustermann-side, and would be happy to help with hanami-router.

2

Hi, @rkh. This sounds interesting. I can’t speak for the core team, but I was the one doing the exploration you mentioned. It would definitely be worthwhile to discuss further.

To be clear, Hanami-router moved to a trie-based approach when @jodosha rewrote it for Hanami 2.0. He used Mustermann for segment matching, but it seems like Mustermann is overkill for that.

Mustermann is an incredibly powerful tool, but for the most basic (and most common) use case, which is matching whole segments, I don’t think Mustermann is needed at all. That was the strategy I was exploring in the branch you referenced.

Based on our findings, I think we can remove Mustermann for the basic usage, and keep it for more complicated matching (and expanding), like globs and sub-segment matching.

I’m curious to know more about your current work. What does a trie-based Mustermann look like? Does that imply a Mustermann construct for an entire routing tree? As opposed to the previous Mustermann object-per-route approach? I’d love to talk more.

3

Correct. The version I’m playing with right now would create one route set and give you the matched pattern, params, and a custom value you can assign to it. I’ve got matching to be fairly performant, and I think I have a way to still match multiple patterns. I think I’ll keep working on it either way and either do a POC with hanami-router, Sinatra, or a custom router to see how it performs on r10k.

Current work in progress API (might not be relevant to Hanami):

set = Mustermann::Set.new(type: :rails)

# Value can be anything, it is optional
set.add("/books/:id", "books.show")
set.add("/authors", "authors.index")
set.add("/books/:book_id/authors", "authors.index")

# matching
match = set.match("/books/1/authors")
match.value # => "authors.index"
match.params # => { "book_id" => "1" }

# expansion
set.expand("authors.index", {}) # => "/authors"
set.expand("authors.index", { books_id: 1 } # => "/books/1/authors"

Not sure what the impact would be compared to the current hanami-router implementation (happy to try it out and leave it be if it isn’t significant).

The trie already accounts for escaped and unescaped characters, which further avoids calls to URI when requests come in.

Where I’m at right now with optimizations is a 2,500x speedup (not missing a percentage sign) on matching of r10k-style routes (10k routes, 4 levels of nesting) compared to looping through an array of patterns, which is what Sinatra does.

My biggest concern is if this will work for complex scenarios, ie where a regular expression would perform backtracking. But maybe not supporting these is a fair-enough trade-off? I also feel like this is more an issue for Sinatra users, where /foo/*/bar/* might actually be in use. Hm… maybe I could just compile everything into one big regexp from the first splat on.

4

This is very cool! :green_heart: You are essentially creating a routing engine. This could be a powerful building block for any ruby web framework! It definitely lowers the barrier for entry with powerful, performant route matching and expanding in a single component. :nerd_face:

I just saw your comment on GitHub. I’d just as soon continue the conversation here, unless anyone thinks there’s more value to the community in that forum.

To be clear, I don’t think Mustermann is “too complex.” I think it’s awesome and super-powerful. But that power comes at a cost that is paid at compilation time (and possibly in memory use, although we did not identify that as a problem).

The Hanami router implements a trie as a deeply-nested Hash, with each complete segment acting as a String key in the Hash. The original approach used a Mustermann matcher for each dynamic segment. This turned out not to be very costly at compile time because the matching segments tended to use a small set of labels (e.g., :id is super-common), so the same matchers were frequently returned due to Mustermann’s internal memoization.

The problem with this approach was the inability to use different labels for dynamic segments appearing at similar locations in the route. The current implementation groups dynamic segments at the same route segment under one node in the trie, and then uses a Mustermann matcher for each complete route. This did prove costly at startup time, since we are now creating a matcher for every route. This is what led to my exploration with removing Mustermann.

Frankly, if you are only dealing with segment-level matching, I don’t see how any implementation (in pure ruby) will ever beat this Hash approach. Although I would love to learn if I am wrong. :nerd_face: However, I recognize that every additional feature request (globbing, sub-segment matching, multiple dynamic values per segment, etc.) brings us closer to re-implementing Mustermann.

I personally favor the approach of embracing additional power as needed. I would like to keep the core functionality with a Hash and simple String segments. I don’t know of anything faster than this. I would then embrace more complex approaches for more complex use-cases, as the core team determines that those use-cases should be supported. That is, I would use the current approach for the base case, without Mustermann for matching or expanding, and use different objects (including possibly Mustermann) as needed for more complex routes. Globbing is a good example: we could still use Mustermann for matching and expanding these routes, while retaining maximum performance for the more common base case.

What are your thoughts on this strategy?

1 Like
5

This makes a lot of sense. I do agree that if you wanted to implement most edge cases, you’d essentially end up rebuilding Mustermann or Journey. I also get that 80% of the use cases are extremely simple, with a single match.

I also agree on discussing this here rather than in the hanami-router PR. The only other place that would make sense is the Mustermann repository, but as long as none of the other maintainers chime in, I think this is fine.

I have found some improvements for the general pattern compile time on the way.

I think it would also be possible to compile patterns lazily, which could mean that full compilation isn’t even needed if all you use Mustermann for is expansion. However, there are some things I dislike about lazy compilation, including that I would expect an exception at pattern creation time if there’s a parse error. Not having that would mean a breaking change in Mustermann, which could have trickle-down effects on Sinatra, which is probably more in sustainability mode atm, so changing behavior that impacts it is something I’d want to avoid.

The trie I’m building atm is character-based, not segment-based. Again, I think this works better with handling escaping (as you don’t know upfront which characters might be escaped and which aren’t). This probably also isn’t relevant for most routes you’ll have in a RESTful CRUD application.

I’m happy to poke at it just for the fun of it. I do think Hanami is an interesting use case, as there’s more active development and still a lot to be built compared to the two other popular routers using Mustermann (Grape and Sinatra). And the more static routing compared to Sinatra means there are a lot fewer edge-cases (you can technically change env["PATH_INFO"] in a Sinatra route and then pass to the next route - issues around that were what made me give up on using a trie or some other approaches in the past). Eventually trying to incorporate this into hanami-router, even if that’s on a fork that never gets used, seems to be an easier way for me to see what the impact of this with a little less isolation would be. Assuming I’m not underestimating how complex the hanami-router internals are.

6

Interesting. How would lazy compilation affect forking web servers? I guess they’d each do their own compilation after forking?

Does the need for escaping implicate only non-RESTful routes? What are the use cases for this? I’m curious.

I did not know Sinatra could modify the path_info while processing. Is this common? It seems like dark hackery.

I think it would be pretty easy for you to replace our trie with a Mustermann::Set in Hanami router. Following my earlier exploration, I would like to start over and implement the improvements we discovered step-by-step in the router. This refactoring may make substituting Mustermann even easier. It sounds like a cool experiment. I hope we can continue our conversation as you go. :nerd_face:

7

Well, technically, any character can be URI escaped. And for non-meaningful characters (like a slash) they should be treated the same. So /books could also be /%62%6F%6F%6B%73 instead. Or any combination thereof. To the extent that most browsers will render both as /books when part of the URI. Not sure how hanami-router handles this at the moment.

I doubt anyone does this, but using pass is not uncommon, and there have been issues in the past whenever we tried to optimize route conditions (which can be arbitrary code in Sinatra). To be fair, though, I have taken a major step back from Sinatra maintenance about a decade ago, and haven’t had a Sinatra app in production with any real-world usage since 2019.

Oh, that sounds promising!

8

Thanks for doing this experiment and sharing it with us @rkh! This is very cool. I defer to others on the approach we should take with this. I’m open to taking linear approach for a small number of routes then use a trie for a larger number of routes.

Since I was the one to bring up the performance degradation at 10k routes, I just want to share that my thinking as changed somewhat. I think it’s good to know about those cases, I don’t think we need to care about it so much. Other than the obvious fact that almost no one needs that many routes, there are ways to nest smaller routers that could enable using that many routes with good performance. E.g. it’s fine for me if we say that you need to mount 10 sub-routers each with 1k routes for decent performance. (And the number can be much lower than 1k even).

9

Oh absolutely. I think it’s good to take a look at the edge case, but the most important thing is the happy path. I think it’s important not to punish a 20 route app so that r10k looks good. The r10k benchmark also doesn’t check what happens with longer paths, optional segments, non-path conditions, etc.

I’m mostly doing open source for the fun of it (love solving challenges, love not having the constraints I’d have with some commercial software), and Mustermann was a bit of my passion project back in the day, so I’m thoroughly enjoying it. I’m glad I found a forum here to chat with other people, so I do think this exercise is worthwhile, no matter the outcome.

That said, I really wanna see what I can get out of Mustermann performance-wise.

10

Little status update. It’s merged into Mustermann’s main branch and pushed as a pre-release to GitHub.

I wrote a little router based on it (something Mustermann shipped with in the past), which helped me further optimize performance. I also wrote my own benchmarking script as an alternative to r10k (in part because r10k gave my initial implementation an unfair advantage, since all routes are a single character, and also because I find it hard to modify Jeremy’s code – the latter part is a criticism of my skills, not his). Don’t trust a statistic you didn’t manipulate yourself, I guess.

Mustermann::Router is more than 4x faster than Hanami::Router in my benchmarks. Granted, this might be due to features Hanami has that my extremely basic router doesn’t. Both hold up really well under an increasing number of routes, though.

Full data set: allocated-objects.csv · GitHub

1 Like
11

I love seeing all of this discussion. Thank you everyone! And thank you @rkh for thinking of us in the first place — it’s great to have you here! :smiley:

So yes, we currently use Mustermann in Hanami Router, and I think this is a good thing. It fits well with our philosophy of embedding ourselves into (and uplifting) the broader Ruby ecosystem whenever we can. It’s why we use Zeitwerk for code loading, Tilt for view rendering, Temple for our own ERB engine, Rack (of course), Sequel for database stuff, and so on. We want to be part of the broader fabric, of people and tools alike.

So let this be my encouragement for us to continue this approach with Mustermann if possible.

I recognise it’s good to improve routing performance wherever we can, but I also agree with the sentiments above, where we shouldn’t over-index on the 10k case at the cost of performance or ergonomics for smaller route sets, or route matching functionality overall.

The matching features of Mustermann that we currently use and I care about preserving are summed up by the usage examples in our README:

  • Fixed strings: /hanami
  • Variables: /flowers/:id
  • Optional tokens: /hanami(.:format)
  • Globs: /*match

Like @dcr8898 mentioned, it’s really only the last two items where we rely on Mustermann right now. The first two kinds of matches we handle via our own Trie implementation.

My reading from @dcr8898’s exploratory PR is that we might have had to drop some of those (or put in extra work to reimplement them) if we were to drop Mustermann for the sake of greater performance performance reasons.

I’d like us to keep all of those, though. They’re all genuinely helpful routing features. And maybe by using more of what’s in Mustermann 4, we can keep those features and make things go faster?

I’m not personally able to work on this for the next few months, but I can definitely provide some input to folks who are interested and motivated.

We have a 3.0 release of Hanami coming up in late May or early June. A bunch of the changes will be performance-related. If there’s any chance we could bring the router to the party, that would be super cool. :smiling_face_with_sunglasses: But I realise that’s all pretty close, so if this needs more time, that’s totally fine.

2 Likes
12

Thanks for the thoughtful reply, @timriley!

My current plan is:

  1. Mustermann 4.0 release (today).
  2. Implement an experimental branch of hanami-router relying on Mustermann::Set (I’ve done the same for Sinatra already).
  3. Present findings with suggestions for three different paths for Hanami:
    a. Just moving from Mustermann 3.1 to 4.0.
    b. Using Mustermann::Set under the hood.
    c. Reducing the use of Mustermann features in Hanami further.

If it is decided to use Mustermann::Set, then I’d be happy to work on a non-experimental implementation.

2 Likes