URL短縮サービスの設計

1. 機能要件
   コア (MVP)

• 短縮URLの作成
  • 入力: long_url、オプションで custom_alias、オプションで expiration、オプションで user_id/api_key
  • 出力: short_url、key、created_at、expiry_at
• リダイレクト
  • GET /{key} -> long_url へ 301/302
  • 有効期限/無効状態を尊重する
• 基本的な分析
  • キーごとのリダイレクト数をカウント (合計 + 時間バケット)
  • オプション: リファラー、国/地域 (概算)、ユーザーエージェントファミリー、デバイスタイプ
• リンク管理
  • メタデータの取得 (long_url、created_at、expiry_at、status)
  • 無効化/削除 (ソフト削除)
    あると嬉しい機能
• 顧客ごとのカスタムドメイン
• 一括短縮API
• QRコード生成
• マルウェア対策/セーフブラウジングチェック
• A/Bルーティング、UTMテンプレート
  非機能要件
• 非常に低いリダイレクトレイテンシ (p95 < ~20–50ms、エッジ/キャッシュより)
• 高可用性 (マルチAZ/リージョン)
• 分析には強い一貫性は不要だが、キー->URLマッピングには必要

2. 高レベルアーキテクチャ
   トラフィックフロー

• DNS -> CDN/エッジ (オプションだが推奨)
• グローバルロードバランサー (GSLB) -> リージョンL7ロードバランサー
• APIゲートウェイ
  • 認証 (APIキー/OAuth)、スロットリング、リクエスト検証
• アプリケーションサービス (ステートレス)
  • 短縮サービス (書き込み)
  • リダイレクトサービス (読み取り、非常にホットなパス)
  • 分析取り込みサービス (非同期)
    データレイヤー
• キー->宛先レコードのマッピングのためのプライマリキーバリューストア
• ホットキー検索のためのキャッシュレイヤー (Redis/Memcached)
• 分析パイプライン
  • リダイレクトサービスがログ/キュー (Kafka/PubSub/Kinesis) にイベントを発行
  • ストリームプロセッサがOLAPストア (ClickHouse/BigQuery/Druid) および/または時系列データベース (Cassandra/Scylla) に集計
  • ダッシュボードのための定期的なロールアップ
    サポートサービス
• キー生成サービス (事前に生成されたIDを使用する場合)
• 悪用検出サービス (URL評判、ユーザー行動)
• 可観測性: メトリクス、トレース、ログ

インタラクション

• 作成:
  • クライアント -> APIゲートウェイ -> 短縮サービス
  • URLの検証、悪用のチェック、オプションのカスタムエイリアスのユニーク性チェック
  • 一意のキーの取得 (後述のエンコーディング戦略)
  • DBへのマッピングの書き込み
  • キャッシュの無効化/プライミング
• リダイレクト:
  • クライアント -> CDN/エッジ -> リダイレクトサービス
  • キャッシュでのキー検索。ミスの場合、DBに問い合わせる
  • 見つかり、期限切れ/無効でなければ: 301/302を応答
  • 非同期分析イベントの発行

3. URLエンコーディング戦略
   目標: ユニーク性、短い長さ、高スループット、中央のボトルネックなし。
   推奨: 数値ID + Base62

• 単調増加する64ビットID (または時間順ID) を使用し、Base62 (0-9a-zA-Z) でエンコードする。
• 月1億件の新規URL (~平均3.86k書き込み/秒、ピークはもっと高い) の場合、ID生成は毎秒数万件以上をサポートする必要がある。
  オプション:
  A) データベースシーケンス (シンプル)
• 長所: 簡単、確実にユニーク
• 短所: ボトルネックになり、シャード間での調整が困難
  B) 分散ID (Snowflakeライク) (推奨)
• 64ビット: タイムスタンプ + リージョン/ノード + シーケンス
• 長所: スケーラブル、単一ライターなし
• 短所: フル64ビットをエンコードするとキーがわずかに長くなる (Base62では最大11文字だがコンパクト)
  C) 事前生成キープール
• バックグラウンドジョブでランダムなBase62文字列を生成し、未使用プールを保存。アプリがキーを予約。
• 長所: 順序付けからの分離、キーを短く保つことができる
• 短所: プール管理の複雑さ
  衝突処理
• IDベースのアプローチの場合: 構成上、衝突なし。
• カスタムエイリアスまたはランダムキーの場合: 条件付きPUT/ユニーク制約でユニーク性を強制。衝突した場合は、新しいキーで再試行。
  キーの長さ
• 必要なBase62の長さ: 月1億件は年間約12億件を意味する。Base62^7 ≈ 3.5兆なので、シーケンシャルIDを使用する場合は7文字で十分。Snowflake IDは10〜11文字になる可能性があるが、許容範囲内。

4. データベース設計
   プライマリストアの要件

• 非常に高い読み取りQPS、キーベースのルックアップ、小さなレコード、低レイテンシ。
• キーのユニーク性のための強く一貫した書き込み。キャッシュが正しければ読み取りは最終的に一貫してもよいが、新しいリンクでは書き込み後の読み取りの一貫性を優先する。
  推奨: DynamoDB / Cassandra / ScyllaDB (NoSQL KV) または MySQL/Postgres (シャーディング付き)。
• NoSQL KVの長所: 水平スケーリング、高スループット、予測可能なレイテンシ。
• SQLの長所: 制約、トランザクション、カスタムエイリアスのユニーク性や管理クエリが簡単。ただし、スケールするとシャーディング/レプリカがより複雑になる。
  実用的な選択肢
• マッピングストア: DynamoDB (またはCassandra/Scylla) をシステムオブレコードとして使用。
• オプションで、ユーザー/アカウント/請求のためのリレーショナルストア。
  コアスキーマ (KV / ワイドカラム)
  テーブル: url_mapping
• key (パーティションキー、文字列)
• long_url (文字列)
• created_at (タイムスタンプ)
• expiry_at (タイムスタンプ、NULL許容)
• status (active|disabled|deleted)
• user_id (文字列/uuid、NULL許容)
• custom_alias (ブール値)
• domain (文字列、デフォルト)
• last_accessed_at (タイムスタンプ、NULL許容)
• redirect_code (整数: 301/302)
  インデックス/アクセスパターン
• プライマリ: key -> record
• ユーザー別 (管理UI用): セカンダリインデックス
  • GSI: user_id をパーティションキー、created_at をソートキー (または逆順)
• long_url別 (オプションの重複排除): hash(long_url) インデックス (「同じlong URLが同じキーを返す」動作をしたい場合のみ)
  分析ストレージ (別)
• オブジェクトストレージ (S3/GCS) に生イベントを保存 + OLAPへのストリーミング集計。
• 集計テーブル例 (ClickHouse): (key, day/hour, redirects, unique_ips_approx, country, referrer_domain, ua_family)
  SQL vs NoSQL のトレードオフ概要
• SQL: カスタムエイリアスのユニーク性、アドホッククエリが容易。注意深いシャーディングなしでの書き込み/読み取りのスケーリングが困難。
• NoSQL: プライマリルックアップワークロードに最適。アクセスパターンを事前に設計する必要がある。カスタムエイリアスのユニーク性は、条件付き書き込みで処理。

5. スケーラビリティとパフォーマンス
   トラフィック推定

• 書き込み: 月1億件 ≈ 平均3.86k/秒、ピーク時10倍を計画 => ~40k/秒。
• 読み取り: 100:1 => 平均386k/秒のリダイレクト、ピーク時10倍を計画 => 世界全体で ~4M/秒。
  ストレージ
• 月1億件 * 12 = 年間12億件のマッピング。
• レコードサイズ (キー ~10B、URL平均200B、メタデータ): ~500B–1KB と仮定。
• 1.2B * 1KB ≈ 年間1.2TB (レプリケーションとインデックスのオーバーヘッドを除く)。
  キャッシュ
• 各リージョンにRedis/Memcachedクラスタ。
• キャッシュキー: 短いキー。値: long_url + status + expiry_at + redirect_code。
• TTL戦略:
  • 有効期限のないリンクの場合: 長いTTL (例: 1〜7日)、アクセス時にリフレッシュ。
  • 有効期限のあるリンクの場合: 有効期限に合わせたTTL。
• 存在しない/無効なキーのネガティブキャッシュ (短いTTL) でDBヒットを削減。
• CDN/エッジキャッシュ (安全な場合):
  • 公開され、有効期限のないリンクの301をキャッシュ。ユーザーごとまたは動的なリダイレクトには注意が必要。
    シャーディング/パーティショニング
• NoSQL: キーでパーティション化。均一な分散を保証。
• SQLの場合: キーハッシュでシャード化。ルーティングレイヤーを維持。
  読み取りレプリカ
• SQLまたはレプリケートされたKVストアを使用する場合: 管理/読み取り負荷の高い非リダイレクトクエリのために読み取りレプリカを追加。
  ホットキー
• 非常に人気のある短縮URLはキャッシュノードを過負荷にする可能性がある。
  • 十分な仮想ノードを持つ一貫性ハッシュを使用。
  • リダイレクトサービスでのインプロセスLRUキャッシュを検討。
  • CDNでのエッジキャッシュはオリジン負荷を軽減。
    書き込みパスの最適化
• 分析イベントをバッチ処理。リダイレクトを分析にブロックさせない。

6. 信頼性と可用性
   マルチAZ

• ロードバランサーの後ろで、複数のAZにAPI/リダイレクトサービスを実行。
• キャッシュ: レプリケーション付きRedisクラスタ + 自動フェイルオーバー (またはマネージドRedis)。
• DB: マルチAZレプリケーション。必要に応じてクォーラム読み取り/書き込み。
  マルチリージョン (グローバルサービスに推奨)
• アクティブ/アクティブリダイレクト: マッピングDBをリージョン間でレプリケート (DynamoDBグローバルテーブル / CassandraマルチDC)。
• 書き込みは最寄りのリージョンにルーティング可能。競合を解決:
  • IDベースのキーの場合、衝突は起こりにくい。カスタムエイリアスはグローバルなユニーク性を必要とする — ドメインごとの「ホームリージョン」へのカスタムエイリアス作成のルーティング、または強く一貫したグローバルコーディネーションの使用 (まれなパス) で対応。
    フェイルオーバー
• ヘルスチェック + GSLBによる自動トラフィックシフト。
• ステートレスサービスにより、高速なスケーリングと置換が可能。
  バックアップとDR
• マッピングストアの継続的なバックアップ/スナップショット。
• 耐久性のあるオブジェクトストレージに生分析ログを保存。
  段階的縮小
• 分析パイプラインがダウンした場合、リダイレクトを継続し、イベントをバッファリング (キュー保持期間) するか、サンプリングする。
• キャッシュがダウンした場合、リダイレクトサービスはDBにフォールバックする (レイテンシ増加を予想するが、サービスは機能し続ける)。

7. レート制限と悪用防止
   レート制限

• 作成エンドポイントに対するAPIキー/ユーザー/IPごとの制限 (APIゲートウェイでのトークンバケット/リーキーバケット)。
• リダイレクトとは別の、より高い制限。CDN/WAFでフラッドから保護。
  悪用対策
• URL検証: スキーム (http/https) の許可リスト、最大長、内部IP範囲のブロック (SSRFスタイル) をプレビュー/スキャンコンポーネント用に使用。
• マルウェア/フィッシング検出:
  • セーフブラウジング/評判フィードとの統合。
  • 非同期スキャン。信頼されていないユーザーに対しては、スキャンが成功するまでオプションで「保留中」状態にする。
• カスタムエイリアスポリシー: 予約語、不適切語フィルタ、商標ポリシー。
• ボット検出: デバイスフィンガープリントヒューリスティクス、疑わしい作成トラフィックに対するCAPTCHA。
• リダイレクト保護:
  • WAFルール、リダイレクトパターンの異常検出。
  • キーごとのリダイレクトレートアラート。一時的なスロットリング。

容量/スループット計画の概要 (概算)

• ピークリダイレクト: 世界全体で数百万リクエスト/秒を目標とする。
  • CDNオフロード + リージョンキャッシュで大部分を処理 (ホットセットのキャッシュヒット率 >95%を目指す)。
  • オリジンDBの読み取りは最小限に抑える。ミス <5%で設計。
• 書き込み: ピーク時で数万/秒。分散ID生成により中央のボトルネックを回避。
• データ成長: 年間約12億件のマッピング。レプリケーションとインデックスのオーバーヘッドを持つ複数TBのストレージを計画。

実装開始点 (コンポーネントリスト)

• APIゲートウェイ + 認証
• 短縮サービス
• リダイレクトサービス (最適化され、依存関係は最小限)
• 各リージョンにRedisキャッシュクラスタ
• マッピングDB (DynamoDB/Cassandra/Scylla)
• IDジェネレーター (Snowflake) ライブラリ/サービス
• Kafka/Kinesis + ストリームプロセッサ + OLAPストア
• 管理/管理サービス + ユーザーDB
• モニタリング/アラート + WAF/CDN

1. 機能要件

• コア機能：

  • URL短縮: ユーザーは長いURLを送信し、一意の短いURLを受け取ることができます。
  • URLリダイレクト: 短いURLにアクセスすると、ユーザーは301（恒久的）リダイレクトで元の長いURLにリダイレクトされます。

• 拡張機能：

  • カスタムURL: ユーザーは短いURLのカスタムエイリアスを選択できます（例：short.co/my-event）。
  • URL有効期限: ユーザーは短いURLの有効期限（時間/日付）を設定でき、それを過ぎるとリダイレクトされなくなります。
  • 分析: サービスは、各リンクの総クリック数、参照元、クリックの地理的位置などの基本的な指標を追跡します。
  • APIアクセス: 短縮サービスをアプリケーションに統合するためのREST APIが開発者向けに提供されます。
  • ユーザーアカウント: 登録ユーザーはリンクを管理し、分析を表示し、より高いAPIレート制限にアクセスできます。

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

システムは、高い可用性とスケーラビリティを備え、読み取りパスと書き込みパスを明確に分離するように設計されています。

1. ロードバランサー (LB): 複数のWebサーバーに受信トラフィックを分散させ、単一のサーバーがボトルネックになるのを防ぎます。SSL終端を処理します。
2. Web/APIサーバー: アプリケーションロジックを実行するステートレスサーバーのフリートです。これらは2つの主要なリクエストを処理します：
   • POST /api/v1/url (書き込みパス): 新しい短いURLを作成します。
   • GET /{short_key} (読み取りパス): 長いURLにリダイレクトします。
3. キー生成サービス (KGS): 一意の短いキーを生成する専用のマイクロサービスです。書き込みパスの低遅延を保証するために、キーを事前生成してキューに保存します。
4. キャッシュ: アプリケーションサーバーとデータベースの間に、分散インメモリキャッシュ（例：Redis Cluster）が配置されます。頻繁にアクセスされるリンクのshort_keyとlong_urlのマッピングを格納し、非常に低い遅延でリダイレクトを提供します。
5. データベース: すべてのURLマッピングとユーザーデータのプライマリデータストアです。
6. 分析パイプライン: リダイレクトイベントはメッセージキュー（例：Kafka）に公開されます。別のサービスがこれらのイベントを消費し、データを集計し、分析クエリのためにデータウェアハウス（例：ClickHouseまたはAWS Redshift）に格納します。

インタラクションフロー（リダイレクト）：
クライアント -> ロードバランサー -> APIサーバー -> キャッシュ (Redis)。キャッシュヒットの場合はリダイレクトを返します。キャッシュミスの場合 -> データベース -> APIサーバー -> クライアント。その後、マッピングは後続のリクエストのためにキャッシュに書き込まれます。

3. URLエンコーディング戦略

Base62エンコーディング戦略と一意のIDジェネレーターを組み合わせて使用します。

• アプローチ: キー生成サービス (KGS) が、グローバルな64ビットカウンタ（例：専用SQLデータベースシーケンス、Zookeeper、またはカスタムサービスを使用して）を管理します。
• プロセス：
  1. アプリケーションサーバーがリンク作成のためにKGSに一意のIDを要求します。
  2. KGSは一意の番号（例：10001）を提供します。
  3. アプリケーションサーバーは、この数値をBase62文字列（[a-zA-Z0-9]）に変換します。例：Base62での10001は2k1です。
  4. 固定長を確保し、短く推測可能なキーを回避するために、7文字の長さを採用できます。64ビットカウンタは、十分な一意のID（2^64）を提供し、Base62文字列にマッピングできます。7文字のBase62文字列は、62^7（約3.5兆）の一意のURLを表すことができ、これは私たちの規模には十分です。
• 衝突処理: このアプローチは一意性を保証するため、設計上衝突は不可能です。これは、衝突を生成し追加チェックを必要とする可能性のある長いURLのハッシュ化よりも優れています。

4. データベース設計

大規模な読み取りスループットとスケーラビリティの要件を考慮すると、Apache CassandraやAmazon DynamoDBのようなNoSQLデータベースが理想的な選択肢です。

• NoSQLの理由？: 主なアクセスパターンは単純なキーバリュールックアップ（short_key -> long_url）です。NoSQLデータベースは、このパターンに対する水平スケーリング、高可用性、低遅延の読み取りに優れており、100:1の読み書き比率に最適です。
• SQLのトレードオフ: シャード化されたSQLデータベース（例：Citusを使用したPostgreSQL）も機能しますが、このレベルでのシャード化とスケーリングにおいて、より多くの運用上の複雑さが生じます。

コアテーブルスキーマ（Cassandra/DynamoDB風）：

• テーブル名: urls
• 主キー: short_key（これはパーティションキーとして機能し、データがクラスター全体に均等に分散されることを保証します）。
• 列:
  • short_key (text, Partition Key)
  • long_url (text)
  • user_id (uuid)
  • created_at (timestamp)
  • expires_at (timestamp) - これを基に、行のTime-To-Live (TTL) を設定して自動クリーンアップできます。

5. スケーラビリティとパフォーマンス

• 容量見積もり：

  • 書き込み: 月間1億URL ≈ 秒間40書き込み（平均）。
  • 読み取り: 月間100億読み取り ≈ 秒間3,850読み取り（平均）。ピークトラフィックはこれの10〜20倍になる可能性があります。
  • ストレージ: 月間1億URL * 12ヶ月 * 5年 = 60億URL。エントリあたり約500バイトとすると、約3TBのデータになります。

• 読み取りパスのスケーリング：

  • キャッシング: これが最も重要なコンポーネントです。マルチレイヤーキャッシュを使用します。
    • CDNキャッシュ: エッジでリダイレクトをキャッシュするためにCDN（例：Cloudflare）を使用します。これにより、人気のあるリンクのトラフィックのかなりの割合をオフロードできます。
    • 分散キャッシュ: Redisのようなインメモリキャッシュを使用します。月間100億読み取りを考えると、多くのURLが「ホット」になります。最もアクティブなURLの10〜20％をキャッシュするだけで、データベースの読み取り負荷を80〜90％以上削減できます。
  • データベースシャーディング: short_keyをパーティションキーとするNoSQLの選択により、これが自然に処理されます。データベースクラスターにノードを追加することで、ストレージとスループットの両方を水平にスケールできます。

6. 信頼性と可用性

• 冗長性: すべてのコンポーネントは、複数のアベイラビリティゾーン (AZ) にまたがってデプロイされます。
  • ロードバランサー、APIサーバー: 少なくとも2つのAZにまたがるオートスケーリンググループにデプロイされます。
  • キャッシュ (Redis): 異なるAZにレプリカを持つクラスター構成でデプロイされます。
  • データベース (Cassandra): データベースは、レプリケーションファクター3で構成され、AZ障害時のデータ耐久性と可用性を確保するために、異なるAZにレプリカが格納されます。
• フェイルオーバー: 自動フェイルオーバーメカニズムが導入されます。ロードバランサーは、正常でないインスタンスから自動的にトラフィックをルーティングします。マネージドデータベースサービスは通常、データベースのフェイルオーバーを自動的に処理します。
• データバックアップ: 災害復旧のために、データベースのスナップショットを定期的に取得し、別のリージョンに保存します。

7. レート制限と悪用防止

• レート制限: APIゲートウェイまたはRedisのようなインメモリストアを使用したアプリケーションロジックで実装されます。
  • 制限は、匿名ユーザーの場合はIPアドレス（例：1分あたり10件の作成）、登録ユーザーの場合はAPIキー（異なるティアあり）に基づいて行われます。
• 悪用防止：
  • 悪意のあるURLスキャン: Google Safe Browsing APIのようなサービスと統合し、送信されたすべてのlong_urlを悪意のあるサイトのブロックリストと照合します。
  • CAPTCHA: 高頻度の送信パターンを示す匿名ユーザー向け。
  • ブラックリスト: スパムで知られるドメインとユーザーアカウントの内部ブラックリストを維持します。