こんにちは、エンジニアの籏野です。
最近、弊社で新たに開発されるアプリケーションではHonoを積極的に利用しています。
Honoといえば高速であることを大きな特徴として掲げており、検索の速度を武器として戦ってきた弊社とも親和性が高いと感じています。
そんなHonoの「速さ」を支える一つの要素としてRouterがあります。
Routerの役割はリクエストパスやメソッドを元に、適切なハンドラーを選択し実行することです。
Honoでは速さ・軽さそれぞれの特徴を持ったRouterを提供しており、実装するアプリやアプリを実行する環境に合わせて最適なRouterを選択可能としています。
今回はそれぞれのRouterがどのようにルーティング先を決定しているのかが気になったため、実際にHonoのソースコードを読んでまとめてみました。
調査対象のRouter
今回調査したのは以下のRouterです。
- TrieRouter
- RegExpRouter
- PreparedRegExpRouter
- LinearRouter
- PatternRouter
- SmartRouter
TrieRouter
Trie木と呼ばれるデータ構造を用いたルーターです。
パスを / で分割し、各セグメントをキーとしてツリー構造を構築します。
以下がTrie木でハンドラーの情報を保持するイメージ図です。
(root)
├─ "/" ──────── [GET: handler1]
│
├─ "users" ──── [GET: handler2, POST: handler4]
│ │
│ └─ ":id" ─ [GET: handler3]
│
└─ "health" ── [ALL: handler5]
Trie木では、パスのセグメントごとにツリーをたどるだけで目的のハンドラーに到達できるため、探索にかかる時間はルート数ではなくパスの深さ（セグメント数）に依存します。
つまり、ルートが100個あっても1000個あっても、/users/:id の探索は常に2ステップで済み、高速なルーティングを実現しています。
また全てのルートパターンをサポートしていることも特徴として挙げられ、後述するSmartRouterを用いて他のRouterが使えない場合のフォールバック先としても用いられています。
RegExpRouter
登録されたパスパターンを「ひとつの巨大な正規表現」にすることで、1回のマッチング処理で対応するハンドラーを取得することができます。
「ひとつの巨大な正規表現」は登録されたルート定義のうち動的パスを元にして作成されています。
静的パスについては辞書として保持されており、こちらも1回の探索でハンドラーの取得が可能になっています。
動的パスを用いた「ひとつの巨大な正規表現」は以下のような手順で生成されます。
まず登録されたすべての動的パスはTrie木に変換された後に以下のような文字列に変換されます。
/(?:posts/([^/]+)@1/comments#1|users/([^/]+)@0#0)
^^ ^^ ^^ ^^
│ │ │ └─ 「ルート0はここ」マーカー
│ │ └─ 「パラメータ0はここ」マーカー
│ └─ 「ルート1はここ」マーカー
└─ 「パラメータ1はここ」マーカー
@1や#1という文字列によって、パスパラメーターの位置や1つのパスを表す正規表現の終端が表現されていることが特徴です。
次に文字列に埋め込まれた「マーカー」を正規表現に変換しつつ、マーカーが出現する順番に応じて配列内に情報を持ちます。
生成される正規表現は以下のようになります。
^/(?:posts/([^/]+)/comments$()|users/([^/]+)$())
一方、ハンドラーの配列は以下のような形で保持しており、マーカーの出現順序と対応する位置にハンドラーが置かれています。
handlerMap = [
undefined,
undefined,
[[handler_posts, { id: 1 }]], // index: 2
undefined,
[[handler_users, { id: 3 }]], // index: 4
];
ここからどのようにリクエストパスとハンドラーのマッチングが行われるのでしょうか。
例えば /users/42 に対してリクエストされた場合を考えてみます。
/users/42に対して、正規表現との照合を行うと以下のような結果が取得できます。
[
'/users/42',
undefined,
undefined,
'42',
'', // ← 空文字
...
]
このうち空文字の位置を取得すると4になっています。
これを元にhandlerMapの4の位置を見てみると、目的のハンドラーであるhandler_usersを取得できることがわかります。
また { id: 3 }というのは「idというパスパラメーターが正規表現の結果の3の位置にある」ことを示しており42という値を取得することができました。
このようにRegExpRouter は作成した巨大な正規表現とリクエストパスを照合し、照合結果の空文字の位置から効率的に対応するハンドラーを取得することを可能にしているのです。
PreparedRegExpRouter
Hono 作者であるyusukebeさんの記事 もぜひ参考にしてほしいのですが、RegExpRouterは初期化の遅さとバンドルサイズが大きくなるという2つの弱点を持っていました。
これを解消するために生まれたのが PreparedRegExpRouter です。
PreparedRegExpRouterは巨大な正規表現相当の情報を持った値を事前に生成することで、Trie木等を用いた正規表現の生成を省略することを可能にしています。
受け取る情報は以下のような形式になっています。
[
// matchers
{
ALL: [
/^\/(?:posts\/([^/]+)\/comments$()|users\/([^/]+)$())/, // 正規表現（RegExpRouterと同じ）
[0, 0, [], 0, []], // handlerMap（ハンドラーは空の状態。0はハンドラーが配置されない位置、[]はadd時にハンドラーが差し込まれる位置）
{}, // 静的パス
],
},
// relocateMap
{
"/posts/:id/comments": [[[2], { id: 1 }]], // handlerMap[2]に差し込む, idはCG(1)
"/users/:id": [[[4], { id: 3 }]], // handlerMap[4]に差し込む, idはCG(3)
},
];
上記のような情報をあらかじめ生成して PreparedRegExpRouter に渡せば初期化にかかる時間を大きく短縮できます。
PreparedRegExpRouterを利用するには、登録されたすべてのリクエストパス定義を抽出し、上記の形式に変換したうえでRouterをPreparedRegExpRouterに切り替える必要があります。
この作業を自動で行ってくれるのが hono optimizeになっていますので、興味のある方は先の記事を参照してください。
LinearRouter
LinearRouterは登録されたルートのパス定義に対して「ほぼ何も処理をしない」というのが大きな特徴です。
ルートが登録された順に配列上でメソッド/パス/ハンドラーの情報を保持しており、マッチングの際には配列内の要素を順番に探索して、メソッド・パスが一致した場合にハンドラーにリクエストを流し込みます。
#routes = [
["GET", "/", handler1],
["GET", "/users", handler2],
["GET", "/users/:id", handler3],
["POST", "/users", handler4],
["ALL", "/health", handler5],
...
]
他のRouterと異なりルート定義追加時の処理がほぼないため、初期化の速さに特化しており、リクエストのたびにアプリが初期化される場合に向いています。
PatternRouter
PatternRouterはhono最小のルーターです。
LinearRouterがリクエストパスとのマッチングロジックを自前実装しているのに対し、PatternRouter はルート登録の際にパス情報を正規表現に変換しており、マッチングロジックを正規表現エンジンに一任することでバンドルサイズの圧縮を行っています。
登録されたルートは以下のように保持されます。
#routes = [
[/^\/$/, "GET", handler1],
[/^\/users\/?$/, "GET", handler2],
[/^\/users\/(?<id>[^/]+)\/?$/, "GET", handler3],
[/^\/users\/?$/, "POST", handler4],
[/^\/health\/?$/, "ALL", handler5],
...
]
SmartRouter
SmartRouterは複数のrouterから適切なルーターを選択するルーターです。
あらかじめ複数のルーターを登録し、登録されたルートすべてに適用可能なルーターが選ばれることになります。
初回の呼び出し時:
候補: [RegExpRouter, TrieRouter]
RegExpRouter に全ルートを add → match
├─ 成功 → RegExpRouter に決定（以降すべてのリクエストで使用）
└─ エラー
↓
TrieRouter に全ルートを add → match
├─ 成功 → TrieRouter に決定（以降すべてのリクエストで使用）
└─ エラー
↓
Fatal error
まとめ
それぞれのルーターの特徴を簡潔にまとめると以下のようになるかと思います。
| ルーター | 優れている点 |
|---|---|
| TrieRouter | 全ルートパターンをサポートかつ高速 |
| RegExpRouter | マッチング速度が最速 |
| PreparedRegExpRouter | RegExpRouter × 初期化コストとバンドルサイズ縮小 |
| LinearRouter | 初期化が高速 |
| PatternRouter | 最小サイズ |
| SmartRouter | ルーターの特性を意識せずに最良のパフォーマンスを得られる |
今回の記事の執筆にあたり、改めてHonoの速さへのこだわりの一端を感じることができました。
今後のHonoのさらなる発展にも期待が高まるばかりです！
この記事を書いた人
籏野 拓
2018年新卒入社
Discussion