Hunter's blog

Implementing a Router for an HTTP Server

As part of my web framework Hayaku, I implemented a router. The router handles directing requests to handlers based on the request path. I based it on fasthttprouter, because my whole framework is inspired by Golang and fasthttprouter can handle parameters; a feature I wanted. In this post, I want to talk about the data structure that matches requests to handlers.

The Data Structure
For hayaku-path I used a Patricia trie to store routes. A Patricia trie is a tree that stores strings based on common prefixes. As an example, here is a diagram of how the words rat, rabbit, and zebra would be stored in a Patricia trie.
  zebra
 /
-    t
 \  /
  ra
    \
     bbit


I am using a slightly modified Patricia trie in order to support parameters. For hayaku-path, path parameters are of the form /{NAME} or /{NAME:REGEX}. Parameters greatly increase the complexity of the trie. For comparison, here are the node types for a standard Patricia trie and my parameterised Patricia trie.
// Standard Patricia trie
struct Node<T> {
    key: String,
    value: Option<T>,
    children: Vec<Box<Node<T>>>,
}

// Parameterised Patricia trie
struct Node<T> {
    key: String,
    value: Option<T>,
    children: Vec<Box<Node<T>>>,
    param: Option<Regex>,
}
In the parameterised node, key serves double duty. For a node without a param, we match directly against key just like in a standard Patricia trie. However, if there is a param, key is the name of the param and we instead check if the path matches the RegEx.

TODO
I initially built a standard Patricia trie and added the param functionality later. This incremental process made it much easier to write initially, but it came with a cost. The added complexity introduced a number of bugs, which I've discovered and fixed over time. The addition of params later on meant that the code became rather messy. I intend to rewrite the data structure, but as often happens with software it is "good enough" for now so I focus on other projects.