URL短縮サービスの設計

A) API 設計

1. 短縮URLの作成

• エンドポイント: POST /v1/urls
• リクエストJSON:
  • long_url (文字列、必須、最大例: 8KB)
  • custom_alias (文字列、任意; 提供される場合は一意であり、許可された文字セット/長さを満たす必要があります)
  • expire_at (タイムスタンプ、任意)
  • metadata (オブジェクト、任意: 例: キャンペーン、user_id)
• レスポンス (201):
  • code (文字列)
  • short_url (文字列)
  • long_url (文字列)
  • created_at (タイムスタンプ)
  • expire_at (タイムスタンプ|null)
• エラー:
  • 400 無効なURL/エイリアス
  • 409 エイリアスが既に存在します
  • 429 レート制限

2. 解決/リダイレクト

• エンドポイント: GET /{code}
• 動作:
  • デフォルトで301 Moved Permanently (またはトラッキング/実験が必要な場合は302)
  • Locationヘッダー = long_url
• オプション: GET /v1/urls/{code} はリダイレクトの代わりにJSONを返します (APIクライアント用)
• エラー:
  • 404 見つかりません/期限切れ

3. 削除/無効化 (任意、不正利用/ユーザー制御用)

• エンドポイント: DELETE /v1/urls/{code}
• 認証必須
• レスポンス: 204

4. 分析 (任意、非同期/近似可能)

• エンドポイント: GET /v1/urls/{code}/stats?from=&to=
• 集計されたカウンター (日別クリック数、参照元、ジオグラフィックなど) を返します

注記:

• 認証: 作成および管理にはAPIキー/OAuthを使用します。リダイレクトは公開のままです。
• Idempotency: POSTリクエストでIdempotency-Keyヘッダーをサポートし、リトライ時の重複を防ぎます。

B) データモデルとストレージ

ワークロード

• 書き込み: 1ヶ月あたり1億件 ≈ 1日あたり333万件 ≈ 平均38.6書き込み/秒 (ピークはより高い)。
• 読み取り: 100:1 => 1ヶ月あたり100億リダイレクト ≈ 平均3.86K読み取り/秒 (ピークははるかに高い)。

ストレージの選択

• プライマリストア: 非常に高い読み取りQPS、低レイテンシ、水平スケーリング、マルチDCレプリケーションに最適化された分散キーバリューストア/ワイドカラムストア (例: DynamoDB/Cassandra/ScyllaDB)。
• 理由: アクセスパターンは主に短いコードによるキー検索です。値は小さく、高可用性と予測可能なレイテンシが強く求められます。
• セカンダリシステム:
  • キャッシュ: リージョンごとのRedis/Memcachedクラスタ。
  • 分析パイプライン: Kafka/PubSub + ストリーム処理 + OLAPストア (クリティカルパスではありません)。

スキーマ

1. url_mapping (プライマリ)

• パーティションキー: code (文字列)
• カラム:
  • long_url (文字列)
  • created_at (タイムスタンプ)
  • expire_at (タイムスタンプ|null)
  • user_id (文字列|null)
  • status (active/deleted)
  • checksum (整合性のため、任意)
• TTL: expire_atが設定されている場合、ネイティブTTLを使用し、期限切れのエントリを自動削除します。

2. alias_reservation (カスタムエイリアスの一意性をサポートする場合、任意)

• キー: custom_alias
• 値: code / 所有権メタデータ

3. idempotency (任意)

• キー: (user_id, idempotency_key)
• 値: code
• TTL: 例: 24時間

ストレージ見積もり (10年間)

• 10年間の新規URL数: 1億件/月 * 12ヶ月 * 10年 = 120億件のマッピング。
• レコードあたりのサイズ概算:
  • code: 約8バイト (または最大約10文字)
  • long_url: 平均200バイトと仮定 (保守的)、オーバーヘッドを追加。
  • メタデータ/カラム/インデックスオーバーヘッド: ストアによって約100〜200バイトと仮定。
  • 合計実効サイズ (まだカウントされていないレプリケーションオーバーヘッドを含む): レコードあたり約400バイト (妥当な計画値)。
• 生データ: 120億 * 400バイト = 4.8TB。
• ストレージエンジンオーバーヘッド + コンパクション + セカンダリインデックスを含む: 約2〜3倍を計画 => 約10〜15TB。
• レプリケーション:
  • リージョン内 (RF=3): 約30〜45TB。
  • マルチリージョン (例: 2つのアクティブ-アクティブリージョン): 倍増 => 全リージョンで合計約60〜90TB。
    (これらは計画値であり、正確な値は平均URL長とDBオーバーヘッドによって異なります。)

C) 短縮URL生成

目標

• できるだけ短く
• 高スケールでの衝突フリー
• 少なくとも10年間の成長をサポート

キー空間の計算

• 10年間で必要なコードの総数: 120億。
• Base62文字セットを使用: [0-9][a-z][A-Z] => 62シンボル。
• 長さLの容量: 62^L。
  • 62^6 ≈ 56.8B (120億には十分)
  • 62^7 ≈ 3.52T (より多くのヘッドルーム)

選択肢

• 最小長6文字の可変長を使用。
• 最初の約568億コードには6文字から開始。これは既に10年間の要件を大幅なマージン (56.8B/12B ≈ 4.7倍) でカバーしています。
• 既存のリンクを壊すことなく、将来的に7文字に移行できる能力を維持します。

生成アルゴリズム (衝突なし)
選択されたオプション: グローバルに一意な数値ID + Base62エンコーディング。

• 単調増加する64ビットID空間を維持します。
• IDをBase62にエンコードしてコードを生成します。
• 衝突回避: IDは構築上一意であるため、不要です。

スケールでのID生成方法

• Snowflakeのような分散IDアロケータ、または範囲リースを持つ中央「IDサービス」を使用します:
  1. IDサービスは、各リージョンで一貫性の高いストア (例: etcd/Spanner) にカウンタを格納します。
  2. 各アプリサーバーは、ローカルで生成するためにIDブロック (例: 100万ID) をリースします。
  3. ブロックが枯渇したら、新しいブロックを要求します。
• これにより、書き込みごとの競合を回避しつつ、一意性を確保します。

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

• custom_aliasが提供された場合:
  • 文字セット/長さを検証します。
  • url_mappingに対する条件付き書き込み (比較・交換) で、キー=aliasとします。存在する場合は409を返します。

D) スケーリングとパフォーマンス

高レベルアーキテクチャ

• Anycast/GeoDNS -> グローバルロードバランサー -> リージョンL7ロードバランサー -> ステートレスAPI/リダイレクトサーバー。
• 分離されたサービス:
  • 書き込みパス: URL作成サービス
  • 読み取りパス: リダイレクトサービス
  • 共有ストレージ + キャッシュ

読み取りと書き込みのスケーリングを独立して行う

• リダイレクトサービスは、QPS/レイテンシに基づいて水平スケーリングされます (おそらく主要なコスト)。
• 作成サービスは、書き込みスループットに基づいてスケーリングされます。
• 別々の自動スケーリンググループと独立したデプロイパイプラインを使用します。

データパーティショニング

• DBノード全体でコードハッシュ (またはコード自体) によってパーティショニングします。
• コードはBase62エンコード時にID空間全体で実質的に均一であるため、均一な分散が可能です。

キャッシング戦略

• プライマリ: リダイレクト用のCDN/エッジキャッシュ + リージョン内インメモリキャッシュ。
  1. CDN:
     • パス (コード) をキーとして301/302レスポンスをTTL付き (例: 5〜60分、またはexpire_atを尊重) でキャッシュします。
     • 非常にホットなリンクの場合、CDNはグローバルにほとんどのトラフィックを吸収できます。
  2. リージョン内キャッシュ (Redis/Memcached):
     • キー: code
     • 値: long_url + expire_at + status
     • TTL: min(default_ttl, expire_at-now)
     • Eviction: LRUまたはLFU (人気が偏っている場合はLFUを推奨)。

期待されるヒット率

• URLアクセスは通常非常に偏っています (Zipf分布)。CDN + リージョン内キャッシュにより、リダイレクトで95〜99%のヒット率が可能です。90%でも役立ちます。
• キャッシュウォーミング: 書き込み時にマッピングをキャッシュにプッシュします。また、無効なコードに対する繰り返しDBヒットを減らすために、ミスに対するネガティブキャッシング (短いTTL) も行います。

<50msのp95リダイレクトレイテンシの達成

• キャッシュヒットのクリティカルパス:
  • エッジ/CDNヒット: 多くの場合 <20ms。
  • リージョン内キャッシュヒット: LB + アプリ + Redisルックアップ + レスポンス: リージョン内では通常5〜15ms。
• キャッシュミスの場合:
  • ローカルリージョンのDBからの単一DB読み取り: 目標5〜20ms。
• リダイレクトサーバーをユーザーの近くに配置します (マルチリージョン + エッジ経由)。
• キープアライブ、コンポーネント間のHTTP/2、Redis/DBへの接続プーリングを使用します。
• 同期分析を避け、クリックイベントをキューに非同期で発行します。

書き込みパフォーマンス

• 書き込みは読み取りに比べて少ないですが、バーストにも対応します。
• 書き込みフロー:
  1. ID/コードを生成します。
  2. DBに書き込みます (リージョン内のクォーラム/マジョリティ)。
  3. キャッシュにライトスルーします。
  4. レスポンスを返します。
• オプション: ハッシュ->コードインデックスを格納して、同一のlong_urlを重複排除します (トレードオフ。Fを参照)。

E) 信頼性と耐障害性

可用性目標: 99.9%

• すべての状態を持つコンポーネントについて、各リージョン内でマルチAZ。
• リダイレクトトラフィックのために、少なくとも2つのリージョンでアクティブ-アクティブ。

レプリケーション戦略

• リージョン内: AZをまたいだレプリケーションファクター3。
• クロスリージョン:
  • url_mappingの非同期レプリケーションにより、書き込みレイテンシを低く保ち、可用性を高くします。
  • リダイレクトはローカルリージョンから提供されます。レプリケーションラグによりローカルマッピングが見つからない場合、別のリージョンにフォールバックします (下記参照)。

データセンター/リージョン障害時の処理 (正常な劣化)

• グローバルロードバランサーのヘルスチェックを使用します:
  • リージョンが非健康的であれば、トラフィックを次に近い健康なリージョンにルーティングします。
• リダイレクトリクエストの場合:
  • リージョン内キャッシュ/DBに障害が発生した場合、リダイレクトサービスは以下を実行できます:
    1. キャッシュを試す
    2. ローカルDBを試す
    3. ローカルDBが利用できない場合、リモートリージョンの読み取りエンドポイントをクエリする (厳密なタイムアウト付き) か、クロスリージョン読み取りレプリカを使用します。
    4. すべて失敗した場合、Retry-After付きの高速な503を返します (正常な障害)。
• 書き込みリクエストの場合:
  • ローカルリージョンでの書き込みを優先します。リージョンがダウンしている場合は、別のリージョンにフェイルオーバーします。
  • ID割り当て: 各リージョンは、フェイルオーバー中の競合を回避するために、独自のIDブロック名前空間 (またはSnowflakeのリージョンビットを使用) を持ちます。

CAP定理のトレードオフ

• グローバル操作については、強力な一貫性よりも可用性を選択します:
  • リダイレクトは非常に利用可能である必要があり、古い読み取りは短時間なら許容されます。
  • クロスリージョンレプリケーションは非同期です。新しく作成された短縮URLは、短い期間、別のリージョンで解決できない可能性があります。
    緩和策:
  • 作成後、同じリージョンドメインでホストされる短縮URLを返します (または、最初の数分間はオリジンリージョンにルーティングするエッジを使用します)。
  • 作成時に、オプションで2つのリージョンに同期書き込みを行います (プレミアム/エンタープライズティアの場合、レイテンシ/コストが高くなります)。

バックアップと災害復旧

• オブジェクトストレージへの定期的なスナップショットと増分バックアップ。
• 定期的なリストア訓練。

F) トレードオフの議論

1. IDベースのコード生成 vs ランダムトークン

• 選択: IDベース (範囲リース/Snowflake) + Base62。
• 利点:
  • 衝突なし、リトライループの必要なし。
  • 予測可能なキャパシティプランニングとシンプルなDB制約。
  • 高速な書き込み。
• 犠牲:
  • コードは推測可能/シーケンシャルです (セキュリティによる秘匿性は提供されません)。
    緩和策:
  • 数値IDに対するオプションの「ソルト付き順列」(例: Feistelネットワーク) を追加して、一意性を維持しながらコードを非シーケンシャルにします。

2. 非同期クロスリージョンレプリケーション (AP) vs 同期マルチリージョン (CP)

• 選択: 非同期クロスリージョンレプリケーション。
• 利点:
  • 低い書き込みレイテンシ、部分的な障害時の高い可用性。
  • リージョンに障害が発生した場合でも、リダイレクトを提供し続ける能力が高い。
• 犠牲:
  • 結果整合性: 新しく作成されたURLが別のリージョンで読み取れない短い期間が存在する可能性があります。
    緩和策:
  • 読み取り修復/オリジンリージョンへのフォールバックで最新リンクに対応。高SLA顧客向けのオプションのデュアル書き込み。

3. 重いキャッシング/CDN vs 常にDBにヒット

• 選択: CDN + リージョン内キャッシュ。
• 利点:
  • <50msのp95を容易に満たし、DB負荷を劇的に削減します。
  • バイラルリンクのトラフィックスパイクに対応します。
• 犠牲:
  • キャッシュ無効化の複雑さ (例: 削除/期限切れリンク)。
    緩和策:
  • 短いTTL、expire_atの尊重、CDNでの削除時の明示的なパージ (サポートされている場合)。ステータスフラグとネガティブキャッシングを慎重に使用します。

A) API 設計:

1. URL 短縮エンドポイント:

   • メソッド: POST
   • パス: /shorten
   • リクエストボディ (JSON):

     {
       "long_url": "string",
       "custom_short_code": "string" (オプション),
       "expires_at": "ISO 8601 datetime string" (オプション)
     }
     

   • レスポンスボディ (JSON - 201 Created):

     {
       "short_url": "string",
       "long_url": "string",
       "custom_short_code": "string" (提供された場合),
       "expires_at": "ISO 8601 datetime string" (提供された場合)
     }
     

   • エラーレスポンス:
     • 400 Bad Request: long_url の形式が無効または欠落している。
     • 409 Conflict: custom_short_code が既に存在する。
     • 500 Internal Server Error: 一般的なサーバーエラー。

2. 短縮URLリダイレクトエンドポイント:

   • メソッド: GET
   • パス: /{shortCode}
   • レスポンス: 302 Found HTTP リダイレクト (long_url へ)。
   • エラーレスポンス:
     • 404 Not Found: shortCode が存在しないか、期限切れである。
     • 500 Internal Server Error: 一般的なサーバーエラー。

B) データモデルとストレージ:

ストレージ選択: シャード化されたリレーショナルデータベース (例: PostgreSQL) とリードレプリカ。

正当性:

• 書き込みに対する強力な一貫性: 短縮コードの一意性を保証するために不可欠。リレーショナルデータベースは ACID プロパティを提供し、URL 作成時の信頼性の高いデータ整合性にとって重要です。
• よく理解されたシャード化: PostgreSQL は、書き込み負荷を分散し、水平スケーリングするためのさまざまなシャード化戦略 (例: レンジベース、ハッシュベース) をサポートしています。
• 効率的なインデックス作成: Bツリーインデックスは、リダイレクトの主要な操作である short_code に対するポイントルックアップに非常に効率的です。
• リードレプリカ: 複数の読み取り専用レプリカを追加することで、読み取り操作 (リダイレクト) のスケーリングを容易にサポートします。
• 成熟度とエコシステム: モニタリング、バックアップ、リカバリのための堅牢なツール。

スキーマ:

urls テーブル:

• id: BIGINT, 主キー, 自動インクリメント (または分散IDサービスによって生成される)。短縮コードの基盤として使用されます。
• short_code: VARCHAR(7), 一意インデックス, NOT NULL。URL に使用される実際の短い文字列。
• long_url: TEXT, NOT NULL。元の長いURL。
• created_at: TIMESTAMP WITH TIME ZONE, NOT NULL, デフォルト: NOW()。
• expires_at: TIMESTAMP WITH TIME ZONE (NULL許容)。短縮URLの有効期限。
• user_id: BIGINT (NULL許容、ユーザーアカウントがサポートされている場合は users テーブルへの外部キー)。

ストレージ見積もり (10年間):

• ボリューム: 月間1億件の新規URL * 年間12ヶ月 * 10年 = 120億件のURL。
• レコードサイズ見積もり:
  • id: 8バイト (BIGINT)
  • short_code: 7バイト (VARCHAR(7))
  • long_url: 平均100バイト (TEXT、可変長)
  • created_at: 8バイト (TIMESTAMP)
  • expires_at: 8バイト (TIMESTAMP)
  • レコードあたり合計: 約131バイト。
• 生データサイズ: 120億レコード * 131バイト/レコード = 1.572 TB。
• インデックスとオーバーヘッド込み: 特に short_code と id のインデックス、レプリケーション、データベースオーバーヘッドを考慮すると、10年間での総ストレージは約3〜5 TBになる可能性があります。これは、シャード化されたデータベースアーキテクチャで管理可能です。

C) 短縮URL生成:

アルゴリズム:

1. 新しいURL短縮リクエストが到着したら、一意で単調増加するIDを取得します。このIDは次のように生成できます。
   • データベースの自動インクリメント: シャード化されたデータベースを使用する場合、各シャードは一意のID範囲を持つように設定できます (例: シャード1はID 1, 11, 21...を使用、シャード2は2, 12, 22...を使用)。
   • 分散IDジェネレーター: Snowflake のような専用サービス (または同様のカスタム実装) は、グローバルに一意で時間順の64ビット整数を生成できます。
2. この一意のIDを base62 文字列に変換します。Base62 は 62 文字 (0-9, a-z, A-Z) を使用し、コンパクトな表現を可能にします。

衝突回避:

• グローバルに一意なID (シャード化された自動インクリメントまたは分散IDジェネレーター経由) から短縮コードを派生させることにより、衝突は本質的に回避されます。生成される各IDは一意であり、その base62 表現も一意になります。
• custom_short_code リクエストの場合、システムはユーザー提供のコードを挿入しようとします。競合が発生した場合 (既存のエントリによる)、ユーザーに 409 Conflict エラーが返されます。

文字セットと長さ:

• 文字セット: Base62 (0-9, a-z, A-Z) - 62 個の一意な文字。
• 長さ: 最初は6文字。

キー空間の十分性に関する数学的根拠:

• 必要なボリューム: 10年間で120億件の一意なURL。
• 6文字でのキー空間: 62^6 = 56,800,235,584 (約568億件の一意なコード)。
• このキー空間 (568億件) は、必要な120億件のURLよりも大幅に大きいため、成長のための十分な余地があり、少なくとも10年間は十分であることを保証します。サービスがこれを超えた場合、短縮コードの長さを7文字に拡張でき、62^7 (約3.5兆件) の一意なコードを提供できます。

D) スケーリングとパフォーマンス:

読み取りのスケーリング (リダイレクト):

• 分散キャッシュ (例: Redis Cluster): 読み取りのスケーリングの主要なメカニズム。short_code から long_url へのマッピングは、高可用性のある分散キャッシュに格納されます。100:1 の読み書き比率を考慮すると、ほとんどのリダイレクト要求はキャッシュから直接提供されます。
• データベースリードレプリカ: シャード化された PostgreSQL インスタンスには、複数のリードレプリカがあります。キャッシュミスの場合、要求はリードレプリカにフォールバックします。ロードバランサーは、これらのレプリカ間でクエリを分散します。
• コンテンツデリバリーネットワーク (CDN): 302 リダイレクト自体を直接キャッシュするわけではありませんが、CDN は静的アセットを提供し、初期リクエストのルーティングを最適化して、地理的に分散したユーザーのレイテンシを削減できます。

書き込みのスケーリング (短縮):

• データベースシャード化: コア戦略。データは、シャードキー (例: short_code が派生する id) に基づいて、複数の PostgreSQL インスタンスにパーティション化されます。これにより、書き込み負荷とストレージ要件が分散されます。
• コネクションプーリング: データベース接続を効率的に管理し、オーバーヘッドを削減します。
• 非同期処理: 分析、ロギング、統計情報の更新など、クリティカルでないタスクには、メッセージキュー (例: Kafka, RabbitMQ) を使用してプライマリ書き込みパスから作業をオフロードし、応答性を向上させることができます。

キャッシング戦略:

• キャッシュタイプ: 分散インメモリキャッシュ (例: Redis Cluster)。
• キャッシュデータ: short_code から long_url へのマッピング。
• キャッシュのポピュレーション: URL 短縮が成功すると、新しいマッピングはデータベースとキャッシュの両方に書き込まれます。リダイレクト中のキャッシュミス時には、マッピングはデータベースから取得され、キャッシュに書き込まれます (ライトスルー/ライトアサイド)。
• エビクションポリシー: LRU (Least Recently Used) が適しています。人気のあるURLはキャッシュに残りますが、あまりアクセスされないものはスペースを確保するためにエビクトされます。特に expires_at フィールドを持つURLには、Time-to-Live (TTL) も適用できます。
• 期待されるヒット率: 100:1 の読み書き比率とURLアクセスのべき乗則分布 (少数のURLがトラフィックの大部分を占める) を考慮すると、90〜95%以上のキャッシュヒット率が十分に達成可能であり、データベース負荷を大幅に削減します。

50ms p95 レイテンシ要件の満たし方:

• 高いキャッシュヒット率: ほとんどのリダイレクト要求は、ミリ秒単位で応答できる分散キャッシュから提供されます。
• 最適化されたデータベースアクセス: キャッシュミスの場合、シャード化されたデータベースの short_code に対する効率的なインデックス作成により、高速なルックアップが保証されます。
• 近接性とネットワーク: ユーザーに近い複数のリージョンにサービスをデプロイし、高速で低レイテンシのネットワークインフラストラクチャを利用します。
• ロードバランシング: 要求を正常なサービスインスタンスとデータベースレプリカ間で効率的に分散します。
• ステートレスアプリケーションサーバー: APIレイヤーの水平スケーリングを容易にし、ピーク負荷を処理するための十分な容量をボトルネックなしで確保します。

D) 信頼性と耐障害性:

データセンター障害:

• マルチリージョンデプロイメント: サービス全体 (APIサーバー、キャッシュクラスター、データベースシャード) は、少なくとも2つの地理的に離れたデータセンター/リージョンにデプロイされます。
• グローバルロードバランサー (例: DNSベースのトラフィック管理): ユーザートラフィックを最も近い正常なリージョンに誘導します。1つのリージョンが失敗した場合、トラフィックは自動的に運用中のリージョンにリダイレクトされます。
• 自動フェイルオーバー: データベースクラスターは、リージョン内 (プライマリからレプリカへ) およびリージョン間 (アクティブ-パッシブまたはアクティブ-アクティブ設定) で自動フェイルオーバーするように構成されています。

データレプリケーション戦略:

• データベース (PostgreSQL):
  • リージョン内: 同期ストリーミングレプリケーションは、プライマリデータベースインスタンスとそのローカルレプリカ間で使用されます。これにより、同じデータセンター内でのプライマリ障害時にデータ損失がゼロになります。
  • リージョン間: 非同期ストリーミングレプリケーションは、アクティブリージョンのプライマリからパッシブ/スタンバイリージョンのレプリカに対して使用されます。これにより、プライマリ書き込みパスへのパフォーマンスへの影響を最小限に抑えながら、ディザスタリカバリ機能が提供されます。アクティブ-アクティブ設定では、各リージョンのプライマリはもう一方に非同期でレプリケートされます。
• 分散キャッシュ (Redis Cluster): データは、各 Redis クラスター内の複数のノードにシャード化され、レプリケートされます。各シャードにはプライマリと少なくとも1つのレプリカがあります。ノード障害が発生した場合、レプリカがプライマリに昇格されます。

トレードオフ (CAP定理):

• 選択: 書き込み操作 (短縮) に対してはデータベースシャード内で強力な一貫性を維持しながら、読み取り操作 (リダイレクト) については 可用性 (A) と パーティション耐性 (P) を優先します。
• 正当性: URL短縮サービスにとって、ネットワークパーティションやデータセンター障害が発生した場合でも、サービスが利用可能で応答性が高い (低レイテンシ) ことが最も重要です。ユーザーは、リダイレクトが迅速に機能することを期待しています。
• 達成方法:
  • 可用性: マルチリージョンデプロイメント、グローバルロードバランシング、データベースリードレプリカ、および高可用性のある分散キャッシュにより、常に要求が提供されることが保証されます。
  • パーティション耐性: システムの分散性質 (シャード化、レプリケーション) は、ネットワークパーティションを本質的に処理します。
  • 一貫性: 書き込みについては、データベースシャード内で強力な一貫性が維持されます。リージョン間レプリケーションは非同期であるため、レプリケーションラグのために新しく作成されたURLに関してリージョン間で小さな不整合のウィンドウが存在する可能性があります。キャッシュも、書き込み時およびキャッシュミス時に更新されるため、最終的に一貫性のあるレイヤーとして機能します。

F) トレードオフに関する議論:

1. リダイレクトの一貫性 vs. 可用性 (CAP定理):

   • 選択: リダイレクトパスについては、強力な一貫性よりも 可用性 と パーティション耐性 を優先します。
   • 理由: URL短縮サービスの主な目的は、高速で信頼性の高いリダイレクトを提供することです。新しく作成されたURLがグローバルに伝播するのに数秒かかる場合、それは些細な不便です。しかし、システムがグローバルな一貫性を待ってからリダイレクトを提供する場合、大幅なレイテンシが発生し、ネットワークパーティションやリージョン障害時の可用性が低下します。ユーザーは、頻繁なタイムアウトや遅いリダイレクトよりも、ごくまれに新しいURLが見つからない方がましだと考えるでしょう。
   • 犠牲: 最終的な一貫性の小さなウィンドウ。ユーザーがリージョンAでURLを作成し、非同期レプリケーションが完了する前にすぐにリージョンBからアクセスしようとすると、一時的に404エラーを受け取る可能性があります。極端なマルチリージョン障害シナリオで非同期レプリケーションを使用する場合、プライマリリージョンがレプリケーションをセカンダリリージョンに完了する前に壊滅的に失敗した場合、ごく最近の書き込みでデータ損失のリスクがわずかにあります。
   • 利点: 高可用性 (99.9%の稼働時間) と非常に低いレイテンシ (p95で50ms未満) をほとんどのリダイレクト要求に対して提供します。これらは最も頻繁な操作です。データセンターがオフラインになっても、システムは運用可能で応答性が維持されます。

2. 短縮コード生成方法 (シーケンシャルIDからBase62 vs. 長いURLのハッシュ化):

   • 選択: 一意でシーケンシャルに増加するID (分散IDジェネレーターまたはシャード化された自動インクリメントから) をBase62に変換して短縮コードを生成します。
   • 理由: この方法は設計上一意性を保証し、書き込みパスを簡素化し、パフォーマンスを向上させます。ハッシュベースのアプローチに固有の衝突検出と解決に関連する複雑さとパフォーマンスのオーバーヘッドを回避します。
   • 犠牲: 短縮コードは、ある程度シーケンシャルに見える可能性があります (例: abcde1, abcde2)。これは一部のユーザーにとっては些細な美的懸念ですが、機能には影響しません。また、堅牢な分散ID生成メカニズムが必要であり、アーキテクチャにコンポーネントが追加されます。
   • 利点:
     • 保証された一意性: 衝突がないため、短縮コード生成中のデータベースルックアップやリトライが不要になり、高い書き込みスループット (月間1億件) に不可欠です。
     • シンプルな書き込みパス: 新しい短縮URLを作成するプロセスは、ID生成後の単純な挿入操作です。
     • 予測可能なキー空間: 将来の成長に対してキー空間を管理し、十分であることを保証しやすくなります。
     • 柔軟性: 同じ long_url を複数回短縮でき、必要に応じて異なる short_code を生成できます (例: 異なるキャンペーンの追跡用)。これは、long_url の単純なハッシュでは不可能です。