Webアプリケーションにおけるパスルーティングアルゴリズムの解剖

@ PyCon JP 2025

Transcript

1. Webアプリケーションにおけるパスルーティン グアルゴリズムの解剖 hkws / 2025.09.27 PyCon JP 2025
2. ⾃⼰紹介 • hkws（かわせ）と⾔います • 通信系の会社でWebアプリケーション開発 を10年くらいやってます • PyCon JP 2024/2025の運営メンバーでもあ ります
3. 最優先⽬標: 普段当たり前に使っている機能の裏側を探求する楽しさを知り、⾃分 でもやってみようかなと思ってもらう 本トークのゴール できたらいいな: • DjangoやFastAPIが、内部でどのようにURLリクエストを解決しているかの 基本的な仕組みを理解する • 正規表現によるマッチングの基本的な仕組みと実装を理解する • Trie Tree/Radix Treeというデータ構造とアルゴリズムについて知る • アルゴリズムによって、私たちが慣れ親しんだ機能の実⾏速度が変わること を理解する
4. Webアプリケーションフレームワークにおける パスルーティング
5. Webフレームワークにおけるパスルーティング ユーザー GET /users/123 {“user_id”: 123}
6. 皆さんがフレームワーク開発者だとして、 リクエストパスから実⾏する処理を特定する ために、どのような実装をしますか？
7. Django: パス登録 Djangoはアプリケーション起動時にurlpatternsをロード。その際、path()関数は RoutePatternインスタンスを⽣成し、パスを正規表現に変換する
8. Django: パス登録 ⼊⼒としてpathをとり、対応する正 規表現と、抽出した値に対する Converterのmapを返す （例）'foo/int:pk' -> '^foo\/(?P[0-9]+)', {'pk':<django.urls.converters.IntConverter>}.
9. Djangoでのパスルーティング アプリ起動時にpath()の登録ルートを正規表現に変換し、URLResolverを構築。 resolve()で登録されたルートを順にチェック。-> 線形探索 + 正規表現マッチング
10. FastAPI / Starletteのパス登録 アプリ起動時にrouting.APIRouterのadd_api_routeを実⾏し、APIRouteをroutes 属性にappend。APIRouteの初期化時、get_dependantでhandlerのシグネチャ から必要に応じてPydanticのModelFieldを作成して返す
11. FastAPI / Starletteのパスルーティング パスパラメータ（{username}など）を事前に正規表現に変換しておく。Routerク ラスがすべてのルートを順番にマッチング。 -> 線形探索 + 正規表現マッチング
12. Litestarでのパス登録 Litestarは基数⽊（Radix Tree）とい うデータ構造を採⽤。パスをセグメ ントに分割し、⽊構造で管理する。
13. Litestarでのパスルーティング Routerに事前にTrie Treeという特別な⽊構造でパスを保持しておき、Rootから順 にたどる -> Trie Treeによるマッチング
14. ⼆つのパスルーティングアルゴリズム 線形探索＋正規表現マッチング Trie Treeによるマッチング
15. ⼆つのアルゴリズムを解剖する
16. アプローチ1：線形探索+正規表現
17. DjangoやFastAPI(Starlette)のルートの準備 • ルートのパターンとハンドラーのペアのリストを記述しておく • アプリケーション起動時にこれを読み込み、パターンを正規表現で記述して いない場合（例：<int:question_id>/results/ など）は、正規表現に変換
18. 正規表現マッチングをリストの先頭から実⾏ 線形探索 + 正規表現によるパスルーティング 処理の流れ： 1. リストの先頭から順番にパター ンをチェック 2. 各パターンで正規表現マッチン グを実⾏ 3. マッチしたら即座に返す（早期 リターン） 4. 全てチェックしてもマッチしな ければ404
19. Pythonにおける正規表現実装の概要
20. 正規表現エンジンの実装⽅針には⼤きく⼆種類あり、PythonはVM型を採⽤ 正規表現によるマッチングの実装 • DFA型 ◦ 正規表現から有限オートマト ン（NFA/DFA）を構成 ◦ DFAの遷移をシミュレート • VM型 ◦ 仮想マシン（VM）上で正規 表現を解釈‧実⾏ ◦ バックトラックを使ったマッ チング
21. VM型エンジン 正規表現をコンパイラが バイトコードに変換 バイトコードとマッチ対 象⽂字列を⼊⼒として仮 想マシン（VM）を実⾏、 マッチ結果を返却する
22. 仮想マシンの構造 • PC (Program Counter): 次に実 ⾏するバイトコードの位置 • SP (String Pointer): 次にマッチ を実⾏する⽂字の位置 • スタック: コンテキスト（ここで はマッチの実⾏状態のこと）を 保持しておく領域 • マッチ実⾏部: PCからバイト コードを取得し解釈して⼊⼒⽂ 字列とのマッチを実⾏
23. • 解の可能性がある候補を順に試し、解ではないと分かったら解の可能性があ る候補まで戻って次の候補を試す（バックトラック） VM型正規表現エンジンによる解の探索 例: 1. /api/v → OK 2. [12] → スタックに状態をpushし、分岐⼀つ⽬の"1" とのマッチを検証 → OK 3. /users/ → OK 4. (\d+|[a-z]+) → スタックに状態をpushし、分岐⼀つ⽬の"\d+" とのマッチを検証 → 失敗 5. 4でpushした状態を復元し、 分岐⼆つ⽬の[a-z]+ を試す → "john" にマッチ 6. /(profile|settings)/ → スタックに状態をpushし、分岐⼀つ⽬の"profile" とのマッチを検証 → OK 7. /$ → OK
24. バックトラックのコスト • 最悪ケース：指数的な時間計算量 O(c^L) (c > 1) • 例：(a*)*b のようなパターンで爆発的増加 • パターンによってコストが⼤きく変わる • ReDoS（正規表現DoS）攻撃の原因 ◦ 悪意のある⼊⼒により正規表現エンジンが⻑時間動作し続ける攻撃 ◦ 例：パターン (a*)*b に対して "aaaaaaa..." のような⽂字列を与えると、バックトラックが 指数的に増加 ◦ 2016年にはStackoverflowが、2019年にはCloudflareがこの攻撃により⼀定時間サービスを 停⽌ ◦ 詳しい解説：第74回 正規表現の脆弱性「ReDoS」徹底解説 〜原理と対策から、Perlでの最適 化まで（1）
25. 線形探索+正規表現マッチングのコスト • 典型的なパターン（例：/users/[a-z]+/profile）ならO(NL) • N: ルート数 • L: パス⻑ • 最悪ケースなら指数時間にもなりうる • (a+)+$ のような繰り返しのネストが有名な例 ◦ regex101.com のRegex Debuggerを使うとイメージしやすいかも • ReDoS（正規表現DoS）攻撃の原因 ◦ 悪意のある⼊⼒により正規表現エンジンを⻑時間動作させ続ける攻撃 ◦ 2016年にはStackoverflowが、2019年にはCloudflareがこの攻撃により⼀定時間ダウン
26. 皆さんなら、正規表現のマッチングを どのように実装しますか？（特に分岐）
27. CPythonにおける正規表現の実装
28. Pythonにおけるmatch関数の実装 PythonではC⾔語で仮想マシンを実装。match関数で、正規表現のバイトコード を⼊⼒⽂字列上でインタプリタ的に実⾏する。
29. Pythonにおけるmatch関数の全体像 LOCAL(Py_ssize_t) SRE(match)(**.){ ** 初期化処理 */ entrance: ** 最適化ヘッダ(INFO)に応じた処理 */ dispatch: switch (*pattern*+) { case SRE_OP_LITERAL: ** 文字比較処理 成功時: goto dispatch */ /*. 失敗時: goto exit */ case SRE_OP_BRANCH: ** 分岐処理 分岐ごとにDO_JUMPする */ /*. 成功時: goto exit */ /*. 失敗時: goto exit */ ** ほか大量の opcode **. */ } exit: ** コンテキストをpopし、一つ前のコンテキストをロード */ goto jumplabel; } #define DO_JUMPX(jumpvalue, jumplabel, nextpattern, toplevel_) \ ** PC, SPの現在の状態を保存 */ \ ** 新しいコンテキストを作りスタックへpush */ \ ** match関数のメインループの先頭へ */ \ goto entrance; \ ** 新しいコンテキストでの評価後ここに戻る */ \ jumplabel: \ ** 保存したPC, SPを復元 */ \
30. Pythonにおけるmatch関数の実装 pattern(実⾏するバイトコード)に応じてswitchで分岐し、バイトコードに対応す る処理を実⾏。
31. Pythonにおけるmatch関数の実装 分岐する場合は、DO_JUMPで⼀つ⽬の分岐を評価し、失敗したら次の分岐へ
32. Pythonにおけるmatch関数の実装 再帰的な呼び出しはDO_JUMPXでマクロで実施。呼び出しコンテキストを⽤意し てgotoで⾶ぶ
33. Pythonにおけるmatch関数の実装 match関数の末尾のexitラベル以下にて復帰処理を実装。スタックからコンテキ ストをポップし、ジャンプの発⽣元に応じて復帰先を振り分けている。
34. Pythonにおけるmatch関数の全体像 LOCAL(Py_ssize_t) SRE(match)(**.){ ** 初期化処理 */ entrance: ** 最適化ヘッダ(INFO)に応じた処理 */ dispatch: switch (*pattern*+) { case SRE_OP_LITERAL: ** 文字比較処理 成功時: goto dispatch */ /*. 失敗時: goto exit */ case SRE_OP_BRANCH: ** 分岐処理 分岐ごとにDO_JUMPする */ /*. 成功時: goto exit */ /*. 失敗時: goto exit */ ** ほか大量の opcode **. */ } exit: ** コンテキストをpopし、一つ前のコンテキストをロード */ goto jumplabel; } #define DO_JUMPX(jumpvalue, jumplabel, nextpattern, toplevel_) \ ** PC, SPの現在の状態を保存 */ \ ** 新しいコンテキストを作りスタックへpush */ \ ** match関数のメインループの先頭へ */ \ goto entrance; \ ** 新しいコンテキストでの評価後ここに戻る */ \ jumplabel: \ ** 保存したPC, SPを復元 */ \ スタックの明示的な管理と goto文により仮 想マシン上での分岐を実現
35. アプローチ2：Trie Tree (Radix Tree) の活⽤
36. Trie Treeとは、おそらくパスルーティングに おいて都合が良いデータ構造のはず。 どんなデータ構造だと都合が良いでしょう？
37. Trie TreeとRadix Tree • Trie Tree：⽂字列の先頭部分を共有して 保存することで、効率的に検索できる⽊構 造 • Radix Tree：Trie Treeとは異なり、単⼀の ⽂字ではなく⽂字の並びでラベルづけさ れる
38. Radix Treeでのルートの表現と探索
39. Radix Treeの実装（Litestarの場合） Litestarでは、Radix Treeを⾃前で実装している
40. Radix Treeでの パスルーティングの実装 ⼊⼒：Radix TreeのRootとリクエストパス 出⼒：マッチしたNodeとパスパラメータ、リク エストパス 1. リクエストパスを"/"で分割し、 path_componentsを得る 2. 以下のどちらかをpath_components数 分繰り返す a. 今⾒ているNodeの⼦にcomponent があればNodeを移動 b. パスパラメータを受け⼊れる⼦ ノードがあれば、パスパラメータ をリクエストパスから抽出し移動
41. パスルーティングの計算量 Radix Treeの場合、バックトラックが無いためマッチング時間はコンポーネント 数に対して線形時間。 • Radix Tree（バックトラックなし） • 平均：O(S) • 最悪：O(S) • （⽐較）線形探索+正規表現（VM型） • 平均：O(N·L)（単純パターン前提） • 最悪：O(N·c^L) • N: ルート数 • L: リクエストパスの⻑さ （⽂字数） • S: URL のコンポーネント数 （/ で区切った数） • c: パターンによって決まる 値（c > 1）
42. ⽐較実験
43. 実験1: ルート数に対するパスルーティング時間 仮説： • Django, FastAPI（線形探索+正規表現ベース）はルート数が増えるとパス ルーティング時間が増える • Litestar（Radix Treeベース）はルート数によらず⼀定 パラメータ： • ルートの数：10, 50, 100, 500, 1000ルート • パスの深さ：4（例：/api/v1/users/:id） ◦ 末尾にパスパラメータを設定（LitestarにRadix Treeによるルーティングをさせるため） • 測定⽅法：各条件で100回のルート解決関数を実⾏し、平均時間を計測 • 環境：Python 3.13.5
44. 実験結果 FastAPIおよびDjangoはルート数に応じてルーティング時間が増加したが、 Litestarはほぼ⼀定となった。 Routes Depth FastAPI (μs) Litestar (μs) Django (μs) 10 4 2.90 1.10 5.05 50 4 7.88 0.91 7.84 100 4 13.87 0.89 12.07 500 4 62.60 0.84 47.56 1000 4 120.74 0.90 90.57
45. 実験2: コンポーネント数に対するパスルーティング時間 仮説： • Django, FastAPI（線形探索+正規表現ベース）はコンポーネント数（パスの 深さ）が増えるとパスルーティング時間が増える • Litestar（Radix Treeベース）もコンポーネント数（パスの深さ）が増えると パスルーティング時間が増える パラメータ： • ルートの数：1000ルート • パスの深さ：5, 10, 50, 100, 500 ◦ 末尾にパスパラメータを設定（LitestarにRadix Treeによるルーティングをさせるため） • 測定⽅法：各条件で100回のルート解決関数を実⾏し、平均時間を計測 • 環境：Python 3.13.5
46. 実験結果 FastAPI, Litestar, Djangoいずれも、コンポーネント数（パスの深さ0の増加とと もにパスルーティング時間が増加 Routes Depth FastAPI (μs) Litestar (μs) Django (μs) 1000 5 49.80 0.98 43.83 1000 10 105.22 1.31 98.15 1000 50 384.43 3.77 542.24 1000 100 642.05 8.02 1116.99 1000 500 3564.34 39.42 6384.65
47. Trie Tree / Radix Treeが最強？本当に？
48. 実験3: Litestarの制約 仮説：線形探索が必要になるルートの登録とリクエストパスの指定により、 Litestarでのみパス解決に失敗する appに登録するroutes 1. GET /foo/{param1:str}/bar 2. GET /{param1:str}/{param2:str} リクエスト：GET /foo/hoge 期待される挙動 • ルート2にマッチし、{"param1": "foo", "param2": "hoge"} を抽出する Litestarは ここで失敗？
49. 実験結果 Litestarでのみ404を返却。Django, FastAPIは期待通りの挙動。 フレームワー ク リクエストパ ス ステータス コード マッチしたパ ターン 解決後パス パスパラメー タ Litestar /foo/hoge 404 — — — FastAPI /foo/hoge 200 /{param1}/{pa ram2} /foo/hoge {'param1': 'foo', 'param2': 'hoge'} Django /foo/hoge 200 /<str:param1> /<str:param2> /foo/hoge {'param1': 'foo', 'param2': 'hoge'}
50. 考察 • FastAPI, Djangoはルート数とパスの深さ、Litestarはパスの深さに応じてパ ス解決時間が変化することを確認 ◦ これは、正規表現やRadix Treeの動作アルゴリズムと⼀致 • ルート数~50, 深さ4程度の規模であれば三者の性能差は定数倍程度 • パス解決速度だけ⾒ればLitestarが最速だが、LitestarはRadix Treeの Traverse時にバックトラックしない。そのため線形探索するDjango, FastAPI では解決できるが、Litestarでは解決できないパスが存在する。
51. まとめ
52. • パスルーティングの内部動作 • 正規表現とRadix Treeの理論と実装 • アルゴリズムの選択がパフォーマンスに与える影響や制約 本発表のコンテンツ 普段当たり前に使っている機能でも • ちゃんと深掘りすると新しい発⾒があって⾯⽩い！ • 意外と難しくない！⾃分でもできそう！ と少しでも思っていただけたら嬉しいです
53. ご清聴ありがとうございました！
54. Litestarの制約の回避 • 明⽰ルートを⽣やす a. /foo/{v:str} を別ハンドラ（もしくは /{p1}/{p2} と同じハンドラ）で定義しておく。 from litestar import get @get("/foo/{v:str}") def foo_two(v: str): ... @get("/{p1:str}/{p2:str}") def two_any(p1: str, p2: str): ...
55. ルーティングアルゴリズムのトレードオフ
56. SRE_STATE