グローバルなURL短縮サービスの設計

Design: グローバルURL短縮サービス

1. 要件と概算見積もり

機能要件:

• 指定された長URLに対して短縮リンクを作成する（カスタムエイリアスは任意）。
• 短縮リンクの訪問者を元のURLにリダイレクトする（HTTP 301/302）。
• 基本的な分析：リンクごとの総クリック数、過去30日間の日別クリック数。

非機能要件:

• 月間新規リンク数1億2000万件、平均約46件/秒の書き込み、ピーク時約200件/秒。
• 月間リダイレクト数12億件、平均約463件/秒、ピーク時（バイラルリンクの場合）約5,000～50,000件/秒。
• リダイレクト可用性99.99%。
• グローバルな低遅延リダイレクト。
• リンクの有効期間は最低5年間。
• 分析結果は10分以内に最終的に整合性が取れること。
• 基本的な不正利用防止。

ストレージ見積もり:

• 月間1億2000万リンク × 60ヶ月（5年間）= 72億リンク。
• 各リンクレコード約500バイト（短縮コード、長URL、メタデータ）で、5年間で約3.6TBのリンクデータ。
• 分析データは追加だが、集計により管理可能。

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

システムは以下の主要コンポーネントで構成されます。

a) APIゲートウェイとロードバランサー：すべてのトラフィックのエントリポイント。TLS終端、レート制限、リンク作成のための認証、ルーティングを処理します。グローバルanycast DNSまたはグローバルロードバランサー（例：AWS Global AcceleratorまたはCloudflare）の後ろに、複数のリージョンにデプロイされます。

b) リンク作成サービス：新しい短縮リンクを作成するためのPOSTリクエストを処理するステートレスサービス。入力を検証し、短縮コードを生成または予約し、カスタムエイリアスの空き状況を確認し、基本的な不正チェックを適用し、プライマリデータベースに書き込みます。

c) リダイレクトサービス：短縮コードのGETリクエストを処理するステートレスで読み取り最適化されたサービス。まずキャッシュで短縮コードを検索し、次にデータベースで検索し、HTTP 301または302リダイレクトを返します。分析のためにクリックイベントを非同期に発行します。

d) 分析サービス：メッセージキューからクリックイベントを消費し、集計して、日次および総クリック数を保存します。分析クエリを提供します。

e) キャッシュレイヤー：各リージョンにデプロイされた分散キャッシュ（RedisまたはMemcachedクラスタ）。サブミリ秒の遅延でホットな短縮コードを提供します。

f) プライマリデータベース：正規のリンクマッピングを保存します。Amazon DynamoDB、Google Cloud Spanner、CockroachDBなどの分散データベース。

g) メッセージキュー：リダイレクトサービスと分析パイプラインの間でクリックイベントをバッファリングするためのKafkaまたはAmazon Kinesis。

h) CDN / エッジレイヤー：最も人気のあるリンクについては、リダイレクト応答をCDNエッジでキャッシュできます（適切なキャッシュヘッダーを持つ301またはルックアップを実行するエッジワーカーを使用）。

アーキテクチャフロー:

• リンク作成：クライアント → APIゲートウェイ → リンク作成サービス → プライマリDB（書き込み）→ キャッシュ無効化/設定 → 短縮URLを返す。
• リダイレクト：クライアント → CDN/エッジ → （キャッシュミス）→ APIゲートウェイ → リダイレクトサービス → キャッシュ → （キャッシュミス）→ DB → 302リダイレクトを返す。クリックイベントをメッセージキューに非同期に発行する。
• 分析クエリ：クライアント → APIゲートウェイ → 分析サービス → 分析DB → 結果を返す。

3. データモデルとストレージ

リンクマッピングテーブル（プライマリストア - DynamoDBまたは類似）:

• short_code（パーティションキー）：文字列、7文字、例：「aB3x9Kz」
• long_url：文字列、元のURL、最大2048文字
• user_id：文字列、任意、作成者
• custom_alias：ブール値、カスタムエイリアスかどうか
• created_at：タイムスタンプ
• expires_at：タイムスタンプ（デフォルトでcreated_at + 5年）
• click_count：整数（最終的に整合性が取れるカウンター、定期的に更新）
• status：enum（active、disabled、expired）

DynamoDBを選択する理由：単一のキーバリュールックアップパターンに最適です。一貫したシングルミリ秒の遅延で水平スケーリングします。パーティションキーは短縮コードであり、生成されたコードのランダムな性質により、適切に分散されます。

分析ストア:

• オプションA：DynamoDBまたはCassandraの時系列テーブルで、パーティションキー=short_code、ソートキー=日付（YYYY-MM-DD）、click_count属性を持つ。
• オプションB：別のテーブルに事前に集計された日次カウントを保存し、日次粒度の行にはTTLを30日間設定する。

日次分析テーブルのスキーマ:

• short_code（パーティションキー）：文字列
• date（ソートキー）：文字列、YYYY-MM-DD形式
• click_count：整数
• TTL：タイムスタンプ、日付から30日後

これにより、効率的な範囲クエリが可能になります：過去30日間のshort_codeのすべての日次カウントを取得します。

総クリック数については、メインのリンクマッピングテーブルで実行中のカウンターを維持し、分析パイプラインによって更新されます。

4. ID / トークン生成戦略

要件：5年間で72億の一意なコード。base62エンコーディング（a-z、A-Z、0-9）を使用すると、7文字のコードで62^7 = 3兆5000億の可能な組み合わせが得られ、これは十分に余裕があります。

アプローチ：分散カウンターまたは範囲ベースの割り当てを使用した事前生成ID範囲。

プライマリ戦略：

• 中央ID生成サービス（Twitter Snowflakeやよりシンプルなカウンターサービスなど）を使用して、各リンク作成サービスインスタンスに数値IDの範囲を割り当てます。たとえば、各インスタンスは一度に10,000件のIDブロックを要求します。
• 各数値IDはbase62にエンコードされ、7文字の短縮コードが生成されます。
• これにより、書き込みごとの調整が不要になり、グローバルな一意性が保証されます。

検討された代替案：衝突チェック付きのランダム生成。これは機能しますが、衝突をチェックするために書き込み前に読み取りが必要であり、遅延が増加します。3兆5000億の可能なコードのうち72億を使用する場合、衝突確率は低い（約0.2%）ですが、チェックは必要です。範囲ベースのアプローチはより決定的です。

カスタムエイリアスの処理：

• ユーザーがカスタムエイリアスを要求すると、サービスはデータベースへの条件付き書き込み（short_codeがまだ存在しないという条件付きのPutItem）を実行します。
• 条件が失敗した場合、エイリアスは使用されており、ユーザーにエラーを返します。
• カスタムエイリアスは検証されます：最小4文字、最大30文字、英数字とハイフン、予約語と不快な用語のブロックリストに対してチェックされます。
• カスタムエイリアスは、カスタムエイリアスフラグをtrueに設定して、生成されたコードと同じテーブルに保存されます。

5. API設計

すべてのAPIはHTTPS経由のRESTfulです。

a) 短縮リンクの作成：
POST /api/v1/links
ヘッダー：Authorization: Bearer （匿名の場合は任意、分析アクセスには必須）
リクエストボディ：
long_url：必須、宛先URL（フォーマットと基本的な安全性を検証済み）
custom_alias：任意、希望する短縮コード
expires_in_days：任意、デフォルト1825（5年）
レスポンス（201 Created）：
short_code：「aB3x9Kz」
short_url：「https://sho.rt/aB3x9Kz」
long_url：「https://example.com/very/long/path」
created_at：「2025-01-15T10:30:00Z」
expires_at：「2030-01-15T10:30:00Z」
エラーレスポンス：400（無効なURL）、409（カスタムエイリアスが使用中）、429（レート制限）

b) リダイレクト：
GET /{short_code}
レスポンス：長URLにLocationヘッダーが設定された302 Found。
ブラウザがリダイレクトを永続的にキャッシュしないように、301（永続リダイレクト）ではなく302（一時リダイレクト）を使用します。これにより、クリック数を追跡し、宛先を更新できる可能性があります。ただし、パフォーマンスのため、CDNエッジで適切なTTLを持つ301を使用できます。
エラーレスポンス：404（見つからないか期限切れ）、410（無効）

c) 分析の取得：
GET /api/v1/links/{short_code}/analytics
ヘッダー：Authorization: Bearer
レスポンス（200 OK）：
short_code：「aB3x9Kz」
total_clicks：154302
daily_clicks：過去30日間の日付とカウントを持つオブジェクトのリスト
エラーレスポンス：401（認証されていない）、404（リンクが見つからない）

d) リンクの削除/無効化：
DELETE /api/v1/links/{short_code}
ヘッダー：Authorization: Bearer
レスポンス：204 No Content

6. キャッシュ、パーティショニング、レプリケーション戦略

キャッシュ：

• レイヤー1 - CDNエッジキャッシュ：リダイレクトパスの場合、短時間TTL（例：5分）でCDNエッジに302応答をキャッシュできます。これは、CDNがトラフィックの大部分を吸収するため、バイラルリンクを非常にうまく処理します。短いmax-ageを持つCache-Controlヘッダーを使用します。エッジワーカー（Cloudflare Workers、Lambda@Edge）は、リージョナルキャッシュから直接ルックアップを実行することもできます。
• レイヤー2 - リージョナルRedisクラスタ：各リージョンには、短縮コードから長URLへのマッピングをキャッシュするRedisクラスタがあります。キャッシュTTLは24時間。LRU（Least Recently Used）エビクションポリシー。これにより、データベースにヒットすることなく、ほとんどのリダイレクトルックアップを処理できます。
• レイヤー3 - アプリケーションレベルのローカルキャッシュ：各リダイレクトサービスインスタンスは、小さなインプロセスLRUキャッシュ（例：10万エントリ）を保持し、最もホットなリンクに対応します。

キャッシュサイズ：月間12億リダイレクトとジップ分布を考えると、上位20%のリンクがトラフィックの80%を占める可能性が高いです。Redisで上位1000万件のアクティブリンクをキャッシュするには、約1000万 × 300バイト = 3GB/リージョンが必要であり、これは非常に管理しやすいです。

キャッシュ無効化：リンクの削除または更新時に、メッセージキュー経由ですべてのリージョンに無効化イベントを発行します。キャッシュエントリには、安全策としてTTLもあります。

パーティショニング：

• DynamoDBは、短縮コードのハッシュキーによって自動的にパーティション化されます。生成されたコードのランダムな性質により、均一な分散が保証されます。
• カスタムエイリアスの場合、分散はそれほど予測可能ではありませんが、DynamoDBの適応型キャパシティがホットパーティションを処理します。
• Redisは、クラスタノード全体で一貫性ハッシュを使用してパーティション化されます。

レプリケーション：

• DynamoDBグローバルテーブルは、最終整合性（通常はサブ秒）でマルチリージョンレプリケーションを提供します。書き込み（リンク作成）用のプライマリとして1つのリージョンを指定し、すべてのリージョンが読み取りを提供できるようにします。
• または、CockroachDBやSpannerを使用すると、強力に整合性の取れたマルチリージョン読み取りが得られますが、書き込みの遅延コストが高くなります。
• Redisクラスタは、各リージョン内でレプリケートされます（プライマリ-レプリカ）。リージョン間のキャッシュは、データベースレプリケーションとローカルキャッシュウォーミングによって個別に設定されます。

7. 信頼性アプローチ

可用性目標：リダイレクトの99.99%は、月あたり最大4.3分のダウンタイムを意味します。

マルチリージョンデプロイメント：

• 少なくとも3つの地理的に分散されたリージョン（例：US-East、EU-West、AP-Southeast）にリダイレクトサービスをデプロイします。
• グローバルDNSベースのルーティング（Route 53のレイテンシーベースルーティングまたはanycast）を使用して、ユーザーを最も近いリージョンに誘導します。
• 各リージョンは、ローカルキャッシュとデータベースレプリカからリダイレクトを独立して提供できます。

障害処理：

• プライマリデータベースリージョンが障害を起こした場合、別のリージョンが昇格されます。DynamoDBグローバルテーブルでは、どのリージョンでも書き込みを受け入れられるため、単一の書き込みリーダーのフェイルオーバーはありません。
• Redisがリージョンで障害を起こした場合、リダイレクトサービスはデータベースにフォールバックします。データベースは一時的に負荷を処理でき、Redisはすぐに回復します。
• 分析パイプライン（Kafka）に問題がある場合、クリックイベントはバッファリングされます。Kafkaの耐久性により、データ損失はありません。分析の最終整合性が最大10分であるため、余裕があります。
• サービス間にはサーキットブレーカーが実装されています。データベースが遅い場合、リダイレクトサービスはキャッシュから提供し、正常に低下します（キャッシュされた結果またはキャッシュミスの場合は一時的なエラーを返します）。

ヘルスチェックと監視：

• 各サービスインスタンスにはヘルスチェックエンドポイントがあります。
• ロードバランサーは、非正常なインスタンスを自動的に削除します。
• 遅延パーセンタイル（p50、p95、p99）、エラーレート、キャッシュヒット率、キューラグのダッシュボードを備えた包括的な監視。
• SLO違反に対するアラート。

データの耐久性：

• DynamoDBは、リージョン間レプリケーションにより99.999999999%の耐久性を提供します。
• 追加の安全策として定期的なバックアップ。

8. 読み取り負荷の高いトラフィックとバイラルホットスポットへのスケーリング

読み取りと書き込みの比率は約10:1（月間12億読み取り対1億2000万書き込み）ですが、バイラルイベント中は、単一のリンクが1時間あたり数百万回のヒットを受ける可能性があります。

戦略：

• CDNエッジキャッシュは、最初で最も効果的な防御策です。バイラルリンクのリダイレクト応答は、世界中の何百ものエッジロケーションにキャッシュされます。5分間のTTLであっても、オリジンはエッジロケーションごとに5分あたり1回の要求しか見ません。
• エッジコンピューティング（Cloudflare WorkersまたはLambda@Edge）は、分散KVストア（Cloudflare KVやDynamoDB DAXなど）から読み取ることで、エッジでリダイレクトルックアップを完全に実行でき、オリジンへのヒットを排除します。
• Redisクラスタの自動スケーリング：キャッシュ負荷を監視し、リードレプリカを動的に追加します。
• 極端なホットスポットの場合、各リダイレクトサービスインスタンスのアプリケーションレベルのローカルキャッシュにより、Redisが圧迫されていても、最もホットなリンクはメモリから提供されます。

バイラルイベント中の分析：

• クリックイベントはKafkaに発行され、バースト的な書き込みをうまく処理します。
• 分析コンシューマーは、書き込み前にバッチ処理と集計を行うことで、書き込み増幅を削減できます。
• 必要に応じて近似カウント（ユニークビジターにはHyperLogLog）を使用しますが、総クリック数については単純なカウンターで十分です。

9. 不正利用防止

基本的な対策（完全な信頼と安全性は範囲外）：

• リンク作成時のレート制限：IPごとおよび認証済みユーザーごと（例：匿名の場合は1時間あたり100リンク、認証済みユーザーの場合は1000リンク）。
• URL検証：不正な形式のURLを拒否し、既知のフィッシング/マルウェアURLブロックリスト（例：Google Safe Browsing API）に対してチェックします。
• カスタムエイリアス検証：不快な単語や予約語のブロックリスト。
• レート制限に近づいた場合の匿名リンク作成のためのCAPTCHA。
• 報告された不正利用リンクを無効化する機能（手動または自動）。
• すべてのリンク作成イベントのログ記録と監査証跡。

10. 主要なトレードオフ

整合性 vs. 遅延：

• リンクマッピングのリージョン間での最終整合性を選択します。新しく作成されたリンクは、遠隔地のリージョンでは数百ミリ秒の間解決できない場合があります。これは、リンクを作成したユーザーが書き込みが即座に整合性の取れる最も近いリージョンにルーティングされ、リージョン間レプリケーションが高速であるため許容できます。分析については、10分間の最終整合性を明示的に受け入れます。

302 vs. 301リダイレクト：

• 302（一時）は、すべてのクリックを追跡し、宛先を変更することを可能にしますが、オリジン負荷を増加させます。301（永続）はより効率的ですが、ブラウザはそれを無期限にキャッシュします。私たちの妥協点：オリジンからは302を使用しますが、CDNエッジキャッシュを短いTTLで許可し、両方の長所を得ます。

コスト vs. パフォーマンス：

• DynamoDBのオンデマンド価格は、リクエストあたりのプロビジョニング済みよりも高価ですが、キャパシティプランニングなしでバースト的なトラフィックを処理します。この規模のサービスでは、ベースラインには自動スケーリング付きのプロビジョニング済みキャパシティを使用し、オーバーフローにはオンデマンドを使用します。
• CDNとエッジコンピューティングはコストを増加させますが、オリジンインフラストラクチャの必要性を劇的に削減し、ユーザーエクスペリエンスを向上させます。

運用複雑性 vs. 信頼性：

• DynamoDBグローバルテーブルを使用したマルチリージョンデプロイメントは、運用上の複雑さを増しますが、99.99%の可用性目標とグローバルな低遅延要件には不可欠です。
• Kafkaは、運用する別のシステムを追加しますが、信頼性の高い分析に必要な分離と耐久性を提供します。

ストレージ vs. 計算：

• 生のクリックイベントからオンザフライで計算するのではなく、日次分析カウントを事前に集計します。これにより、ストレージ効率とクエリパフォーマンスおよびシンプルさのバランスを取ります。

カスタムエイリアスのユニーク性：

• カスタムエイリアスは、生成されたコードと同じ名前空間を共有します。生成されたコード空間（正確に7つのbase62文字）を予約し、カスタムエイリアスに異なる長さにするか、生成された範囲に対してチェックするように要求します。よりシンプルなアプローチ：すべてのコード（生成されたものとカスタムのもの）を同じテーブルに入れ、条件付き書き込みにより、どちらの場合も一意性が保証されます。

11. 技術選択の概要

• グローバルロードバランシング：AWS Global Acceleratorまたはanycast DNSを備えたCloudflare
• CDNとエッジ：エッジワーカーを備えたCloudFrontまたはCloudflare
• コンピューティング：各リージョンのステートレスサービス用のKubernetesクラスタまたはECS/Fargate
• プライマリデータベース：DynamoDBグローバルテーブル（リンクマッピングと日次分析）
• キャッシュ：各リージョンのElastiCache Redisクラスタ
• メッセージキュー：クリックイベント用のAmazon KinesisまたはApache Kafka（MSK）
• 分析処理：リアルタイム集計用のKafka StreamsまたはFlink
• ID生成：小規模なコーディネーションストア（DynamoDBまたはZooKeeper）をバックエンドとする範囲ベースの割り当てサービス
• 監視：アラート用のCloudWatch、Prometheus、Grafana、PagerDuty

この設計は、書き込みパス（リンク作成）、読み取りパス（リダイレクト）、および分析パスを明確に分離し、それぞれが独立してスケーリング可能であるという点で、指定された要件を満たします。レイヤードキャッシュ戦略（エッジ、リージョナルRedis、ローカル）により、極端なバイラルトラフィックも正常に処理され、DynamoDBグローバルテーブルを使用したマルチリージョンアーキテクチャは、99.99%のSLAに必要な耐久性と可用性の保証を提供します。

1. ハイレベルアーキテクチャ

システムは、低レイテンシと高可用性を確保するために、グローバルに分散されたマルチリージョンアーキテクチャとして設計されています。各リージョンは、自己完結型のプレゼンスポイント（PoP）として機能します。

コアコンポーネント:

• グローバルロードバランサー（GLB）: DNSベースのルーティング（例：レイテンシベース、ジオベース）を使用して、ユーザーを最も近い正常なリージョンに誘導します。
• CDN（コンテンツデリバリーネットワーク）: アプリケーションサーバーの前に配置され、人気のあるリンクのリダイレクト応答（HTTP 301）をエッジでキャッシュし、バイラルコンテンツのレイテンシとインフラストラクチャへの負荷を劇的に削減します。
• リージョナルロードバランサー: リージョン内のトラフィックをステートレスWebサーバーに分散します。
• Webサーバー（APIゲートウェイ）: TLSを終端し、リクエストを適切なバックエンドサービスにルーティングします。
• リダイレクトサービス（リードパス）: GET /{short_id}リクエストを処理する、高度に最適化されたステートレスマイクロサービスです。キャッシュ優先、次にデータベースでルックアップを実行し、リダイレクトを発行します。これは最も重要でトラフィック量の多いコンポーネントです。
• リンクサービス（ライトパス）: 新しいショートリンクを作成するためのPOST /api/v1/linksを処理するマイクロサービスです。IDジェネレーターと連携し、データベースに書き込みます。
• アナリティクスサービス: GET /api/v1/links/{short_id}/analytics経由で分析データを提供するマイクロサービスです。専用のアナリティクスデータストアから読み取ります。
• IDジェネレーターサービス: ショートリンクに使用される、グローバルに一意で、おおよそ時間順にソート可能な64ビットIDを生成する専用サービス（例：Snowflakeベース）です。
• メッセージキュー（例：Kafka、AWS SQS）: クリティカルなリダイレクトパスと、クリティカルではないアナリティクス処理を分離します。リダイレクトサービスは、すべての成功したリダイレクトに対して軽量な「クリックイベント」をキューに発行します。
• アナリティクス取り込みプロセッサー: メッセージキューから読み取り、クリックイベントを処理し、アナリティクスデータストアと集計カウンターを更新するコンシューマーサービスです。

(概念図リンク)

2. データモデルとストレージの選択

特定のアクセスパターンに合わせて最適化された2つの別々のデータストアを使用します。

A. リンクマッピングストア

• 選択肢: Amazon DynamoDB with Global Tables または Apache Cassandra のような分散NoSQLキーバリューストア。
• 正当化: この選択は、大規模なスケーラビリティ、高可用性、および低レイテンシのキーベースのルックアップの必要性によって推進されます。主なリードパターンは short_id による直接ルックアップであり、これはキーバリューストアモデルに最適です。マルチリージョン、マルチマスター設定（DynamoDB Global Tablesのような）は、グローバルユーザー向けの低レイテンシの読み書きと、組み込みの災害復旧を提供します。
• スキーマ（linksテーブル）:
  • short_id（文字列、パーティションキー）：一意の7文字コードまたはカスタムエイリアス。
  • long_url（文字列）：宛先URL。
  • created_at（タイムスタンプ）：作成タイムスタンプ。
  • total_clicks（数値）：アナリティクスプロセッサーによって更新される、総クリック数のアトミックカウンター。

B. アナリティクスデータストア

• 選択肢: Apache Cassandra または Amazon Timestream のようなワイドカラムまたは時系列データベース。
• 正当化: このストアは、クリックイベントの非常に高い書き込みスループットを処理し、時間範囲（例：過去30日間）でデータを効率的にクエリする必要があります。ワイドカラムストアは、これを効果的にモデル化することを可能にします。
• スキーマ（clicks_by_dayテーブル）:
  • short_id（文字列、パーティションキー）：リンク識別子。
  • event_date（文字列、クラスタリングキー、フォーマット YYYY-MM-DD）：クリックの日付。
  • daily_count（カウンター）：その日のクリック数の分散カウンター。

この事前集計モデルは、必要なクエリ（「日ごとのクリック数」）に対して効率的です。必要であれば、生のイベントデータは、長期アーカイブのために安価なオブジェクトストア（S3のような）に保存できます。

3. ID生成戦略

• 生成されたID: 短く、一意で、非シーケンシャルなIDが必要です。Base62エンコーディング（[a-zA-Z0-9]）を使用した7文字の文字列は、62^7（約3.5兆）の一意の組み合わせを提供し、5年間で予想される72億リンクを十分にカバーします。
  1. IDジェネレーターサービスは、タイムスタンプ、リージョン/マシンID、シーケンス番号を組み合わせた、グローバルに一意の64ビット整数（TwitterのSnowflakeに類似）を生成します。これにより、単一障害点と競合が回避されます。
  2. リンクサービスは、ジェネレーターにIDを要求します。
  3. 次に、64ビット整数をBase62エンコードして short_id 文字列を作成します。
• カスタムエイリアス:
  1. ユーザーがカスタムエイリアスを送信すると、リンクサービスはエイリアスをキーとして links テーブルに対する直接読み取りを実行します。
  2. キーが存在しない場合、条件付き書き込み（例：put if not exists）を使用して新しいエントリの書き込みに進み、2人のユーザーが同時に同じエイリアスを要求する競合状態を防ぎます。
  3. キーが存在する場合、409 Conflictエラーを返します。

4. API設計

サービスはシンプルなRESTful APIを公開します。

• ショートリンクの作成: POST /api/v1/links
  • リクエストボディ: `{