Introduction to Custom URL Routing: Episode 2

#http #urlrouting #router

This article was originally published on bmf-tech.com.

Overview

This article is a continuation of Introduction to Custom URL Routing: Episode 1 and is the 15th day of the Makuake Development Team Advent Calendar 2019.

Creating Custom URL Routing

Continuing from the previous article.

When creating a custom router, let's consider what kind of processing the router performs from the perspective of data structure.

I have illustrated an example of what input the router receives and what output it returns in the case of dynamic routing.

The router's role is to receive the URL path part as input, determine the data that matches the path, output it, and connect it to the next process.

How to perform path matching is the core part of the implementation.

The performance required of the router may vary depending on the context in which it is introduced (such as the scale of the application or the direction of the architecture), but here I would like to consider implementing matching processing using a tree structure instead of just regular expression-based matching.※

※In the past, I wrote a library called bmf-san/bmf-react-router for use in React, which was based on regular expressions. It was merely a component wrapping the matching process, thanks to the convenient library path-to-regexp...

Now, let's briefly explain tree structures.

A tree structure is a data structure that has a root, edges, nodes, and leaves (terminal nodes). There are various types of tree structures depending on the pattern of data storage and search methods. Since URL routing mainly deals with strings, we will adopt a trie tree, which is specialized for string search. For more on trie trees, refer to bmf-tech.com - A Trie implementation in Golang.

We will customize the trie tree to store data for URL path matching as follows.

As an example, we define routing that only supports GET.

/foo/
/baz/
/foo/bar/
/foo/:name[string]/
/foo/bar/:id[int]

Nodes are grown directly under the root for each HTTP method, and paths are stored for each HTTP method. Nodes starting with : are nodes that store path parameters, and the DSL [int] is used to associate regular expressions with those parameters. The values that connect to the output (which I think is the router's responsibility to the point of function invocation) may or may not be held by each node. This depends on the predefined routing content.

If you can write code that reproduces the data structure defined above based on the routing definition, you can theoretically create your own router by writing code for the client that uses the router. Theoretically.※

※There is something being implemented, but it's still in progress... I'll try to complete it by the 20th day of Qiita - Go6 Advent Calendar 2019.

The latter part became a bit rushed and rough, but once you get the image, it's just a matter of writing code, so it's as good as done ().

This time, I explained a data structure like a custom extension of a trie tree, but if you are more conscious of memory efficiency, it might be better to adopt a Patricia tree structure. I saw it being adopted when I was exploring Golang implementations.

I have attempted to implement a Patricia tree before but gave up once, so I would like to try again someday...※

※I thought I would understand by reading the code of a Patricia tree, but unlike a simple trie tree, the implementation patterns are "everyone is different and everyone is good," so I tried various things to properly understand and implement the data structure of a Patricia tree, but it was too difficult...

Thoughts

I think routers are a genre with many competitors as OSS libraries, but if you can create something that can stand shoulder to shoulder with even the later ones, the world you see will change, and it will be more fun, so I want to continue in this field as long as I don't get bored.