システムデザイン面接完全ガイド2025：大規模システム設計、スケーラビリティ、可用性パターン

面接官：「URL短縮サービスを設計してください。」

良い質問の例：
Q：「想定DAUはどれくらいですか？」
A：「1億人です。」

Q：「URL短縮とリダイレクションのどちらが重要ですか？」
A：「リダイレクションがより重要です。読み取りの方が圧倒的に多いです。」

Q：「短縮URLの長さに制限はありますか？」
A：「できるだけ短くしてください。」

Q：「カスタムURLをサポートする必要がありますか？」
A：「はい、オプションでサポートしてください。」

+-----------+     +---------------+     +---------------+
|  Client   |---->| Load Balancer |---->|  Web Server   |
+-----------+     +---------------+     +------+--------+
                                               |
                    +--------------------------+
                    v                          v
             +-----------+            +---------------+
             |   Cache   |            |   Database    |
             +-----------+            +---------------+

スケーリング前：          スケーリング後：
+---------------+      +---------------+
|  4 CPU        |      |  32 CPU       |
|  16GB RAM     | ---> |  256GB RAM    |
|  500GB SSD    |      |  4TB SSD      |
+---------------+      +---------------+

                    +---------------+
              +---->|  Server 1     |
              |     +---------------+
+-----------+ |     +---------------+
|   Load    |-+---->|  Server 2     |
| Balancer  | |     +---------------+
+-----------+ |     +---------------+
              +---->|  Server 3     |
              |     +---------------+
              |     +---------------+
              +---->|  Server N     |
                    +---------------+

Bad (Stateful):
+-----------+  session  +-----------+
|  Client   |---------->| Server A  |  (Server Aが落ちるとセッション喪失)
+-----------+           +-----------+

Good (Stateless):
+-----------+     +-----------+     +-----------+
|  Client   |---->|   Any     |---->|   Redis   |
+-----------+     |  Server   |     | (Session) |
                  +-----------+     +-----------+

# AWS Auto Scaling設定例
AutoScalingGroup:
  MinSize: 2
  MaxSize: 20
  DesiredCapacity: 4
  TargetTrackingScaling:
    TargetValue: 70.0          # CPU 70%維持
    PredefinedMetricType: ASGAverageCPUUtilization

  # スケジュールベーススケーリング（予測可能なトラフィック）
  ScheduledActions:
    - Schedule: "0 8 * * MON-FRI"   # 平日午前8時
      MinSize: 6
    - Schedule: "0 22 * * *"        # 毎日午後10時
      MinSize: 2

1. Round Robin（順次配分）
   Request 1 -> Server A
   Request 2 -> Server B
   Request 3 -> Server C
   Request 4 -> Server A  （最初に戻る）

2. Weighted Round Robin（加重順次）
   Server A (weight=5): 5リクエスト処理
   Server B (weight=3): 3リクエスト処理
   Server C (weight=2): 2リクエスト処理

3. Least Connections（最少接続）
   Server A: 10 connections  <-- 新リクエストはここへ
   Server B: 25 connections
   Server C: 18 connections

4. IP Hash（IPベース配分）
   hash(client_ip) % server_count = target_server
   -> 同じクライアントは常に同じサーバーへ

L4（トランスポート層）:
+----------+    TCP/UDP     +-----------+
| Client   |--------------->| L4 LB     |-- IP:Portベースの分配
+----------+                +-----------+
  高速、シンプル、SSLオフロード不可

L7（アプリケーション層）:
+----------+    HTTP/HTTPS  +-----------+
| Client   |--------------->| L7 LB     |-- URL, Header, Cookieベースの分配
+----------+                +-----------+
  コンテンツベースルーティング、SSL終端、より柔軟

通常のハッシュ:
hash(key) % 3 = サーバー番号
-> サーバー追加時: hash(key) % 4 = ほとんどのキーが移動！

コンシステントハッシュ（ハッシュリング）:

        Server A
        /      \
       /   0    \
      /          \
  Server D     Server B
      \          /
       \   key  /
        \  |  /
        Server C

-> サーバー追加時: 隣接キーのみ移動（全体の約1/N）

class ConsistentHash:
    def __init__(self, nodes, virtual_nodes=150):
        self.ring = SortedDict()
        self.virtual_nodes = virtual_nodes

        for node in nodes:
            for i in range(virtual_nodes):
                key = self._hash(f"node-vn-i")
                self.ring[key] = node

    def get_node(self, data_key):
        if not self.ring:
            return None
        hash_val = self._hash(data_key)
        # ハッシュリング上で時計回りに最も近いノードを見つける
        idx = self.ring.bisect_right(hash_val)
        if idx == len(self.ring):
            idx = 0
        return self.ring.peekitem(idx)[1]

    def _hash(self, key):
        return int(hashlib.md5(key.encode()).hexdigest(), 16)

1. Cache-Aside（Lazy Loading）:
   +--------+  1.読取  +---------+
   |  App   |-------->|  Cache  |
   +---+----+  miss   +---------+
       | 2.DB読取        ^
       v           3.キャッシュ保存
   +--------+
   |   DB   |
   +--------+

2. Write-Through:
   +--------+  1.書込  +---------+  2.同期書込  +--------+
   |  App   |-------->|  Cache  |------------>|   DB   |
   +--------+         +---------+             +--------+
   （常に一貫性保証、書込レイテンシ増加）

3. Write-Back（Write-Behind）:
   +--------+  1.書込  +---------+  2.非同期バッチ書込  +--------+
   |  App   |-------->|  Cache  |==================>|   DB   |
   +--------+         +---------+                   +--------+
   （書込性能優秀、データ喪失リスク）

4. Write-Around:
   +--------+  1.書込  +--------+
   |  App   |-------->|   DB   |
   +---+----+         +--------+
       | 2.読取時キャッシュロード
       v
   +---------+
   |  Cache  |
   +---------+

# Redis - 多様なデータ構造をサポート
import redis

r = redis.Redis(host='localhost', port=6379)

# String
r.set('user:1001:name', 'Alice', ex=3600)  # 1時間TTL

# Hash
r.hset('user:1001', mapping={
    'name': 'Alice',
    'email': 'alice@example.com',
    'login_count': 42
})

# Sorted Set（リーダーボード）
r.zadd('leaderboard', {'player_a': 1500, 'player_b': 1800})
top_10 = r.zrevrange('leaderboard', 0, 9, withscores=True)

# Pub/Sub
r.publish('notifications', 'New message!')

CDNなし:
ユーザー(東京) ---- 10000km ----> Origin Server(米国)
RTT: ~200ms

CDNあり:
ユーザー(東京) ---- 20km ----> CDN Edge(東京) -- cache hit
RTT: ~5ms

Cache Miss時:
ユーザー(東京) -> CDN Edge(東京) -> Origin(米国)
                | キャッシュ保存
         次リクエストからEdgeで応答

1. TTLベース: Cache-Control: max-age=86400
2. バージョニング: /static/app.v2.3.1.js
3. 手動無効化: CloudFront Invalidation
4. タグベース: Surrogate-Keyヘッダーで選択的パージ

1. Cache Stampede（キャッシュスタンピード）:
   TTL満了 -> 数千リクエストが同時にDBへ殺到
   解決: Mutexロック + 事前更新

2. Cache Penetration（キャッシュ貫通）:
   存在しないキーの繰り返し照会 -> 毎回DB照会
   解決: Bloom Filter + 空結果もキャッシュ

3. Hot Key Problem:
   特定キーにトラフィック集中 -> 単一キャッシュノード過負荷
   解決: ローカルキャッシュ + キー複製（key_1, key_2, ...）

Master-Slaveレプリケーション:
+-----------+     同期/非同期レプリケーション     +-----------+
|  Master   | ==================================> |  Slave 1  |  <- 読取専用
|  (Write)  | ==================================> |  Slave 2  |  <- 読取専用
+-----------+                                     +-----------+

Multi-Masterレプリケーション:
+-----------+ <=================================> +-----------+
| Master 1  |          双方向レプリケーション        | Master 2  |
| (R/W)     |                                     | (R/W)     |
+-----------+                                     +-----------+
（コンフリクト解決が必要）

シャーディング前:
+-----------------------+
|   Single Database     |
|   10TB、レイテンシ増加  |
+-----------------------+

シャーディング後（Hashベース）:
hash(user_id) % 4 = shard_number

+-----------+ +-----------+ +-----------+ +-----------+
|  Shard 0  | |  Shard 1  | |  Shard 2  | |  Shard 3  |
|  2.5TB    | |  2.5TB    | |  2.5TB    | |  2.5TB    |
+-----------+ +-----------+ +-----------+ +-----------+

1. ジョインクエリ: シャード間ジョイン不可 -> 非正規化またはアプリレベルジョイン
2. リバランシング: データ増加時のシャード再分配 -> Consistent Hashing活用
3. ホットスポット: 特定シャードにトラフィック集中 -> シャードキー再設計
4. トランザクション: 分散トランザクション -> Sagaパターンまたは2PC
5. ユニークID: グローバルユニークID必要 -> Snowflake ID, UUID

       Consistency（一貫性）
         /          \
        /            \
       /     CA       \
      /  (single DC)   \
     /------------------\
    |                    |
 CP |  分散システム       | AP
    |  Pは避けられない    |
    |--------------------|
         Availability
         （可用性）

ネットワークパーティション発生時:
CPシステム -> 一貫性維持、一部リクエスト拒否
APシステム -> 可用性維持、一時的不整合許容

if (Partition) then
    Choose between Availability and Consistency
else
    Choose between Latency and Consistency

例:
- DynamoDB:   PA/EL（可用性 + 低レイテンシ）
- MongoDB:    PC/EC（一貫性優先）
- Cassandra:  PA/EL（可用性 + 低レイテンシ）
- PostgreSQL(single): PC/EC（一貫性 + 一貫性）

同期処理:
Client -> API -> メール送信(3s) -> 画像リサイズ(2s) -> ログ保存(1s) -> Response
合計6秒待機

非同期処理:
Client -> API -> Message Queue -> Response（即座に）
                    |
             +------+------+
             v             v
       Email Worker   Image Worker
         (3s)           (2s)
合計0.1秒待機

Apache Kafka:
+-----------+     +---------------------------+
| Producer  |---->|  Topic: orders            |
+-----------+     |  +-------+-------+------+ |
                  |  |  P0   |  P1   |  P2  | |
                  |  +---+---+---+---+--+---+ |
                  +------+-------+------+-----+
                         v       v      v
                  +------------------------+
                  |  Consumer Group A       |
                  | （各パーティション1消費者）|
                  +------------------------+

1. At-Most-Once（最大1回）:
   Producer -> Broker（ACK待たない）
   高速だがメッセージ喪失の可能性
   用途: ログ、メトリック（喪失許容）

2. At-Least-Once（最低1回）:
   Producer -> Broker -> ACK
   ACK失敗時に再送 -> 重複の可能性
   用途: ほとんどのシステム（冪等処理必要）

3. Exactly-Once（正確に1回）:
   トランザクションベースまたは冪等キー使用
   パフォーマンスオーバーヘッドあり
   用途: 金融、決済（正確性必須）

import time
import threading

class TokenBucket:
    def __init__(self, capacity, refill_rate):
        self.capacity = capacity        # バケット最大トークン数
        self.tokens = capacity           # 現在のトークン数
        self.refill_rate = refill_rate   # 毎秒追加トークン
        self.last_refill = time.time()
        self.lock = threading.Lock()

    def allow_request(self):
        with self.lock:
            now = time.time()
            # トークン補充
            elapsed = now - self.last_refill
            self.tokens = min(
                self.capacity,
                self.tokens + elapsed * self.refill_rate
            )
            self.last_refill = now

            # リクエスト許可判定
            if self.tokens >= 1:
                self.tokens -= 1
                return True
            return False

# 毎秒10リクエスト、バースト最大20
limiter = TokenBucket(capacity=20, refill_rate=10)

import time
from collections import deque

class SlidingWindowLog:
    def __init__(self, window_size, max_requests):
        self.window_size = window_size   # ウィンドウサイズ（秒）
        self.max_requests = max_requests
        self.requests = deque()

    def allow_request(self):
        now = time.time()
        # ウィンドウ外の古いリクエストを削除
        while self.requests and self.requests[0] < now - self.window_size:
            self.requests.popleft()

        if len(self.requests) < self.max_requests:
            self.requests.append(now)
            return True
        return False

# 1分間に最大100リクエスト
limiter = SlidingWindowLog(window_size=60, max_requests=100)

Sliding Window Counter（メモリ効率的）:

前ウィンドウカウント: 84
現ウィンドウカウント: 36
ウィンドウサイズ: 60秒
現在位置: ウィンドウの25%地点

加重カウント = 84 * (1 - 0.25) + 36 = 84 * 0.75 + 36 = 99

max_requests = 100 -> 許可（99 < 100）

書込: 1億DAU * 平均0.1 URL/日 = 1000万/日
QPS（書込）= 10,000,000 / 86,400 = ~116 QPS
QPS（読取）= 116 * 100 = ~11,600 QPS
ピークQPS = 11,600 * 3 = ~35,000 QPS

ストレージ容量（5年）:
10,000,000 * 365 * 5 = 182.5億レコード
各レコード ~500 bytes -> 182.5億 * 500B = ~9.1TB

+----------+     +------+     +---------------+
|  Client  |---->|  LB  |---->|  API Server   |
+----------+     +------+     +------+--------+
                                     |
                    +----------------+----------------+
                    v                v                v
              +-----------+  +-----------+  +-----------+
              |   Redis   |  |  MySQL    |  | Analytics |
              |   Cache   |  | (Sharded) |  |  (Kafka)  |
              +-----------+  +-----------+  +-----------+

import hashlib

def generate_short_url(long_url, counter):
    # 方法1: Base62エンコーディング（auto-increment ID）
    chars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
    short = ""
    n = counter
    while n > 0:
        short = chars[n % 62] + short
        n //= 62
    return short  # 例: "dK4x9Z"

    # 方法2: MD5ハッシュ + Base62（最初の7文字）
    hash_val = hashlib.md5(long_url.encode()).hexdigest()
    num = int(hash_val[:12], 16)
    short = ""
    for _ in range(7):
        short = chars[num % 62] + short
        num //= 62
    return short

# 62^7 = 約3.5兆個のユニークURL可能

Fan-out on Write（Pushモデル）:
ユーザーがツイート投稿時 -> 全フォロワーのタイムラインに事前保存

User Aがツイート -> Fan-out Service
                   +--> Follower 1のタイムラインキャッシュに追加
                   +--> Follower 2のタイムラインキャッシュに追加
                   +--> Follower Nのタイムラインキャッシュに追加

メリット: 読取が非常に高速（事前計算済み）
デメリット: フォロワーが多いと書込負荷が膨大

Fan-out on Read（Pullモデル）:
タイムラインリクエスト時 -> フォロー中ユーザーのツイートをリアルタイムで組立

User Bのタイムラインリクエスト -> フォローユーザー照会
                                +--> User Xの最新ツイート
                                +--> User Yの最新ツイート
                                +--> User Zの最新ツイート
                                -> マージ + ソート -> 返却

メリット: 書込がシンプル
デメリット: 読取時に複数DB照会が必要

一般ユーザー（フォロワー < 10,000）: Fan-out on Write
セレブリティ（フォロワー > 10,000）: Fan-out on Read

タイムライン取得:
1. キャッシュから事前ファンアウト済みツイートを取得
2. フォロー中セレブリティの最新ツイートを照会
3. 両結果をマージ + 時間順ソート

WebSocketベースのリアルタイム通信:

+----------+  WebSocket  +---------------+
| User A   |<==========>|  Chat         |
+----------+             |  Server      |
                         |  Cluster     |
+----------+  WebSocket  |              |
| User B   |<==========>|              |
+----------+             +------+-------+
                                |
                    +-----------+-----------+
                    v           v           v
              +----------+ +--------+ +----------+
              |  Redis   | | Kafka  | | Message  |
              | Presence | |        | |    DB    |
              +----------+ +--------+ +----------+

方法1: サーバータイムスタンプ（シンプルだが時計同期問題）
方法2: Snowflake ID（時間 + サーバー + シーケンス）

Snowflake ID構造（64ビット）:
+---------------+----------+----------+--------------+
|  Timestamp    | Datactr  | Machine  |   Sequence   |
|   41 bits     |  5 bits  |  5 bits  |   12 bits    |
+---------------+----------+----------+--------------+
-> 時間順ソート可能 + グローバルユニーク
-> 毎秒約400万ID生成可能

ビデオアップロードパイプライン:

+-----------+    +-----------+    +-------------------+
| Uploader  |--->|  Object   |--->|  Transcoding      |
|           |    |  Store    |    |  Pipeline          |
+-----------+    |  (S3)     |    |                    |
                 +-----------+    |  +---------------+ |
                                  |  | 240p          | |
                                  |  | 480p          | |
                                  |  | 720p          | |
                                  |  | 1080p         | |
                                  |  | 4K            | |
                                  |  +---------------+ |
                                  +---------+----------+
                                            v
                                  +-------------------+
                                  |   CDNにデプロイ    |
                                  |（全世界Edge）      |
                                  +-------------------+

ユーザーのネットワーク状態に応じて画質を自動調整:

帯域幅10Mbps -> 1080pセグメントをリクエスト
帯域幅3Mbps  -> 480pセグメントに切替
帯域幅回復   -> 段階的に画質を上げる

HLS（HTTP Live Streaming）方式:
1. ビデオを2~10秒セグメントに分割
2. 各セグメントを複数画質でエンコード
3. m3u8マニフェストファイルでセグメント一覧を提供
4. クライアントが帯域幅に合ったセグメントを選択

レイテンシ:
- L1キャッシュ参照: ~1ns
- L2キャッシュ参照: ~4ns
- メインメモリ参照: ~100ns
- SSDランダム読取: ~150us
- HDDシーク: ~10ms
- 同一DCラウンドトリップ: ~0.5ms
- 米国 - 欧州ラウンドトリップ: ~75ms

容量:
- 1文字 = 1 byte（ASCII）/ 2~4 bytes（UTF-8）
- 1 UUID = 36 bytes（文字列）/ 16 bytes（バイナリ）
- 1画像（中サイズ）= ~200KB
- 1動画（1分、720p）= ~50MB

日次換算:
- 1日 = 86,400秒 = ~100,000秒（簡易計算）
- 100万リクエスト/日 = ~12 QPS
- 1億リクエスト/日 = ~1,200 QPS

Twitter規模の推定:
- DAU: 3億人
- 平均ツイート閲覧: 100回/日
- 読取QPS = 3億 * 100 / 86,400 = ~347,000 QPS
- ピークQPS = 347,000 * 3 = ~1,000,000 QPS

- 平均ツイート投稿: 2回/日
- 書込QPS = 3億 * 2 / 86,400 = ~6,944 QPS

ストレージ:
- ツイートサイズ: ~300 bytes（テキスト + メタデータ）
- 日次: 6億ツイート * 300B = ~180GB/日
- 5年: 180GB * 365 * 5 = ~328TB
- メディア含む: ~5倍 = ~1.6PB

1. 要件確認なしにいきなり設計開始
   -> 必ず5分は質問に投資

2. 1つのコンポーネントだけに集中
   -> 全体像を先に、面接官が求める部分を深堀り

3. 完璧な設計を追求
   -> トレードオフを説明する方が重要

4. 数字なしの設計
   -> QPS、ストレージ量、帯域幅を必ず計算

5. 一方的に話し続ける
   -> 面接官と対話しフィードバックを受容

6. 過剰な技術導入
   -> 問題に適した適切な技術選択

1. 構造化されたアプローチ:
   - 4段階フレームワークを常に遵守
   - 各ステップでの時間管理

2. トレードオフの説明:
   - 「このアプローチのメリットはA、デメリットはBです。」
   - 「代替案Cもありますが、今回の状況ではDがより適切です。」

3. 実例の引用:
   - 「Netflixはこの問題をXアプローチで解決しました。」
   - 「以前のプロジェクトで同様の問題を経験しました。」

4. ホワイトボードの活用:
   - きれいなダイアグラム
   - データフローの矢印
   - 数値/メトリックの表示

5. 面接官のヒントを受容:
   - 面接官の質問はヒント
   - 「良い指摘です、その部分を改善すれば…」