Day 7: URL短縮サービスの設計
今日学ぶこと
- システム設計面接の進め方（フルウォークスルー）
- 要件定義と見積もり
- URL短縮のエンコーディング手法
- データベース選定
- キャッシュ戦略
- アナリティクスパイプライン
- 301 vs 302リダイレクト
ステップ1：要件の明確化
面接では、まず要件を確認することが最も重要です。
機能要件
- URL短縮: 長いURLを短いURLに変換する
- リダイレクト: 短縮URLにアクセスすると元のURLにリダイレクトする
- カスタムエイリアス: ユーザーが任意の短縮文字列を指定できる（オプション）
- アナリティクス: クリック数、地域、デバイス等の統計
- URL有効期限: 指定した期間後にURLを無効化
非機能要件
- 高可用性: リダイレクトは常に利用可能であること
- 低レイテンシ: リダイレクトは数十ミリ秒以内
- 短縮URLは推測困難: セキュリティ上、順番にならない
ステップ2：概算見積もり
面接で概算を求められることは多いです。桁を間違えなければOKです。
| 項目 | 値 |
|---|---|
| 読み取り（リダイレクト） | 100M リクエスト/日 |
| 書き込み（URL作成） | 1M リクエスト/日 |
| 読み書き比率 | 100:1 |
| URL保存期間 | 5年 |
計算
// Write QPS
1M / 86400 ≈ 12 writes/sec
// Read QPS
100M / 86400 ≈ 1,160 reads/sec
Peak: ~2,300 reads/sec (2x average)
// Storage (5 years)
Total URLs = 1M × 365 × 5 = 1.825B URLs
Average URL size = 500 bytes (original URL + metadata)
Storage = 1.825B × 500B ≈ 912 GB ≈ ~1 TB
// Cache (80/20 rule: 20% of URLs generate 80% of traffic)
Daily unique URLs accessed = 100M × 0.2 = 20M
Cache size = 20M × 500B = 10 GB
ステップ3：ハイレベルアーキテクチャ
flowchart TB
Client["クライアント"]
LB["Load Balancer"]
Client --> LB
subgraph App["アプリケーション層"]
API1["API Server 1"]
API2["API Server 2"]
API3["API Server N"]
end
LB --> API1
LB --> API2
LB --> API3
subgraph Cache["キャッシュ層"]
Redis["Redis Cluster"]
end
subgraph DB["データベース層"]
Primary["Primary DB"]
Replica1["Read Replica 1"]
Replica2["Read Replica 2"]
end
subgraph Analytics["アナリティクス"]
Kafka["Kafka"]
Spark["Spark / Flink"]
OLAP["Analytics DB"]
end
API1 --> Redis
API2 --> Redis
API1 --> Primary
Primary --> Replica1
Primary --> Replica2
API2 --> Kafka
Kafka --> Spark --> OLAP
style App fill:#3b82f6,color:#fff
style Cache fill:#f59e0b,color:#fff
style DB fill:#8b5cf6,color:#fff
style Analytics fill:#22c55e,color:#fff
ステップ4：URLエンコーディング
短縮URLのキーをどう生成するかが設計の核心です。
方式1：Base62エンコーディング
Base62は [a-zA-Z0-9] の62文字を使います。
7文字のBase62 = 62^7 = 3.5兆 パターン（十分）
例: https://short.url/aB3x9Kz
方式2：ハッシュベース
Original URL → MD5/SHA256 → 先頭7文字を使用
例: "https://example.com/very/long/url"
→ MD5: "a1b2c3d4e5f6..."
→ 短縮キー: "a1b2c3d"
方式3：カウンターベース
Auto-increment ID → Base62変換
例: ID 1000000 → Base62 "4c92"
方式の比較
| 方式 | メリット | デメリット |
|---|---|---|
| Base62 + ユニークID生成 | 衝突なし、予測困難 | ID生成器が必要 |
| ハッシュベース | 実装が簡単 | 衝突の可能性、衝突解決が必要 |
| カウンターベース | 衝突なし、シンプル | 予測可能（セキュリティ懸念） |
flowchart LR
subgraph Recommended["推奨: ユニークID + Base62"]
IDGen["ID Generator\n(Snowflake/UUID)"]
Encode["Base62\nエンコード"]
Short["短縮キー\naB3x9Kz"]
end
IDGen --> Encode --> Short
style Recommended fill:#22c55e,color:#fff
ユニークID生成の選択肢
| 方式 | 説明 | 適用 |
|---|---|---|
| UUID | 128ビットのランダムID | 衝突確率が極めて低い |
| Snowflake | タイムスタンプ + マシンID + シーケンス | Twitter方式、順序保証 |
| Zookeeper | 分散カウンター | 中央管理型 |
| Redis INCR | Redisのアトミックインクリメント | 高速だがSPOF注意 |
ステップ5：データベース選定
スキーマ設計
-- URL mapping table
CREATE TABLE urls (
id BIGINT PRIMARY KEY,
short_key VARCHAR(7) UNIQUE NOT NULL,
original_url TEXT NOT NULL,
user_id BIGINT,
created_at TIMESTAMP DEFAULT NOW(),
expires_at TIMESTAMP,
click_count BIGINT DEFAULT 0
);
-- Index for fast lookups
CREATE INDEX idx_short_key ON urls(short_key);
CREATE INDEX idx_expires_at ON urls(expires_at);
SQL vs NoSQL
| 観点 | SQL（PostgreSQL） | NoSQL（DynamoDB） |
|---|---|---|
| クエリ | 柔軟なクエリ | Key-Valueルックアップに最適 |
| スケーラビリティ | Read Replicaで読み取りスケール | 水平スケーリングが容易 |
| 一貫性 | Strong Consistency | Eventual Consistency（設定可能） |
| 適性 | 複雑なクエリが必要な場合 | 高スループット、シンプルなアクセスパターン |
この設計の場合: アクセスパターンがシンプル（キーでのルックアップ）なので、NoSQL（DynamoDB）が適しています。ただし、SQLでも十分にスケールできます。
ステップ6：キャッシュ戦略
読み取りが圧倒的に多い（100:1）ため、キャッシュが非常に効果的です。
flowchart TB
Client["クライアント"]
API["API Server"]
Redis["Redis Cache"]
DB["Database"]
Client -->|"GET /aB3x9Kz"| API
API -->|"1. キャッシュ確認"| Redis
Redis -->|"Hit: URLを返す"| API
Redis -->|"Miss"| API
API -->|"2. DBから取得"| DB
DB -->|"URLデータ"| API
API -->|"3. キャッシュに保存"| Redis
API -->|"302 Redirect"| Client
style Redis fill:#f59e0b,color:#fff
style DB fill:#8b5cf6,color:#fff
キャッシュ戦略：
- Cache-Aside: キャッシュミス時にDBから読み、キャッシュに書く
- TTL: 24時間（よくアクセスされるURLは自然に維持される）
- 容量: 約10GB（20%のホットデータをカバー）
- 置換ポリシー: LRU（Least Recently Used）
ステップ7：リダイレクト — 301 vs 302
| コード | 意味 | 特徴 |
|---|---|---|
| 301 Moved Permanently | 恒久的なリダイレクト | ブラウザがキャッシュする |
| 302 Found | 一時的なリダイレクト | 毎回サーバーにアクセスする |
flowchart LR
subgraph R301["301の場合"]
C1["ブラウザ"]
S1["短縮URLサーバー"]
O1["元のURL"]
C1 -->|"初回のみ"| S1
S1 -->|"301"| C1
C1 -->|"2回目以降\n直接アクセス"| O1
end
subgraph R302["302の場合"]
C2["ブラウザ"]
S2["短縮URLサーバー"]
O2["元のURL"]
C2 -->|"毎回"| S2
S2 -->|"302"| C2
C2 --> O2
end
style R301 fill:#3b82f6,color:#fff
style R302 fill:#22c55e,color:#fff
アナリティクスが必要な場合は302を使用します。 301だとブラウザがキャッシュするため、2回目以降のクリックを計測できません。
ステップ8：アナリティクスパイプライン
flowchart LR
Click["クリックイベント"]
Kafka["Kafka"]
Process["Stream Processing\n(Flink/Spark)"]
Store["Analytics DB\n(ClickHouse)"]
Dash["ダッシュボード"]
Click --> Kafka --> Process --> Store --> Dash
style Kafka fill:#f59e0b,color:#fff
style Process fill:#22c55e,color:#fff
style Store fill:#8b5cf6,color:#fff
記録するデータ：
- クリック日時
- IPアドレス → 地域（GeoIP）
- User-Agent → デバイス、ブラウザ
- Referer → 流入元
- 短縮URLキー
リアルタイム処理にはKafka + Flink、バッチ分析にはSpark + Data Warehouseを使います。
URL有効期限の実装
flowchart TB
subgraph Expiration["有効期限の処理"]
Check["リダイレクト時に\n期限チェック"]
Cron["定期バッチで\n期限切れURLを削除"]
Lazy["遅延削除\n(アクセス時に確認)"]
end
style Expiration fill:#f59e0b,color:#fff
2つのアプローチ：
| 方式 | 説明 | メリット |
|---|---|---|
| 遅延削除（Lazy） | アクセス時に期限をチェック | 即座に反映、余分な処理なし |
| 定期削除（Cron） | バッチジョブで期限切れURLを削除 | ストレージを節約 |
推奨: 両方を組み合わせます。リダイレクト時に期限チェック（即座にエラー返却）+ 日次バッチで古いデータを削除（ストレージ節約）。
まとめ
設計のポイント一覧
| コンポーネント | 選択 | 理由 |
|---|---|---|
| URLエンコーディング | Snowflake ID + Base62 | 衝突なし、予測困難 |
| データベース | NoSQL（DynamoDB） | Key-Valueルックアップ、水平スケール |
| キャッシュ | Redis（Cache-Aside） | 読み取り比率100:1に対応 |
| リダイレクト | 302 Found | アナリティクスのため |
| アナリティクス | Kafka + Flink | リアルタイム集計 |
| 有効期限 | 遅延削除 + 定期バッチ | 即時反映 + ストレージ節約 |
面接の進め方チェックリスト
- 要件確認（5分）: 機能・非機能要件を確認
- 概算見積もり（5分）: QPS、ストレージ、帯域を計算
- ハイレベル設計（10分）: コンポーネント図を描く
- 詳細設計（15分）: 核心部分を深掘り
- ボトルネック議論（5分）: スケーリング、障害対策
練習問題
基礎レベル
- Base62で7文字の短縮URLを使う場合、何個のユニークなURLを生成できるか計算してください
- 301リダイレクトと302リダイレクトの違いを、URL短縮サービスの観点で説明してください
中級レベル
- カスタムエイリアス機能を追加する場合、データベーススキーマとAPIをどう変更するか設計してください
- 短縮URLサービスが1日10億リクエストを受けた場合、キャッシュサイズとサーバー台数を概算してください
チャレンジ
- URL短縮サービスにURL有効期限機能を追加し、期限切れURLのストレージを効率的に回収する仕組みを設計してください。数十億のURLが存在する場合のパフォーマンスも考慮してください
参考リンク
次回予告
Day 8: SNSフィードとチャットシステムの設計 — ニュースフィードのPush/Pullモデルの比較と、WebSocketを使ったリアルタイムチャットシステムを設計します。