システム設計面接：URL短縮サービスの設計

プロンプトと範囲

HTTPまたはHTTPSのURLを受け取り、短縮リンクを返すサービスを設計します。短縮リンクにアクセスすると、保存されている転送先へユーザーをリダイレクトする必要があります。基本設計では、任意のカスタムエイリアスと有効期限の設定をサポートします。クリック分析、カスタムドメイン、アカウント管理、リンクプレビューはコア要件ではなく、発展的な課題として扱います。

すべてのキャパシティ試算を再現可能にするため、以下のケース前提条件を使用します：

• 1日あたり新規リンク100万件、リダイレクト1億件；
• トラフィックのピークは1日の平均の10倍；
• リンクは、期限切れまたは無効化されない限り5年間保持；
• リダイレクト処理は、月間可用性99.99%およびサービスレイテンシp99 100 ms未満を目標とする；
• 保存されるマッピングのサイズは、インデックスやレプリケーション前で平均500バイト。

これらは面接用の前提条件であり、特定の製品の実測値ではありません。これらは読み取り主体のシステムであることを示唆していますが、設計においては、並行生成時の一意性の維持、曖昧なタイムアウト後に新規作成されたリンクの確実な返却、そして期限切れや不正利用リンクに対する定義された伝播時間内での配信停止を満たす必要があります。

面接官が評価するポイント

第1のシグナルは要件のコントロールです。優れた回答では、リンク生成とリダイレクトを分析やアカウント機能から切り離し、転送先を変更可能にするかどうかを定義し、有効期限やカスタムエイリアスの挙動について確認します。これらの取り決めを定義する前にキュー、検索エンジン、グラフデータベースなどを導入すると、設計が曖昧になります。

第2のシグナルは、規模の見積もりが設計判断に反映されているかです。想定されるワークロードは、平均して毎秒約12件の生成と1,200件のリダイレクトであり、ピーク時には毎秒約120件と12,000件に達します。5年間の生成により、約18億件のマッピングと約0.9 TBの生データが発生します。レプリケーション、インデックス、ストレージオーバーヘッド、余裕分（ヘッドルーム）を考慮すると、プロビジョニングする容量は数倍になります。これらの数値は、パーティション分割可能な永続ストレージとキャッシュの導入を正当化しますが、考え得るすべての分散コンポーネントを導入する理由にはなりません。

第3のシグナルは識別子の正確性です。8文字のBase62コードには 62^8 通り、約218兆通りの値が存在します。18億件のリンクを保持する場合でも、使用率は0.001%未満です。そのため、新規にランダム生成した場合の衝突確率はごくわずかですが、試行回数が増えると、システム全体で一度でも衝突が発生する確率は高くなります。ランダム性は予測困難性を高めますが、一意性を保証するものではありません。永続書き込み時には、コードが存在しないことをアトミックにアサートし、ランダムな衝突が発生した場合はリトライする必要があります。

第4のシグナルは、読み取りパスと障害に関する論理的思考です。キャッシュは最適化のためのものであり、信頼できる唯一の情報源（Source of Truth）ではありません。有効期限のチェックはクリーンアップジョブに依存するのではなく、読み取り時に行う必要があります。ホットキー、キャッシュ障害、データベースのタイムアウト、重複POST、リージョン間のレプリケーション遅延、分析のバックログ、緊急のテイクダウン（削除対応）のそれぞれについて、明確な動作を定義する必要があります。

最後に、質の高い回答では、セキュリティをリダイレクトのコア要件として扱います。短縮リンクはフィッシングの転送先を偽装するために使われる可能性があり、予測可能なコードは全件探索（列挙）を可能にしてしまいます。URLのパース、許可されたスキーム、レート制限、レピュテーションチェック、不正報告、迅速な無効化、非連続な公開コードなどは、「後からセキュリティを追加する」といった汎用的な枠組みではなく、設計そのものに組み込むべきです。

回答前の確認質問

• 作成後に転送先を変更できますか？ 基本のマッピングはイミュータブル（不変）です。不変性にすることで、キャッシュや監査履歴がシンプルになります。編集が必要な場合は、バージョニングと厳格な無効化SLOを追加します。
• 同一の長いURLは同じコードを共有すべきですか？ いいえ。所有者、キャンペーン、有効期限、ポリシーが異なれば、別々のリンクが必要になる場合があります。重複排除は転送先のハッシュ化による偶発的な副作用ではなく、明示的なオプションとすべきです。
• カスタムエイリアスは必須ですか？ オプションであり、選択されたドメイン内で一意です。競合が発生した場合は 409 を返します。サービスが要求されたエイリアスを勝手に変更することはありません。
• 有効期限が切れるとどうなりますか？ 期限切れまたは無効化されたことが判明しているコードは 410 を返し、不明なコードは 404 を返します。読み取り時に expires_at をチェックし、非同期の削除処理はストレージの回収のみを行います。
• どのリダイレクトステータスが期待されますか？ マッピングが無効化される可能性があり、ポリシー適用や分析のためにサービス側ですべてのリクエストを捕捉したい場合があるため、デフォルトでは 302 を使用します。301 は、クライアントや中間サーバーによる長期キャッシュを所有者が許容する不変リンクに対してのみ提供します。
• どのような整合性が必要ですか？ コードの予約とカスタムエイリアスの生成には強力な一意性が必要です。既存のリダイレクトでは可用性が重視されますが、生成が成功した後は、キャッシュへの投入またはRead-After-Writeパスを介して即座に読み取れる必要があります。
• 分析データは完全無欠損（ロスレス）である必要がありますか？ 基本パスの対象外です。追加する場合は、分析パイプラインの遅延がリダイレクトをブロックしないよう、許容される損失と鮮度を個別に定義します。
• サービスは転送先コンテンツを取得（フェッチ）しますか？ リダイレクトパスでは行いません。URLを取得するプレビューやマルウェアスキャナーは、SSRF防御を備えた独立した非同期サービスで実行します。

30秒の回答フレームワーク

「生成とリダイレクトを2つのコアフローとして維持します。1日あたり100万件の生成と1億件のリダイレクトがあるため、平均では毎秒約12件の書き込みと1,200件の読み取りが発生し、ピーク時にはその10倍になります。暗号学的に安全なランダム性を用いて8文字のBase62コードを生成し、アトミックな未存在時挿入（insert-if-absent）で予約します。カスタムエイリアスも同じ条件を使用します。永続マッピングストアはコードのハッシュによってパーティション分割され、信頼できる唯一の情報源として機能します。リダイレクトサーバーはCache-Asideを採用し、ステータスと有効期限を確認した上で 302 Location レスポンスを返します。生成は冪等であり、キャッシュエントリがリンクの有効期限を超えて残ることはなく、更新や削除時には無効化がプッシュされます。アクセスの集中する読み取りパスを個別にスケーリングし、キャッシュミスによるスタンピードを防止し、分析は非同期に保ちます。一意性の競合、レスポンス喪失時のリトライ、ホットキー、キャッシュおよびデータベースの障害、有効期限の境界条件、不正利用による無効化の伝播を、明確なSLOに照らして検証します。」

ステップごとの詳細解説

まずは小規模なキャパシティ計算から始めます：

Creates:   1,000,000 / 86,400 ≈ 12/s average, ≈ 120/s at 10x peak
Redirects: 100,000,000 / 86,400 ≈ 1,200/s average, ≈ 12,000/s at 10x peak
Mappings:  1,000,000 × 365 × 5 = 1.825 billion
Raw data:  1.825 billion × 500 bytes ≈ 0.9 TB before overhead and replicas
Code space: 62^8 = 218,340,105,584,896; occupancy remains below 0.001%

コアAPIはシンプルに保つことができます：

POST /v1/links
Idempotency-Key: client-generated-key
{ "url": "https://example.com/a", "customAlias": null, "expiresAt": null }
-> 201 { "code": "aZ3kP9qR", "shortUrl": "https://sho.rt/aZ3kP9qR" }

GET /{code}
-> 302 Location: https://example.com/a
-> 404 when the code never existed
-> 410 when it is expired or disabled

主なアクセスパターンはコードによるポイントルックアップであるため、1つの永続レコードには生成、リダイレクト、ライフサイクルポリシーに必要なフィールドのみを持たせます：

links
  code          primary key
  long_url
  owner_id
  status        ACTIVE | DISABLED
  created_at
  expires_at    nullable
  version

create_requests
  owner_id + idempotency_key    unique key
  request_fingerprint
  code
  status
  expires_at

Base62の8文字を生成するには、暗号学的に安全な乱数生成器を使用します。7文字の空間でも約3.5兆個の値を保持できますが、8文字にすることでより多くの余裕が生まれ、わずかなURL長の増加でオンラインでの列挙攻撃をより困難にできます。ランダム生成器を使用することで、中央集権的な数値採番器や予測可能なシーケンスを回避できます。ただし、アトミックな条件付き書き込みは依然として必要です。マッピングは code が存在しない場合にのみ挿入します。生成されたコードで条件が満たされない場合は、上限回数を定めて再試行します。カスタムエイリアスが競合した場合は、変更すると呼び出し元との取り決めに違反するため、409 を返します。

Base62としてエンコードされたカウンターも有効な選択肢です。採番器が正しければ一意でコンパクトな値が保証され、範囲リース（range leasing）によって協調処理を削減できます。トレードオフとしては、採番器の復旧、範囲の損失、リージョンごとの所有権管理、予測可能な列挙などが挙げられます。長いURLのハッシュ化も万能ではありません。切り詰めた場合に衝突する可能性があり、同一の転送先でも個別のリンクが必要になる場合があり、衝突の解決には依然としてストレージが必要になります。ランダムコード、リースされたカウンター、ハッシュの中から選択する前に、どの特性を重視するかを明示してください。

生成は以下の順序で処理されます：

1. 必要に応じて認証を行い、呼び出し元のレート制限を実施し、URLをパースして http と https のみを許可し、長さやポリシーの制限を適用し、カスタムエイリアスを正規化します。
2. 冪等性キーをチェックします。異なるリクエストフィンガープリントで再利用した場合はコンフリクト（競合）となり、同一のリクエストで再利用した場合は元の結果を返します。
3. コードを生成または受け入れます。単一のトランザクション内でコードを条件付きで予約し、冪等性レコードを永続化します。このトランザクションにより、2人の作成者が同じエイリアスを取得することを防ぎ、レスポンスが失われた場合でもリトライ時に別のリンクが生成されるのを防ぎます。
4. 永続ストレージへのコミット後、キャッシュ状態を投入または無効化し、非同期のレピュテーションスキャンをキューに追加します。キャッシュにのみ存在するコードは絶対に返してはなりません。

書き込みがタイムアウトした場合、クライアントは同じ冪等性キーで再試行します。サービスはまずリクエストレコードを読み取り、コミット済みの結果があればそれを返します。むやみに別のコードを生成すると、曖昧なレスポンスが原因で永続状態の重複が発生します。トランザクションがコミットされたかどうかをストアで証明できない場合は、障害と判断して新規マッピングを作成するのではなく、処理中またはリトライ可能な結果として報告します。

リダイレクト処理では、エッジまたはステートレスなリダイレクトサービスが迅速に伝播される拒否リスト（denylist）を確認し、分散キャッシュから code を検索します。キャッシュヒット時も status と expires_at を確認します。キャッシュミスの場合は、永続ストアからポイントリードを行い、同じライフサイクルフィールドを検証してマッピングをキャッシュします。キャッシュのTTLは expires_at を超えないように設定します。多数のエントリが同時に期限切れにならないよう、広範なTTLにはわずかなジッター（揺らぎ）を加えます。探索（スキャン）攻撃を吸収するために未知のコードも短時間キャッシュしますが、そのコードでカスタムエイリアスが作成された場合はネガティブエントリを無効化します。

デフォルトでは 302 と Location ヘッダーを返します。HTTPセマンティクスにおいて302は一時的な場所と定義されているため、クライアントは今後のリクエストでも短縮URLを使い続けます。301は恒久的な新しいURIを示し、ヒューリスティックにキャッシュ可能であるため、サービスからトラフィックを逃がすことができますが、失効処理、転送先の変更、リクエストレベルの分析が遅れる原因にもなります。リダイレクトステータスと Cache-Control はプロダクトの取り決めであり、サービス内に隠されたパフォーマンス調整用スイッチではありません。

永続ストアには、キーバリューストアまたは code のハッシュによってパーティション分割されたリレーショナルデータベースを使用できます。コア要件は、アトミックな未存在時作成（create-if-absent）、高耐久なレプリケーション、ポイントリード、バックアップ、そしてテスト済みの復元パスです。ランダムなコードは通常のトラフィックを自然に分散させますが、バイラルな単一コードは依然としてホットキーになります。キャッシュをレプリケーションし、極端なホットリンク用に小規模なローカルキャッシュを追加し、並行ミスを合流（coalesce）させることで、1つの期限切れによってデータベースに何千もの同一の読み取りが送られないようにします。

障害ポリシーは、信頼できる唯一の情報源の境界を維持する必要があります：

• キャッシュが利用できない場合は、サーキットブレーカー、上限を設けた直接読み取り、ローカルホットエントリ、受付制御（admission control）を使用します。無制限のキャッシュバイパスは、キャッシュ障害をデータベース障害へと発展させる可能性があります。
• データベースの読み取りパスが利用できない場合は、プロダクト側がそのリスクを許容する場合に限り、上限付きで古いポジティブキャッシュエントリを提供します。期限切れのリンクを延長したり、テイクダウン拒否リストをバイパスしたりしてはなりません。
• 永続書き込みパスで一意性を保証できない場合は、生成を失敗させます。可用性を理由に、1つのコードに2つの転送先を発行することは正当化されません。
• 分析処理が遅延している場合でもリダイレクトは継続し、個別に定められた分析契約に従ってクリックイベントをバッファリング、サンプリング、または破棄します。
• クリーンアップ処理が停止しても、読み取り処理によって有効期限は引き続き適用されます。ストレージは増加しますが、期限切れのリンクが配信されることはありません。

セキュリティの検証は作成時から始まり、その後も継続します。正規のパーサーを使用して非HTTPスキームや不正な形式のURLを拒否します。アカウント、ネットワーク、リスクシグナルごとにレート制限を適用し、転送先を非同期でスキャンし、報告および異議申し立てのフローを維持し、確認されたテイクダウンをリダイレクトパスに迅速に伝播します。短縮コードによってプライベートコンテンツへのアクセス権が付与されるべきではありません。転送先で認可が必要な場合は、転送先システム側でそれを強制する必要があります。短いコードによる難読化（隠蔽）はアクセス制御ではありません。

検証では、特性や障害のテストを行う必要があります。多数の作成者で単一のカスタムエイリアスを奪い合わせ、正確に1つだけが成功することを確認します。最初のPOSTレスポンスを破棄し、冪等なリトライによって同じコードが返されることを確認します。有効期限の1秒前、期限到達時、1秒後をテストします。ネガティブキャッシュの検索直後にコードを作成します。ランダムコードを大量に生成し、条件付きの競合を意図的に発生させます。広範なワーキングセットと単一のホットコードの両方で10倍のピーク負荷をかけ、その状態でキャッシュノードのダウン、データベースのスロットリング、無効化の遅延、クリーンアップや分析ワーカーの停止を発生させます。平均スループットだけでなく、リダイレクトの成功率、p99レイテンシ、キャッシュヒット率、DBへのミス負荷、条件付き競合、古いリンクの配信有無、テイクダウンの伝播時間を測定します。

質の高い回答例

「ベースシステムは、短縮リンクの作成と解決、およびオプションのカスタムエイリアスと有効期限の設定にスコープを絞ります。転送先はイミュータブル（不変）であり、同一の長いURLにも異なるコードが割り当てられる可能性があり、期限切れと判明しているリンクは410を返し、分析処理がリダイレクトをブロックしないことを前提とします。

ケースの前提条件に基づくと、生成は平均毎秒約12リクエスト、ピーク時は約120リクエストであり、リダイレクトは平均約1,200リクエスト、ピーク時は約12,000リクエストになります。5年間で約18億件のマッピングが保持され、1件あたり500バイトとすると生データで約0.9 TBになります。そのため、ポイントリード、パーティショニング、レプリケーション、アトミックな条件付き挿入をサポートし、code をパーティションキーとする永続ストアを使用します。

生成リンクについては、暗号学的に安全なランダム性を用いて8文字のBase62コードを生成します。空間は約218兆個の値を持つため、この規模であれば挿入ごとの衝突確率は極めて低いままですが、ランダム性は一意性の証明にはなりません。未存在時挿入によってコードを予約し、生成の衝突時はリトライします。カスタムエイリアスの競合時は409を返します。POSTリクエストには冪等性キーも含め、マッピングとリクエストレコードを一緒にコミットすることで、レスポンスが失われた場合でも同じコードを返せるようにします。

リダイレクトサービスは、テイクダウン拒否リストとキャッシュを確認します。キャッシュミスの場合はポイントリードを実行し、アクティブ状態と有効期限をチェックし、残りの有効期間を超えない範囲でキャッシュして、Location を伴う302を返します。マッピングが無効化される可能性があり、サービスがリクエストレベルのポリシーや分析を必要とする可能性があるため、デフォルトで302を使用します。不変リンクは301とより強固なキャッシュを選択できます。ネガティブエントリには短いTTLを設定し、カスタムエイリアスの作成時にネガティブキャッシュエントリを無効化します。

永続マッピングが信頼できる唯一の情報源です。キャッシュ障害時は受付制御を伴う上限付きのDB読み取りへと縮退し、DB障害時はポリシーで許可されている場合に限り上限付きで古いポジティブエントリを使用し、一意性が保証できない場合は生成を失敗させます。ホットキーにはレイヤードキャッシュとミスの合流（coalescing）を使用します。分析とレピュテーションスキャンは非同期とし、確認された不正利用は迅速に伝播される制御パスを介してリンクを無効化します。

この設計は、並行エイリアス競合、レスポンス喪失時のリトライ、有効期限の境界、ネガティブキャッシュの無効化、ホットキーおよび広範なデータセット負荷、キャッシュ喪失、DBスロットリング、クリーンアップ停止、テイクダウン伝播によって検証します。合否基準は、リダイレクト可用性99.99%、指定ピーク下でのp99 100 ms未満、コード獲得者の重複ゼロ、期限切れリンクの配信ゼロ、および測定された無効化伝播時間と関連付けます。」

よくある間違い

• 長いURLをハッシュ化して一意であると仮定する → 切り詰めによる衝突が発生し、同一URLでも別々のポリシーが必要になる場合があります → アトミックな予約を使用し、重複排除が必要かどうかを定義してください。
• 条件付き書き込みを行わずにランダムコードを使用する → 確率の低さを保証と混同しています → コードが存在しない場合にのみ挿入し、生成衝突時はリトライしてください。
• 書き込みタイムアウト後に新しいコードを返す → クライアントの単一のアクションによって複数のリンクが作成されてしまいます → リトライを永続化された冪等性キーに紐付け、元の結果を復元してください。
• 永続ストレージより先にキャッシュへ書き込む → 正常に作成されたように見えたリンクが、キャッシュ破棄時に消失します → 信頼できる唯一の情報源へ先にコミットしてから、キャッシュに投入してください。
• 有効期限の処理を削除ジョブに依存する → ジョブの遅延によって期限切れリンクが配信されてしまいます → すべての解決パスで expires_at をチェックし、クリーンアップは容量回収のみに使用してください。
• 301を「より高速」、302を「キャッシュ不可」と呼ぶ → キャッシュの挙動と変更可能性（ミュータビリティ）を過度に単純化しています → プロダクトの取り決めに従ってリダイレクトセマンティクスと明示的なキャッシュ制御を選択してください。
• 404を無期限にキャッシュする → 新規作成されたカスタムエイリアスにアクセスできない状態が続きます → 短いネガティブTTLを使用し、生成時に無効化してください。
• すべてのキャッシュミスを直接データベースに送る → ホットキーの期限切れによってスタンピードが発生します → リクエストの合流（coalescing）、TTLジッター、レイヤードホットキーキャッシュを使用してください。
• 分析を同期処理にする → コアではないパイプラインの障害によってリダイレクトが停止します → 解決後にイベントを発行し、分析の欠損許容度と鮮度を個別に定義してください。
• 短縮コードを認可情報として扱う → 列挙や共有によって保護されたコンテンツが露出します → 転送先で認可を必須とし、コードは単なるロケーター（位置指定子）として使用してください。

発展的な質問と対策

発展質問1: 準リアルタイムのクリック分析をどのように追加しますか？

リダイレクトの判定後に、code、イベント時刻、リクエストID、およびプライバシー承認済みのディメンションのみを含むクリックイベントを発行します。リンクごとに順序どおり集計できるようコードでストリームをパーティション分割しますが、特定のパーティションが飽和した場合は、極端なホットコードにソルト（salt）を付加するか分割します。コンシューマーは分単位および日単位の集計を冪等に更新します。確認応答（ACK）の方式を選択する前に、許容される損失、重複、鮮度、保持期間、ボットフィルタリング、同意について定義してください。リダイレクトが分析ストアの応答を待ってはいけません。

発展質問2: どのようにリージョン間のActive-Active構成を展開しますか？

リージョンごとのキャッシュとレプリカにより、読み取りをローカルに保ちます。コードの生成には依然としてグローバルな一意性が必要です。グローバルに条件付きなストアを使用するか、リージョンごとに重複しないランダムまたは数値の名前空間を割り当てるか、生成リクエストをホームリージョンにルーティングします。生成が成功した後は、レプリケーションが追いつくまでRead-After-Write戦略が必要です。テイクダウンのメタデータには、通常のマッピングレプリケーションとは別に測定される、より高速な伝播パスが必要です。

発展質問3: 転送先を変更可能（編集可能）にする場合、何が変わりますか？

バージョニングされた条件付き更新、監査レコード、所有者認可、およびコードとバージョンをキーとするキャッシュ無効化を追加します。すでにキャッシュされた301レスポンスが古いまま残ることを許容するかどうかを定義します。迅速な編集や失効が重要である場合は、キャッシュの鮮度期間を制限した302をデフォルトとします。ある編集者が別の編集者の内容を誤って上書きしないよう、並行更新には期待されるバージョン（expected version）の指定を必須とします。

発展質問4: 毎秒数百万件のリクエストを受け取る1つのリンクをどのように処理しますか？

CDNまたはエッジキャッシュ、リージョンキャッシュ、小規模なインプロセストレージから配信し、テイクダウンのチェックを一貫して行います。単一のキーをそのコードでシャーディングしようとするのではなく、ホットな値をレプリケーションします。更新を合流させ、期限切れ前にリフレッシュ（事前更新）を行い、ホットキーのトラフィックを分離してキャッシュやデータベースの接続枠を使い果たさないようにします。キャッシュされたバイラルリンクは迅速に失効させることが最も困難なリンクでもあるため、無効化の負荷テストを実施してください。

発展質問5: カスタムドメインはキーとルーティングモデルにどのように影響しますか？

一意性の単位が code だけでなく (domain, code) になります。ドメインの所有権を確認し、証明書をプロビジョニングし、ホストによってルーティングを行い、テナントごとのクォータや不正利用ポリシーを維持します。キャッシュキーとデータベースのパーティションキーにはドメインを含める必要があります。同じエイリアスが2つのドメインに存在する場合、互いに上書きしたり無効化したりしてはなりません。

発展質問6: 法的な要請により転送先を即座に完全削除（消去）する必要がある場合はどうしますか？

サービス配信の無効化と物理的な消去を分離します。まずレコードを無効としてマークし、拒否リストを更新し、キャッシュを無効化し、テイクダウンSLO内にすべてのリージョンが410を返すことを確認します。その後、保持ポリシーに従って永続レコード、バックアップ、分析ディメンション、検索・スキャナーのコピーを削除または暗号学的に消去（暗号消去）します。非同期の削除ジョブだけでは、リンクの解決が停止したことを証明できません。

発展質問7: 8文字からより長いコードへどのように移行しますか？

書き込み側を変更する前に、リゾルバー（解決側）がバージョニングされた範囲の長さを許容できるようにします。古いマッピングが変更なく解決され続ける一方で、新しい書き込み側はより長いコードを発行できます。新しいフォーマットで削除されるような固定の文字位置にパーティショニングが依存していてはなりません。リゾルバーのエラーとキャッシュキーのパースを監視した上で古い書き込み側のバージョンを廃止します。単に長さを統一するためだけに既存の公開コードを書き換えてはなりません。