URLルーティングをつくる　エピソード1

bmf-san アルゴリズムとデータ構造
#HTTP#URLルーティング#木構造#router

URLルーティングをつくる　エピソード1

概要

以前、Reactで非常に軟弱なルーティング（cf. ReactとHistory APIを使ってrouterを自作する）を作ったが、改めてそこそこにちゃんとしたルーティングを自作したいと思い、挑戦することにした。 きっかけは、最近触っているGolangだ。 Golangでは標準ライブラリを駆使することでアプリーケーションをうすーく実装できるようだが、ルーティング周りは標準ライブラリがパワー不足なのものあって、外部のライブラリに依存するケースが多いらしい。 そんなこともあってルーティングを自作できるようになるとGolangでもそれ以外でもルーティングを自前で用意できて世界が広がる気がしたので重い腰を上げてやってみることにした。

URLルーティングとはそもそも何をするのか？

リクエストされるURLに対して、実行したい処理は何か判定させるもの。 必要に応じて、パスパラメータやクエリパラーメータのデータを処理の実行時に扱えるようにする。

URLルーティングの実装パターン

大まかに2パターン。

  • 正規表現でURLのマッチングを行うパターン
  • 木構造を用いて文字列探索を行うパターン

ルーティングがアプリケーションの実行速度に与える影響の割合はそこまでないかもしれないが、なるべく速いに越したことはないはず。 言語問わずメモリ使用量、計算量の最適化されたアルゴリズムで実装すべし。

今回は木構造で実装するパターンを選択する。 パフォーマンスを測定したわけではないが、正規表現よりも計算量が最適か木構造のアルゴリズムを用いるほうがパフォーマンス的にはよろしい気がするので、木構造にする。 実際、木構造で実装されているライブラリは多い。

木構造とは？

グラフ理論という数学の分野で定義されている木の構造を持つデータ構造のこと。 グラフ理論で定義されている木とは、複数の点（nodeまたはvertex）と複数の辺（edge）で構成されたグラフのことである。

ノードの性質や木の高さなどによって色々な種類の木構造があるが、ここでは割愛。

木構造の例

URLルーティングをつくる

何を木構造として扱うか？ これはもちろん、ルート定義のリストを木構造として扱う。

実装の流れをざっくり説明すると、ルート定義と現在のURL（パス）をインプットとして与えられたときに、 ルート定義から木構造を生成し、現在のURL（パス）をターゲットとして木構造を探索し、マッチしたデータを返すというだけ。

木構造を扱う際はノードの追加や削除等の処理も実装する場合があるが、URLルーティングの場合はとりあえず不要なので実装しない。

データ構造を決める

ルーティング定義のDSLを先に決める。 多くのライブラリではシンプルなDSLが提供されているが、今回は複数階層あるちょっと複雑なDSLを定義する。

先程ルート定義から木構造を生成すると書いたが、ルート定義そのものを最初から木構造となるような形で定義することにする。 なぜこのような形をとったかというと単純に木構造を生成するアルゴリズムを書くのが面倒そうだったからであるが、逆に考えてみるとむしろ余計なアルゴリズムが減ってパーフォマンス的に良いではという気がしているがいかに・・ さほどわかりにくくないルート定義だと思うが、一般的なルーティングライブラリのDSLがこのようになっていないのは何か理由があるはずだとは思っている。

木構造の終端ノードとなる部分（葉）がちょうどHTTPメソッドになる。

木構造とは別にHTTPメソッドのリストを用意しておく。 Golangだとnet/httpに最初から定義されていて楽ですね。今回はPHPでやりますが・・

実装

インプットして与えられる現在のURL（パス）を木構造の探索の際に使いやすいように配列に加工する関数とその配列とルート定義の配列を引数としてマッチングしたパスのデータを返す関数の2つを実装する。 なお今回はクエリパラーメータは特に考慮していない。

実装方針として、他の言語への移植性を考慮し、ビルトイン関数の使用を極力避けて実装する。

実装途中というわけでエピソード1はこれにて終幕。　

所感

最初からパトリシア木とかなんとか木とかからやろうとすると大やけどする。 参考になりそうな実装も色々見てみたが、一つ一つを理解するのは中々ハードなので、まずはアルゴリズムのイメージを掴むことと考えながら手を動かすことから始めてみたが、数学的素養が乏しいと辛いところはある。 実装途中ではあるが、割とゴールが見えるような気がしないでもない。 が、こんな感じで実運用に使えそうなベースまで持っていけるか自信はない。

追記

Makuake LT Party（社内LT大会）にてLTをした。

speaker-deck - URLルーティングをつくるエピソード１

参考