Padrino Frameworkのルーターを開発した話

正直この手の技術解説記事を書くのはあまり得意ではないので避けていたところがありますが、
自分以外の人にも深く理解してもらいツッコミを入れてもらえる環境にしておくことがリスクヘッジになるのではないかと考えたために書くことにしました。
ちなみに、このルーターはgithubのmasterブランチには既に取り込まれています。
また、ここでの新しいルーターとは、pendragonを指すことにします。

なぜ新しいルーターなのか

そもそもの発端はこのイシューで、http_routerをドロップして新しいルーターを開発しようという動きは私が開発に参加するより以前からあったようです。
大まかな理由は以前書いた「Padrino Frameworkの最新事情と今後について」にある通りですが、補足としていくつか説明します。

http_routerの仕組み

http_routerは一つのルートを追加する毎に、100行から150行ほどのコードを生成します。
それらを連結し、def call(env); #{生成されたコード} endとして展開したものをinstance_evalすることがhttp_routerにおけるコンパイルであり、
http_router由来のバグも大抵、その生成されるコード群に集約されます。
大方それらのバグはモンキーパッチによって修正しましたが、まだどんなしぶといバグが残ってるか知れませんし、個人的に必要だと思われる機能が実装されていなかったりします。
例えば以下のようなコードです。

Sample::App.controller :foo do
  get :index do
    url(:foo, :splatter, splat: "hello") # "/foo/hello"になってほしいが"/foo/?splat=hello"になる
  end

  get :splatter, map: "/foo/*" do
  end
end

また、実際のソースコードは本当に読み難くて、さながら魔境のようです。長らくバグが放置されるのも納得といった様相を呈しています。
そんなわけで、新しいルーターはhttp_routerよりもメンテナンス性に優れ、尚かつhttp_routerと同等以上のパフォーマンスを発揮することを目標に開発しました。

高速なルーターを開発するために

Mustermannというライブラリを使用して、素直にルーターを作ること自体は然程大変ではありません。
また、padrinoが保有するテスト群を全てパスする作業はなかなか大変でしたが、特筆すべき内容はないのでこの点については省きます。
ちなみに、初期実装はここに書かれている高速なルーターではなく、あくまで一般的な線形探索で実装したものでした。

高速なルーターを実現するために参考にしたのはrack-multiplexerというgemで、正規表現を連結してマッチング回数を減らすというやり方には感銘を受けました。
ただし、この方法ではルートを一つしか取り出せないため、このアプローチを採用するにしても、Padrinoに組み込むには複数個のルートを取り出せるようにするというのが必要条件でした。
これについては無い頭をひねって悩みましたが、以下の方法をとることにしました。

ルート個分の連結された正規表現を、先頭から一つずつ減らしながら作成する。
マッチング時には、オフセットを持っておき、ルートの探索は可能であればジャンプしながら行う。
この方法では、マッチング回数を(条件にマッチするルートの個数+1)回に抑えることができる。
なかなか言語化するのが難しいので、実際にコードを書いて説明してみます。

# 重複する正規表現/fooを含む正規表現群を用意します。
routes = []
routes << /\/foo/
routes << /\/bar/
routes << /\/baz/
routes << /\/foo/

# 目的のパスは"/foo"ということにします。
path = "/foo"

一般的なアプローチですと、selectを使った探索が挙げられるでしょう。
マッチング回数の確認のため、p("called"); を実行した上で検証するのが以下のコードです。

routes.select{|regexp| p("called"); regexp === path } #=> [/\/foo/, /\/foo/] 
# calledは4回表示されました。

次に、私が考えたアプローチを使ってみます。
少し長いです。

class MultipleRegexps
  # 各ルート用即席クラス
  class Route < Struct.new(:regexp, :index)
  end

  # 正規表現群を受け取り、Routeのインスタンス群に変換する。
  def initialize(regexps)
    @routes = regexps.map.with_index{|regexp, index| Route.new(regexp, index) }
  end

  # 受け取った正規表現をもとに、新たな正規表現を生成し、コンパイルする。
  def compile!
    @regexps = @routes.map {|route| /(?<_#{route.index}>#{route.regexp})/ }
    @regexps = compile(@regexps)
  end

  # 正規表現群を連結して保存する。
  # 保存後は先頭の正規表現を取り除いた上で繰り返す。
  def compile(regexps, paths = [])
    return paths if regexps.length.zero?
    paths << Regexp.union(regexps)
    regexps.shift
    compile(regexps, paths)
  end

  # 作られた正規表現データをもとにマッチングを行う。
  def match(path)
    offset = 0
    loop.with_object([]) do |_, candidacies|
      p "called"
      return candidacies unless @regexps[offset] === path
      route = @routes[offset..-1].detect{|route| Regexp.last_match["_#{route.index}"] }
      candidacies << route
      offset = route.index + 1
    end
  end
end

regexps = MultipleRegexps.new(routes)
regexps.compile!
regexps.match("/foo") #=> [/\/foo/, /\/foo/] 二つ取り出せます。
# calledは3回表示されました。

まあ、この程度の差だとあまり嬉しさがないんですが、登録されるルートの個数が増えるにつれて嬉しさが増してくるのではと思います。
その後、このアプローチを組み込んだものを使ってベンチマークを取った結果、もともとの線形的に探索するものよりも、そしてhttp_routerよりも高速であるという結果が出ました。
厳密に様々な角度から検証すると、ルートの個数が少ない段階や、あまり複雑なルーティングを行わない場合などではhttp_routerと同等程度くらいにまで落ち込みますが、それでも普通にやるよりは大分速い。
私は自分には非常に甘い人間なので、この時点で満足したというわけです。

ちなみに

お気づきの方もいるかと思いますが、高速化の余地はまだ残されています。
sinatraやpadrinoでは複数個のルートを取り出さなければならないといっても、passを使わないケースでは不要となります。
そこで、MultipleRegexps#matchのループ中にyieldするように変更することで、無駄なマッチングをせずに探索を終了させることができます。

没案

試した結果没にしたアイデアがあります。

線形探索ホントに駄目か法

Mustermannのマッチングが遅いので、Mustermannが生成する正規表現を連結せずに持っておき、線形的に探索する方法。
初期実装よりは高速でしたが、前述の方法よりは遅かったので没にしました。

他にも、連結した正規表現に対する一回のマッチングで複数個のルートの取り出しを試みましたが、有用なアプローチといえるものはまだありません。

Mustermann19を作った件

Mustermannは便利ですが、公式のgemはruby2.0以降しかサポートしていないため、mustermann19というgemをリリースしました。
これはRuby1.9でも動きます。
Padrinoではこれを使用しています。

おわりに

文章にするとすんなり書けたように読めますが、実際にはここに至るまで、何度もベンチマークを取って検証しています。
それなりに大変でしたが、当初の目標を達成できたということについては満足しています。
とはいえ、まだまだやれるだろうという思いがないわけではないので、今後も高速なルーティングの実現については色々と試行錯誤を続けていくつもりです。
Padrinoでは、新しいルーターに対して積極的にコミットしていただける方を募集しています(もちろんそれ以外についても)。
我こそはという方は、New pull requestというボタンを押してみましょう。

この文章は2014年11月13日現在のルーターの実装としては正しいですが、最新の実装はこれとは異なる場合があります。