1万リクエスト/秒に対応するURL短縮サービスの設計

システム設計：スケーラブルなURL短縮サービス

前提条件

1. リダイレクトトラフィックのピークは毎秒10,000リクエストとします。名目上の100:1の読み取り/書き込み比率を考慮すると、ピーク時には約100件の作成リクエスト/秒となります。

2. 5年間で300億件のリンクを保存するには、平均で毎秒約190件の作成リクエストが必要となるため、この数値を調整し、バーストを吸収するために、ストレージと書き込みパスは少なくとも毎秒1,000件の作成リクエストに対応できるようにプロビジョニングします。

3. リンクはデフォルトで不変です。後で削除や宛先編集がサポートされる場合は、明示的なバージョン管理とキャッシュ無効化を使用します。

4. 基本的な分析は最終的に一貫性があり、壊滅的な障害中にごくわずかなイベントを失う可能性があります。リダイレクトの正確性は分析に依存しません。

5. リダイレクト応答は、永続的な301リダイレクトではなくHTTP 302または307を使用し、運用上の制御を維持し、分析の可視性を向上させます。

6. サービスは、少なくとも3つの地理的リージョンでアクティブ/アクティブで実行され、グローバルにレプリケートされたリンクデータストアを使用します。

7. 高レベルアーキテクチャ

コンポーネントは、グローバルDNSまたはAnycastルーティング、リージョンロードバランサー、ステートレスリダイレクトサービス、ステートレス作成サービス、ローカルインプロセスキャッシュ、リージョナル分散キャッシュ、パーティション化されたリンクデータストア、耐久性のあるイベントストリーム、および分析プロセッサとストレージです。

作成パス

1. クライアントは、最も近い正常なリージョンにロングURLとオプションのカスタムエイリアスを送信します。
2. APIは、呼び出し元を認証またはレート制限し、URL構文を検証し、URL長を制限し、HTTPおよびHTTPSなどのサポートされているスキームのみを許可し、予約済みエイリアスをチェックします。
3. 自動生成されたリンクの場合、サービスは暗号学的にランダムなコードを作成します。カスタムエイリアスの場合、文書化された、大文字/小文字を区別する、または区別しないポリシーに従ってエイリアスを正規化します。
4. 作成サービスは、コードまたはエイリアスがまだ存在しない場合にのみ挿入する条件付き挿入を権威あるデータストアに対して実行します。
5. ランダムな衝突が発生した場合、別のコードを生成して再試行します。カスタムエイリアスの衝突の場合、要求されたエイリアスをサイレントに変更せずにHTTP 409を返します。
6. データベースが書き込みを承認した後、サービスはローカルリージョンキャッシュに新しいマッピングを挿入し、他のリージョンにキャッシュフィルまたは無効化メッセージをブロードキャストします。
7. 短縮URLを返します。リクエストの冪等性キーは、繰り返しのクライアントリクエストを同じ結果にマッピングできます。

書き込みは、クォーラムまたはコンセンサスコミット後にのみ承認されます。これにより、ゾーン間および（データストア構成によっては）リージョン間の書き込みレイテンシが追加されますが、権威あるグローバル一意性の保証が作成されます。作成は、リダイレクトトラフィックよりもレイテンシに対する感度がはるかに低いです。

リダイレクトパス

1. グローバルルーティングは、リクエストを最も近い正常なリージョンに送信します。
2. リダイレクトサービスは、コードを検証して抽出します。
3. 小さなインプロセスキャッシュをチェックします。存在しない場合は、リージョナル分散キャッシュをチェックします。
4. キャッシュミスの場合、コードをプライマリキーとしてローカルデータストアレプリカに対してポイントルックアップを実行します。
5. 見つかり、アクティブな場合、両方のキャッシュレベルをポップレートし、クリックイベントを非同期に発行し、宛先を含む302または307応答を直ちに返します。
6. 存在しない場合、404を返します。否定的な結果は、繰り返しスキャンを防ぐために短時間のみキャッシュされます。

リダイレクトパスには、同期分析操作も、通常の条件下でのリージョン間ネットワークホップもありません。ステートレスサービスは、リージョンロードバランサーの後ろで水平方向にスケールします。

2. 短縮コードの生成と一意性

7文字のbase62空間には62^7、約3.52兆の値を格納でき、技術的には300億件のリンクを保持できます。しかし、300億件のリンクが保存された場合、その名前空間の約0.85パーセントしか使用されません。したがって、ランダムなバルクスキャナーは、約117回の推測で1つの有効なリンクを発見することになり、コードがバルクで推測されにくいという要件を満たしません。

したがって、デフォルトのコードは、暗号学的に安全なランダムソースから生成された11文字のURLセーフなbase62を使用します。これにより、約65.5ビット、5.2 x 10^19の可能性が得られます。300億件のアクティブリンクがある場合、ランダムな推測が成功する確率は約5.8 x 10^-10です。レート制限と不正利用検出により、列挙がさらに制限されます。トレードオフは、リンクが4文字長くなることです。7文字のエイリアスは、ユーザーが明示的に選択した場合でも許可されることがありますが、それらは同じ非列挙可能性保証を受けません。

ランダム生成は、作成順序を公開せず、キーを均等に分散します。プライマリキーの条件付き挿入が、最終的な一意性の権威となります。ランダムシステムでは、履歴全体での誕生日衝突が予想されますが、運用上問題となるのは同時候補衝突のみです。すべての試行された挿入はチェックされ、再試行されます。11文字空間の計画された占有率では、再試行は事実上存在しません。

代替案としては、シーケンス番号の暗号化またはキー付き置換の適用が考えられます。これにより一意の生成入力が保証されますが、キーライフサイクル管理とシーケンス割り当てが必要です。ランダム生成と条件付き挿入はよりシンプルで、中央集権的なID割り当てを排除し、この名前空間サイズでは十分に効率的です。

カスタムエイリアスは、生成されたコードと同じプライマリキー名前空間を共有します。エイリアス正規化は挿入前に行われ、グローバルに一貫した条件付き挿入が同時リクエストの勝者を決定します。ヘルス、API、管理、静的などの予約済みパスは拒否されます。エイリアスが大文字/小文字を区別しない場合、正規化された小文字形式がキーとなり、要求された表示形式は別途保存される場合があります。

3. データモデルとデータストア

権威あるリンクレコードのフィールドは次のとおりです。

code: プライマリキー
long_url: 宛先URL
created_at: タイムスタンプ
owner_id: オプションのアカウント識別子
status: active, disabled, or deleted
ttl_or_expiry: オプション
version: キャッシュ無効化のための単調増加値
custom_alias: boolean

クリック数は、人気のあるリンクが書き込みホットスポットになるのを防ぐため、リダイレクトごとにこのレコードで更新されません。

リンクストアは、DynamoDB、Bigtable、一貫性が慎重に管理されたCassandra、または同等の内部運用システムなど、プライマリキーアクセスに最適化された分散パーティションキーバリューストアです。グローバルに一意な条件付き書き込みのために、選択された実装は、ネイティブまたはシャーディングごとのコンセンサスリーダーを通じて、キーの線形化可能な条件付き作成を提供する必要があります。リダイレクトパスでは、リレーショナル結合や範囲スキャンは必要ありません。

プライマリパーティションキーは、フルコードのハッシュです。ハッシュ分散は、時系列のホットスポットを防ぎ、生成されたコードとカスタムエイリアスの両方を均等に分散します。論理キースペースは数千の仮想シャードに分割され、ノードが追加されると再割り当てされます。各シャードは、アベイラビリティゾーン全体に少なくとも3つのレプリカを持ち、さらにリージョン間レプリカがあります。

容量見積もり

平均URLを400バイト、キー、メタデータ、エンコーディング、インデックス、ストレージエンジンのオーバーヘッドを約200バイトと仮定します。レコードあたり約600バイトで、300億レコードには約18 TBの論理データが必要です。長いURL、コンパクションオーバーヘッド、トゥームストーン、運用上のヘッドルームを考慮して、30 TBの論理容量を予算計上します。3つの耐久性のあるレプリカには約90 TBが必要であり、バックアップとリージョン間コピーはフリート割り当てを約150〜250 TBに引き上げることができます。これは、水平パーティション化されたキーバリューストアの意図された範囲内にありますが、単一の従来のデータベースインスタンスには不向きです。

毎秒10,000リダイレクトの場合、完全なキャッシュ障害でも、毎秒10,000件のランダムポイントリードしか発生しません。データストアは、サービングリージョンあたり少なくとも20,000〜30,000リード/秒（フェイルオーバー時）および少なくとも1,000件の条件付き作成/秒（作成時）に対応できるようにプロビジョニングされます。容量は、通常の要求スループットよりも、データセットサイズ、レプリケーション、フェイルオーバーリザーブによってより多く制御されます。

分析は別のストレージを使用します。ストリームプロセッサは、コードごと、時間バケットごとのカウントを、コードと日または時間の組み合わせをキー、カウントを値とするモデルで、分析キーバリューストアまたはカラムナストアに書き込みます。コンパクトな合計を非同期に維持できます。分析を分離することで、ホットリンクカウンターがリダイレクトルックアップと競合するのを防ぎます。

4. キャッシュ戦略

各リダイレクトプロセスには、最もホットなマッピングのための、制限付きLRUまたはTinyLFUインメモリキャッシュがあります。リージョナルRedisまたはMemcached互換クラスターが2番目のレベルを形成します。キャッシュされた値には、宛先、ステータス、有効期限、レコードバージョンが含まれます。

代表的なターゲットは、リージョンキャッシュヒット率95〜99％です。Zipf分布のURL人気は、コーパス全体が非常に大きいにもかかわらず、通常これを可能にします。キャッシュは、300億件のリンクすべてではなく、ホットオブジェクトを格納します。たとえば、約600バイトのエントリが1億件あっても、キャッシュオーバーヘッドを考慮すると約60 GB、実際には100〜150 GB程度で、リージョンキャッシュクラスターに分散されます。

マッピングはデフォルトで不変であるため、肯定的なエントリは6〜24時間（ジッター付き）などの長いTTLを持つことができます。編集、無効化、または削除がサポートされている場合、権威ある書き込みが最初にコミットされ、次にコードと新しいバージョンを含む無効化メッセージをすべてのリージョンに発行します。短いTTLは、無効化メッセージが失われた場合の古い値の提供時間を制限します。安全性が重要な無効化操作は、すべてのリダイレクトプロセスにグローバルな拒否リストを短時間配置することもできます。

否定的な結果は、繰り返しスキャンを防ぐために約5〜30秒間キャッシュされます。作成パスは、コードの取得に成功した後、否定的なキャッシュエントリを無効化します。短い否定的なTTLは、別のリージョンがレプリケーションまたは無効化が到着する前にミスを短時間キャッシュしたレースを制限します。

キャッシュミスの場合、リダイレクトサービスはリージョナルデータストアレプリカを読み取り、両方のキャッシュレベルをフィルします。リクエストの合算により、新しく人気が出たコードに対する同時ミスが、数千ではなく1回のデータベースリクエストで処理されるようになります。TTLジッターは同期的な有効期限切れを防ぎます。データストアは、分散キャッシュが失敗した場合に、毎秒10,000リクエストの全負荷を処理できるようにサイズ設定されており、若干高いレイテンシを受け入れつつも機能し続けます。

長いキャッシュTTLのトレードオフは、編集後の潜在的な陳腐化です。不変性、バージョン付き無効化、および制限付きTTLにより、そのトレードオフが明示されます。新しく作成されたリンクのリダイレクトの正確性は、作成リージョンを同期的にフィルし、必要に応じてそのリージョンに即時読み取りをルーティングすることで向上させることができます。

5. スケーリングとレイテンシ

リダイレクトサービスはステートレスであり、リクエスト/秒、CPU、p99レイテンシに基づいて水平方向にスケールします。1つのインスタンスが安全に毎秒1,000リクエストを処理できる場合、各リージョンは、毎秒10,000リクエストのリージョンフェイルオーバー負荷に対応するために、少なくとも15〜20インスタンスを実行し、さらにデプロイメントとゾーン障害のヘッドルームを確保する可能性があります。実際のサイジングは負荷テストによって確立されます。

通常のキャッシュヒットレイテンシ予算は約2〜5ミリ秒（ロードバランシングとアプリケーション処理）、1〜3ミリ秒（インプロセスルックアップ）または2〜8ミリ秒（リージョナル分散キャッシュルックアップ）、および応答構築に数ミリ秒です。キャッシュミスの予算は、ローカルレプリケートデータストアのポイントルックアップに約10〜25ミリ秒を割り当てます。これらの予算により、オリジンサーバーサイドのp99を50ミリ秒未満に抑えることができます。

厳密なホップごとのタイムアウトは、破損したキャッシュまたはレプリカがレイテンシ予算全体を消費するのを防ぎます。キャッシュアクセスは約8ミリ秒、データストアアクセスは約25〜30ミリ秒に制限され、十分な予算が残っている場合にのみ再試行されます。遅延してレート制限されたヘッジリードを2番目のローカルレプリカに対して使用して、通常の負荷の倍増を避けることができます。

キーは仮想シャード全体にハッシュパーティション化されます。ランダムに生成されたコードは自然にトラフィックをバランスさせますが、例外的にホットな個々のリンクは、インプロセスおよびリージョナルキャッシュによって吸収されます。ホットキーがデータストアに到達した場合、リクエストの合算とレプリケートリードにより、1つのストレージノードがボトルネックになるのを防ぎます。

オートスケーリングは、完全なアベイラビリティゾーン損失と、少なくとも1つのリージョンが障害のあるピアからのリダイレクトトラフィックを受信するのに十分な容量を維持します。リージョンは、ピーク容量の約50〜60％未満で実行されます。トレードオフは、99.99％の可用性目標のために、より高いアイドルコストです。

6. 信頼性と障害処理

可用性目標

月間99.99％の目標は、30日間の月で約4.4分間の利用不可を許容します。単一のキャッシュノード、アプリケーションインスタンス、アベイラビリティゾーン、またはリージョンがリダイレクトに必要とされることはありません。

アプリケーションインスタンスまたはゾーン障害

ヘルスチェックは失敗したインスタンスを削除し、ロードバランサーは少なくとも3つのゾーンにリクエストを分散します。サービスは、ローリングまたはカナリアデプロイメント、コネクションドレイン、および自動ロールバックを使用します。リージョン容量は、1つのゾーンの損失に耐えます。

キャッシュノードまたはキャッシュクラスター障害

キャッシュノードは、リージョン内でシャーディングおよびレプリケートされます。個々のノードが失敗した場合、そのレプリカが引き継ぎます。キャッシュ全体が利用できない場合、リダイレクトサービスはサーキットブレーカーを使用し、キャッシュ呼び出しをスキップし、データストアを直接クエリします。データベース容量とアプリケーション接続プールは、このモードのために明示的にプロビジョニングされています。アドミッションコントロールは、データストアを無制限のスキャナートラフィックから保護します。

データストアノード障害

各シャードは、クォーラムまたはコンセンサスを使用してゾーン全体でレプリケートされます。失敗したリーダーは自動的に置き換えられ、読み取りは別の正常なローカルレプリカを使用します。条件付き作成は、重複所有権のリスクを回避するために、短い選挙期間中、シャードに対して利用できなくなります。レプリカとキャッシュからリダイレクトを継続できます。これは、作成の正確性を優先しつつ、読み取りの可用性を維持します。

リージョン障害

グローバルなヘルスベースルーティングは、失敗したリージョンを削除し、トラフィックを最も近い正常なリージョンに送信します。各サービングリージョンには、リンクデータのレプリケートコピーと独立したリダイレクト、キャッシュ、イベント取り込みインフラストラクチャがあります。フェイルオーバー後のキャッシュヒット率は最初は低くなります。そのため、スタンバイリージョンはグローバルにホットなリンクのウォームキャッシュと、コールドキャッシュの急増に対応できる十分なデータストア/読み取り容量を保持します。

生成されたコードの場合、データストアアーキテクチャが各キーをホームシャードにルーティングする場合、グローバルレプリケーションはコンセンサスバックの権威ある挿入後に非同期になる可能性があります。カスタムエイリアスの場合、権威ある条件付き挿入はグローバルにシリアル化される必要があります。新しく作成されたリンクが壊滅的な損失の前に生き残ったリージョンに到達していない場合、サービスは不正確なマッピングの代わりに、一時的に再試行可能なエラーを返す可能性があります。より強力な同期マルチリージョンレプリケーションは、このリカバリポイントウィンドウを短縮しますが、作成レイテンシを増加させます。推奨される構成では、書き込みは比較的低量であるため、少なくとも2つのリージョンにわたるレプリカにリンク作成をコミットします。

バックアップと破損

データストアは、チェックサム、ポイントインタイムリカバリ、不変スナップショット、および定期的にテストされた復元手順を使用します。削除は、物理的な即時削除ではなく、トゥームストーンと保持期間を使用します。バックアップは論理的な破損から保護しますが、通常のredirectフェイルオーバーの一部ではありません。

過負荷時の動作

レート制限は、ソース、アカウント、および疑わしいコードスキャンパターンに適用されます。作成および分析トラフィックは、リダイレクトよりも優先度が低くなります。ロードシェディングは、リダイレクト容量に影響を与える前に、不正または過剰な作成リクエストを拒否します。サーキットブレーカー、制限付きキュー、およびデッドラインは、カスケード障害を防ぎます。

7. クリック分析

リダイレクト先を選択した後、サービスはイベントID、コード、タイムスタンプ、リージョン、およびオプションで大まかなリファラーまたはユーザーエージェントフィールドを含むコンパクトなイベントを作成します。イベントを制限付きのローカル非同期バッファに配置し、分析の承認を待たずにリダイレクトを返します。

リージョンコレクターは、イベントをバッチ処理して、Kafka、Pulsar、またはKinesisなどの耐久性のあるレプリケートストリームに書き込みます。ストリームプロセッサは、イベントをコードと時間バケットごとに集計し、バッチ処理されたインクリメントを分析ストアに書き込みます。定期的なコンパクションにより、合計クリック数が生成されます。ダッシュボードとAPIは、権威あるリダイレクトテーブルではなく、分析ストアを読み取ります。

イベントIDにより、コレクターが再試行した場合のダウンストリームの重複排除が可能になります。ストリームをコードで直接パーティション化すると、バイラルリンクが1つのパーティションに集中するため、取り込みキーはコードとランダムなストライプの組み合わせにすることができます。プロセッサは最初にストライプ化されたカウンターを集計し、次にそれらをマージします。これにより、ホットリンク分析を水平方向にスケールできます。

完全にインメモリの非同期バッファは、リダイレクトプロセスがクラッシュした場合にイベントを失う可能性があります。より強力な耐久性が必要な場合は、各ホストまたはサイドカーがバッチをローカルのライトアヘッドログに追記してから転送できますが、リダイレクト応答は中央ストリームを待つべきではありません。基本的な分析で受け入れられるトレードオフは、最終的な一貫性と、リダイレクトレイテンシと可用性を維持することと引き換えに、深刻な障害中のわずかな、測定されたアンダーカウントです。

結果

通常のredirectパスは、ローカルキャッシュルックアップと、ミスの場合のみローカルパーティションキーバリュールックアップです。ランダムな11文字のコードは、シーケンシャルな露出を防ぎ、成功したバルク推測を非現実的にします。条件付き挿入は一意性を提供し、ハッシュパーティション化は300億レコードのコーパスをサポートし、アクティブ/アクティブなリージョンサービングはリージョンの単一障害点を排除し、非同期ストライプ化分析はカウンター書き込みをレイテンシクリティカルパスから完全にオフに保ちます。

システム設計：URL短縮サービス (10K RPS)

前提条件：

• 初期段階では単一リージョンを対象とし、マルチリージョンは将来的な拡張とします。
• 読み書き比率が100:1であるため、リダイレクトパスを最優先します。
• カスタムエイリアスは二次的な機能であり、標準リダイレクトと比較してわずかに高いレイテンシや一時的な利用不可に耐えうるとします。
• クリック分析は厳密なリアルタイム性を必要とせず、わずかな遅延を許容します。

1. 高レベルアーキテクチャとリクエストフロー

書き込みパス（短縮リンクの作成）：

1. API Gateway: 長いURLとオプションのカスタムエイリアスを含むPOSTリクエストを受信します。
2. Load Balancer: 書き込みリクエストをURL短縮サービス（US）APIインスタンスに分散します。
3. US API（書き込みサービス）：
   • 入力URLを検証します。
   • 短縮コードを生成します（セクション2参照）。
   • カスタムエイリアスが指定されている場合、まずそれを予約しようとします（セクション2参照）。
   • マッピング（short_code -> original_url, custom_alias -> short_code）をデータストアに永続化します。
   • 生成された短縮URLをクライアントに返します。

読み取りパス（リダイレクト）：

1. API Gateway: 短縮URLのGETリクエストを受信します。
2. Load Balancer: 読み取りリクエストをUS APIインスタンスに分散します。
3. US API（読み取りサービス）：
   • URLパスから短縮コードを抽出します。
   • キャッシュ検索: 分散キャッシュ（例：Redis Cluster）で短縮コードを検索します。
     • キャッシュヒット: 見つかった場合、元のURLを取得し、HTTP 301/302リダイレクトレスポンスを返します。
     • キャッシュミス: 見つからなかった場合、プライマリデータストアに問い合わせます。
   • データストア検索: プライマリデータストアで短縮コードに関連付けられた元のURLを検索します。
   • キャッシュ更新: データストアで見つかった場合、元のURLが将来のリクエストのためにキャッシュに追加されます。
   • リダイレクト: 元のURLを含むHTTP 301/302リダイレクトレスポンスを返します。
   • エラー処理: 見つからなかった場合、404 Not Foundを返します。
4. クリック分析（非同期）： 別のサービスまたはメカニズム（セクション7参照）がクリックイベントを非同期に記録します。

トレードオフ：

• 関心の分離: 読み取りサービスと書き込みサービスを分離することで、独立したスケーリングと最適化が可能になります。読み取りパスは低レイテンシと高スループットに最適化されています。
• API Gateway/Load Balancer: 高可用性が構成されていない場合、単一障害点となりますが、スケーリングとトラフィック管理には不可欠です。
• キャッシュミスのペナルティ: キャッシュミスはデータストア検索によるレイテンシの増加を招きますが、これは大規模なキャッシュと高いヒット率によって緩和されます。

2. 短縮コード生成戦略

戦略： カウンター/IDジェネレーターを使用したBase62エンコーディング。

1. ID生成: 一意で単調増加する64ビット整数を生成するために、分散ID生成サービス（例：SnowflakeライクまたはZooKeeper/etcdを使用した専用サービス）を使用します。これにより、ソースでの一意性が保証され、衝突が回避されます。
   • トレードオフ: 高可用性と高性能なID生成サービスが必要です。これが失敗すると、新しい短縮リンクを作成できなくなります。
2. Base62エンコーディング: 生成された各64ビット整数IDは、Base62文字列（0-9、a-z、A-Z）に変換されます。64ビットIDは最大2^64の一意な値を表すことができます。最初の6文字は約680億（62^6）の一意な値を表し、7文字は約4.1兆（62^7）を表します。5年間で300億リンクの場合、7文字で十分であり、成長のための十分な余地があります。
   • トレードオフ: Base62エンコーディングは単純なハッシュよりもわずかに複雑ですが、より短いURLを提供し、シーケンシャルIDと比較して推測可能性を回避します。
3. カスタムエイリアス：
   • ユーザーがカスタムエイリアス（例：「/my-link」）を要求すると、書き込みサービスはまず、データストア内の専用テーブル/インデックス（例：custom_aliasesテーブル、alias -> short_codeをマッピング）でエイリアスが既に取得されているかどうかを確認します。
   • エイリアスが利用可能な場合、それは予約され、新しく生成された短縮コードに関連付けられます。
   • エイリアスが取得されている場合、APIはユーザーにエラーを返します。
   • 衝突処理: ID生成とBase62エンコーディングにより、生成された短縮コードの一意性が保証されます。カスタムエイリアスは、衝突を防ぐためにデータストアでの個別のアトミックなチェックアンドセット操作を通じて処理されます。
   • トレードオフ: カスタムエイリアスの検索は、書き込みパスにわずかなオーバーヘッドを追加します。カスタムエイリアスの可用性は保証されません。

一意性の保証： 分散IDジェネレーターによって達成されます。各IDは一意であり、そのBase62表現も一意になります。

推測不可能： Base62エンコードされたIDはシーケンシャルではなく、作成順序やリンクの総数を示しません。実質的にランダムに見える文字列です。

3. データモデルとデータストア（複数可）

データストアの選択： プライマリリンクマッピング用の分散NoSQLキーバリューストア（例：Cassandra、DynamoDB、またはVitessのようなシャーディングされたリレーショナルDB）、および分析用の別個のシステム。

プライマリデータストア（リンクマッピング）：

• スキーマ：

  • linksテーブル/コレクション：
    • short_code（主キー、文字列、例：「aBcDeFg」）
    • original_url（文字列）
    • created_at（タイムスタンプ）
    • user_id（オプション、所有権/管理用）
  • custom_aliasesテーブル/コレクション：
    • alias（主キー、文字列、例：「my-link」）
    • short_code（文字列、links.short_codeへの外部キー）

• データストアタイプの正当化： 分散NoSQLキーバリューストアは、その高可用性、水平スケーラビリティ、およびキー検索の優れた読み取りパフォーマンスにより選択されます。これはリダイレクトパスにとって非常に重要です。300億エントリという膨大な規模を処理できます。

• 容量/ストレージ見積もり：

  • Linksテーブル： 300億エントリ。
    • short_code：約7バイト（Base62、7文字）
    • original_url：平均100バイト（大きく変動する可能性あり、平均値と仮定）
    • created_at、user_id：約10バイト
    • エントリあたりの合計：約117バイト。オーバーヘッドとレプリケーションのために150バイトに切り上げます。
    • 合計ストレージ：300億 * 150バイト = 4.5 * 10^12バイト = 4.5 TB。
  • Custom Aliasesテーブル： リンクの10％がカスタムエイリアスを持つと仮定（30億）。
    • alias：平均15バイト（長いURLより短い）
    • short_code：約7バイト。
    • エントリあたりの合計：約22バイト。オーバーヘッドのために50バイトに切り上げます。
    • 合計ストレージ：30億 * 50バイト = 150 * 10^9バイト = 0.15 TB。
  • プライマリ合計ストレージ： 約4.65 TB。これは分散NoSQLシステムにとって管理可能です。

• パーティショニング/シャーディング： データストアは、linksテーブルの場合はshort_code（またはそのハッシュ）、custom_aliasesテーブルの場合はaliasでシャーディングされます。これにより、データと読み書き負荷が複数のノードに分散されます。

トレードオフ：

• NoSQL vs. SQL: NoSQLストアは、スキーマの柔軟性と水平スケーリングのために好まれます。リレーショナルDBも機能しますが、より複雑なシャーディング管理（例：Vitess）が必要になります。
• データ冗長性: NoSQLストアは通常、可用性のためにデータをレプリケートし、ストレージ要件を増加させますが、耐障害性を向上させます。
• カスタムエイリアステーブル: メインのlinksテーブルをスキャンするのではなく、エイリアスの可用性を効率的にチェックするために別個のテーブルが使用されます。これは非効率的です。

4. キャッシュ戦略

戦略： 分散インメモリキャッシュ（例：Redis Cluster、Memcached）。

• キャッシュするもの： 頻繁にアクセスされるshort_codeからoriginal_urlへのマッピング。
• キャッシュキー： short_code（例：「aBcDeFg」）
• キャッシュ値： original_url（例：「https://www.verylongurl.com/...」）
• キャッシュサイズ： ホットリンクの大部分を保持できるようにサイズ設定します。10K RPSと100:1の比率を考慮すると、毎秒数百万のアクティブリンクが予想されます。100万から500万エントリを保持するキャッシュは、ホットリンクに対して高いヒット率を提供する必要があります。
• キャッシュ無効化：
  • 標準リンクの明示的な無効化は不要： 作成されたリンクは不変です。マッピングは変更されません。
  • カスタムエイリアスの場合： カスタムエイリアスが変更された場合（通常は許可されませんが、もしそうなら）、古いshort_code -> original_urlマッピングはキャッシュに残ります。しかし、標準的なプラクティスでは、カスタムエイリアスは設定されると一意で永続的です。リンクが削除された場合（URL短縮サービスでは一般的な機能ではありません）、そのエントリはキャッシュから削除されます。
• キャッシュミス処理：
  1. キャッシュミスが発生すると、US API（読み取りサービス）はshort_codeを使用してプライマリデータストアからoriginal_urlを検索します。
  2. データストアで見つかった場合、original_urlはクライアントに返される前に、有効期限（TTL）（例：24〜48時間）とともにキャッシュに書き戻されます。
  3. データストアで見つからなかった場合、404が返され、キャッシュにエントリは追加されません。

トレードオフ：

• キャッシュの陳腐化： TTLベースのキャッシングは、リンクが更新された場合（更新が許可されていれば）キャッシュが古くなる可能性のある小さなウィンドウがあることを意味します。しかし、不変のリンクではこれは問題になりません。
• キャッシュの可用性： キャッシュは重要なコンポーネントです。失敗した場合、データストア検索のためにレイテンシが大幅に増加しますが、サービスは利用可能なままです（ただし遅くなります）。
• コスト： 大規模なインメモリキャッシュは高価になる可能性があります。

5. スケーリング戦略

読み取りパスのスケーリング（リダイレクト）：

• ステートレスAPIサーバー： リダイレクトを処理するUS APIインスタンスはステートレスです。これにより、ロードバランサーの後ろで無限に水平スケーリングできます。
• 分散キャッシュ： シャーディングおよびレプリケーションされた分散キャッシュ（Redis Clusterなど）は、数百万のQPSを処理でき、低レイテンシを提供します。水平スケーリングのために設計されています。
• データストアのスケーリング： 選択された分散NoSQLデータストア（Cassandra、DynamoDB）は水平スケーリングのために設計されています。ノードを追加することで、スループットと容量を増やすことができます。
• ロードバランサー： 複数のレイヤー（API Gateway、サービス間）のロードバランサーがトラフィックを均等に分散します。

データパーティショニング/シャーディング：

• データストアシャーディング： セクション3で述べたように、プライマリデータストアはlinksテーブルの場合はshort_code（またはそのハッシュ）、custom_aliasesテーブルの場合はaliasでシャーディングされます。これにより、データと読み書き負荷が複数のノードに分散されます。
• キャッシュシャーディング： 分散キャッシュは本質的にシャーディングされており、キーをノード全体に分散します。
• ID生成サービス： このサービスもスケーラブルである必要があります。ZooKeeper/etcdまたは分散合意プロトコルによって調整された複数のインスタンスを使用する可能性があります。

トレードオフ：

• 複雑さ： シャーディングと分散システムは、運用上の複雑さを大幅に増加させます。
• ホットスポット： シャーディングは役立ちますが、非常に人気のあるリンクは、特定のキャッシュシャードまたはデータストアパーティションにホットスポットを作成する可能性があります。一貫性ハッシュやより高度なロードバランシングなどの戦略でこれを軽減できます。

6. 信頼性と障害処理

可用性目標（99.99%）： すべてのレイヤーで冗長性が必要です。

• データストアノード障害：
  • 戦略： データは複数のノード（例：3〜5レプリカ）に、場合によってはリージョン内のアベイラビリティゾーン（AZ）全体にレプリケートされます。
  • 処理： データストアクラスターは、レプリカを昇格させることでノード障害を自動的に処理し、リクエストの提供を続行します。フェイルオーバー中の読み書きは、わずかなレイテンシのスパイクを経験する可能性がありますが、サービスは利用可能なままです。
  • トレードオフ： レプリケーションによるストレージコストの増加。
• キャッシュノード障害：
  • 戦略： Redis Clusterのような分散キャッシュは、レプリケーションとシャーディングで設計されています。ノードが失敗した場合、そのレプリカが引き継ぐか、データが再分散される可能性があります。
  • 処理： キャッシュが再構築またはフェイルオーバーする間、キャッシュミスが一時的に増加します。システムはデータストアにフォールバックし、レイテンシは高くなりますが、可用性は維持されます。
  • トレードオフ： キャッシュ障害時の一時的なパフォーマンス低下。
• APIサーバー障害：
  • 戦略： ロードバランサーの後ろで、ステートレスなUS APIサーバーの複数のインスタンスを実行します。
  • 処理： ロードバランサーは正常でないインスタンスを検出し、トラフィックの送信を停止します。トラフィックは正常なインスタンスに自動的にルーティングされます。
  • トレードオフ： 強力なロードバランシングとヘルスチェックが必要です。
• リージョン障害：
  • 戦略： 単一リージョン内の複数のアベイラビリティゾーン（AZ）にサービスをデプロイします。より高い可用性のために、マルチリージョンアクティブアクティブまたはアクティブパッシブ構成を実装できます。
  • 処理： 1つのAZが失敗した場合、トラフィックは正常なAZにルーティングされます。リージョン全体が失敗した場合、トラフィックはセカンダリリージョンにルーティングされます（グローバルロードバランシングとデータレプリケーションが必要です）。
  • トレードオフ： マルチリージョン展開における複雑さとコストの大幅な増加。

可用性目標の達成： 冗長性、自動フェイルオーバー、およびグレースフルデグラデーション（キャッシュミス時のデータストアへのフォールバック）が鍵となります。障害を迅速に検出し対応するには、監視とアラートが不可欠です。

7. クリック分析の収集

戦略： クリティカルなリダイレクトパスに影響を与えないように、非同期処理。

1. イベント生成： リダイレクトが発生したとき（元のURLが取得され、リダイレクトレスポンスが送信される前）、US API（読み取りサービス）は軽量なイベントを発行します。