はじめに
本記事では、Golangの標準パッケージであるnet/httpを用いて、HTTPルーターを自作する方法について解説します。
標準パッケージはあまり多くのルーティングの機能を提供していません。
例えばHTTPメソッドごとのルーティングの定義ができなかったり、URLをパスパラメータとして利用できなかったり、正規表現を利用したルーティングの定義ができなかったりします。
その為、実際のアプリケーション開発ではより高機能なHTTPルーターを導入していることが少なくないのではないでしょうか。
そんなHTTPルーターですが、自作してみると次のようなメリットを享受できます。
- net/httpについて知ることができる
- アルゴリズムの面白さに触れることができる
- 自分が使いたい、使いやすいと思えるHTTPルーターを実装できる
- 実装を全て理解したHTTPルーターを自分のアプリケーションに組み込むことができる
本記事では次のような構成でHTTPルーターの自作について解説します。
- はじめに
- 目次
- 第1章HTTPルーターとは何か
- 第2章HTTPルーターのデータ構造
- 第3章HTTPサーバーのコードリーディング
- 第4章HTTPルーターの実装
- まとめ
各章について本筋から離れる内容についてはコラムとして記載しています。
本記事は以下のような読者にとって有意義な内容となることを想定しています。
- Golangの文法は理解したので何かを作ってみたい
- Golangの標準パッケージについて理解を深めるきっかけが欲しい
- 簡単なアルゴリズムの実装にGolangで取り組んでみたい
- 標準のルーティング機能が物足りないので拡張する方法が知りたい
- 普段使っているHTTPルーターの実装を理解したい
本記事を読むに当たっては、次のような前提知識があれば内容を十分に理解できます。
- Golangの基本的な文法の理解
- 何かしらのHTTPルーターを利用した経験
筆者はbmf-san/goblinというHTTPルーターのパッケージを公開しています。
ぜひコードを見たり、使ってみたりしてみてください。コントリビュートも大歓迎です。
目次
- はじめに
- 第1章HTTPルーターとは何か
- 第2章HTTPルーターのデータ構造
- 第3章HTTPサーバーのコードリーディング
- 第4章HTTPルーターの実装
- まとめ
第1章HTTPルーターとは何か
HTTPルーターはURLルーターと呼ばれたり、単にルーターと呼ばれたりもしますが、本記事ではHTTPルーターと呼称を統一することにします。
HTTPルーターは次の図のように、リクエストされたURLとレスポンスの処理を結びつけるアプリケーションです。
HTTPルーターは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に応じたレスポンスの処理を探し出すことを「ルーティング」と定義します。
また、HTTPにおいてルーティングを行うアプリケーションのことを「HTTPルーター」と定義します。
コラム：URLの仕様
URLは、インターネット上のページのアドレスを表し、Uniform ResourceLocatorの略語です。
URL文字列の形式は次のように定義されています。
この部分にはhttp、https、ftpなどのプロトコル名がよく使用されますが、プロトコル名以外のスキーマ名も定義されています。
<scheme-specific-part>の部分では、スキーマに基づく文字列が定義されています。
例えば、httpおよびhttpsスキームの場合、ドメイン名とパス名（またはディレクトリ名）が定義されるという規則があります。
詳細なURL仕様については、RFC 1738を参照してください。
RFC 1738は、インターネット標準（STD1）として位置付けられています。
第2章HTTPルーターのデータ構造
データ構造を考える
以下は第1章で例示したルートマップです。
| 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 |
URLに着目すると階層構造であることが見て取れます。
階層構造は木構造と相性が良いので、ルートマップを木構造で表現することを考えます。
木構造とは
グラフ理論における木の構造をしたデータ構造のことです。
木構造は階層構造を表現するのに適したデータ構造です。
木を構成する要素をノード（節）、一番上位に親のないノードをルート（根）、最下位にある子のないノードをリーフ（葉）と呼びます。ノードとノードの繋がりはエッジ（枝）と呼びます。
木にノードを追加することを挿入、木からノードを探し出すことを探索と言います。
木構造の中でも基本的な木である二分探索木の実装例を次に示します。
ここでは詳細に説明することは割愛しますが、二分探索木は木構造の基本的なアルゴリズムを学ぶにちょうど良い木です。
木構造には二分探索木の他にも様々な種類があります。その中でもトライ木（プレフィックス木ともいわれる。本記事ではトライ木と呼称します）と呼ばれる木構造は文字列の探索がしやすいという特徴があります。
トライ木を利用することによりルーティングで扱いやすいデータ構造を表現できます。
トライ木とは
トライ木は、IPアドレス探索や形態素解析などでも利用されている木構造の一種です。
各ノードは単一または複数の文字列あるいは数値を持ち、根ノードから葉に向かって探索して値をつなげていくことで単語を表現します。
アルゴリズムを可視化して動的に理解できるサービスがあるので、そちらを見てみるとトライ木のデータ構造を理解しやすいです。
cf. Algorithm Visualizations - Trie (Prefix Tree）
トライ木は比較的簡単に実装できます。
次のコードは探索と挿入だけ実装されたトライ木のコード例です。
このトライ木をベースにすることで、ルーティングに最適化したデータ構造を検討します。
トライ木をベースにルートマップのデータ構造を考える
トライ木の考え方をベースにルートマップのデータ構造を考えます。
以下は筆者が開発しているbmf-san/goblinで採用しているデータ構造となります。
goblinでは、ミドルウェアやパスパラメータをサポートしているため、それらに対応したデータ構造となっています。
このデータ構造は次のようなルートマップを表現しています。
| Request URL | Handler | Middleware |
|---|---|---|
| GET / | IndexHandler | none |
| GET /foo | FooHandler | FooMws |
| POST /foo | FooHandler | FooMws |
| GET /foo/bar | FooBarHandler | none |
| GET /foo/bar/:id | FooBarHandler | none |
| GET /foo/baz | FooBazHandler | none |
| GET /foo/bar/baz | FooBarBazHandler | none |
| GET /baz | BazHandler | none |
観点としては、以下の二点に集約されます。
- URLをどのようなルールで木構造として表現するか
- ノードに持たせる必要なデータは何か
前者はルーティングの性能を決める部分であり、処理時間やメモリ効率などを追求する場合はより高度な木構造の採用を検討する必要があります。
後者はHTTPルーターの機能に関わる部分なので、提供したい機能によって様々です。
今回紹介したトライ木をベースとした木構造は、あくまで筆者が考えた木構造に過ぎません。
HTTPルーターの実装要件によりデータ構造はそれぞれです。
次の章でこのデータ構造をHTTPルーターに組み込むため上で知っておきたいことについて説明します。
コラム：基数木（パトリシア木）
文字列を格納するトライ木を更に発展させた木構造に基数木という木構造があります。
基数木はパフォーマンスに配慮したHTTPルーターでは良く使われているのを筆者は観測しています。
Golangのstringsパッケージの内部でも使われているようです。
https://cs.opensource.google/go/go/+/refs/tags/go1.17.2:src/strings/strings.go;l=924
第3章HTTPサーバーのコードリーディング
HTTPルーターの実装について説明する前に、次のようなnet/httpを利用したHTTPサーバーのコードを例に、HTTPルーターを実装する上で知っておきたいことについて説明します。
必要に応じて以下のリンクを参照してください。
https://cs.opensource.google/go/go/+/refs/tags/go1.17.2:
このコードは単純であるものの、HTTPルーターを自作する上で示唆に富んだコードです。
このコードはマルチプレクサの呼び出し、ハンドラの登録、サーバーの起動という流れの処理になっています。
それぞれについて順番に見ていきます。
マルチプレクサの呼び出し
まず最初のコードは、http.ServeMuxという構造体を生成しています。
net/httpのドキュメントでは、http.ServeMuxはHTTPリクエストマルチプレクサ（以下、マルチプレクサ）であると説明がなされています。
このマルチプレクサは、リクエストのURLを登録済みのパターンと照らし合わせて、最もマッチするハンドラ（レスポンスを返却する関数）を呼び出すという役目を持っています。
http.ServeMuxはつまり、ルーティングのための構造体であるということが言えます。
このhttp.ServeMuxにはServeHTTPというメソッドが実装されています。
cs.opensource.google - go1.17.2:src/net/http/server.go;l=2415
ServeHTTPの以下の部分を更に読み進めていくと、ServeHTTPのルーティングの処理が見えてきます。
順々にコードジャンプしていくと、マッチするハンドラを探して返却する関数にたどり着きます。
マッチするハンドラが見つかった場合は、そのハンドラのServeHTTPを呼びだすことで、レスポンスのための処理を呼び出します。
それがhttp.ServeMuxに実装されたServeHTTPメソッドの末尾にある処理です。
HTTPルーターを自作するためには、標準のマルチプレクサに取って代われるように、http.Handler型を満たした（≒ServeHTTPを実装した）マルチプレクサを実装してあげる必要があります。
ハンドラの登録
続いて次のコードでは、マルチプレクサにハンドラを登録しています。
マルチプレクサに登録されるハンドラは、http.Handler型を満たす（≒ServeHTTPが実装される）必要があります。
あるいは、http.HandlerFunc型を実装する形でもハンドラを作成できます。
http.HandlerFunc型はfunc(ResponseWriter, *Request)を型として定義したもので、ServeHTTPメソッドを実装しています。
https://cs.opensource.google/go/go/+/refs/tags/go1.17.2:src/net/http/server.go;l=2045
従ってhttp.HandlerFunc型を使う場合は次のようにハンドラを作成できます。
HTTPルーターを実装する上では、http.Handler型をサポートするように実装を意識すると、ハンドラの作成方法に柔軟性をもたせることができるため、扱いやすいパッケージになります。
サーバーの起動
最後のコードでは、サーバーを起動するポート番号とマルチプレクサを関数に渡して、HTTPサーバーを起動しています。
内部的には、http.Server型のListenAndServeが呼び出されています。
この関数では、第2引数がnilのときはhttp.DefaultServeMuxというデフォルトのhttp.ServeMuxが利用されるようになっています。
つまり、マルチプレクサを拡張したいようなケース以外では、マルチプレクサをわざわざ生成しなくても良いということです。
HTTPルーターを実装していく上では、話の前触れとして必要だったため、マルチプレクサをわざわざ生成するようなコードを例として上げました。
HTTPルーターを実装する上での必要なコードリーディングができたので、次の章から実装の解説をします。
コラム:末尾スラッシュについて
URLの末尾に付与される/はドメイン名末尾と、サブディレクトリ末尾のケースでそれぞれ違いがあります。
ドメイン名末尾の場合、一般的なブラウザでは/が無い場合は、/が有るURLにリクエストします。
https://bmf-tech.com→https://bmf-tech.com/にリクエストhttps://bmf-tech.com/→https://bmf-tech.comにリクエスト
ドメイン名末尾の場合は/の有無にあまり違いはありませんが、サブディレクトリ末尾場合は明確な違いがあります。
https://bmf-tech.com/posts→ ファイルへのリクエストhttps://bmf-tech.com/posts/→ ディレクトリへのリクエスト
より詳しく仕様について知りたい場合はRFCを参照してください。
HTTPルーターを実装する上では、URLのパス部分をどう解釈するかという点で気にしておく必要がある部分です。
筆者が開発したbmf-san/goblinでは、末尾/有無は同じルーティングの定義として扱う仕様としています。
第4章HTTPルーターの実装
HTTPルーターの実装をするための準備ができたので、実装の解説をします。
今回は標準パッケージよりも少しだけ高機能なルーターを実装します。
具体的には次の2つの特徴を備えたルーターになります。
- メソッドベースのルーティングをサポートしている
- トライ木をベースとしたアルゴリズムを実装している
標準パッケージの機能では、HTTPメソッド別にルーティングを登録できません。
HTTPメソッド別にルーティングをしたい場合はハンドラーの中でHTTPメソッドごとの条件分岐をするような実装が必要となります。
ハンドラーにこのような条件分岐を定義せずとも、メソッドごとにルーティングを定義できる機能を実装します。
メソッドベースでルーティングを定義可能なHTTPルーターのアルゴリズムとしては、HTTPルーターのデータ構造で説明したトライ木をベースとした木構造を採用します。
準備
今回実装するHTTPルーターのソースコードは以下にあります。
bmf-san/introduction-to-golang-http-router-made-with-net-http
テストコードは実装過程で書くことを推奨しますが、テストコードについて解説は行いません。
CIについても同様です。
Golangのバージョンは1.17を利用しています。
実装
実装手順としてはまず、トライ木をベースとしたルーティングのアルゴリズムを実装するところから始めます。
その後でメソッドベースのルーティングをサポートするための実装をします。
トライ木をベースとしたルーティングのアルゴリズムの実装
それでは早速実装していきます。
ここで実装するコードは全て以下で参照できます。
bmf-san/introduction-to-golang-http-router-made-with-net-http/blob/main/trie.go
今回は、goblinのデータ構造を簡素化した以下のような木構造を採用することにします。
この木構造で表現されるルートマップは以下の通りです。
| 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 |
上記の木構造を表現するために、まずは必要なデータを定義していくところから書き始めます。
trie.goというファイルを作成し、構造体を定義してください。
treeは木そのもの、nodeは木を構成する要素で、label、actions、childrenを持ちます。
labelはURLのパス、actionsはHTTPメソッドとハンドラーのマップを表現します。childrenはlabelとnodeのマップで、子ノードを表現します。
resultは木からの探索結果を表現します。
続いてこれらの構造体を生成する関数を定義しておきます。
では、木へノードを追加する部分の処理を実装します。
treeをポインタレシーバとしたInsertメソッドを定義します。
この関数の引数のポイントとしては、HTTPメソッドを複数渡せるように引数を定義している点です。
HTTPメソッドごとに単一のハンドラーを定義できるだけでなく、複数のメソッドに対して同一のハンドラーを定義できるようになっています。
実装の方針によっては、ハンドラーの中でHTTPメソッドの条件分岐をしたいというケースもあるという可能性を考慮して、汎用性を持たせています。
続いて、Insertの中身ですが、最初にスタート地点となるノードを変数として定義しています。
次に探索する対象が/（ルート）の場合の条件分岐を処理します。
/の場合は、後続のループ処理をする必要がないので、ここで木へのノード追加して終了するように処理します。
/以外の場合は処理を継続します。
URLのパスを/で分解して、[]string型のスライスにパスの文字列を格納する処理を行います。
[]string型のスライスは、ノード追加する位置を見つけるために、rangeで走査します。
ここでの処理はHTTPルーターのデータ構造で説明したトライ木の実装がベースとしています。
子ノードが見つからなかったときにノードを追加するようにします。
ルーティングの定義が重複するようなケースとなった場合は、後勝ちとなる仕様になるように処理しています。
最終的なInsertの実装は次のようになります。
これで木への挿入の処理が実装できたので、次は木からの探索の処理を実装します。
挿入と比べて探索は比較的シンプルなので、一度で説明します。
探索の場合も挿入と同じく、URLのパスが/か否かでループ処理に進むかどうか決まります。
ループ処理に進む場合は、子ノードを見ていき対象のノードが存在するか探索していくだけです。
対象のノードが存在する場合は、リクエストのHTTPメソッドとマッチするハンドラを探して、resultを返します。
メソッドベースのルーティングをサポートするための実装
ここで実装するコードの全体像は以下になります。
bmf-san/introduction-to-golang-http-router-made-with-net-http/blob/main/router.go
ここではHTTPルーターとしての機能を提供するための実装も合わせて行います。
まずは構造体の定義と生成用の関数です。
Routerはnet/httpでいうhttp.ServeMuxに当たります。
routeはルーティングの定義のためのデータを持ちます。
次に、Routerに次の3つのメソッドを実装します。
MethodsはHTTPメソッドのセッター、HandlerはURLのパスとハンドラーのセッターでHandleを呼び出します。Handleでは先程実装した木への挿入の処理を呼び出します。
MethodsやHandlerはHTTPルーターを利用する側の可読性を意識して、メソッドチェインとして実装しています。
メソッドベースのルーティングは木と組み合わせてこれで実現できます。
最後は、RouterにServeHTTPを実装させたら完成です。
実装したHTTPルーター使ってみる
今回実装したHTTPルーターは次のように使うことができます。
サーバーを起動してそれぞれのエンドポイントにリクエストして動作確認してみてください。
駆け足気味になってしまいましたが、実装の解説は以上です。
コラム：HTTPルーターのパフォーマンス比較
HTTPルーターのパフォーマンス比較に興味があるのであれば、以下のリポジトリを見てみてください。
julienschmidt/go-http-routing-benchmark
筆者はこのリポジトリにgoblinのパフォーマンス比較のPRを出しました。
まとめ
本記事ではHTTPルーターを自作するまでのアプローチについて解説しました。
第1章では、HTTPルーターは何をするアプリケーションなのかについて整理しました。
第2章では、HTTPルーターにおけるデータ構造について、例を混じえながら解説しました。
第3章では、net/http使ったHTTPサーバーのコードについて深堀りしました。
そして、第4章ではHTTPルーターの実装方法についてコードとともに説明しました。
本記事を通じて、何か1つでも読者の役に立つことがあったり、興味を持ってもらえることがあれば幸いです。
また。拙作であるbmf-san/goblinについてもコードを見てもらえるきっかけになれば嬉しいです。
質問や修正依頼、フィードバック等あればぜひ教えて下さい。
あとがき
- zenn.dev -
net／httpでつくるHTTPルーター 自作入門
- この記事の内容を本にしてあります。
- dev.to - Introduction to Golang HTTP router made with net/http
- 英語に翻訳したものです。
- github.com - bmf-san/book-introduction-to-golang-http-router-made-with-net-http
- 原文管理しているリポジトリです。
- net/httpでつくるHTTPルーター自作入門
- Go Conference 2021に登壇してきました