Vercelにおける無限スケーリングリダイレクト

リダイレクトは小規模では単純ですが、数百万件になるとレイテンシとコストが実際のシステム上の問題となります。 以前、Vercel ではリダイレクトはルーティングルールとミドルウェアによって処理されていました。ルーティングルールはワイルドカードを含む最大 2,000 の複雑なリダイレクトをサポートしており、順序付きリストとして順次評価されます。各ルールには正規表現マッチングが含まれる可能性があり、1 つのリクエストで多数の高コストな評価がトリガーされる可能性があります。これは数千件のルーティングルールであれば許容範囲ですが、件数が増えるとリクエストあたりの処理量が線形に増加します。 ミドルウェアはより柔軟性がありますが、すべてのリクエストで追加コードを実行するためレイテンシが発生します。低レイテンシで数百万件のリダイレクトを提供するには、リクエストあたりほぼ定数時間または対数時間で動作する専用のルックアップパスが必要でした。ブルームフィルタ（Bloom filters）を用いてグローバルルーティングを高速化した以前の取り組みに基づき、私たちは数百万件へのスケーリングを実現する方法を見つけました。 最適化の目標 スケール: - 各プロジェクトで数百万件の静的リダイレクトをサポート ランタイム動作: - リダイレクトを設定していないプロジェクトには追加のレイテンシコストが発生しない - ほとんどのリクエストはリダイレクトされないため、高速な「リダイレクトなし」パスを確保 低プロセスメモリ使用量:外部ストレージとキャッシュ層に依存し、メモリ使用を抑える エンジニアリングの価値観: - 先走った最適化よりも、シンプルさとデバッグ容易性を優先 - 最初から完璧を目指そうとするのではなく、反復的に進化させる これらの目標を念頭に置き、私たちは考え得る最もシンプルな設計から始めました。リダイレクトと Bloom フィルターを単一のファイルに統合したものです。リダイレクトデータはすでに JSON 形式であり、Bloom フィルターも JSON エクスポートをサポートしていたため、この情報を保存するために JSONL ファイル形式を採用することにしました。 JSON と Bloom フィルター versus ナプキン計算 Bloom フィルター（Bloom filter）とは、ある要素が集合に属しているかどうかを検証する確率的データ構造です。Bloom フィルターは偽陽性（false positive）を返す可能性がありますが、偽陰性（false negative）を返すことは決してありません。つまり、「確実に集合に含まれない」か「集合に含まれる可能性がある」という回答を行います。まず小さくキャッシュされた Bloom フィルターをチェックすることで、一致しないリクエストについてはリダイクトルックアップ自体をスキップでき、一般的な「リダイレクトなし」のパスを極めて低コストに保つことができます。一致が検出された場合にのみ、JSON ファイルの解析が行われます。 シンプルですが、これはスケーラブルでしょうか？ナプキン計算（napkin math）では「いいえ」という答えでした。100 万件のリダイレクトがあれば、ファイルサイズが数百メガバイトに達することは容易にあり得ます。そのような巨大なデータをフェッチして解析すれば、レイテンシとメモリの予算を圧迫してしまうでしょう。一度にデータセット全体を読み込むことは避けなければなりませんでした。 シャード化と Bloom フィルターでメモリ使用量を低く保ち、検索速度を高速化する 解決策はシャーディングでした。巨大な JSONL ファイル 1 つの代わりに、リダイレクトパスをハッシュ化してエントリを多数の小規模なシャードに分散させました。これにより、特定のリクエストに対してデータの一部のみを読み込むことが可能になり、負荷がプロセスメモリから外部ストレージおよびファイルシステムキャッシュへとシフトします。ブルームフィルタは依然として先頭に配置され、大部分のトラフィックに対する照会を短絡化しています。しかし今、リクエストがブルームフィルタを通過した場合でも、リダイレクトセット全体ではなく、単一の小さなシャードのみを取得して解析すればよいようになりました。 シャード構造 各シャードは 3 つの部分で構成されています: - ブルームフィルタのプロパティを符号化したヘッダー行 - Base64 でエンコードされたブルームフィルタ - src パスをキーとするリダイレクトの JSON オブジェクト 以下にサンプルを示します: ビルド時には、すべてのシャードとそのブルームフィルタを生成し、外部ストレージへアップロードします。ランタイムでは、サーバーはリクエストを受信した際に、特定のプロジェクトまたはデプロイメントに対してどのデータセットとシャード数が適用されるかを知るだけで十分です。 照会パスでは JSON を解析する前にブルームフィルタをチェックします リクエスト時には、一括リダイレクトの照会は以下の手順で行われます: - プロジェクトまたはデプロイメントに一括リダイレクトが設定されているか確認します。設定されていない場合は、すべての処理をスキップして通常通り進行します。 - 受信したリクエストからリダイレクトキーを計算し、ハッシュ化して対象のシャードを特定します。 - シャードをキャッシュまたはオリジンから取得し、ブルームフィルタをチェックします。 - キーがブルームフィルタに含まれていない場合、シャードの JSON 本文は解析しません。 キーが Bloom フィルタに存在する可能性がある場合、そのシャードの JSON 本体を読み込み、そのオブジェクト内で正確なリダイレクトを検索します。 この設計にはいくつかの良い特性があります: 高速なネガティブ検索: Bloom フィルタは非常に高速であり、偽陽性率を極めて低く設定できるよう調整可能です 人間が読みやすいシャード: シャードは単なる JSONL ファイルです。何か問題が発生した場合でも、シャードをダンプしてその内容を正確に確認するのは容易です 実装リスクの低さ: JSON パースと Bloom フィルタはシンプルであるため、迅速にリリースでき、実際の運用データを収集することが可能です JSON パースが正の検索におけるボトルネックとなった JSON パースがボトルネックになる可能性を懸念しており、社内での活用（dogfooding）によってそれが確認されました。Bloom フィルタでリダイレクトが存在する可能性があることが示された場合、関連するシャードの完全な JSON 本体をパースするのにかなりの時間がかかりました。また、JSON パースは CPU を多く消費し、ノード上の他のすべての処理とリソースを競合するため、CPU 負荷が高い状況では著しいレイテンシのスパイクも観測されました。 シャードサイズを小さくすればパース速度が向上しますが、シャードが小さいほど管理すべきシャード数（カルディナリティ）やキャッシュミス率が増加します。これによりトレードオフが生じました。大きなシャードはパースによる CPU オーバーヘッドが大きくなる一方、小さなシャードはキャッシュミスによる I/O レイテンシが大きくなります。シャード全体をパースすることなく単一の値を取得できるデータ形式が必要でした。 シャード全体をパースしないために、ソート済みキーに対してバイナリサーチを行う リダイレクトを JSON ブロブに保存する代わりに、リダイレクトパスをキーとしたバイナリ探索を実装しました。各シャードはリダイレクトキーをソート済み順序で保持しているため、これらのキーに対して対数時間の検索を行うことができます。キーを見つけたら、その特定のリダイレクトの JSON だけを読み解けばよいのです。これにより、シャードサイズの課題を完全に回避できます。検索コストがシャード内のデータ総量に比例して増加しなくなるため、キャッシュヒット率を高めるためにシャードを十分に大きく保ちつつ、フル JSON パースのコストを支払う必要がなくなります。 レイテンシが低下し、スパイクが消滅しました 正の検索（リダイレクトが存在する場合）におけるホットパスから JSON パースが外れたことで、実際に存在するリダイレクトへのリクエストは、より高速かつ予測可能になりました。 最も目に見える改善点は、高い CPU 負荷下で発生していたレイテンシスパイクの完全な排除です。フル JSON シャードをパースする際、リダイレクト検索はノード上で実行されている他のすべての処理と CPU 時間を競合していました。バイナリ探索を採用したことで、1 リクエストあたりの CPU コストが十分に低下し、リソース競合が要因となることはなくなりました。 一般的なケースを想定した設計 リダイレクト自体は単純です。課題は、この単純な抽象化を、主にコールド（アクセス頻度の低い）な大規模データセットと、エッジでの厳格なレイテンシ要件と組み合わせる点にあります。ルーティングルールはこのタスクには不適切なツールでした。 代わりに、バッチリダイレクト専用のパスを構築しました： - リダイレクトデータをシャード化し、各ピースが小さく保たれるようにする - ブルームフィルタを使用し、一般的な「リダイレクトなし」ケースのコストを抑える キーに対して二分探索をサポートするレイアウトにリダイレクトを保存する 今回の開発サイクルは、私たちが繰り返し強調している原則を再確認させるものでした。先行的な最適化を避けることです。シンプルでデバッグ可能な実装から始め、それを計測することで、実際に複雑さが必要となる箇所を生産データが示してくれるようになります。 一括リダイレクトの開始方法 一括リダイストは Pro および Enterprise カスタマー向けに利用可能で、プロジェクト設定、ダッシュボード、API、または CLI を経由して構成できます。現在の制限はプロジェクトあたり 100 万個のリダイレクトです。より多くの容量が必要な場合は、お問い合わせください。 プラン 含まれるリダイレクト数 追加容量 Pro プロジェクトあたり 1,000 件 25,000 件ごとに月額 $50 Enterprise プロジェクトあたり 10,000 件 25,000 件ごとに月額 $50 一括リダイレクトを使用して、大規模な移行の管理、壊れたリンクの修正、期限切れページの処理などを行ってください。詳細は、一括リダイレクトのドキュメントまたはスタートガイドをご覧ください。 続きを読む

Vercelにおける無限スケーリングリダイレクト

背景や根拠まで確認しますか？

関連記事

調べる

選ぶ

サイト