pixiv insideは移転しました！ ≫ https://inside.pixiv.blog/

PHPで高速に動作するURLルーティングを自作してみた

この記事は ピクシブ株式会社 Advent Calendar 2015 13日目の記事です。

qiita.com

こんにちは、おはようございます、こんばんは、エンジニアのneo-nanikakaです。

最近、業務でURLルーティングの処理が必要になりました。 社内の他のPHPプロジェクトでは Teto Routing というライブラリを使っているのを知っていたので、こちらを使ってみることにしました。

見事にURLルーティング処理は実現され、他の処理の実装に入ることができました。

完

っと思っていた時期が私にもありました。

Teto Routingは、実行時間がルーティング数に依存する 実装になっています。 ここでいう実行時間とは、Teto RoutingにリクエストURL文字列を渡してから結果が返ってくるまでの時間のことです。 実際、Teto Routingは表1のような時間がかかります。私の環境なので数値自体にあまり意味はなく、ルーティング数に線形比例して実行時間が増えているのが注目ポイントです。

表1. Teto Routingの実行時間

ルーティング数 実行時間 (ms)
5 0.328
50 2.515
100 4.995

ルーティング数が少ないプロダクトでは十分高速に動作しますが、私が導入しようとしてるプロダクトではルーティング数が多くなるので、次第に高速さが失われていくことになります。 数ミリ秒という世界の話ですが、URLルーティングは全てのリクエストに発生する処理なので、少しでも性能を上げておきたいところです。

どう高速化するかを色々考えたり手を動かしたりした結果、最終的に自分でURLルーティング処理を書く運びとなりました。 この記事では、その結果実装された CommonPrefixTrieRouter *1 の紹介をしようと思います。

そもそもURLルーティングとは

リクエストされたURLに対してどういう処理を実行するか を判定することです。

http://a.example.com/about

というリクエストが来た場合に、例えば 'AboutController'というコントローラー名を返せればURLルーティングが出来ていることになります。

URLには、パラメータが含まれているケースもあります。

http://a.example.com/user/12345

というリクエストが来た場合には、これを実行するコントローラー名の他に、ユーザIDの数字が12345だったという結果も返せればOKです。

CommonPrefixTrieRouterの使い方

1. ルーティングルールを設定ファイルに書く

ルーティングルールは

[httpメソッド, パターン, マッチしたときに返す値(, パラメータの形式)]

としました。例えば、以下のような感じになります。

$conf = [
  ['GET', '/', 'IndexController'],
  ['GET', '/user/:user_id', 'UserController', ['user_id' => CommonPrefixTrieRouter::URL_PARAMETER_TYPE_NUM]],
  ['GET', '/user/:user_id/contents', 'ContentsController', ['user_id' => CommonPrefixTrieRouter::URL_PARAMETER_TYPE_NUM]],
  ['GET', '/search/:query', 'SearchController', ['query' => CommonPrefixTrieRouter::URL_PARAMETER_TYPE_STRING]],
];

パターンの中に :user_id や :query のようにコロンで始まる部分があった場合、それはURLパラメータであることを示します。

パラメータの形式には、正規表現でなくクラス定義された特定のパターンしか指定できないようにしました。 現在は、URL_PARAMETER_TYPE_NUMとURL_PARAMETER_TYPE_STRINGの2種類のみです。

定義 マッチするパターン サンプル
URL_PARAMETER_TYPE_NUM 数字のみから構成される1文字以上の文字列 "12345"
URL_PARAMETER_TYPE_STRING 1文字以上の任意の文字列 "abcdefg", "12345"

以上を踏まえると、上述したルーティングルールだと以下のようなURLルーティング処理がなされます。

REQUEST_URI マッチするパターン
http://a.example.com/ /
http://a.example.com/user/12345 /user/:user_id
http://a.example.com/user/12345/contents /user/:user_id/contents
http://a.example.com/search/ほげほげ /search/:query
http://a.example.com/user なし
http://a.example.com/user/ほげほげ なし

2. ルーティングルールから探索木を構築する

ルールを探索木に変換します。結果だけバッサリ載せると

$conf = [
  ['GET', '/', 'IndexController'],
  ['GET', '/user/:user_id', 'UserController', ['user_id' => CommonPrefixTrieRouter::URL_PARAMETER_TYPE_NUM]],
  ['GET', '/user/:user_id/contents', 'ContentsController', ['user_id' => CommonPrefixTrieRouter::URL_PARAMETER_TYPE_NUM]],
  ['GET', '/search/:query', 'SearchController', ['query' => CommonPrefixTrieRouter::URL_PARAMETER_TYPE_STRING]],
];

これを

$tree = [
  'GET' => [
    `/` => [
      VALUE => 'IndexController',
    ],
    '/user' => [
      TYPE_NUM => [
        PARAM_NAME => 'user_id',
        VALUE => 'UserController',
        '/contents' => [
          VALUE => 'ContentsController',
        ],
      ],
    ],
    '/search' => [
      TYPE_STRING => [
        PARAM_NAME => 'query',
        VALUE => 'SearchController',
      ],
    ],
  ],
];

こういう木構造にします。 大文字になっているキーの場所は、実際にはCommonPrefixTrieRouterが定める特別な文字列となります。 CommonPrefixTrieRouterのみが使用する文字列なので、特に意識する必要はありません。

図示するとこんな感じです。

f:id:devpixiv:20151212002732p:plain

緑色のノードが、ルーティングルールが存在するノードです。返す値がVALUEというキーに入っています。 つまり、VALUEはルーティングルールがマッチするノードにしか存在しません。 TYPE_NUMもしくはTYPE_STRINGというノードは、URLパラメータにマッチするノードです。 これらのノードにはPARAM_NAMEというキーが存在し、URLパラメータの名前が格納されます。

3. 探索木を使ってURLルーティング結果を得る

URLルーティング処理は、リクエストされたURLを先頭から1文字ずつパースし、探索木のノードを遷移して行くことで解析を行います。 リクエストが

GET http://a.example.com/user/12345/contents

だった場合を考えてみましょう。

初期状態は、探索木の根にいます。 まず、HTTPメソッドがGETなので、GETのノードへ遷移します。

f:id:devpixiv:20151212003442p:plain

Routerは、/user までパースします。現在のノードの下には、/userというノードが存在するので、そちらに状態を遷移します。

f:id:devpixiv:20151212003544p:plain

次に、 /12345 までパースします。現在のノードの下に、 /12345 というノードは存在しません。 代わりに、TYPE_NUMというノードが存在して/12345はそれにマッチするのでそちらに状態を遷移することができます。

f:id:devpixiv:20151212003634p:plain

続いて、/contentsまでパースします。/contentsというノードが存在するので、そちらに状態が遷移します。

f:id:devpixiv:20151212003656p:plain

これでリクエストされたURLを最後までパースし終わりました。 パースが終了した時点でのノードにVALUEキーがあればその値を結果として返します。 今回は、VALUEキーが存在するのでContentsControllerを返します。 VALUEキーが無い場合はどのルールにもマッチしなかったということなので、nullを返します。 また、パースの途中で遷移することができなくなる場合もあります。その場合も同様に、マッチするルールが無かったことを意味するのでnullを返します。

CommonPrefixTrieRouterの特徴

実行時間がルーティング数に依存しない

そもそもルーティングを自作したのはこれを実現するためでした。 探索木を使った探索の実行時間はルーティング数に依存せず、探索木の高さに依存します。 探索木の高さは、ルーティングルールによって決まるので入力依存だとも言えるのですが、 URLのパス構造を考えると、ルーティング数が増大しても木の高さはかなり小さく押さえられることが期待できます。

一方、Teto Routingでは、ルーティングルールをforeachで回して、1つずつpreg_matchするという実装になっています。 ルーティング数が増大すると、preg_matchする平均回数も増えるため、実行時間が遅くなっていたのです。

さらに付け加えると、ルーティング数に依存しないのは実行時間だけです。 探索木の構築時間はガッツリルーティング数に線形比例します。 構築時間が無視できないコストになってきた場合、構築した探索木をキャッシュすることで解消できます。 なぜなら、ルーティングルールに変更が入らない限り、1度作った探索木は使いまわすことができるからです。

マッチしないURLを与えても実行時間が遅くならない

マッチしないURLを探索木に与えると、途中で遷移できなくなるか、パースを終えたときのノードの状態でマッチしないことを判断できます。 どちらにせよ、マッチするURLと同等以下の時間で結果を返すことができます。

URLパラメータに正規表現を利用できない

URLルーティングのライブラリを読むと、正規表現ベースのルーティングルールの記述ができて当然のようです。 CommonPrefixTrieRouterでは以下の2点から、正規表現をサポートしないことを試みました。

1つ目に、私の現状ではURLにおいて「数字が並んだ文字列」と「それ以外の文字列」が区別できれば十分そうだったということです。 2パターンしか無いなら、フリーダムな正規表現をサポートするより、Routerの定数として指定できた方が使いやすくなるのではないかと考えました。

2つ目に、preg_matchを使わない実装にできるということです。 可能な限り、URLルーティング処理で使用されることの多いpreg_matchの使用回数を減らしたいです。 正規表現のサポートをバッサリ切ることで、回数を0にできました。

今後、URLパラメータに指定できる種類が2つでは足りなくて辛くなってきた場合は、大人しくパターンを増やすか、正規表現をサポートするか、他のライブラリに乗り換えるかを検討します。

実行時間計測

CommonPrefixTrieRouterの実行時間の計測結果です。

表2. CommonPrefixTrieRouterの実行時間

ルーティング数 マッチするURLを与えたか 実行時間 (ms) 構築時間+実行時間(ms)
23 yes 0.1164 0.8625
23 no 0.1248 0.9383
2300 yes 0.0823 78.5526
2300 no 0.0867 77.8185

ルーティング数を100倍にしても実行時間は横ばいで、性能が落ちません。 構築時間はルーティング数が2300個もあるとさすがに重いようです。

最後に

本記事では、ルーティング数が増加しても性能が落ちないRouterが欲しくて自作に至った経緯と、その実装について書きました。 「リクエストURLを入力にして値を返す」と、言葉にすると単純な処理ですが、 いざ自作しようとすると、探索アルゴリズムをどうするか、正規表現をどう扱うか、など 悩みポイントは多かったです。 最終的には、URLルーティング処理について理解が深まり、望みのRouterを手に入れることができました。 CommonPrefixTrieRouterは早速プロダクトに導入しています。愛着が湧いているのでテンションが上がります。

また、CommonPrefixTrieRouterのソースコードをこっそり公開しておきます。 実装が気になる方などは覗いてみてください。

ピクシブ株式会社では、既存の処理やライブラリの性能を比較検討し、必要になれば実装方針を考え始めるような、試行錯誤が好きなエンジニアを歓迎しています！

recruit.pixiv.net

明日は、@bash0C7さんのターンです。ご期待ください！

*1:データ構造が共通接頭字がノードになったTrie木構造だったからという安易な理由で命名してしまいました。長くて呼びづらいですね