初級 System Design 面接：Design Bitly w/ a Ex-Meta Staff Engineer

Hello Interview（Evan、元Meta staff engineer）による BitlyのようなURL短縮サービスの設計 のメモ — 定番の初級システム設計問題として位置づけられ、上級動画よりゆっくり概念を説明する。

面接のロードマップ

1. 要件（機能要件 + 非機能要件）
2. コアエンティティ
3. API
4. ハイレベル設計（機能要件を満たす）
5. 深掘り（非機能要件を満たす）

ユーザー向けプロダクト設計では data flow はスキップ（レートリミッターやメッセージキューなどのインフラ問題向け）。

最初の back-of-envelope 計算は任意 — 数字が設計を変えるときだけ見積もる。

システムの役割

URL短縮サービスは長いURLを短く変換し、短いURLにアクセスするとリダイレクトして元のURLへ向かう。

機能要件

• ユーザーは長いURLから短いURLを作成できる
• ユーザーは短いURLから元のURLへリダイレクトされる

面接でよく出るオプション拡張：

• カスタムエイリアス — ユーザーが自分の短縮コードを指定（例：bit.ly/Evan）、未使用なら
• 有効期限 — 短いURLが一定期間だけ有効（例：1週間のカンファレンスリンク）

非機能要件

Evanが候補者に提示する典型的な規模：

• 1億 DAU
• 約10億URLが累計で短縮される

文脈に即して挙げるべきNFR：

懸念	URL短縮サービスでの言い方
低レイテンシのリダイレクト	リダイレクトパスは速くなければならない — ユーザーはレイテンシを即座に感じる
短縮コードの一意性	衝突すると誤ったサイトへ飛ばされる — 一意性を保証する
スケーラビリティ	1億DAUと10億のマッピングをサポート
CAP	強い一貫性より可用性 + 分区間耐性を優先（下記参照）

コアエンティティ

• User — 短いURLを所有（email、パスワードハッシュなどは補助；面接で詳述しすぎない）
• URL mapping — 短縮コード ↔ 長いURL（中核テーブル）

API

• POST /urls — body：長いURL（+ 任意のカスタムエイリアス、任意の有効期限）→ 短いURLを返す
• GET /{shortCode} — 長いURLへリダイレクト（ハイレベル設計では302）

ハイレベル設計（v1）

Client → Load balancer → URL Service → Database (URL mappings)

• 作成： (shortCode, longUrl) を挿入 → 短いURLを返す
• リダイレクト： shortCode をルックアップ → 長いURLへ 302リダイレクト

301 vs 302 リダイレクト

コード	挙動	使い分け
302	一時的 — ブラウザは常にサーバーに到達	analytics不要のデフォルト、または毎回ログしたいとき
301	永続的 — ブラウザ/CDNがキャッシュ；サーバーをスキップしうる	本当に永続的でクリックごとのログが不要なとき

analyticsなしのBitlyなら302で十分。analyticsありなら302でリダイレクトが常にサーバーに来てクリックを数えられる。

深掘り：短縮コードの生成

悪いアプローチ：

1. 長いURLのプレフィックス — 多くのURLが同じプレフィックス（twitter.com/...）を共有 → 1対多マッピング、衝突
2. 長いURLのみハッシュ — 決定的なので同じ長いURLは常に同じ短縮コード（重複排除OK）だが、ハッシュ衝突の処理が必要；衝突時はsalt追加して再ハッシュ

良いアプローチ：

カウンター + base62（動画で推奨）

• 新しいURLごとに自動インクリメントカウンターを維持
• カウンターをbase62エンコード（0–9、A–Z、a–z）でコンパクトな文字列に
• 6文字 → 62⁶ ≈ 560億の組み合わせ
• 衝突なし — 連番IDは構造上ユニーク

乱数 + base62

• [0, 56B) の乱数を選び、base62エンコード
• 誕生日のパラドックス： 衝突確率は直感より早く上がる — 約10億URLで衝突が現実的な問題に
• 衝突時はDBを確認してリトライが必要

長いURLのハッシュ + base62スライス

• ハッシュ（MD5、Murmur、SHA-256）→ base62 → 先頭6文字
• 同じ長いURLの決定的な重複排除
• 衝突時はsaltを付けて再ハッシュ

深掘り：CAPと一貫性

URL短縮サービスはread-after-writeの強い一貫性を必要としない（銀行やチケット予約とは異なる）。

ユーザーが短いURLを作って即座に共有しても、結果整合性で十分 — 短い「1分後に再試行」エラーは許容できる。APをCPより優先。

深掘り：読み取りのスケール（リダイレクト偏重）

リダイレクトがトラフィックの大半 — read-heavyなワークロード。

read/write サービス分離

• Write service — 短いURLを作成
• Read service — リダイレクトを処理
• API Gateway が POST /urls → write service、GET /{shortCode} → read service にルーティング

各層を水平スケール（ロードバランサー背後のオートスケーリンググループ）。

Redisキャッシュ（read-through LRU）

• リダイレクト時：Redisで shortCode → longUrl を確認
• キャッシュミス： DBを読み、キャッシュを更新して返す
• ホットな短縮URL向け read-through + LRU 退避

Postgresの主キールックアップ（B-tree）は既に速いが、キャッシュがスケール時のDB負荷を除去する。

ピーク時リダイレクトQPS（概算）：1億DAU × 1日数回のリダイレクト → 平均 ~1K req/s、バースト倍率で10–100K req/s。

要点

• Bitlyは定番の入門システム設計問題 — 要件 → エンティティ → API → 設計 → 深掘り
• カウンター + base62が最も衝突のない短縮コード戦略；乱数は誕生日のパラドックス計算が必要
• URLプレフィックスを短縮コードに使わない — 共有プレフィックスが1対1マッピングを壊す
• 302 vs 301はサーバー側リダイレクトログ（analytics）が必要かどうかによる
• リダイレクト偏重のスケールには read/write分離 + Redis read-throughキャッシュ
• 結果整合性でOK — すべてのシステムが強いread-after-writeを必要とするわけではない
• back-of-envelope見積もりはアーキテクチャ判断を変えるときだけ行う

---

🌐 Claudeによる翻訳