Summary of "Introduction to Golang HTTP router made with net/http"
Tags: go, algorithms, http, beginners
Published: 2021-12-14 14:18:16

This article is a translation of [qiita.com.com --Self-made HTTP router made with net / http] (https://qiita.com/bmf_san/items/312fac5b3132d8bee4ca)

This is a summary of the [article](https://dev.to/bmf_san/introduction-to-golang-http-router-made-with-nethttp-3nmb) I wrote the other day.

I wrote this article because I wish I could get more people's eyes and feedback.

I'm waiting for a star to [bmf-san/goblin](https://github.com/bmf-san/goblin). :D

If you just want to see the code, see below.
[bmf-san/introduction-to-golang-http-router-made-with-net-http/blob/main/trie.go] (https://github.com/bmf-san/introduction-to-golang- http-router-made-with-net-http / blob/main/trie.go)

I would be grateful if you could also see the HTTP router I made.
[bmf-san/goblin](https://github.com/bmf-san/goblin)

# What are you talking about?
It's a story about how to think and how to make your own HTTP router using only standard packages in Go.

Create your own HTTP router like the one below.
[bmf-san/introduction-to-golang-http-router-made-with-net-http/blob/main/trie.go] (https://github.com/bmf-san/introduction-to-golang- http-router-made-with-net-http/blob/main/trie.go)

# What's interesting?
- It will be an opportunity to deepen your understanding of net/http
- It will be an opportunity to learn algorithms and data structures
- You can know the contents of the HTTP router
- You can make your own HTTP router and play with it.

# Prerequisite knowledge
- Understanding the basic grammar of Go
- It would be nice if you had touched some kind of HTTP router

# What is an HTTP router?
It is an application that connects the requested URL and the processing of the response.

![route_in_client_and_server](https://user-images.githubusercontent.com/13291041/138551922-8fce2b9c-51d6-49e6-bea1-015e383cdb6e.png)

Mapped data is required to connect the URL and the process.

|       Request URL       |     Handler      |
| :---------------------- | :--------------- |
| GET  /                  | IndexHandler     |
| GET  /foo               | FooHandler       |
| POST /foo               | FooHandler       |
| GET  /foo/:id           | FooHandler       |
| POST /foo/:id           | FooHandler       |
| GET  /foo/:id/:name     | FooHandler       |
| POST /foo/:id/:name     | FooHandler       |
| GET  /foo/bar           | FooBarHandler    |
| GET  /foo/bar/:id       | FooBarHandler    |
| GET  /foo/bar/:id/:name | FooBarHandler    |
| GET  /foo/bar/baz       | FooBarBazHandler |
| GET  /bar               | BarHandler       |
| GET  /baz               | BazHandler       |

Inside the HTTP router, such data is converted into a manageable data structure and held.

# data structure
Adopt a tree structure that is just right for expressing the hierarchical structure of URLs.

![tree_structure](https://user-images.githubusercontent.com/13291041/138551925-b0544b07-1f2d-44bb-9724-495780908b2d.png)

The tree is made up of Nodes. The Node at the top is called Root, and the Node at the bottom is called Leaf. The "branch" that connects Nodes is called Edge.

The operation to add a Node to a tree is called Insert, and the operation to find a Node from a tree is called Search.

When making your own HTTP router, I think you should know at least this much.

It is even better to understand one of the basic trees in the world of algorithms and data structures, the binary search tree.

[bmf-tech.com - アルゴリズムとデータ構造 - 二分探索木](https://bmf-tech.com/posts/%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%A8%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0%20-%20%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2%E6%9C%A8)

In talking about my own work this time, I will adopt a tree structure based on a data structure called a trie tree.

I think that many libraries adopt some kind of tree structure in the observation range, but it seems that famous places often adopt a data structure called radix tree.

For a description of tri-trees, see [bmf-tech.com - Golangでトライ木を実装する
](https://bmf-tech.com/posts/Golang%E3%81%A7%E3%83%88%E3%83%A9%E3%82%A4%E6%9C%A8%E3%82%92%E5%AE%9F%E8%A3%85%E3%81%99%E3%82%8B), so I will omit it.

For an understanding of the algorithm, we also recommend [Algorithm Visualizations - Trie (Prefix Tree）](https://www.cs.usfca.edu/~galles/visualization/Trie.html).

Since we will implement a tree structure based on the tri-tree, if you understand the tri-tree, it will be easier to understand the implementation of the HTTP router you will make this time.

The data structure of the HTTP router that I make this time is the following tree structure.

![tree_for_implementation](https://user-images.githubusercontent.com/13291041/138551924-ca2e28f5-a0c1-4ae4-ac9f-76d6ee1c46d9.png)

This tree structure represents the following mapping of URL and response processing.


|       Request URL       |     Handler      |
| :---------------------- | :--------------- |
| GET  /                  | IndexHandler     |
| GET  /foo               | FooHandler       |
| POST /foo               | FooHandler       |
| GET  /foo/bar           | FooBarHandler    |
| GET  /foo/bar/baz       | FooBarBazHandler |
| GET  /bar               | BarHandler       |
| GET  /baz               | BazHandler       |

Since it is an introduction, it is assumed that the functions will be reduced as much as possible and simple things will be implemented.

# net/http Basic knowledge
We need to know how to use net/http to extend the functionality of HTTP routers, so let's sort out the points.

net/http has features called multiplexers and handlers.

The multiplexer has the role of comparing the URL of the request with the registered pattern and calling the handler that matches the best.

The handler is responsible for returning the processing in response to the request.

Go allows you to implement an HTTP server with just a few lines of code.

```golang
package main

import (
"fmt"
"net / http"
)

func main () {
mux: = http.NewServeMux ()
mux.HandleFunc ("/", handler)

http.ListenAndServe (": 8080", mux)
}

func handler (w http.ResponseWriter, r * http.Request) {
fmt.Fprintf (w, "Hello World")
}
```

From the above code, if you read the net / http code with the following points in mind, you can see what to implement.

- Where and how the multiplexer registers handlers, and what are the specifications for matching URLs and patterns?
- How to create a handler (whether there is a variation of handler creation, what interface should be satisfied)

Details [bmf-tech.com - 第3章HTTPサーバーのコードリーディング](https://bmf-tech.com/posts/net%EF%BC%8Fhttp%E3%81%A7%E3%81%A4%E3%81%8F%E3%82%8BHTTP%E3%83%AB%E3%83%BC%E3%82%BF%E3%83%BC%E8%87%AA%E4%BD%9C%E5%85%A5%E9%96%80#%E7%AC%AC3%E7%AB%A0HTTP%E3%82%B5%E3%83%BC%E3%83%90%E3%83%BC%E3%81%AE%E3%82%B3%E3%83%BC%E3%83%89%E3%83%AA%E3%83%BC%E3%83%87%E3%82%A3%E3%83%B3%E3%82%B0), so please refer to it if you have time.

# Implementation
As I introduced at the beginning, the HTTP router implemented this time is in the following repository.

[bmf-san/introduction-to-golang-http-router-made-with-net-http](https://github.com/bmf-san/introduction-to-golang-http-router-made-with-net-http/)

This time we will implement a simple HTTP router that "supports method-based routing".

* Since it is a summary version, detailed explanation of the code is omitted.

Method-based routing means that you can register URLs by HTTP method.

In the function of Go standard package only, if you want to route by method, you need to implement conditional branching in the handler.

```go
// ex.
func indexHandler (w http.ResponseWriter, r * http.Request) {
    switch r.Method {
        case http.MethodGet:
            // do something ...
        case http.MethodPost:
            // do something ...

        ...

        default: default:
```

This time, we will implement it only with the goal of eliminating this trouble.

In order to achieve method-based routing, we will adopt a tri-tree-based data structure.

Since it is a simple function, a simpler data structure (such as making it possible to use the standard multiplexer function for each method) is fine, but we will adopt it in anticipation of various implementations later. (To be honest, I just simplified the implementation of [bmf-san/goblin] (https://github.com/bmf-san/goblin).)

The general things to do in implementing an HTTP router are as follows.

- Process to add URL and handler mapping to data structure
    - https://github.com/bmf-san/introduction-to-golang-http-router-made-with-net-http/blob/main/trie.go#L51
- Process to search for matching data from the mapped data structure (≈ tri-tree-based data structure)
    - https://github.com/bmf-san/introduction-to-golang-http-router-made-with-net-http/blob/main/trie.go#L93
- Implementation of DSL for registering mapping
    - Around here https://github.com/bmf-san/introduction-to-golang-http-router-made-with-net-http/blob/main/router.go#L47
- Implementation of function as a multiplexer (≈ implementation of ServeHTTP)
    - https://github.com/bmf-san/introduction-to-golang-http-router-made-with-net-http/blob/main/router.go#L54

The first thing you want to do to implement is to implement the data structure.

![tree_for_implementation](https://user-images.githubusercontent.com/13291041/138551924-ca2e28f5-a0c1-4ae4-ac9f-76d6ee1c46d9.png)

It is easier to work if you use the debug function of the editor (using delve in vscode) or write test code to check if it is implemented well.

For implementation details, see [bmf-tech.com - 第4章HTTPルーターの実装](https://bmf-tech.com/posts/net%EF%BC%8Fhttp%E3%81%A7%E3%81%A4%E3%81%8F%E3%82%8BHTTP%E3%83%AB%E3%83%BC%E3%82%BF%E3%83%BC%E8%87%AA%E4%BD%9C%E5%85%A5%E9%96%80#%E7%AC%AC4%E7%AB%A0HTTP%E3%83%AB%E3%83%BC%E3%82%BF%E3%83%BC%E3%81%AE%E5%AE%9F%E8%A3%85).

# Summary
HTTP routers are almost indispensable for creating web applications, and aren't they very much taken care of?

My motivation was that I wanted to make something that I used as a matter of course and use it myself.

There are already a lot of great HTTP routers out there, so I think one of the real thrills is that it's worth researching.

This time I implemented it in Go, but if I understand the mechanism, I think that it can be implemented in languages ​​other than Go.

In Go, the interface is provided in a form that makes it easy to extend the function of the standard package, so I felt that it was relatively easy to make by myself.

If you are interested in this article, I would be grateful if you could take a look at [bmf-san/goblin] (https://github.com/bmf-san/goblin). 

Feel free to send an Issue or Pull Request. :D