URL短縮サービスの設計

A. 短縮URL生成戦略

1. 要件駆動型の選択

• 新規書き込み: 1億件/月 ≈ 330万件/日 ≈ 平均38.6件/秒。
• 読み取り比率100:1 ≈ 33億件/月 ≈ 平均1,270件/秒、ピークは10～50倍になる可能性あり。
• コンパクトで、グローバルに一意なIDと非常に高速な検索が必要。

2. コード生成アプローチ
   決定論的なID生成サービスとBase62エンコーディングを使用する。

フロー:

• グローバルに一意な数値IDが生成される。
• その整数が文字[0-9a-zA-Z]を使用してBase62にエンコードされる。
• 例: 125 → Base62で「21」。

このアプローチを採用する理由:

• IDが一意であれば、衝突のリスクはない。
• 生成が非常に高速。
• ランダムコードの衝突チェックと比較して運用が容易。
• コード長の予測可能な成長。

3. IDジェネレーターの設計
   推奨オプション:

• Snowflakeスタイルの64ビットIDジェネレーターまたは集中型レンジアロケーターを使用する。
• IDフィールドにはタイムスタンプ + マシンID + シーケンスを含めるか、アプリサーバーに単調増加するレンジを割り当てる。

2つの良い実装:

• SnowflakeライクなID: 分散型、高スループット、低協調。
• メタデータストアからのレンジ割り当て: 各書き込みノードがIDブロック（例: 100万件）をリースする。

書き込みスループットは控えめなので、シンプルさからレンジ割り当てを好む。各書き込みサーバーはリースされたレンジからローカルでIDを生成でき、ホットな中央依存を回避できる。

4. エンコーディングスキームと予想される長さ
   Base62の容量:

• 62^6 ≈ 56.8億
• 62^7 ≈ 3.52兆

5年間の総リンク数:

• 1億件/月 * 60ヶ月 = 60億件

したがって、IDがグローバルに密に使用される場合、長期的なヘッドルームのために6文字のBase62では不十分だが、7文字あれば十分すぎる。

予想される長さ:

• 必要であれば、初期段階では6文字から始める。
• 実用的には、実装をシンプルに保ち、ユーザーの期待における長さの変更を避けるために、7文字に標準化する。

5. 衝突処理
   決定論的な一意IDの場合:

• コードレベルでの衝突はない。
• 短縮コードに対するデータベースの一意性制約が最終的なセーフティネットとなる。
• ソフトウェアバグやIDの設定ミスにより、非常にまれな重複が発生した場合は、新しいIDから再生成し、アラートを出す。

6. 排出戦略

• 7文字のBase62は3.52兆の組み合わせを提供し、5年間で必要な60億件をはるかに超える。
• 将来的にスケールが大幅に増加した場合でも、8文字のコードをシームレスにサポートする。
• リダイレクトサービスはコード長を可変として扱うべきなので、移行の問題はない。

7. オプションのカスタムエイリアス
   製品がユーザー定義のエイリアスをサポートする場合:

• 同じマッピングテーブルに一意性を強制して保存する。
• ブロックされた単語や不適切な用語を予約する。
• カスタムエイリアスは競合のホットスポットであるため、より厳格なレート制限を適用する。

B. データストレージ

1. プライマリデータベースの選択
   URLマッピングには、以下のような分散型で高可用性のキーバリューストアを使用する:

• DynamoDB / Bigtable / Cassandra

理由:

• 主なアクセスパターンは、short_codeによる単純なキー検索である。
• 水平スケーリング、高可用性、マルチレプリカ読み取りが必要。
• 書き込みは控えめで、読み取りが支配的。
• キーバリューストアへのアクセスは、50ミリ秒未満のリダイレクトレイテンシに最適。

概念的にはDynamoDBライクまたはCassandraライクなストレージを選択する:

• short_codeのハッシュでパーティション化する。
• アベイラビリティゾーンをまたいでレプリケートする。
• 低レイテンシのポイントリードにチューニングする。

2. セカンダリストア

• コントロールプレーンのメタデータ、請求、ユーザー、ドメイン、ポリシー用のリレーショナルDB。
• 分析/クリックログ用のオブジェクトストレージ + データレイク。
• 管理者が作成者、日付、タグなどでクエリする必要がある場合は、オプションの検索/インデックスストア。

3. スキーマ設計
   プライマリマッピングテーブル:

• short_code (PK)
• destination_url
• created_at
• expires_at (NULL許容)
• owner_id (NULL許容)
• status (active, disabled, deleted)
• redirect_type (301/302)
• checksumまたはnormalized_urlハッシュ (オプション)
• metadata pointer (オプション)

製品がテナントごとに同じ長URLに同じ短縮URLを返すことを望む場合のオプションの重複排除テーブル:

• dedup_key = hash(tenant_id + canonicalized_url)
• short_code
  これはオプションである。多くのURL短縮サービスは、セマンティクスがユーザー、キャンペーン、または分析ニーズによって異なるため、グローバルな重複排除を行わない。

4. 5年間のストレージ見積もり
   総リンク数:

• 60億件のレコード

レコードあたりの概算:

• short_code: 約8バイト相当（生）
• destination_url: 平均200バイトと仮定
• タイムスタンプ/ステータス/フラグ: 約24バイト
• レプリケーション/バージョニング/インデックスのオーバーヘッド: 実際のシステムでは大きい
• ストレージエンジンのオーバーヘッド: プライマリDBあたりレコードあたり実効合計350～500バイトと仮定

400バイト/レコードを使用:

• 60億 * 400バイト = 2.4 TB の論理データ（生）

レプリケーションファクター3の場合:

• 7.2 TB

インデックス、コンパクションオーバーヘッド、トゥームストーン、メタデータ、運用上のヘッドルームを追加:

• 5年間でプライマリストレージに10～15 TBを計画

分析/クリックログはマッピングよりもはるかに大きい。
書き込み100件あたり100回の読み取りの場合:

• 5年間で6000億回のリダイレクト
  各クリックログイベントの平均が圧縮状態でわずか100バイトであっても、それは約60 TB（圧縮状態）であり、よりリッチなフィールドがあればおそらくそれ以上になる。したがって、ログはサービングデータベースではなく、安価なオブジェクトストレージに格納すべきである。

5. パーティショニング/シャーディング戦略
   プライマリテーブルのシャーディング:

• パーティションキー: short_code または hash(short_code)
• IDが適切に混合された、分散性の高い数値IDまたはレンジIDからエンコードされるため、均一に分散される。

重要な注意:

• 純粋なシーケンシャルIDは、キーの局所性が重要である場合、一部のデータベースでホットパーティションを作成する可能性がある。
• これを回避するには、次のいずれかを行う:
  1. パーティション配置のためにshort_codeをハッシュする。
  2. 下位ビットに十分なエントロピーを持つIDを使用する。
  3. Base62エンコーディングの前にシャードビットをプレフィックスとして付ける。

均一な分散を保証するために、short_codeで明示的にハッシュパーティション化する。

C. 読み取りパスアーキテクチャ

1. 読み取りパスの概要
   リクエストフロー:

• ユーザーが https://sho.rt/abc1234 にアクセスする。
• DNSが最寄りのエッジ/CDNにルーティングする。
• CDNがキャッシュヒットしない場合、リージョナルリダイレクトサービスに転送する。
• リダイレクトサービスがインメモリ/Redisキャッシュをチェックする。
• キャッシュミスの場合、分散KVストアから読み取る。
• HTTP 301/302とLocationヘッダーを返す。
• クリックイベントを非同期に分析パイプラインに発行する。

2. <50ms p95レイテンシの達成
   リダイレクトパスは非常に軽量である必要がある。

レイテンシバジェットの例:

• エッジ/CDNルーティング: 小規模、地理的にローカル。
• アプリケーション処理: 1～3ms。
• Redis/インメモリキャッシュヒット: 1～5ms。
• リージョン内のDBミスパス: 通常5～15ms。
• p95合計50ms未満は、リージョナルサービングと積極的なキャッシュで達成可能。

3. キャッシュレイヤー
   レイヤー1: CDN/エッジキャッシュ

• エッジでホットリンクのリダイレクトレスポンスをキャッシュする。
• 多くの人気のある短縮リンクは繰り返しアクセスされるため、非常に効果的。
• TTL（例: 可変性に応じて数分から数時間）を持つCache-Controlヘッダーを使用する。
• リンクを迅速に無効化できる場合は、より短いTTLまたはパージサポートを選択する。

レイヤー2: アプリケーションローカルキャッシュ

• 各リダイレクトノードは、ホットマッピングのLRUキャッシュを保持する。
• 超低レイテンシで、Redisへのネットワークホップを回避する。
• 最も頻繁にリクエストされるコードに適している。

レイヤー3: 分散キャッシュ (Redis/Memcached)

• リージョナルフリート用の共有キャッシュ。
• short_code → destination_url, status, redirect type を格納する。
• 不変リンクの場合はTTLを長く設定できる。可変/管理者が管理するリンクの場合は短くする。

4. 読み取りのためのレプリケーション戦略

• 各リージョン内のマルチAZレプリカ。
• ローカルリージョンのストレージレプリカから読み取りをサーブする。
• 複数のリージョン間でのアクティブ/アクティブ。
• 最も近い正常なリージョンにルーティングするために、ジオDNSまたはAnycastを使用する。

5. キャッシュポピュレーション戦略

• ミス時のリードスルー: アプリケーションがDBからフェッチし、Redisとローカルキャッシュをポピュレートする。
• 存在しない/無効化されたコードのネガティブキャッシュを短いTTLで設定し、アビューズやタイポストームを吸収する。
• 分析から既知のトレンドリンクについては、キャッシュを事前ウォームアップする。

6. リダイレクトセマンティクス

• デフォルトでは302。宛先が変更される可能性がある場合、または分析/追跡ポリシーで柔軟性が必要な場合。
• クライアントやCDNが積極的にキャッシュする可能性のある永続リンクの場合は301。
• 製品の決定により、両方のオプションを提供できる。

7. 読み取りパスでのアビューズ処理

• 疑わしい高レートのリクエストに対して、IP / ASN / トークンによるレート制限。
• CDNでのWAFとボットフィルター。
• ブルートフォースの短縮コードスキャンからオリジンを保護する。

D. 書き込みパスアーキテクチャ

1. 書き込みパスの概要
   リクエストフロー:

• クライアントが長URLとオプションのメタデータ/カスタムエイリアスを送信する。
• APIゲートウェイが認証とレート制限を行う。
• URLの検証と正規化はステートレスなアプリ層で行われる。
• アプリケーションが短縮コードを取得/生成する。
• マッピングをプライマリKVストアに永続化する。
• 即時利用のために、キャッシュを非同期または同期的にポピュレートする。
• 作成イベントをキューに発行し、分析、アビューズスキャン、および下流のインデックス作成を行う。

2. 容量
   1億件/月は最新のシステムとしては多くない:

• 平均約39件/秒
• 100倍のバーストでも数千件/秒程度

したがって、主な目標は、極端な書き込みスループットではなく、信頼性、冪等性、および運用のシンプルさである。

3. 検証ステップ

• URL構文を検証する。
• 通常はhttp/httpsのみの許可プロトコルを強制する。
• オプションで、セーフブラウジングまたはマルウェアスキャンを非同期で行う。リスクが見つかった場合はリンクを無効化する。
• オプションの重複排除ロジックのためにURLを正規化する。

4. キューイングと非同期処理
   サイドエフェクトのために、耐久性のあるキューまたはログ（Kafka/SQS/PubSubなど）を使用する:

• 新規リンク作成の分析イベント
• アビューズ/詐欺/フィッシング検出
• キャッシュウォームアップ
• 検索インデックス作成
• 通知/監査パイプライン

クリティカルパスには、マッピングの作成と短縮URLの返却に必要なものだけを含めるべきである。

5. 一貫性モデル
   作成レスポンスの場合、新しい短縮コードに対して書き込み後の作成一貫性を使用する:

• APIが成功を返したら、リダイレクトはすぐに機能するはずである。

方法:

• DBコミット前に、プライマリDBのクォーラム/リーダーにマッピングを永続化する。
• オプションで、DBコミット後にRedisにライトスルーする。
• リダイレクトパスはキャッシュミス時にDBにフォールバックするため、キャッシュ伝播の遅延は正当性を損なわない。

6. 冪等性
   リトライ中の重複リンクを防ぐために、APIクライアント向けの冪等性キーをサポートする。

• 短い期間のTTLで、高速なストアに request_id → short_code を格納する。
• 特にモバイル/ネットワークリトライシナリオで役立つ。

7. レート制限

• アビューズを制御するための、ユーザー/APIキーごとのクォータ。
• カスタムエイリアスリクエストに対するより強力な制限。
• 攻撃によって引き起こされる書き込み増幅を防ぐためのグローバルなセーフガード。

E. 信頼性と耐障害性

1. 可用性目標: 99.9%
   99.9%のアップタイムは、月あたり約43.8分のダウンタイムを許容する。これは、マルチAZデプロイメントとリージョンフェイルオーバーで達成可能である。

2. 障害処理
   ノード障害:

• ステートレスアプリノードはロードバランサーの後ろに配置し、正常でないインスタンスを自動的に置き換える。
• ローカルキャッシュは破棄可能。
• Redisは高可用性クラスタ/センチネルモードでデプロイされる。

AZ障害:

• アプリ層は少なくとも3つのAZにまたがってデプロイされる。
• プライマリDBはAZをまたいでレプリケートされる。
• ロードバランサーが正常でないAZを除外する。

リージョン/DC障害:

• 複数のリージョン間でのアクティブ/アクティブな読み取りサービング。
• データは、DBの機能に応じて、非同期またはニアシンクロナスでクロスリージョンにレプリケートされる。
• DNS/トラフィックマネージャーがユーザーを正常なリージョンにフェイルオーバーする。

3. データ耐久性

• プライマリDBのレプリケーションファクター3をAZをまたいで設定。
• オブジェクトストレージへの定期的なスナップショット/バックアップ。
• サポートされている場合はWAL/コミットログのアーカイブ。
• 災害復旧のためのクロスリージョンバックアップコピー。

4. バックアップとリカバリ戦略

• 毎日のフルスナップショットと増分バックアップ。
• 偶発的な削除/破損に対するポイントインタイムリカバリ。
• RTO/RPOを検証するためのステージングへの定期的なリストアドリル。
• 5年間のアクセス可能性要件とコンプライアンスニーズに合わせたバックアップ保持期間。

合理的な目標:

• RPO: 数分～1時間（クロスリージョンレプリケーションモデルによる）
• RTO: リージョンフェイルオーバーの場合は1時間未満、完全なストレージ再構築の場合はそれ以上だが、それはまれであるべき。

5. キャッシュ無効化戦略
   リンクのほとんどが不変であれば、キャッシュはシンプルである。
   可変リンク（無効化/宛先変更/有効期限変更）の場合:

• まずDBを更新する。
• 無効化イベントを発行する。
• Redisキーとローカルキャッシュエントリをエビクトする。
• エッジキャッシュがそのコードに使用されている場合は、CDNキャッシュをパージする。
• TTLを制限し、無効化が失敗した場合でも古いキャッシュが自己修復するようにする。

6. データ破損とアビューズからの保護

• short_codeに対するDBの一意性制約。
• レコードのチェックサム/バージョンフィールド。
• 管理アクションの監査ログ。
• ハード削除ではなく、可能な限りソフト削除または無効化状態。
• マルウェア/フィッシングスキャンとテイクダウンツール。

F. 主要なトレードオフ

1. 決定論的ID生成 vs ランダム短縮コード
   オプション:

• 決定論的シーケンシャル/レンジベースID: シンプル、衝突なし、コンパクト、高速。
• ランダムコード: 予測可能/列挙可能ではないが、衝突チェックとより多くの複雑さが必要。

選択:

• Base62でエンコードされた決定論的IDを選択する。

理由:

• このスケールでは、よりシンプルで、高速で、運用上安全である。
• リトライループなしで衝突フリー。
• スループットが控えめで、主な課題が読み取りレイテンシであるため、より適している。

コスト:

• コードがより列挙可能/予測可能になる可能性がある。
  緩和策:
• レート制限、ボット検出、機密性の高いリンクのためのオプションのより長い/非シーケンシャルエイリアス。

2. 作成時の強力な一貫性 vs すべての場所での最終的な一貫性
   オプション:

• 最終的な一貫性は、書き込みレイテンシを削減し、マルチリージョン書き込みを簡素化できる。
• 耐久性のある書き込み後の強力な確認により、返された短縮URLがすぐに機能することを保証する。

選択:

• ホームリージョン内の単一リンク作成パスでは強力な一貫性を使用する。セカンダリキャッシュとクロスリージョン伝播では最終的な一貫性を使用する。

理由:

• より良いユーザーエクスペリエンス: APIが返されたら、リダイレクトは成功するはずである。
• 書き込み量は、クリティカルな書き込みで一貫性を緩和する必要がないほど少ない。

3. 積極的なエッジキャッシュ vs 高速な無効化
   オプション:

• 長いCDN TTLは、読み取りパフォーマンスを最大化し、オリジンコストを削減する。
• 短いTTLは、無効化/更新操作をより迅速に伝播させる。

選択:

• 可変/管理者が管理するリンクの場合は、明示的なパージを伴う中程度のTTL。不変リンクの場合はより長いTTL。

理由:

• 短縮されたURLのほとんどは実質的に不変であるため、キャッシュは大幅なレイテンシとコストのメリットをもたらす。
• しかし、アビューズのテイクダウンには、ある程度高速な無効化が必要である。

4. シンプルさ vs リダイレクトパスでの分析の豊富さ
   オプション:

• 同期クリックロギングは、即時の分析保証を提供するが、レイテンシと障害の結合を追加する。
• 非同期イベント発行は、リダイレクトを高速に保つが、障害発生時に分析が遅延したり、少量失われたりする可能性がある。

選択:

• 非同期分析。

理由:

• 製品のハードSLAは、リダイレクトレイテンシと可用性であり、ゼロロスリアルタイム分析ではない。
• リダイレクトパスは、下流のロギングシステムのためにブロックされるべきではない。

アーキテクチャの概要

• 短縮コード生成: レンジリースまたはSnowflakeスタイルのユニーク64ビットIDをBase62でエンコード、標準7文字コード。
• プライマリストア: 分散KVデータベース、short_codeによるハッシュパーティショニング、RF=3、マルチAZ。
• 読み取りパス: CDN + ローカルキャッシュ + Redis + KVストアフォールバック。マルチリージョンアクティブ/アクティブ読み取り。
• 書き込みパス: ステートレスAPI + 耐久性のあるDB書き込み + サイドエフェクト用の非同期キュー。冪等性とレート制限。
• 信頼性: マルチAZ、クロスリージョンレプリケーション、バックアップ、キャッシュ無効化イベント、DNSフェイルオーバー。
• この設計は、1億件/月の新規URL、100:1の読み取り比率、5年間の保持期間、99.9%のアップタイム、および<50msのp95リダイレクトを余裕でサポートする。

URL短縮サービスの設計

このドキュメントは、月間1億件の新規URL、100:1の読み取り/書き込み比率、5年間のデータ保持、99.9%の稼働時間、および95パーセンタイルで50ミリ秒未満のリダイレクト遅延に対応できるURL短縮サービスの設計について概説します。

A. 短縮URL生成戦略

エンコーディングスキーム: Base62エンコーディング（0-9、a-z、A-Z）を使用します。このスキームはURLセーフであり、一意な識別子をコンパクトに表現できます。

予想URL長: 5年間で、サービスは月間1億件のURL * 年間12ヶ月 * 5年間 = 60億件の一意なURLをサポートする必要があります。6文字のBase62文字列は、62^6 = 56,800,235,584の可能な一意なキーを提供し、60億件のURLには十分すぎるほどです。6文字から開始し、キー空間が枯渇に近づいた場合は、7文字（62^7 ≈ 3520億キー）に拡張する柔軟性を持たせます。

生成方法: **キー生成サービス（KGS）**を採用します。このサービスは、一意で単調増加する数値IDの生成を担当します。これらのIDはBase62エンコードされ、短縮URLコードが生成されます。KGSは、分散ID生成アルゴリズム（例：Snowflake IDジェネレーターの改良版、または競合を回避するために複数のKGSインスタンスにIDブロックを事前に割り当てるカウンターをインクリメントする専用サービス）を使用できます。このアプローチにより、データベースルックアップなしで一意性が保証され、キー生成中の競合が回避されます。

競合処理: KGSが一意な数値IDを生成するため、競合は本質的に回避されます。生成された各IDは一意であり、そのBase62エンコーディングも一意になります。ランダムな生成戦略が選択された場合、競合処理には、存在を確認するためにデータベースをチェックし、競合時に再生成することが含まれますが、これは遅延と複雑さを増加させます。

キー空間の枯渇: 前述の通り、6文字のBase62キーは60億件のURLに十分なスペースを提供します。サービスがこれを超えて成長した場合、キー長を7文字に拡張することで、さらに大きな容量が得られます。KGSは、必要に応じてより長いIDを生成することで、この移行をシームレスに処理できるように設計されます。

B. データストレージ

データベース選択: コアとなるshort_codeからlong_urlのマッピングには、分散NoSQLキーバリューストアであるApache Cassandraを使用します。Cassandraは、高いスケーラビリティ、耐障害性、および高ボリューム、低遅延の読み書きに最適化されており、読み取り負荷の高いワークロードに理想的です。その分散性と組み込みのレプリケーション機能により、高可用性とデータの耐久性が保証されます。

ストレージ見積もり:

• 5年間の総URL数: 60億件。
• 各エントリには以下が格納されます:
  • short_code: 6-7文字（約7バイト）
  • long_url: 平均100文字（約100バイト）
  • created_at: タイムスタンプ（8バイト）
  • expires_at: タイムスタンプ（8バイト、5年間の保持期間用）
  • click_count: カウンター（8バイト）
  • user_id（オプション）: 例：UUIDで36バイト
• 各エントリの合計（オーバーヘッドを含む保守的な見積もり）: 約150バイト。
• 総生ストレージ: 60億URL * 150バイト/URL = 9000億バイト = 0.9 TB。
• レプリケーション係数3（高可用性のためのCassandraで一般的）の場合: 0.9 TB * 3 = 2.7 TB。

スキーマ設計（Cassandra）:

CREATE TABLE short_urls (
    short_code text PRIMARY KEY,  -- パーティションキーで均等分散
    long_url text,
    created_at timestamp,
    expires_at timestamp,
    click_count counter,
    user_id text
);

パーティショニング/シャーディング戦略: Cassandraは、プライマリキー（short_code）に基づいてデータパーティショニングとシャーディングを自動的に処理します。Base62のshort_codeは、クラスターノード全体にデータを均等に分散させ、ホットスポットを防ぎ、効率的なデータ取得を保証します。耐障害性と高可用性のために、レプリケーション係数3でCassandraを設定し、複数のデータセンターまたはアベイラビリティゾーンに分散させます。

C. 読み取りパスアーキテクチャ

スループット: 月間1億件の書き込みと100:1の読み取り/書き込み比率により、月間100億件の読み取り、平均約3,858件/秒を予想します。ピーク時の負荷は5〜10倍になり、20,000〜40,000件/秒に達する可能性があります。

アーキテクチャコンポーネント:

1. ロードバランサー（例：AWS ELB、Nginx）: 短縮URLへのHTTPリクエストを複数のリダイレクトサービスインスタンスに分散させます。
2. 分散キャッシュ（例：Redis Cluster）: 遅延とスループットの要件を満たすために不可欠です。キャッシュはshort_codeからlong_urlのマッピングを格納します。100:1の読み取り/書き込み比率を考慮すると、非常に高いキャッシュヒット率（例：95%以上）が期待され、データベースへの負荷が大幅に軽減されます。
   • キャッシュ無効化: 短縮URLのマッピングは一般的に不変です。キャッシュエントリは非常に長いTTLを持つか、永続化できます。もしlong_urlが更新される必要がある場合（まれ）、明示的なキャッシュ無効化がトリガーされます。
3. リダイレクトサービス（アプリケーションサーバー）: ロードバランサーの後ろにあるステートレスアプリケーションサーバー（例：Go、Java、Node.jsで実行）のフリート。
   • 短縮URLリクエストを受信すると、サービスはまずRedisキャッシュをチェックします。
   • キャッシュヒットの場合、すぐにHTTP 301（恒久的）または302（一時的）リダイレクトをlong_urlに発行します。
   • キャッシュミスの場合、Cassandraデータベースにshort_codeをクエリします。
   • Cassandraから取得した後、マッピングは将来のリクエストのためにRedisに格納され、その後リダイレクトが発行されます。
   • クリック数は非同期で更新されます（例：分析サービスで処理するためのKafkaキューにメッセージを送信するか、Cassandraでカウンターを直接インクリメントする。Cassandraはアトミックインクリメントをサポートしています）。
4. データベース（Cassandra Cluster）: すべてのURLマッピングの永続ストレージとして機能し、キャッシュミスを処理します。その分散性とレプリケーションにより、必要なスケールでの高可用性と低遅延のデータ取得が保証されます。

レプリケーション戦略:

• アプリケーションサーバー: 複数のアベイラビリティゾーンにデプロイされた複数のインスタンスで、オートスケーリンググループによって管理されます。
• キャッシュ: 各シャードのマスターレプリカ構成を持つRedis Clusterで、高可用性とデータ冗長性を保証します。
• データベース: 複数のデータセンターにまたがるCassandraネイティブのマルチデータセンターレプリケーション（例：レプリケーション係数3）は、強力な耐障害性と災害復旧機能を提供します。

D. 書き込みパスアーキテクチャ

スループット: 月間1億件の新規URLは、平均約38件/秒に相当します。ピーク時の負荷は300〜400件/秒に達する可能性があります。

アーキテクチャコンポーネント:

1. ロードバランサー: 新規URL短縮のリクエストをWrite Serviceインスタンスに分散させます。
2. Write Service（APIゲートウェイ/アプリケーションサーバー）:
   • ユーザーからlong_urlを受信します。
   • **キー生成サービス（KGS）**を呼び出して、一意なshort_codeを取得します。
   • short_codeからlong_urlへのマッピングを構築します。
   • このマッピングを**メッセージキュー（例：Apache Kafka）**に発行します。これにより、Write Serviceとデータベースが分離され、バッファリングが提供され、信頼性が向上します。
   • 生成されたshort_codeをユーザーに返します。
3. キー生成サービス（KGS）: セクションAで説明したように、一意な数値IDを生成し、Base62のshort_codeにエンコードします。ピーク時の書き込み時にキー取得の遅延を最小限に抑えるために、キーブロックを事前に生成できます。
4. ワーカープロセス（コンシューマー）: Kafkaキューからメッセージを消費するワーカープロセスのプール。
   • 各メッセージについて、ワーカーはshort_codeとlong_urlをCassandraデータベースに書き込みます。
   • その後、すぐにマッピングをRedisキャッシュに書き込み、新しく作成された短縮URLが即座に読み取り可能であることを保証します。
5. データベース（Cassandra Cluster）: 新しいURLマッピングを永続的に格納します。

整合性に関する考慮事項:

• short_codeからlong_urlへのマッピングについては、強い整合性が求められます。適切な整合性レベル（例：QUORUM）でCassandraに書き込み、その後すぐにキャッシュを投入することで、短縮URLがユーザーに返された後、正しく解決されることを保証します。
• メッセージキューの使用は、永続化レイヤーに最終的な整合性を提供しますが、即時のキャッシュ更新により、読み取りパスが新しいURLに対して整合性を保ちます。キャッシュ更新が失敗した場合、読み取りパスは最終的にデータベースにヒットし、整合性が保たれます。

E. 信頼性と耐障害性

ノード障害:

• アプリケーションサーバー（リダイレクト＆Write Service）: ステートレスであり、複数のアベイラビリティゾーンにわたるオートスケーリンググループにデプロイされます。ロードバランサーは、障害のあるインスタンスから自動的にトラフィックをルーティングし、新しいインスタンスがそれらを置き換えるために起動されます。
• 分散キャッシュ（Redis Cluster）: マスターレプリカレプリケーションで構成されています。マスターノードが障害を起こした場合、レプリカが自動的にマスターに昇格され、キャッシュされたアイテムのダウンタイムとデータ損失が最小限に抑えられます。
• データベース（Cassandra Cluster）: 複数のノードとデータセンターにわたるレプリケーション係数3で高可用性を持つように設計されています。ノードが障害を起こした場合、そのデータは他のレプリカで利用可能になり、Cassandraは自動的にデータ修復と障害ノードの交換を処理します。
• キー生成サービス（KGS）: ロードバランサーの後ろに複数のインスタンスをデプロイして構成されています。基盤となる分散ID生成メカニズム（例：Zookeeperを使用した調整または高可用性カウンター）により、一部のKGSインスタンスが障害を起こした場合でも、一意なIDを生成できます。
• メッセージキュー（Kafka）: レプリケーションを備えたクラスターとしてデプロイされます。ブローカーが障害を起こした場合、他のブローカーは引き続き動作し、データはレプリケーションされてメッセージ損失がないことを保証します。

データセンター障害: システム全体は、少なくとも2つの地理的に離れたデータセンターまたはリージョン内の複数のアベイラビリティゾーンにデプロイされます。ロードバランサーは、クロスゾーン/クロスリージョンフェイルオーバーのために構成されます。Cassandraのマルチデータセンターレプリケーションは、データセンター全体が利用できなくなった場合でも、データの耐久性と可用性を保証します。

キャッシュ無効化: short_codeからlong_urlへのマッピングはほとんど不変であるため、明示的なキャッシュ無効化はほとんど必要ありません。キャッシュエントリは非常に長いTTLを持つことができます。もしlong_urlが更新される必要がある場合（例：法的理由）、Write Serviceはデータベースを更新し、その後Redisキャッシュ内の対応するエントリを明示的に無効化/更新します。

バックアップとリカバリ戦略:

• データベース: Cassandraクラスターデータの定期的な自動スナップショットが取得され、耐久性の高いオブジェクトストレージサービス（例：AWS S3、Google Cloud Storage）に保存されます。これらのバックアップにより、データ破損または誤削除の場合にポイントインタイムリカバリが可能になります。Cassandraの増分バックアップとコミットログも、より詳細なリカバリに使用できます。
• 構成: すべてのインフラストラクチャ（Infrastructure as Code）とアプリケーション構成はバージョン管理（例：Git）され、自動化されたパイプラインを使用してデプロイされ、サービス構成の迅速な復元を可能にします。
• 監視とアラート: システムの健全性、パフォーマンスメトリクス、エラー率を追跡するために、包括的な監視（例：Prometheus、Grafana）が実施されます。自動アラートは、異常や障害が発生した場合に運用チームに通知し、迅速な対応とリカバリを可能にします。

F. 主要なトレードオフ

1. 整合性 vs. 可用性（short_codeからlong_urlへのマッピングについて）

   • 選択されたトレードオフ: コアとなるshort_codeからlong_urlへのマッピングについては強い整合性を優先し、クリック数のような補助データについては最終的な整合性を許容します。
   • 説明: URL短縮サービスの基本的な目的は、短縮URLを正しい長URLに確実にリダイレクトすることです。不整合なマッピング（例：間違ったURLへのリダイレクト、またはリダイレクトの失敗）は、ユーザーエクスペリエンスを著しく低下させ、サービスのコア契約を破ることになります。したがって、short_codeが作成されてユーザーに返された後、それが正しいlong_urlに即座に解決されることを保証します。これは、強い整合性レベル（例：QUORUM）でCassandraに書き込み、Redisキャッシュを即座に投入することによって達成されます。可用性は、広範なレプリケーションと分散アーキテクチャを通じて維持され、強い整合性要件を持つクリティカルパスでもサービスが稼働し続けることを保証します。一方、クリック数などのデータは、更新の遅延をわずかに許容できるため、最終的な整合性が許容されます。

2. シンプルさ vs. スケーラビリティ/パフォーマンス（キー生成戦略）

   • 選択されたトレードオフ: データベースで競合を確認するランダムなBase62文字列を生成するという単純なアプローチよりも、分散カウンターとBase62エンコーディングを使用した専用のキー生成サービス（KGS）を選択しました。これはより複雑ですが、スケーラビリティとパフォーマンスに優れています。
   • 説明: ランダムな文字列を生成してデータベースで競合を確認することは、初期実装は単純ですが、スケーラビリティとパフォーマンスに関するいくつかの課題をもたらします。キー空間が満杯になるにつれて、競合の確率が増加し、リトライが増加し、書き込みパスの遅延が増加します。この読み取り前の書き込みパターンは、高負荷の書き込み下でボトルネックになる可能性があります。選択されたKGSアプローチは、設計と保守がより複雑ですが（分散IDジェネレーターが必要）、競合なしで一意なキーを保証します。キーブロックの事前生成を可能にし、Write Serviceのキー取得の遅延を大幅に削減します。この初期の複雑さは、サービスの5年間のライフサイクルにわたる予測可能で高性能、かつ高スケーラブルなキー生成の必要性によって正当化され、システムが成長しても書き込みパスが効率的で信頼性の高いままであることを保証します。