先日、net／httpでつくるHTTPルーター 自作入門という薄い本を書いたのですが、もっと手短に内容を伝えたいと思ったので、本の要約を書いてみました。
コードだけ見たいという場合は以下を参照してください。
bmf-san/introduction-to-golang-http-router-made-with-net-http/blob/main/trie.go
合わせて筆者が自作したHTTPルーターも見てもらえると嬉しいです。
bmf-san/goblin
何の話？
Goで標準パッケージだけを使ってHTTPルーターを自作するための考え方とやり方の話です。
以下のようなHTTPルーターを自作します。
bmf-san/introduction-to-golang-http-router-made-with-net-http/blob/main/trie.go
何が面白い？
- net/httpの理解を深めるきっかけになる
- アルゴリズムとデータ構造を学ぶきっかけになる
- HTTPルーターの中身を知ることができる
- 自作HTTPルーターを作って遊ぶことができる
前提知識
- Goの基本的な文法を理解していること
- 何かしらのHTTPルーターに触れたことがあると良い
# HTTPルーターとは
リクエストされるURLとレスポンスの処理を結びつけるアプリケーションのことです。
URLと処理を結びつけるためには、マッピングされたデータが必要です。
| 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 |
HTTPルーターの内部では、このようなデータを扱いやすいデータ構造に変換して保持します。
データ構造
URLの階層構造を表現するのに丁度良い木構造を採用します。
木はNodeで構成されています。最上位にあるNodeをRootと呼び、最下位にあるNodeをLeafと呼びます。Node間をつなぐ”枝”の部分はEdgeといいます。
木にNodeを追加する操作を挿入（Insert）、木からNodeを探し出す操作を探索（Search）といいます。
HTTPルーターを自作する上では、最低限これだけ知っておけば良いのではないかと思います。
アルゴリズムとデータ構造の世界では基本的な木の一つである二分探索木について理解しておけるとなお良いです。
bmf-tech.com - アルゴリズムとデータ構造 - 二分探索木
今回自作の話をする上では、トライ木と呼ばれるデータ構造をベースとした木構造を採用します。
筆者が観測範囲では、多くのライブラリは何かしらの木構造を採用していると思いますが、有名所は基数木と呼ばれるデータ構造を採用しているケースが多いようです。
トライ木についての解説はbmf-tech.com - Golangでトライ木を実装する
で解説しているので割愛します。
アルゴリズムの理解については、Algorithm Visualizations - Trie (Prefix Tree）もおすすめします。
トライ木をベースとした木構造を実装するので、トライ木については理解があると今回自作するHTTPルーターの実装を理解しやすいかと思います。
今回自作するHTTPルーターのデータ構造は次のような木構造になります。
この木構造では次のようなURLとレスポンスの処理のマッピングを表現しています。
| 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 |
入門ということで機能は極力削ってシンプルなモノを実装する想定です。
net/http基礎知識
net/httpをどのように利用してHTTPルーターの機能を拡張するのかについて知っておく必要あるので、要点を整理します。
net/httpには、マルチプレクサとハンドラという機能があります。
マルチプレクサとは、リクエストのURLを登録済みのパターンと照らし合わせて、最もマッチするハンドラ呼び出すという役目を持っています。
ハンドラはリクエストに応じた処理を返すという役目を持っています。
Goでは数行のコードでHTTPサーバーが実装できます。
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")
}
上記のようなコードから、以下のような点に意識を置いてnet/httpのコードリーディングをすると、何を実装したら良いかが見えてきます。
- マルチプレクサはどこでどうやってハンドラを登録しているのか、URLとパターンのマッチングはどのような仕様になっているか
- ハンドラはどのように作成するのか（ハンドラ作成のバリエーションがあるか、どんなインターフェースを満たせば良いか）
委細についてbmf-tech.com - 第3章HTTPサーバーのコードリーディングで解説しているので、時間があれば参照してみてください。
実装
冒頭でも紹介しましたが、今回実装したHTTPルーターは以下のリポジトリにあります。
bmf-san/introduction-to-golang-http-router-made-with-net-http
今回は”メソッドベースのルーティングをサポート”したシンプルなHTTPルーターを実装します。
※要約版なので、コードについての詳細の説明は省きます。
メソッドベースのルーティングというのは、HTTPメソッド別にURLを登録できるということです。
Goの標準パッケージのみの機能では、メソッド別にルーティングをしたい場合はハンドラの中で条件分岐をするような実装が必要になります。
// ex.
func indexHandler(w http.ResponseWriter, r *http.Request) {
switch r.Method {
case http.MethodGet:
// do something...
case http.MethodPost:
// do something...
...
default:
今回はこの手間を解消してすることだけを目標として、実装します。
メソッドベースのルーティングを実現するために、トライ木をベースとしたデータ構造を採用することにします。
シンプルな機能なのでもっと単純な（メソッドごとに標準のマルチプレクサの機能を利用できるようにするなど）データ構造でも良いのですが、後々に色々実装したくなることを見越した上での採用とします。（bmf-san/goblinの実装を単純にしただけ、というのが正直な話ではあります。）
HTTPルーターの実装でやることは概ね以下の通りです。
- URLとハンドラのマッピングをデータ構造に追加する処理
- マッピングされたデータ構造（≒トライ木ベースのデータ構造）からマッチするデータを探す処理
- マッピングを登録するためのDSLの実装
- マルチプレクサとしての機能の実装（≒ServeHTTPの実装)
実装する上で一番にやっておきたいことは、データ構造の実装です。
エディタのデバッグ機能（vscodeでdelve使っています）を活用したり、テストコードを書くなどして上手く実装できているか確認しながら手を進めると作業しやすいです。
実装の詳細についてはbmf-tech.com - 第4章HTTPルーターの実装を参照してください。
まとめ
楽しいと思うのでやってみてください（雑
HTTPルーターはWebアプリケーションを作るでは殆ど必須な存在で、非常に世話になっているのではないでしょうか？
当たり前のように使っているものを自分で作って自分で使って見たかったというのが筆者のモチベーションでした。
既に素晴らしいHTTPルーターが沢山存在しているので、研究しがいがあるというのが醍醐味の一つかなと思っています。
今回はGoで実装しましたが、仕組みが分かればGo以外の言語でも実装できるかと思います。
Goでは標準パッケージが機能を拡張しやすいような形でインターフェースが提供されているので、比較的自作しやすさがあるように感じました。
記事を通して興味を持ってもらえたら、bmf-san/goblinもぜひ見てもらえると嬉しいです。IssueやPull Requestを気軽に送ってください:D）
追記
関連リンクぶら下げたツイートを貼っておきます。
— Kenta Takeuchi (@bmf_san) October 24, 2021