大規模なURL短縮サービスの設計

ハイレベルアーキテクチャ（テキスト図とコンポーネント） - クライアント：Webブラウザ、モバイルアプリ。短いURL（short.example/abc1234）と短いURL作成用の書き込みAPIにアクセスします。 - CDN / Edge（CloudFront、Fastly）：着信ショートURLリクエストを受信するエッジレイヤー。エッジはリダイレクト応答（HTTP 301/302）をキャッシュし、レイテンシSLAを満たすために可能な限りオリジンに触れることなく提供します。 - Edgeルーティング / グローバルDNS（Route53、anycast）：書き込みAPIコールを最寄りのリージョンにルーティングし、ショートURLヒットを最寄りのエッジ/リージョンにルーティングします。ヘルスチェックとフェイルオーバーが設定されています。 - リージョンAPIゲートウェイ + ロードバランサー（API Gateway / ALB）：クライアントの書き込みと管理コールを受け入れます。アベイラビリティゾーン全体にデプロイされたコンテナ（ECS/Kubernetes）内の書き込みサービスにルーティングします。 - 書き込みサービス（ステートレスマイクロサービス）：入力を検証し、IDジェネレーターモジュールを介して短いトークンを生成し、マッピングをプライマリDBに書き込み、イベントをストリームに発行し、キャッシュを更新し、短いURLを返します。 - 読み取りパスサービス / リダイレクトサービス（ステートレス）：エッジからのキャッシュミスまたは直接ヒットを受信し、ローカルキャッシュ（Redisクラスター）をクエリし、DBにフォールバックし、適切なキャッシュヘッダーを持つリダイレクトを返します。 - 分散キャッシュ（リージョンごとのRedisクラスター、クラスター化/レプリケーション）：マイクロ秒応答のためにホットルックアップがここに格納されます。各リージョンには、AZ全体にレプリケーションを持つ独自のRedisクラスターがあります。 - プライマリストレージ（DynamoDBまたはCassandra/Scylla代替）：マッピングshort_id -> long_url、メタデータ、有効期限、所有者、作成タイムスタンプを格納します。高スループットの読み書き、TTLサポート、マルチリージョンレプリケーションのために選択されました。 - イベントストリーム（Kinesis / Kafka）：すべての書き込みは、分析、インデックス更新、キャッシュ無効化メッセージ、および非同期処理のためにイベントを生成します。 - バックグラウンドワーカー（コンテナ化）：TTLクリーンアップ、再利用キュー、分析、および非同期レプリケーションチェックを処理します。 - モニタリングと運用：Prometheus/Grafana、CloudWatch、アラート、自動化されたランブック。 コンポーネント間のやり取り（読み取り）：ユーザーがショートURLにヒット -> エッジキャッシュがキャッシュされたリダイレクトをチェック -> ヒットした場合、キャッシュされたリダイレクトを返します（<5ms）。ミスの場合、エッジはリージョンLBに転送 -> リダイレクトサービスがRedisキャッシュをクエリ -> ヒットした場合、リダイレクトを返し、エッジがキャッシュします。ミスの場合、リダイレクトサービスがプライマリDBをクエリ -> リダイレクトを返します -> Redisにセットし、エッジがリダイレクトをキャッシュします。 コンポーネント間のやり取り（書き込み）：クライアントがAPIを呼び出す -> APIゲートウェイ -> 書き込みサービス -> IDジェネレーターがトークンを生成 -> 書き込みサービスがプライマリDBにマッピングをTTL付きで書き込む -> 書き込みサービスがストリームにイベントを発行 -> 書き込みサービスがRedisキャッシュに書き込み、ショートURLを返します。バックグラウンドワーカーは、必要に応じて分析や他のリージョンにイベントを非同期でレプリケートします。 URL短縮アルゴリズムとキー生成戦略 目標：最大7文字の英数字トークン、推測不可能（シーケンシャルなトークンなし）、衝突確率が低い、再現可能な障害/再試行動作。 スペースと制約：62^7 ~= 3.52e12個の可能なトークン。月間新規トークン目標1億はスペースに対して小さいですが、簡単な列挙を確実にしないようにする必要があります。 選択された戦略（プライマリ）： - 新しいショートURLごとに暗号学的に安全なランダム生成を使用します。64ビットの暗号学的に安全なランダム整数を生成し、拒否サンプリングを適用してモジュロバイアスなしで範囲[0, 62^7 - 1]にマッピングし、次にbase62エンコードして正確に7文字にします。これにより、7文字のスペース全体に均一にランダムなトークンが得られ、シーケンシャル性はなくなります。 - コミットする前に、DBへのアトミック挿入を試み、short_idをプライマリキーとして一意性を強制します。挿入がまれな衝突のために失敗した場合、新しいランダムトークンで再試行します（予想される衝突確率は無視できるほど小さいです。予想される再試行は<< 1です）。 シーケンシャルIDまたは増加するカウンターの双射エンコーディングを使用しない理由：シーケンシャルまたはタイムスタンプ由来のIDは推測可能であり、列挙とスクレイピングを可能にします。推測不可能性を満たすためにこれらを拒否します。 検討された代替案と却下されたもの：長いURLの切り捨てられた暗号ハッシュ（例：SHA256の最初の7文字のbase62）。決定論的なマッピングが攻撃者が人気のあるURLをハッシュできる場合にトークンを推測可能にするため却下されました。また、切り捨てると衝突がより頻繁になります。HMAC（longURL、secret）を使用して決定論的で推測不可能なものにすることはできましたが、決定論的なマッピングは複数の入力バリエーションにわたるショートトークンの再利用を防ぎ、TTL/取り消しを複雑にします。 データベーススキーマとストレージ技術（正当化付き） 選択されたプライマリストア：DynamoDB（AWS）またはマネージドCassandra/Scylla（セルフホストの場合）。主な理由：マネージド、水平スケーラブル、高スループットの読み書き、組み込みTTLサポート、マルチリージョンレプリケーション（DynamoDBグローバルテーブル）、および適切にプロビジョニングされていればシングルディジットミリ秒アクセス。これは、99.9％のアップタイムと簡単な運用にとって重要です。 スキーマ（論理、DynamoDBスタイル）： - テーブル：url_map - パーティションキー：short_id（文字列、7文字） - 属性：long_url（文字列）、created_at（タイムスタンプ）、expires_at（タイムスタンプ）、owner_id（文字列）、metadata（JSONブロブ）、version（int）、deleted（ブール値）、deletion_marked_at（タイムスタンプ）、click_count（数値、オプション）、analytics_shard_id（クリックシャーディング用） - TTL属性：DB TTL機能による自動有効期限切れのためのexpires_at インデックス：リダイレクトパスに追加のグローバルセカンダリインデックスは不要です。オプションで、管理とユーザーによる一括削除のためのowner_id上のGSI、および再利用処理のためのdeletion_marked_at上のGSI。 正当化：キーバリューストアのアクセスパターンはDynamoDBにきれいにマッピングされます。short_idは自然な一意キーです。TTLは組み込みです。他のクラウドプロバイダーの場合は、TTL付きのCosmos DBまたは行ごとのTTL付きのScylla/Cassandraを使用します。 キャッシング戦略と無効化 目標：スケーリング時に95パーセンタイルリダイレクトを10ms未満で達成し、DB負荷を最小限に抑え、マルチリージョンをサポートする。 レイヤー： - リダイレクト応答のエッジキャッシュ（CDN）。エッジは、マッピング有効期限から計算されたキャッシュTTLを持つ301/302をキャッシュします。最大キャッシュTTLは残りのTTLに制限されます。新しく作成されたショートURLの場合、最初のN秒間は短いキャッシュTTLを設定して一貫性を確保します。 - リージョンRedisクラスター（クラスターモードが有効なElastiCache Redisクラスター）。Redisはマッピングshort_id -> シリアライズされたリダイレクト応答と有効期限メタデータを格納します。RedisセットTTLはマッピング有効期限に等しくなります。 - リダイレクトサービス内のローカルインプロセスLRUキャッシュ（小）でマイクロヒットを処理します。 キャッシュヒットの仮定とサイジング： - ショートURLのCDNヒット率70％（人気のあるリンク）、エッジミスに対するRedisヒット率（リージョンアクセスパターン）で85％を仮定します。これらは使用状況に基づいて調整可能です。 キャッシュのポピュレーションと無効化： - 書き込み時：書き込みサービスはDBに書き込み、すぐにリージョンRedisに書き込み、キャッシュ無効化イベントをイベントストリームに発行します。すべてのリージョンが購読します。これにより、キャッシュがウォームでほぼリアルタイムで一貫性が保たれます。 - 更新または削除時：書き込みサービスはDBを更新し、無効化イベントを発行します。購読者はRedisからキーを削除し、キャッシュ制御ヘッダーを介してエッジキャッシュを無効化するか、CDNにPURGE/Cache APIを送信します（または短いキャッシュTTLを0に設定してエッジが最新情報を取得できるようにします）。パージコールは最小限に抑えられます。TTLベースの有効期限切れとパブ/サブ無効化を優先します。 - TTL有効期限の場合：DB TTLに依存して行を削除し、バックグラウンドワーカーがイベントを発行してキャッシュをクリーンアップし、トークンを再利用キューに追加します。 読み取りパス（詳細）とスループット計算 トラフィック計算（ベースライン月間 -> 秒間）： - 書き込み：100,000,000 / 30 / 24 / 3600 ~= 38.6書き込み/秒（平均）。ピーク係数5を日次/スパイクトラフィックに仮定 -> 約193書き込み/秒（ピーク）。 - 読み取り（リダイレクト）：10,000,000,000 / 30 / 24 / 3600 ~= 3,858読み取り/秒（平均）。ピーク係数5 -> 約19,290読み取り/秒（ピーク）。 - 読み書き比率：指定どおり100:1。 読み取りパス（レイテンシ最適化）： 1. クライアントがshort.example/abc1234をリクエスト -> DNSがCDNエッジノードに解決します。 2. エッジキャッシュルックアップ：リダイレクトがキャッシュされている場合、HTTP 301/302を直ちに返します。これは、人気のあるリンクのほとんどのリクエストをカバーします。 3. エッジミスの場合：リクエストはリージョンLB -> リダイレクトサービスに転送されます。 4. リダイレクトサービスはインプロセスキャッシュ（非常に小さい） -> Redisクラスターget(short_id)を参照します。Redis GETはネットワークに応じてミリ秒未満です（通常、リージョン内では1ms未満）。Redisヒットの場合、サービスはリダイレクトを返し、エッジは適切なTTLでキャッシュします。 5. Redisミスの場合：サービスはプライマリDB（DynamoDB GetItem）をクエリします。これはシングルディジットミリ秒、通常は3-6msです。サービスはリダイレクトを返し、Redisとエッジキャッシュをポピュレートします。 スループット機能とサイジング例： - Redisクラスター：ピーク時20k読み取り/秒を仮定します。3〜5個のシャードをレプリケーションでデプロイして、50k+ ops/秒を処理し、ヘッドルームを提供します。各シャードは10k ops/秒（適切なノードタイプ）用にサイズ設定されます。HAのために各AZに読み取りレプリカがあります。 - DynamoDB：書き込み約200 TPS（ピーク）とキャッシュミスの読み取りのための容量が必要です。キャッシュヒット率が全体で90％の場合、DB読み取り負荷はピーク時に約1,929読み取り/秒です。最終的なピークと安全係数2で、4kの強力に一貫性のある読み取り/秒（または読み取りRCUコストを半分にするために最終的に一貫性のある読み取りを使用）をプロビジョニングします。 書き込みパス（詳細）とスループット 書き込みパス： 1. クライアントがAPIに作成リクエストを送信 -> APIゲートウェイ -> リージョンLB -> 書き込みサービス。 2. 書き込みサービスはURLを検証します（サニタイズ、オプションでマルウェアチェック）、レート制限とクォータをチェックします。 3. IDジェネレーター：CSPRNGを使用してトークンを作成します。short_idが存在しないことを条件とするDBへの挿入を試みます（アトミック）。PutItemが既存キーのために失敗した場合（まれ）、生成を再試行します。挿入にはlong_url、created_at、expires_atが含まれます。 4. 挿入が成功すると、書き込みサービスはRedisに書き込んで即座にキャッシュをウォームアップし、分析とクロスリージョン伝播のためにイベントをストリームに発行します。 5. クライアントにショートURLを返します。 書き込みのスループットサイジング： - ベースライン39書き込み/秒（平均）、プロビジョニングされたピーク約200書き込み/秒。DynamoDBは、適切な容量またはオンデマンドモードで、数千の書き込み/秒を容易にサポートします。 - ステートレス書き込みサービスは水平スケーリングされます。各インスタンスは200〜500 req/sを処理できると仮定します。ヘッドルームを維持するためにオートスケーリンググループを設定します。200書き込み/秒（ピーク）の場合、2〜4個のインスタンスで十分です。冗長性とレート制限などの他の処理のために10〜20個を割り当てます。 スケーリング戦略と10倍の成長への対応 シナリオ：10倍の成長は、月間10億件の書き込みと月間1000億件のリダイレクトを意味します。 戦略： - オートスケーリング：すべてのステートレスサービス（書き込み/リダイレクト）は、CPU/RPSとリクエストレイテンシに基づいて自動スケーリングします。コンテナにはクラスターオートスケーラーを使用します。 - キャッシュスケーリング：Redisシャードを追加し、メモリを増やします。Redisクラスターモードは動的な再シャーディングを可能にします。CDNはエッジスケーリングを自動的に処理します。 - DBスケーリング：DynamoDBはオンデマンドスケーリングをサポートするか、書き込み/読み取り容量を増やします。セルフホストのCassandra/Scyllaの場合は、ノードを追加してトークンを再分散します。 - パーティショニング：DynamoDBハッシュキーはすでにパーティションに分散されています。Cassandraの場合は、パーティションを小さく保つのに十分なノードを確保します。 - レート制限とバックプレッシャー：突然のスパイクに対して、ユーザーごとおよびAPIキーごとのレート制限を適用し、非クリティカルな作業（分析）のためにバックグラウンドタスクをキューに入れます。グレースフルデグラデーション（例：悪用されたクライアントの新規作成を拒否する）を実装し、リダイレクトに影響を与えないようにします。 - グローバルトラフィック：より多くのリージョンを追加し、データをレプリケートします。クロスリージョンRedis読み取りレプリカを追加するか、オンデマンド読み取りでウォームアップされたローカルキャッシュに依存します。 10倍後の容量見積もり： - ピーク読み取り約20万/秒。90％のキャッシュヒット率の場合、DB読み取りはピーク時に約2万/秒です。DBの前にDynamoDB/DAXまたはマネージドキャッシュが必要になります。Redisクラスターは数百のシャードにスケーリングされ、CDNはグローバル負荷を削減するための主要な役割を果たし続けます。 マルチリージョンデプロイメントと一貫性モデル 選択されたモデル：イベント発生時の整合性を持つアクティブ-アクティブマルチリージョン。非クリティカルデータにはクロスリージョンでのイベント発生時の整合性を使用します。DynamoDBグローバルテーブルまたはCassandraマルチDCレプリケーションを使用します。 理由とCAPトレードオフ： - 要件：99.9％のアップタイムとクロスリージョン災害復旧。可用性とパーティション耐性（AP）を厳密な整合性（CP）よりも優先します。リダイレクトはリージョンパーティション中でも利用可能でなければならないためです。新しく作成されたショートURLが別のリージョンで利用可能になるまでのレプリケーションのわずかな遅延は許容されます。URLを作成したユーザーは通常、同じリージョンで即座に使用し、ローカル書き込みとキャッシュウォームアップによりそれが見えるようになります。 - 実装：書き込みサービスはローカルリージョンDB（DynamoDBローカルまたは同じリージョンテーブル）に書き込み、その後他のリージョンへのレプリケーションはグローバルテーブルを介して行われます。リージョン内の読み取りは、ローカルを優先的に読み取ります。書き込み後の強力なローカル読み取り一貫性のために、書き込み直後に同じリージョンでDynamoDBの強力に一貫性のある読み取りを使用するか、単に即座のキャッシュウォームアップに依存して、書き込み元のリージョンでリダイレクトが機能することを保証します。 トレードオフ： - イベント発生時の整合性は、グローバルな可用性を簡素化し、読み取りのレイテンシを低減します。レプリケーションが完了するまで、リージョンAで作成されたショートURLがリージョンBで見えない可能性がある短いウィンドウを許可します。これは、主なSLAがリダイレクトの可用性とレイテンシに関係するため、受け入れます。 - 厳密なクロスリージョン整合性が必要な場合、クロスリージョン同期レプリケーションを実装する必要がありますが、これは書き込みレイテンシを大幅に増加させ、パーティション中の可用性を低下させます。したがって却下されました。 TTL有効期限とURL再利用メカニズム 要件：ショートURLごとに設定可能なTTL（デフォルト5年）、有効期限切れのURLは再利用可能であること。 メカニズム： - DB TTL属性（expires_at）を使用します。DynamoDBはTTL経過後にアイテムを自動的に削除しますが、削除は最終的に一貫性があり、即時ではない場合があります（一部のシステムでは最大48時間かかる場合があります）。したがって、アクティブな再利用パイプラインを実装します。 - expires_atが近づくと（例：24時間以内）、バックグラウンドワーカーはURLを有効期限切れとしてマークし、ストリームを介してイベントをプッシュします。これにより、キャッシュは短いTTLを設定し、パージの準備ができます。 - 実際の有効期限切れ時に、バックグラウンドワーカーは有効期限切れの行をスキャンし（deletion_marked_at上のGSIまたはテーブルTTLイベントを使用）、キーをメタデータ（short_id、deletion_marked_at、original_expires_at）とともに再利用キューに移動します。 - 再利用ポリシー：有効期限切れ後、設定可能な猶予期間（例：30日）を導入し、その間、ショートIDはトームストーン（削除フラグとトームストーンレコードを保持）され、即時の再利用を防ぎ、レプリケーションラグとユーザーの異議申し立てから保護します。トームストーン期間中、ショートIDは404または「このリンクは期限切れです」ページに解決されます。クリックは監査のためにログに記録されます。 - 猶予期間後、再利用ワーカーはショートIDを再利用可能なトークンプール（KafkaトピックまたはDynamoDBトークンプールテーブル）に移動します。プール内のトークンはリサイクルでき、再利用されたトークンにはクールダウンが含まれ、明示的に要求されない限り、同じ所有者に即座に再発行されることはありません。 - 再利用の衝突と悪用を回避するために、最近使用されたトークンのトームストーンインデックスを維持し（サイズは制限され、例：別のテーブルに1年間保持）、再利用前にチェックします。あるいは、トークンを再利用する代わりに、7文字のスペースが大きいため、リサイクリング率を非常に低く保つことを優先します。 障害モードと復旧 1) リージョンまたはグローバルエッジプロバイダーの障害におけるCDN / エッジ障害 - 影響：エッジキャッシングが停止し、より多くのリクエストがリージョンリダイレクトサービスとバックエンドキャッシュにヒットし、負荷とレイテンシが増加します。 - 回復：DNS/anycastによって他のエッジまたはフォールバックオリジンにトラフィックがリダイレクトされます。リダイレクトフリートを自動スケーリングし、インスタンス数を増やします。オリジンシールドを使用し、オリジンフェイルオーバーを設定します。エッジが回復するまでオリジンから直接リダイレクトを提供します。 2) プライマリDBリージョンの障害（完全なAZ/リージョン障害） - 影響：ローカルDBが利用できなくなり、そのリージョンから書き込みと読み取りを提供できなくなります。 - 回復：グローバルテーブルを介して別のリージョンにフェイルオーバーします。DNSとAPIゲートウェイを正常なリージョンにルーティングします。データは非同期でレプリケートされるため、書き込みが事前にレプリケートされていない限り、障害が発生したリージョンでの最近の書き込みは短時間失われる可能性があります。システムはこの状況を受け入れ、高可用性を実現します。リージョンが復旧したら、バックグラウンドの整合性チェックが競合を修復しようとします。 3) Redisクラスターの障害またはパーティション - 影響：キャッシュミスが増加し、DB負荷が増加し、レイテンシが増加します。 - 回復：クライアントはDB読み取りにフォールバックします。DB読み取り容量をスケールアップするか、DAX（DynamoDB Accelerator）または追加のRedisノードを有効にします。DBスナップショットからRedisクラスターを再構築するか、分析/ホットキーリストを使用してプリフェッチすることでキャッシュをウォームアップします。Redis SentinelまたはマネージドRedisクラスターと自動フェイルオーバーを使用して、ノードレベルの冗長性を確保します。 4) IDジェネレーターサービスのバグによる衝突またはレート制限の枯渇 - 影響：書き込み失敗、重複トークンエラー、または新規トークン作成の失敗。 - 回復：ジェネレーターをステートレスCSPRNGベースで設計します。バグが検出された場合、以前の安定したバージョンにロールバックし、リクエストをフォールバックジェネレーター実装（例：別のRNGライブラリまたはHMACソルトと組み合わせた短期間のバックカウンター）にルーティングします。衝突率の監視を追加します。衝突率がわずかな閾値を超えた場合、新規トークンの発行を停止し、修正されるまで5xxを返します。 5) イベントストリームコンシューマーのバックログまたはワーカー障害 - 影響：キャッシュ無効化、分析処理、および再利用が遅延します。 - 回復：コンシューマーを自動スケーリングし、無効化および再利用トピックを優先し、新規コンシューマーが追いつけるように保持期間を設定します。必要に応じてDBから状態を再構築します。 主要なトレードオフと検討された代替案 1) ストレージの選択：DynamoDB（マネージドNoSQL） vs RDBMS vs Cassandra/Scylla - 選択：DynamoDB（またはマネージドCassandra）。理由：水平スケーリング、TTL、マネージドサービス、マルチリージョン用のグローバルテーブル。RDBMSはスケーリングの複雑さ、シャーディング、および極端なスケールでの単一行レイテンシの遅さのため却下されました。 2) トークン生成：ランダムトークン vs シーケンシャルカウンター vs 長いURLのハッシュ - 選択：暗号学的に安全なランダムトークンを7文字のbase62にマッピング。理由：推測不可能、均一な分布、スケーリングが容易、DBバックの衝突解決による小さな衝突確率。シーケンシャルカウンターは推測可能であるため却下されました。決定論的なハッシュは、衝突リスクが高く予測可能であるため却下されました。 3) アクティブ-アクティブマルチリージョン vs アクティブ-パッシブフェイルオーバー - 選択：イベント発生時の整合性を持つアクティブ-アクティブ。理由：可用性が高く、最寄りのリージョンへのクライアントルーティングが低レイテンシで簡単です。アクティブ-パッシブはより強力な整合性を提供しますが、フェイルオーバー時間を増加させ、レイテンシ/可用性要件に違反する可能性があります。 4) トークンの再利用 vs トークンを再利用しない - 選択：猶予期間/トームストーン期間付きで再利用可能。理由：トークンスペースは広いため、頻繁な再利用は必要ありませんが、仕様により再利用が必要です。トームストーン保持と再発行前のクールダウンにより安全性が向上します。トークンが病的なシナリオで枯渇した場合、長年後に名前空間を節約する必要がある可能性があるため、再利用しないことは却下されました。 5) エッジでのキャッシング vs オリジンのみ - 選択：短いTTLを持つヘビーエッジキャッシング。理由：グローバルユーザーの95パーセンタイルレイテンシを10ms未満で達成します。オリジンのみは、オリジンレイテンシとクロスリージョンホップがレイテンシSLAを超えるため却下されました。 運用上の考慮事項と数値 - SLO：99.9％のアップタイム。エッジ、Redis、DB、書き込みサービスのヘルスとレイテンシを監視します。エラー率と95パーセンタイルレイテンシのアラート閾値を設定します。 - 容量計画の例：ベースライントラフィックの場合、DBを約4k読み取り/秒および約200書き込み/秒（ピーク）用にプロビジョニングします。Redisクラスターを約30k ops/秒用にサイズ設定します。10倍スケールの場合、DBを約40k読み取り/秒、Redisを約300k ops/秒（オートスケーリングシャード付き）用にプロビジョニングします。 - セキュリティと悪用対策：APIキー/IPごとのレート制限、URLスキャン（オプションで非同期）、アカウントごとのクォータ強制。 WAFとAPIキーでエンドポイントを保護します。 - データ保持とプライバシー：ユーザーがTTLを削除/延長するための管理APIを提供します。監査可能性とトームストーン保持のためのソフトデリートセマンティクス。 概要 この設計は、マルチレイヤーキャッシングアプローチ（CDNエッジ + リージョンRedis）を、水平スケーラブルなNoSQLストア（DynamoDBまたはCassandra）とステートレスマイクロサービスでバックアップし、スループットとレイテンシの要件を満たします。トークン生成は、推測不可能性を保証するために、DBバックの衝突解決を備えたCSPRNGベースのbase62 7文字トークンを使用します。システムは、アップタイムとレイテンシSLAを満たすために、可用性とパーティション耐性（アクティブ-アクティブマルチリージョンイベント発生時の整合性）を優先し、再利用の回避のためにトームストーン猶予期間を持つ再利用パイプラインとDB TTLによって処理される再利用とTTLを扱います。アーキテクチャは、10倍の成長に対応するためにオートスケーリングとシャーディングで水平にスケーリングし、99.9％のアップタイム目標を満たすために一般的な障害モードの回復パスを含みます。

このシステム設計は、月間1億件の新規短縮URL作成と100億件のリダイレクト処理能力を持ち、厳格なレイテンシと稼働時間の要件を満たす、堅牢でスケーラブル、かつ高可用なURL短縮サービスのアウトラインを示しています。 全体的なアーキテクチャの説明: アーキテクチャは、マイクロサービスアプローチを活用し、高可用性、スケーラビリティ、低レイテンシを実現するように設計されています。主要なコンポーネントは以下の通りです。 1. **ロードバランサー（例：AWS ELB/GCP Load Balancer/Nginx）**: 受信トラフィックをサービスインスタンスに分散させます。 2. **APIゲートウェイ（例：AWS API Gateway/Kong）**: APIリクエスト、認証、レート制限を処理し、トラフィックを適切なバックエンドサービスにルーティングします。 3. **短縮サービス（書き込みパス）**: 新しい短縮URLを作成するリクエストを処理するステートレスマイクロサービスです。キー生成サービスとデータベースと連携します。 4. **リダイレクトサービス（読み取りパス）**: 短縮URLを長URLに解決し、HTTP 301/302リダイレクトを実行する、高度に最適化されたステートレスマイクロサービスです。キャッシュを多用します。 5. **キー生成サービス**: 一意でランダムな短縮URLキーのプールを事前に生成・管理する専用サービスです。推測困難性を保証し、衝突を回避します。 6. **データベース（例：Apache Cassandra）**: 短縮URLマッピングの主要な永続ストレージです。高い書き込み/読み取りスループット、水平スケーラビリティ、マルチリージョンレプリケーション機能により選択されました。 7. **分散キャッシュ（例：Redis Cluster）**: 頻繁にアクセスされる短縮URLマッピングを保存し、データベースの負荷を軽減し、低レイテンシのリダイレクトを実現します。 8. **メッセージキュー（例：Apache Kafka/AWS SQS）**: 分析用のイベント発行、キャッシュ無効化、URL有効期限切れなど、サービス間の非同期通信に使用されます。 9. **分析サービス**: メッセージキューからイベントを消費し、クリック数を追跡し、レポートを生成し、使用パターンを監視します。 10. **有効期限切れ・回収サービス**: 有効期限切れのURLを特定し、マークを付け、キー生成サービスのプールに再利用のために戻すバックグラウンドワーカーサービスです。 11. **CDN（コンテンツデリバリーネットワーク、例：Cloudflare/Akamai）**: グローバルユーザーのレイテンシとオリジンサーバーの負荷をさらに軽減するために、エッジでのリダイレクトキャッシュに（オプションですが強く推奨されます）。 連携: * **書き込みパス**: ユーザー -> ロードバランサー -> APIゲートウェイ -> 短縮サービス -> キー生成サービス（キー取得） -> データベース（マッピング書き込み） -> メッセージキュー（'new_url'イベント発行） -> キャッシュ（更新/書き込みスルー）。 * **読み取りパス**: ユーザー -> ロードバランサー -> CDN（ヒットした場合、リダイレクト） -> リダイレクトサービス（ローカルキャッシュ -> 分散キャッシュ -> データベースを確認） -> リダイレクト。 URL短縮アルゴリズムとキー生成戦略: 推測困難性、一意性、および7文字の制限を満たすために、事前生成戦略を採用しています。 1. **キー生成サービス**: このサービスは、7文字の英数字文字列（例：暗号学的に安全な疑似乱数生成器を使用）を継続的に生成します。文字セットには `a-z`、`A-Z`、`0-9` が含まれ、合計62文字です。7文字の文字列は 62^7 の一意なキーを可能にし、約3.5兆となり、月間1億URLの要件をはるかに超えます。 2. **一意性チェック**: プールに追加する前に、各生成キーはデータベース（または専用の一意キー格納庫）に対して一意性がチェックされます。これは生成時の1回限りのチェックであり、短縮リクエスト時のチェックではありません。 3. **キープール**: 一意なキーは、高可用性で高速アクセスのプール（例：Redis Setまたは'status'フィールドを持つCassandraの専用テーブル、'available'のようなステータスフィールド）に保存されます。キー生成サービスは、キーが常にすぐに利用可能であることを保証するために、大きなバッファ（例：数十億キー）を維持します。 4. **短縮プロセス**: ユーザーが新しい短縮URLをリクエストすると、短縮サービスはキー生成サービスにキーを要求します。キー生成サービスは、利用可能なキーをプールからアトミックにポップし、「使用中」とマークし、返します。これにより、高負荷時の競合が回避されます。 5. **衝突回避**: 一意なキーを事前に生成してアトミックに割り当てることで、実際の短縮リクエスト時の衝突は事実上排除されます。データベースも、最終的な保護策として `short_url_key` に対する一意性制約を強制します。 データベーススキーマとストレージ技術の選択: データベース選択: **Apache Cassandra**（またはマネージド代替としてAWS DynamoDB）。 選定理由: * **高い書き込み/読み取りスループット**: Cassandraは、高ボリューム、低レイテンシの操作のために設計されており、100:1の読み書き比率と数十億回の読み取りに最適です。 * **水平スケーラビリティ**: ノードを追加することで簡単にスケールし、データと負荷をクラスター全体に分散させます。 * **高可用性 & 耐障害性**: データは複数のノードとデータセンターにレプリケートされ、ノード障害が発生した場合でも継続的な運用を保証します。 * **結果整合性**: このユースケースでは許容されます。新しいURLがリージョン全体に伝播するのに数ミリ秒かかる場合がありますが、コア機能には影響しません。 * **シンプルなキーバリュールックアップ**: 主要なアクセスパターンは `short_url_key` から `long_url` へのマッピングであり、Cassandraはこの点で優れています。 スキーマ（キースペース：`url_shortener`、テーブル：`short_urls`）: ``` CREATE TABLE url_shortener.short_urls ( short_url_key text PRIMARY KEY, -- パーティションキー、7文字の英数字 long_url text, user_id text, -- オプション、ユーザー固有のURL用 created_at timestamp, expires_at timestamp, click_count counter, -- アトミックインクリメント用のCassandraカウンター型 status text -- 'active', 'expired', 'reclaimed' ); ``` キャッシング戦略とキャッシュ無効化アプローチ: キャッシュは、リダイレクトレイテンシを10ms未満に抑え、月間100億件のリダイレクトを処理するために不可欠です。 戦略: 1. **マルチティアキャッシング**: * **CDN（エッジキャッシュ）**: 地理的に分散されたPoP（Point of Presence）でリダイレクトをキャッシュします。これは読み取りリクエストの最初の防御線です。 * **分散キャッシュ（Redis Cluster）**: `short_url_key` から `long_url` へのマッピングを保存する、中央の高性能キャッシュです。各エントリには `expires_at` も保存されます。 * **インメモリキャッシュ**: 各リダイレクトサービスインスタンスは、最も頻繁に使用されるURLのために、小さく高速なインメモリキャッシュを維持します。 2. **リードスルー**: リダイレクトサービスがリクエストを受信すると、まずインメモリキャッシュを確認し、次にRedis Clusterを確認します。見つからない場合は、Cassandraから取得し、マッピングをRedisとローカルキャッシュに保存してからリダイレクトします。 3. **ライトスルー**: 新しいURLが短縮されると、短縮サービスはマッピングをCassandraに書き込み、次にRedis Clusterに即座に書き込みます。 キャッシュ無効化: 1. **TTLベースの有効期限切れ**: Redisとインメモリキャッシュのエントリには、設定可能なTTL（例：5分またはURLの `expires_at` に合わせた時間）があります。これにより、結果整合性が処理され、古いデータが永久に残らないことが保証されます。 2. **明示的な無効化**: URLが有効期限切れまたは回収サービスによって回収された場合、「url_expired」イベントがメッセージキューに発行されます。キャッシュ無効化ワーカーはこのイベントを消費し、Redis Clusterから対応するエントリを明示的に削除します。CDNキャッシュは、API呼び出しまたは適切な `Cache-Control` ヘッダーと短いmax-ageを設定することで無効化されます。 読み取りパスと書き込みパスのスループット計算: 仮定：1ヶ月 = 2,592,000秒。 書き込みパス（月間1億件の新規URL短縮）: * **平均スループット**: 100,000,000 URL / 2,592,000秒 ≈ 38.6書き込み/秒。 * **ピークスループット**: ピークを平均の3倍と仮定すると、約120書き込み/秒に対応するように設計します。 * **フロー**: ロードバランサー -> APIゲートウェイ -> 短縮サービス（キー生成サービスからキーを要求、Cassandraに書き込み、Redisに書き込み、Kafkaにイベント発行）。 * **コンポーネント**: 短縮サービス、キー生成サービス、Cassandraノード、Redisノード、Kafkaブローカーの複数のインスタンス。 * **レイテンシ目標**: 書き込みは100ms未満（読み取りほど重要ではない）。 読み取りパス（月間100億件のリダイレクト）: * **平均スループット**: 10,000,000,000 リダイレクト / 2,592,000秒 ≈ 3,858読み取り/秒。 * **ピークスループット**: ピークを平均の3倍と仮定すると、約12,000読み取り/秒に対応するように設計します。 * **フロー**: ユーザー -> CDN（ヒットした場合、リダイレクト） -> ロードバランサー -> リダイレクトサービス（インメモリキャッシュ -> Redis Cluster -> Cassandraを確認） -> リダイレクト。 * **キャッシュヒット率**: Cassandraの負荷を軽減するために、>95%のキャッシュヒット率（CDN + Redis）を目指します。 * **実効DB読み取り数**: 12,000読み取り/秒 * 5%（キャッシュミス）= 600読み取り/秒がCassandraへ。 * **レイテンシ目標**: 95パーセンタイルで10ms未満。 * **コンポーネント**: リダイレクトサービス、Redis Clusterノード、Cassandraノードの多数のインスタンス。CDNが重要な役割を果たします。 スケーリング戦略: 1. **水平スケーリング（ステートレスサービス）**: 全てのステートレスサービス（APIゲートウェイ、短縮サービス、リダイレクトサービス、キー生成サービス、分析サービス、有効期限切れ・回収サービス）は、ロードバランサーの後ろに複数のインスタンスとしてデプロイされます。CPU使用率、メモリ、またはリクエストキューの深さ（例：Kubernetes HPAまたはAWS Auto Scaling Groupsを使用）に基づいて、インスタンスを追加することでスケールアウトできます。 2. **データベーススケーリング（Cassandra）**: Cassandraは、クラスターにノードを追加することで水平にスケールします。データは自動的に再分散されます。これにより、ストレージ容量と読み書きスループットが増加します。 3. **キャッシュスケーリング（Redis Cluster）**: Redis Clusterはシャーディングとレプリケーションを提供し、マスターおよびレプリカノードを追加することで水平にスケールできます。 4. **メッセージキューのスケーリング（Kafka）**: Kafkaは本質的にスケーラブルであり、ブローカーとパーティションを追加することでスループットを向上させることができます。 5. **CDN**: オリジンサーバーからの読み取りトラフィックのかなりの部分をオフロードし、読み取りパスをグローバルに効果的にスケールします。 6. **マイクロサービス**: モジュール化されたアーキテクチャにより、個々のサービスを特定の負荷要件に基づいて独立してスケールできます。 マルチリージョンデプロイメントとデータ整合性モデル: 99.9%の稼働時間とディザスタリカバリを実現するために、サービスは少なくとも2つの地理的リージョン（例：米国東部と欧州西部）でアクティブ・アクティブ構成でデプロイされます。 デプロイメント: * 各リージョンは、全てのサービス（ロードバランサー、APIゲートウェイ、短縮/リダイレクトサービス、キー生成サービス、Cassandraクラスター、Redis Cluster、Kafkaクラスターなど）の完全で独立したスタックをホストします。 * グローバルロードバランサー（例：レイテンシベースルーティングを備えたAWS Route 53またはグローバルトラフィックマネージャー）は、ユーザーを最も近い正常なリージョンに誘導します。 データ整合性モデル: * **Cassandraマルチデータセンターレプリケーション**: Cassandraの `NetworkTopologyStrategy` を使用して、リージョン間クラスター間でデータを非同期にレプリケートします。各リージョンはデータの完全なコピーを保持します。 * **書き込み**: 書き込みは通常、低レイテンシのためにプライマリリージョン内で `LOCAL_QUORUM` 一貫性で行われます。Cassandraの組み込みレプリケーションは、リージョン間の結果整合性を保証します。リージョンAで作成された新しい短縮URLは、最終的にリージョンBに伝播します。 * **読み取り**: 読み取りも通常、低レイテンシのために `LOCAL_QUORUM` 一貫性で行われ、ローカルリージョンのCassandraクラスターまたはキャッシュからデータをサービスします。キーが見つからない場合（例：非常に新しいURLのレプリケーションラグのため）、クロスリージョン読み取りへのフォールバックを実装することも可能ですが、レイテンシが増加します。読み取り負荷が高くキャッシュが多いため、これはまれです。 トレードオフ（CAP定理）: * **選択**: 強力なリージョン間 **一貫性** よりも、**可用性** と **パーティション耐性** を優先します。 * **理由**: URL短縮サービスにとって、サービスが常に利用可能で高速に動作することがより重要であり、たとえ新しく作成されたURLがグローバルにアクセス可能になるまでに数ミリ秒かかるとしてもです。地理的に分散されたデータセンター間での強力な一貫性は、許容できない書き込みレイテンシと複雑さを導入します。結果整合性は適切なトレードオフです。 TTL有効期限切れとURL回収メカニズム: 1. **有効期限切れ**: `short_urls` テーブルの `expires_at` タイムスタンプが使用されます。有効期限切れ・回収サービス（バックグラウンドワーカーセット）は、定期的に `short_urls` テーブルをスキャンし、`expires_at` が過去で `status` が 'active' のエントリを探します。 * 有効期限切れのURLを特定すると、サービスはその `status` をCassandraで「expired」に更新します。 * 次に、「url_expired」イベントをメッセージキューに発行し、RedisとCDNでのその `short_url_key` のキャッシュ無効化をトリガーします。 2. **回収**: 有効期限切れから設定可能な猶予期間（例：24〜48時間、全てのキャッシュがクリアされ、実行中のリダイレクトに影響がないことを確認するため）の後、有効期限切れ・回収サービスは、猶予期間を過ぎた `status` が「expired」のURLを特定します。 * 次に、それらの `status` を「reclaimable」に更新します。 * その後、`short_url_key` がキー生成サービスの利用可能なキーのプールに追加されます。これにより、7文字のキー空間が時間とともに効率的に再利用されることが保証されます。 * プールに戻す前に一意性の最終チェックを行うことも可能ですが、キー生成サービスの設計により、真の衝突は防止されるはずです。 障害モードと復旧: 1. **データベースノード障害（例：Cassandraノードのクラッシュ）**: * **検出**: 監視システムがノードの到達不能または高いエラー率を検出します。 * **復旧**: レプリケーションファクター（RF）が3（以上）のCassandraの分散アーキテクチャにより、データの冗長性が保証されます。ノードが失敗した場合、他のレプリカがデータをサービスします。クラスターは運用を継続します。失敗したノードは自動的に交換されるか、手動でオンラインに戻すことができます。データ損失はなく、サービスの中断は最小限です。 2. **キー生成サービス障害**: * **検出**: ヘルスチェックと監視により、サービスの利用不能またはキープールの枯渇が検出されます。 * **復旧**: キー生成サービスは複数のインスタンスでデプロイされます。1つが失敗した場合、他のインスタンスが引き継ぎます。サービス全体が失敗した場合、一意なキーを取得できないため、新しいURL短縮リクエストは一時的に失敗します。ただし、既存のリダイレクトは通常どおり機能し続けます。自動スケーリンググループが新しいインスタンスを起動します。事前に生成された大きなキーバッファ（数十億キー）は、一時的な障害の影響を大幅に軽減します。 3. **キャッシュクラスター障害（例：Redis Clusterの停止）**: * **検出**: 監視により、Redisノードまたはクラスターの利用不能が検出されます。 * **復旧**: リダイレクトサービスは、キャッシュが利用不能な場合にCassandraデータベースにフォールバックするように設計されています。これにより、リダイレクトレイテンシが増加し（10ms未満から50〜100msになる可能性）、Cassandraへの負荷が増加しますが、サービスは完全に機能し続けます（パフォーマンスは低下）。Redis Clusterはレプリケーションにより高可用性を提供し、クラスター全体の障害を軽減します。 4. **リージョン全体の障害**: * **検出**: グローバルロードバランサー（例：Route 53ヘルスチェック）が、リージョン内の全てのサービスが正常でないことを検出します。 * **復旧**: グローバルロードバランサーは、全てのトラフィックを正常なセカンダリリージョンに自動的にルーティングします。ユーザーはフェイルオーバー中にレイテンシのスパイクを経験する可能性がありますが、サービスは利用可能なままです。データ整合性はわずかに遅れる可能性がありますが、システムは結果整合性を許容するように設計されています。 行われた主要なトレードオフと検討された代替案: 1. **一貫性 vs. 可用性/レイテンシ（CAP定理）**: * **選択**: リージョン間データレプリケーションの結果整合性と、高可用性/低レイテンシの読み取り。 * **却下**: リージョン間の強力な一貫性。 * **理由**: 強力な一貫性は、書き込みとクロスリージョン読み取りに大きなレイテンシを導入し、高スループット、低レイテンシのリダイレクトサービスには許容できません。新しいURLマッピングの数ミリ秒の一貫性のずれは、高可用性とパフォーマンスのメリットと比較してわずかなトレードオフです。 2. **キー生成戦略（事前生成 vs. オンザフライハッシュ/シーケンシャル）**: * **選択**: 専用サービスによる事前生成されたランダム英数字キー。 * **却下**: 長URLのハッシュ化（例：MD5、SHA-256切り捨て）または自動インクリメントIDのベース62エンコーディング。 * **理由**: ハッシュ化は衝突（特に7文字制限の場合）を引き起こす可能性があり、複雑な衝突解決ロジックが必要となり、書き込みパスにレイテンシと複雑さを追加します。自動インクリメントIDのベース62エンコーディングは、URLをシーケンシャルで推測可能にし、重要な要件に違反します。事前生成は、一意性、推測困難性を保証し、書き込み時の高速なキー取得を可能にし、短縮プロセスを簡素化します。 3. **データベース選択（NoSQL vs. リレーショナルSQL）**: * **選択**: Apache Cassandra（NoSQL）。 * **却下**: PostgreSQL/MySQL（リレーショナルSQL）。 * **理由**: リレーショナルデータベースは、このサービスの極端な読み書きスループットと水平スケーラビリティの要件に、大幅なシャーディングの複雑さなしでは対応が困難です。CassandraのようなNoSQLデータベースは、このスケール、高可用性、パフォーマンスのために特別に設計されており、特に単純なキーバリュールックアップ（これが主要なアクセスパターンです）に適しています。 4. **TTL実装（バックグラウンドサービス vs. データベースTTL）**: * **選択**: `expires_at` をスキャンする専用の有効期限切れ・回収サービス。 * **却下**: データベースレベルのTTL（例：Cassandraの組み込みTTL）のみに依存すること。 * **理由**: データベースTTLはデータを自動的に有効期限切れにできますが、`short_url_key` を再利用可能なプールに制御された方法で回収したり、明示的なキャッシュ無効化をトリガーしたりすることを容易にはしません。専用サービスは、猶予期間や安全なキー再利用を含む、ライフサイクル全体に対するより詳細な制御を提供します。