(Ruby Advent Calendar 2015 6日目)

Ruby 用の高速なルーティングライブラリ Rack::JetRouter 1.0.0 をリリースしました。

• Rubygems: https://rubygems.org/gems/rack-jet_router
• GitHub: https://github.com/kwatch/rack-jet_router

これは Rails より 100 倍速いフレームワーク Keight.rb の Router クラスをもとにしています。Keight.rb の Router クラスはちょっと分かりにくいので、ソースを読むなら Rack::JetRouter のほうをお勧めます。

というわけで、今回もルーティングの話です。意味ないとディスられようが、最悪のクズと罵られようが、しつこくルーティングの高速化について書きます。

ルーティング高速化の概要

ルーティングを高速化については、以前のエントリで概要を説明しました。もう一度説明すると、以下の 3 点です。

• URL パスパラメータを含まないエントリ (ex: /api/hello) は Hash に格納する。
• URL パスパラメータを含むエントリは prefix (ex: /api, /admin) でグループ化する。
• 重い正規表現を避け、軽い正規表現で済ませる。特に名前つきキャプチャは遅いので全力で避ける。

1 点目は、たとえばこんな感じです。URL パスパラメータを含まない場合は O(1) で探索でき、また含む場合の探索数を大きく減らせます。

## こうなっているのを、
urlpaths = [
  ['/',               HomePage],
  ['/api/books',      BooksAPI],
  ['/api/books/:id',  BookAPI],
]
## こうする
fixed_urlpaths = {           # ← O(1) で検索できる
  '/'          => HomePage,
  '/books'     => BooksAPI,
}
variable_urlpaths = [        # ← エントリ数が大きく減る
  ['/api/books/:id',  BookAPI],
]

2 点目は、たとえばこんな感じです。これでエントリ数が増えても遅くなりにくくなります。線形探索より二分探索のほうが速いのと同じですね。

## こうなっているのを、
variable_urlpaths = [
  ['/api/books/:id',      BookAPI],
  ['/api/authors/:id',    AuthorAPI],
  ....,
  ['/admin/books/:id',    AdminBookAPI],
  ['/admin/authors/:id',  AdminAuthorAPI],
  ....,
]
## こうする
variable_urlpaths = [
  ['/api', [
      ['/books/:id',      BookAPI],
      ['/authors/:id',    AuthorAPI],
      ....,
  ]],
  ['/admin', [
      ['/books/:id',      AdminBookAPI],
      ['/authors/:id',    AdminAuthorAPI],
      ....,
  ]],
]

ここまでは難しくないでしょう。

そして 3 点目はソースコードを読まないとわからないと思うので、今から解説します。

高速ルーティングを実現する正規表現

たとえばこんなルーティングの設定があったとして：

urlpath_mapping = [
    ['/api', [
        ['/cats', [
            ['',          'CatsApp#index'],
            ['/new',      'CatsApp#new']
            ['/:id',      'CatsApp#show'],
            ['/:id/edit', 'CatsApp#edit'],
        ]],
        ['/dogs', [
            ['',          'DogsApp#index'],
            ['/new',      'DogsApp#new']
            ['/:id',      'DogsApp#show'],
            ['/:id/edit', 'DogsApp#edit'],
        ]],
    ]],
]

Keight.rb や Rack::JetRouter ではこれを次のように分解・構築します (細部は少し違います)。

fixed_urlpath_dict = {
  '/api/cats'      => 'CatsApp#index',
  '/api/cats/new'  => 'CatsApp#new',
  '/api/dogs'      => 'DogsApp#index',
  '/api/dogs/new'  => 'DogsApp#new',
}
variable_urlpath_list = [
  [%r'\A/api/cats/([^./]+)\z',      ["id"], 'CatsApp#show'],
  [%r'\A/api/cats/([^./]+)/edit\z', ["id"], 'CatsApp#edit'],
  [%r'\A/api/dogs/([^./]+)\z',      ["id"], 'DogsApp#show'],
  [%r'\A/api/dogs/([^./]+)/edit\z', ["id"], 'DogsApp#edit'],
]
urlpath_rexp = Regexp.new('
    \A
    (?:
        /api
            (?:
                /cats
                    (?: [^./]+(\z) | [^./]+/edit(\z) )
            |
                /dogs
                    (?: [^./]+(\z) | [^./]+/edit(\z) )
            )
    )
    \z
'.gsub(/\s+/, ''))

urlpath_rexp の正規表現には、丸カッコによるキャプチャが「(\z)」でしか出てこないことに注目してください。「\z」は文字列の終端を表すので、「(\z)」は「文字列の終端に一致したときだけ空文字列、それ以外は nil」という意味になります。

この urlpath_rexp を使うと、何番目の「(\z)」にマッチしたかがわかります。たとえば：

## URLパスが /api/cats/123 の場合
request_path = '/api/cats/123'
m = urlpath_rexp.match(request_path)
p m.captures   #=> ['', nil, nil, nil]
index = m.captures.find_index('')
p index        #=> 0

## URLパスが /api/cats/123/edit の場合
request_path = '/api/cats/123/edit'
m = urlpath_rexp.match(request_path)
p m.captures   #=> [nil, '', nil, nil]
index = m.captures.find_index('')
p index        #=> 1

これで分かるように、urlpath_rexp の役割は何番目のエントリにマッチしたかを高速に調べることであって、URL パスパラメータの値を取り出すことではありません。そのため、丸カッコによるキャプチャは「(\z)」にのみ使えばよく、これは空文字または nil にしかならないので、「([^./]+)」や「(?<id>[^./]+)」と比べてキャプチャが軽いです。

またインデックスを調べるのも m.captures.find_index('') で済むため、高速です。名前つきキャプチャを使うと、ここを each() などのループで探すことになるので、特に URL パスの数が増えると如実に遅くなります。

あとはこのインデックスを使って variable_urlpath_list を調べれば、URL パスパラメータの値がわかります。たとえば：

rexp, names, target = variable_urlath_list[index]
values = rexp.match(request_path).captures
p names     #=> ["id"]
p values    #=> ["123"]
dict = Hash[names.zip(values)]
p dict      #=>  {"id"=>"123"}

このように、何番目のエントリにマッチしたかを調べるための正規表現 (urlpath_rexp) と、URL パスパラメータの値を取り出すための正規表現 (variable_urlpath_list) を分けたおかげで、ルーティングを高速化できました。

一見すると、正規表現のマッチングが 2 回必要になるため、 1 回で済む正規表現 (Rack::Multiplexer など) と比べて遅くなるように見えます。しかし実際には、重い正規表現 1 回よりも軽い正規表現 2 回のほうが速いという結果になりました。特に、エントリ数が増えても速度があまり落ちないという点が重要です。

なお上で説明した正規表現には、最適化できる余地がまだあります。しかしベンチマークでは効果を確認できなかったため、Keight.rb や Rack:JetRouter では実装していません。

## これは
   (?: [^./]+(\z) | [^./]+/edit(\z) )
## こうできる
   (?: [^./]+  (?: (\z) | /edit(\z) )  )

ルーティングのさらなる高速化

Keight.rb や Rack:JetRouter では、ルーティングにかかる時間は数マイクロ秒で済んでいます。なのでこれ以上高速化する必要は、通常はないでしょう。

それでも高速化したい場合はどのような方法があるでしょうか。手っ取り早いのは、一度検索したものをキャッシュすることです。Keight.rb でのやり方は以前紹介しましたし、同じオプションが Rack::JetRouter でも使えます。

正規表現ライブラリのエンジンを、より高速なものに置き換えるという方法も考えられます。デフォルトの正規表現エンジンを変更するのは難しいでしょうが、機能は限定されるけどより高速な正規表現ライブラリ¹があればそれをルーティングにのみ使う、という方法なら十分現実的です。

究極的には、ルーティング用のパーサやコンパイラを作るのがいちばん高速だと思われます。ルーティングの設定ファイルを読み込んで、C 言語のソースコードを生成してコンパイルする (あるいは JIT コンパイルする) ようなツールがあれば、光の速さで動作することでしょう。Ragel を使えば²できそうな気がしますよね。すでにあってもおかしくないし、だれかチャレンジしませんか？

おわりに

Keight.rb や Rack::JetRouter がどのようにルーティングを高速化しているか、その方法を紹介しました。特に正規表現まわりを高速化する方法を詳しく説明しました。

ところで、今回のようにルーティングを 1 つの正規表現で表す方法は、正規表現を組み立てるときに URL パスのパターンがすべて分かっている必要があります。そのため、「URL にアクセスがあって初めてクラスファイルを読み込む」というような遅延ロードとは相性が悪いです³。1 つの正規表現で表す今回のような方法を使わずに、遅延ロードと相性がいいままでルーティングを高速化できる方法も分かってきたので、いつか紹介したいです。