HTTPルーティングにおけるライブラリの中身を知るために　全探索と正規表現を活用したTinyRouterを実装

自己紹介

宮原光氏（以下、宮原）：ではさっそく始めていきたいと思います。「HTTPルーティングライブラリ入門」ということで、電通国際情報サービスの宮原が発表します。

まずは簡単に自己紹介させてください。名前は宮原光と言います。電通国際情報サービスという会社で働いています。業務は全社の案件支援や、GitHubやJiraなどの構成管理ツールの提供、それから社内ツールの開発などを行っています。

仕事でGoを利用することもありますが、ふだんはTypeScriptやReactでフロントエンドアプリケーションを開発することが多いです。趣味はサッカーです。

本編に入る前に、簡単に弊社の紹介をさせてください。弊社は、株式会社電通国際情報サービスという会社で、ITソリューション提供を事業とする会社です。社名が長いため、「ISID」という名称で呼ばれることも多いです。これは英語表記の社名の頭文字を取ったものになります。

英名が「Information Services International-Dentsu, Ltd.」となっており、頭文字を取って、ISIDとなります。みなさんもぜひ、ISIDという名前で覚えていただければ幸いです。

ISIDの事業領域は、主に4つあります。金融業務領域のITソリューションを提供する金融ソリューション事業部。製造業向けにものづくり・ことづくりを支援する製造ソリューション事業部。マーケティングから基幹業務領域まで、企業のビジネスプロセス最適化をITで支援するコミュニケーションIT。会計・人事パッケージの開発や販売を行うビジネスソリューションの4つから成り立っています。

メインの領域は、金融、製造、電通グループ向け、会計・人事パッケージといった感じになっています。

2019年には4つの事業領域を横断する組織として、私とこのあとに登壇する佐藤さんが所属する全社横断の技術組織、Xイノベーション本部が設立されました。

私や佐藤さんはこの部署で、主に事業部の案件支援や、全社の構成管理基盤の提供を行ったりしています。Xイノベーション本部は、新規事業創出を目的として活動しています。

そのため、ふだんは新規事業創出のための研究開発やPoC（Proof of Concept）、それから全社の支援を行っています。Xイノベーション本部内はさらに複数部署が設置されていて、各分野の精鋭たちが集まっています。

扱っている領域は、UI/UXや、VR・AR、それからAI機械学習など、多岐にわたります。気になる方は、それぞれの部署ごとのホームページを参照してみてください。ホームページでは、各部署での事例や扱っている製品などが載っています。

それから、弊社有志社員が技術ブログとしてQiitaを書いています。こちらもぜひ参照してみてください。

HTTPのルーティングで使用されることの多い3つのライブラリ

ここから本編になります。みなさんはふだん、Webアプリケーションを開発する際、どのようなライブラリを利用しているでしょうか？　特にHTTPのルーティングを行うようなライブラリは、どのようなものを利用されているでしょうか？

まず思いつくのは、Go標準のDefaultServeMuxです。（スライドを指して）DefaultServeMuxを利用したコードは、以下のようになります。http.HandleFuncでパスとハンドラを受け取り、ハンドラをDefaultServeMuxへ登録します。

それから、http.ListenAndServe関数を用いてサーバーを起動します。http.ListenAndServe関数の第2引数をnilにすることで、DefaultServeMuxが呼び出されるようになります。

Goの標準ではないものだと、gorilla/muxを利用されている方も多いのではないでしょうか。（スライドを指して）gorilla/muxを利用したコードは以下のようになります。mux.NewRouterでルーターを初期化し、HandleFunc関数を通してパスとハンドラを登録します。それからhttp.ListenAndServe関数を通して、サーバーを起動します。

今回はListenAndServe関数の第2引数に、gorilla/muxのルーターを渡します。DefaultServeMuxとの差分としては、HTTPメソッドが定義できることや、パスパラメータを利用できることが挙げられます。パスパラメータの値は、ハンドラ内で利用することも可能です。

それから、chiというライブラリを利用されている方もいるのではないでしょうか。（スライドを指して）chiを利用したコードは以下のようになります。書き方はgorilla/muxに似ています。chi.NewRouterでルーターを初期化し、Getメソッドを通してパスとハンドラを登録します。これはHTTPのGETメソッドに対して、パスとハンドラを登録するメソッドです。chiもgorilla/muxと同様に、パスパラメータの値を取得可能です。

このほかにも、GinやEchoといったライブラリを利用されている方もいらっしゃると思います。

ここまで3つのライブラリのコード例を見てきましたが、3つに共通することは、どれもハンドラの登録、それから呼び出しの役割を担っていることです。このようなハンドラの登録、それから呼び出しを行うライブラリのことを、本セッションでは“HTTPルーティングライブラリ”と定義します。

HTTPルーティングライブラリの中身

みなさんは、HTTPルーティングライブラリの中身を見たことはあるでしょうか？　今回私は、HTTPルーティングライブラリの仕組みを学ぶために、実際にHTTPルーティングライブラリを作ってみました。そこで得た知見をみなさんに共有できればと思っています。

今回は、TinyRouterというライブラリを作りました。TinyRouterの仕様は、以下の2つです。1つはパスベースルーティングに対応できること。それから、パスパラメータの取得に対応できることです。

一般的なHTTPルーティングライブラリの機能としては、ほかにもミドルウェアの登録や呼び出し、CORS（Cross-Origin Resource Sharing）やCookieへのアクセスを簡単にするユーティリティな関数などが提供されていますが、今回は学習目的であるため、極力シンプルな仕様にしました。また、今回はライブラリを実装するにあたり、gorilla/muxの実装を参考にしました。

次に、TinyRouterのインターフェイスを見ていきます。インターフェイスは大きく分けて2つの部分からなっています。1つ目は、ハンドラの登録メソッドです。こちらのメソッドでは、パスとハンドラを受け取ります。また、今回はHTTPメソッドに対応する登録メソッドを用意しました。

2つ目は、ServeHTTPメソッドです。このメソッドを実装することによって、Go標準のhttp.Handlerインターフェイスを満たします。http.Handlerインターフェイスを満たすことによってhttp.ListenAndServe関数や、http.Server構造体で利用が可能です。

http.ListenAndServe関数の中では、ServeHTTPメソッドが呼び出されます。ServeHTTPメソッドは、Goの標準パッケージとルーティングライブラリとをつなぐ、非常に重要なメソッドとなっています。

多くのHTTPルーティングライブラリでは、このServeHTTPメソッドが実装されています。みなさんも、利用しているHTTPルーティングライブラリのServeHTTPメソッドの実装を、ぜひ見てみてください。ServeHTTPメソッドの中では、ハンドラの出し分けのロジックが記述されているはずです。

（スライドを指して）TinyRouterの完成形は以下のようになります。完成したものは、gorilla/muxやchiに近いものになっています。tinyrouter.Newでルーターを初期化し、Getメソッドでパスとハンドラーを登録します。

それから、ListenAndServe関数でサーバーを起動するかたちです。パスパラメータを利用する際は、パスパラメータとなる部分を中カッコで囲います。実際の値は、tinyrouter.Param関数をとおして取得が可能です。

ルーティングライブラリの流れ

ここからは、TinyRouterの実装の概要を簡単に説明していきたいと思います。まずは、パスベースルーティングの流れを図で確認しましょう。まず最初に、ルーティングライブラリは、登録メソッド経由でハンドラを登録していきます。一つひとつ順に登録していきます。

リクエストが来たら、ServeHTTPメソッド経由で適切なハンドラにリクエストを渡します。ルーティングライブラリの流れはこのようになります。

ルーティングライブラリの流れから、以下のような実装が思いつくのではないでしょうか？　

パスベースルーティングの流れ

まず最初にハンドラを登録する。リクエストが来たら、ハンドラのHTTPメソッドとパスをリクエストと順に比較する。これは、登録されているハンドラを一つひとつチェックする、いわゆる全探索です。そして、HTTPメソッドとパスの文字列が一致したらハンドラを呼び出すといった流れです。

この流れを図式化してみましょう。まずはハンドラを登録します。今回は、3つのハンドラがルーティングライブラリに登録されています。リクエストが来たら、ServeHTTPメソッド経由で適切なハンドラを決定していきます。今回はリクエストとして、「GET /books」が来たとします。

ServeHTTPメソッドの中では、リクエストとハンドラのメソッドを、パスが一致するかを一つひとつ確認していきます。そして、メソッドとパスの文字列が一致すればOKです。

しかしながらこのアルゴリズムでは、パスパラメータがある場合にうまく対応できません。今、ハンドラ3には「GET /users/{id}」が登録されているとします。そして、リクエストとして「GET /users/1」が来たとします。

GET /users/1のリクエストは、本来であればハンドラ3にルーティングされるべきですが、単純な文字列比較だと、users/1と/users/{id}は文字列として一致しないため、うまくルーティングできません。

1つ目のパスベースルーティングの概要を振り返ります。ハンドラのHTTPメソッドとパスをリクエストと順に比較する全探索の方針は、ひとまずよさそうでした。しかしながら、文字列の完全一致だと、パスパラメータに対応できないことがわかりました。

正規表現を用いたパスベースルーティングの流れ

そこで、パスパラメータに対応するために、今回は正規表現を利用します。

正規表現を利用するパスベースルーティングの実装2の流れを見ていきます。まずルーティングライブラリは、ハンドラの登録時にパスを正規表現へと変換します。どのように変換するかは、のちのスライドで説明します。

そしてリクエストが来たら、ハンドラのHTTPメソッドとパスをリクエストと順に比較していきます。HTTPメソッドが一致する、かつ、パスの正規表現がマッチしたらハンドラを呼び出すという流れです。

（スライドを指して）パスの正規表現への変換は、以下のように実施していきます。パスとして「/user/{id}」が渡ってきた場合には、右のような正規表現へと変換します。

この正規表現は、「/users/abc」や「/users/123」の文字列にマッチします。正規表現内の「[^/]+」は、「/」以外の文字列の1回以上の繰り返しを意味します。「[/]?」は、パスの末尾に「/」がある場合とない場合に対応するためのものです。正規表現内で利用されているカッコの意味については、のちのスライドで説明するので覚えておいてください。

それでは、正規表現を用いたパスベースルーティングの実装の流れを図で確認していきましょう。まず、登録メソッドをとおしてハンドラを登録します。ハンドラを登録する際に、パスの文字列を正規表現へと変換しておきます。リクエストが来たら、ServeHTTPメソッド経由でルーティングするべきハンドラを決定していきます。

/users/1のパスはハンドラ3の正規表現とマッチするので、無事適切なルーティングが可能になりました。

パスパラメータの取得

ここまで、パスベースルーティングの実装の流れを見てきました。次は、もう1つの仕様の、パスパラメータの取得についてです。

パスパラメータの取得には、先ほど変換した正規表現と、regexpパッケージのFindStringSubmatch関数を利用します。FindStringSubmatch関数は、正規表現内のカッコの中にマッチした値を返してくれます。（スライドを指して）右の図は、FindStringSubmatch関数を利用したコード例となっています。

正規表現をコンパイルし、そののちFindStringSubmatch関数を利用し、正規表現にマッチする文字列を取得します。FindStringSubmatch関数の返り値は、Stringのスライスです。

スライスの1番目の要素は、正規表現にマッチした文字列全体が入ります。2番目の要素以降に、カッコの中の正規表現にマッチした値が入ります。今回の例では、コメント文のように、「/users/abc」と「abc」がスライスに入って、返り値として返ってきます。

FindStringSubmatch関数を利用したパスパラメータ取得の流れを示します。まず、ハンドラの登録時に、パラメータ名を取得しておきます。ここでパラメータ名を取得する理由は、パスを正規表現へと変換する際に、パラメータ名が失われてしまうためです。

リクエストが来たら、FindStringSubmatch関数でパスパラメータの値を取得します。それからパラメータと値の組を、map[string]interface{}に入れ、そのmapをRequest内のcontextへと入れます。

TinyRouterとしてはハンドラ内でパスパラメータを取得できるよう、contextから値を取り出す関数を提供します。

TinyRouterの実装

ここからは、TinyRouterの実装を見ていきたいと思います。時間の都合上、メインとなる部分だけをピックアップして紹介しています。実装の詳細を見たい方は、のちほど共有するリポジトリのURLから確認してみてください。

まずは、TinyRouter構造体です。（スライドを指して）これが一番最初に紹介したTinyRouterのインターフェイスを満たす構造体となります。TinyRouter構造体は、route構造体のスライスをフィールドに持ちます。

route構造体は1つのハンドラを表しています。フィールドにはHTTPメソッドや、パスの正規表現、それからハンドラとなる関数を持ちます。TinyRouter構造体は、登録メソッドを通して、ハンドラをroute構造体へと変換しスライスに追加します。

次にルーティングのメイン部分となる、ServeHTTPメソッドの実装です。ServeHTTPメソッドを通して、リクエストに応じたルーティングを実施します。

（スライドを指して）ServeHTTPメソッドの実装は、右の図のようになります。ServeHTTPメソッドの中でも重要な部分は、赤枠で囲んでいる部分になります。

この部分では、TinyRouter構造体が持つrouteのスライスをfor文で1つずつ取り出し、リクエストにマッチするかをチェックしています。route.matchメソッドの中では、HTTPメソッド、それからパスの正規表現がリクエストとマッチするかをチェックしていきます。

マッチした場合は、route構造体のハンドラ関数を取り出し、for文から抜けます。

for文から抜けたあとはパスパラメータをセットし、ハンドラを呼び出します。

これで、ルーティングライブラリは完成です。

TinyRouterのベンチマーク

次に、このTinyRouterがどの程度の性能なのかを測るために、ベンチマークを実施します。ベンチマークには、testingパッケージのベンチマーク機能を利用しました。今回の比較対象はtinyrouter、gorilla/mux、chiの3つです。

ベンチマークの内容としては、GitHubで利用されている756のエンドポイントをルーティングライブラリへと登録し、リクエストを投げます。

エンドポイントを登録する際、ハンドラとして空の関数をセットします。これは、純粋なルーティングアルゴリズムのパフォーマンスを計測するためです。

GitHubの756のエンドポイントは、GitHubがOSSとして提供している「OpenAPI Spec」から定義を取得しました。

（スライドを指して）ベンチマークの結果は、以下のようになりました。ベンチマークは手元のMacで実施しました。ベンチマーク結果の1列目を見てみると、chiの試行回数が、ほかに比べて1桁程度多いことがわかりました。また、メモリ使用量やメモリアロケーションの回数に、そこまで大きな差がないこともわかりました。

なぜchiの試行回数がここまで多くなるのかを簡単に考察してみました。chiの実装を見てみると、ルーティングアルゴリズムとして基数木を利用していることがわかりました。基数木は、ツリーベースのアルゴリズムとなります。chiは登録されている各パスから基数木を構築していきます。chiはこの基数木を用いて、効率的にルーティングを行っていたのです。

ルーティングは文字列アルゴリズムと深く関係している

まとめです。今回、全探索と正規表現を使って、ルーティングライブラリを作ってみました。ルーティングライブラリを作る中で、いろいろなライブラリの実装を見ましたが、ルーティングは、文字列アルゴリズムと深く関係していることがわかりました。

（スライドを指して）今回作ったライブラリは、以下のURLで公開しています。実装の詳細が気になる方は、ぜひ参照してみてください。

これで私の発表を終わります。ご清聴ありがとうございました。