main-logo

技術登攀録

一覧へ

Webフレームワークのリクエストルーティングを調べてみた

webroutingweb-framework

はじめに

Webアプリを作るとき、多くの人が何気なく使っている「ルーティング機能」。 フレームワークを使用することで簡単にルーティングパスを設定することができ、クライアントからのリクエストを意図したハンドラーにルーティングすることができます。

// express.js
const express = require('express')
const app = express()

app.get('/ping', (req, res) => {
  // handler1
})

app.post('/jobs', (req, res) => {
	// handler2
})
// 省略

// gin
// 省略
func main() {
  r := gin.Default()
  r.GET("/ping", func(c *gin.Context) {
	// handler1
  })
  r.POST("/jobs", func(c *gin.Context) {
	// handler2
  })
  // 省略
}

書き方は多くのフレームワークで似ていますが、フレームワークごとに「どう探して」「どうマッチしているか」の仕組みはかなり違います。
普段は意識しない「その裏側」を、実際のコードやアルゴリズムをもとに探ってみようと思います。

取り扱う探索手法

  • Linear探索
  • Radix Tree探索
  • RegExp探索

リクエストルーティングに必要な処理

リクエストルーティングを行うためには、ざっくりと下記の2つの処理が必要になります。

  • ルーティングパスを登録する
  • ルーティングパスからリクエストパスと一致するものを探索する。

今回はこれらの処理をどのように実現しているのかを見ていきます。 また、実際には/user/[:id]などの動的パスをどのように同一と判定するかといった「判定処理」も探索の中に含まれますが、今回は静的パスに限って見ていこうと思います。

Linear探索

初めは、直感的にわかりやすいLinear探索から見ていきます。

【概要】 Linear探索は最もシンプルな探索方法で、古くからの伝統的なフレームワークで使用されている。 パスをそのままテーブルとして保存し、順番に探索していく

[
  "/",
  "/user",
  "/user/new",
  "/user/create"
]

【Linear探索の処理】

  1. ルートテーブルに順番にパスとハンドラーを登録する。
  2. リクエストが来た時にルートテーブルを先頭からスキャンしていき、一致するものを探す。
  3. 一致するものが見つかったらその時点でスキャンを止めて、登録されているハンドラーを実行する。
  4. 一致するものが見つからなかったら、該当パスなしとしてエラー処理を行う。

【特徴】

  • アルゴリズムがシンプルでわかりやすい。
  • ルート登録はリストの末尾に追加するだけなので計算量はO(1)に近くなる。
    • 正規表現に整形するコストが発生する場合はあるが、それでも追加コストは小さい。
  • 正規表現ベースの一致判定処理を柔軟にサポートしやすい。(ワイルドカードを任意の位置に入れられる。)
  • 探索時の計算量がO(n) (n = ルーティングパス数)であり、登録するルーティングパスに比例して探索時間が増加していく。
  • パスごとに独立して保存するため、共通部分が重複して登録されてしまい大量のルートを登録するとメモリ消費量が大きくなってしまう。
    • /user/newと/user/createはそれぞれ別で登録されるため、/userというのが重複している。

=> ルーティングパス数が少ない、小規模なアプリケーションに向いている

【使用しているフレームワーク】

  • Express.js (Javascript)
  • Gorilla Mux (Go)
  • Flask (Python)
  • FastAPI (Python)

Radix Tree探索

次に現在のモダンであり高速と言われるフレームワークに採用されているRadix Tree探索を見ていきます。

【概要】 Radix Treeは圧縮Trie Treeとも呼ばれ、セグメントごとにパスを分割して、それを木構造として保持する探索手法です。

(root)
 ├─ "/" (ルートパス "/")
 └─ "user"
     ├─ ""      (マッチ "/user")
     ├─ "/new"  (マッチ "/user/new")
     └─ "/create" (マッチ "/user/create")

【Radix Tree探索の処理】

  1. 登録するルーティングパスをセグメントに分割する。
  2. 分割されたセグメントを木構造で登録する。
  3. リクエストパスの文字列を先頭から順に木で探索し、対応する枝を辿っていく。
  4. 一致するものが見つかったらその時点でスキャンを止めて、登録されているハンドラーを実行する。
  5. 一致するものが見つからなかったら、該当パスなしとしてエラー処理を行う。

【特徴】

  • 探索時の計算量はルーティングパスのセグメント数に比例するため、ルート数に影響は受けない。
    • /user/newと/user/createのような共通部分/userの探索は一度だけ行えば、その先の分岐を調べるだけで探索できる。
  • ルートの登録時はパスをセグメントに分割して、既存のセグメントと比較しながらノードの登録をするため、Linear探索のルート登録よりは複雑で時間がかかる。
  • 重複部分を共通化して保持するため、メモリ効率が良い。
  • パスが一意で保存されるため、静的パスと動的パスのバッティングが構造上は起こりにくい。
  • 一般的に100以上のパスがあるとLinear探索との差が見えてきて、1000以上だと目に見えて違いがわかってくると言われます。

=> 速度とメモリ効率のバランスが良いため、高性能なフレームワークでの採用率が高い

【使用しているフレームワーク】

  • Fastify (Javascript)
  • HttpRequest (Go)
  • gin (Go)

RegExp探索

最後にHonoで採用されているRegExp探索(正規表現統合方式)を見ていこうと思います。 honoのRouterについてはこちら

(正直ここはあまり理解できてないので、誤ってたらすみません)

【概要】 RegExp探索は全てのルーティングパスをまとめて一つの正規表現パターンに統合します。


^\/(user(\/(new|create)?)?)?$

この探索ではサポートしないパターンや曖昧な定義を事前に排除しているため、HonoではRadix Tree探索と柔軟に使い分けています。

【RegExp探索の処理】

  1. ルーティングパスをセグメントに分割した上で、すべてのパスを一つの正規表現に統合する。
  2. リクエストパスに対して一度のマッチング判定を行う。
  3. マッチ結果配列を分析して、対応するハンドラを呼び出す。
  4. 一致するものが見つからなかったら、該当パスなしとしてエラー処理を行う。

【特徴】

  • 静的パスの高速判定が可能
    • 静的パスは正規表現マッチが不要なため、辞書探索が可能
  • 巨大な正規表現を利用した一回のマッチ処理でルート選択とパラメータの抽出ができる。
    • 各ルートにユニークなマーカーを埋め込み、どのルートがマッチしたかを正規表現のキャプチャ結果の位置から特定する工夫がされています。
  • 特にルート定義が多い場合に従来の方法よりも性能が上回る可能性がある。
  • 対応できないパターンがあるため、他の手法との並列的な実行が必要になる。
  • 登録処理で巨大な正規表現を構築する必要があるため、ビルド時に時間がかかる。

=> 巨大な正規表現を使った新しい探索手法。今後広まっていくかどうかに注目

まとめ

今回はWebフレームワークのリクエストルーティングについて見てきました。 「このフレームワークは速い」などと謳われている時に、なぜ速いのか？他のフレームワークとどう違うのか？を確認すること技術選択の大きな後押しになると思います。

NestJSのドキュメントを見ると下記のような文言があります。

A fair question is why does Nest use Express as the default HTTP provider? The reason is that Express is widely-used, well-known, and has an enormous set of compatible middleware, which is available to Nest users out-of-the-box. (なぜNestはExpressをデフォルトのHTTPプロバイダーとして使っているのか？その理由は、Expressが広く使われ、よく知られており、互換性のあるミドルウェアの膨大なセットを持っているからである。)

そして、Fastifyの方が高速であり、乗り換えることもできると記載されています。

「一般的に広く使用されていること」と、「機能的に優れていること」は必ずしも一致しないということですかね？ また、全ての場面で優れているものなどないため、自分が作るものには何が適しているのかを考えて選択するということが大切だと感じました。

新しい探索アルゴリズムが出てきたら、またフレームワークの在り方も変わってくるのかなと思うと楽しみですね！