難易度: ★☆☆（最初に練習すべき問題）

1-1. 要件の確認

機能要件:
  ・長い URL を短い URL に変換する
  ・短い URL にアクセスすると元 URL へリダイレクトする
  ・任意のカスタムエイリアス（optional）
  ・有効期限（optional）
機能外:
  ・分析（クリック数）は今回は簡易的に
非機能:
  ・可用性が最重要（リダイレクトが落ちると全リンクが死ぬ）
  ・リダイレクトのレイテンシ p99 < 50 ms
  ・短縮 URL は推測されにくい方が望ましい
  ・読み:書き = 100:1

1-2. 見積もり

書き込み: 1 億 URL/月 = 1億 / (30 × 10^5) ≒ 33 QPS（ピーク 100 QPS）
読み取り: 33 × 100 = 3,300 QPS（ピーク 1 万 QPS）
ストレージ: 1 レコード ≒ 500 B（短縮キー、元URL、user_id、作成日、期限）
  5 年分 = 1 億 × 12 × 5 = 60 億件 × 500 B = 3 TB
  → **単一ノードの容量だけでなく、IOPS、ワーキングセット、復旧時間を評価し、レプリカ + 将来のシャーディングを考慮**
キャッシュ: 全レコードの割合ではなく、アクセス分布、TTL、キャッシュ項目サイズ、ヒット率目標から容量を決める

1-3. API

POST /v1/urls  {long_url, custom_alias?, expires_at?} → {short_url}
GET  /{key}    → 301/302 リダイレクト

📐 301 と 302 の選択（頻出）:

• 301 (Permanent): ブラウザがキャッシュ → サーバー負荷が減るが、クリック計測ができない
• 302 (Found): 毎回サーバーに来る → 計測できるが負荷が高い → 分析が要るなら 302、負荷削減優先なら 301。実務では 302 + 短い Cache-Control が多い。

1-4. 短縮キーの生成（この問題の核心）

📐 推奨: C（Key Generation Service）

オフラインで 62^7 空間からキーを生成し、生成時に一意性を確認して reserved として保存
  → 各アプリノードが 1000 個ずつアトミックに claim してメモリに保持
  → 採番はメモリ内で完結（DBアクセスなし）
  → ノード再起動で未使用キーが失われても、再利用・回収できる状態を持つ

📐 長さの計算: 62^7 = 約 3.52 兆。60 億件使っても占有率は約 0.17% ですが、 ランダム抽出の誕生日問題では衝突確率はほぼ 1 です。期待される衝突ペア数は概算で m(m-1)/(2N) ≒ 510 万。一意性は空間の広さではなく、生成・保存時に保証します。

1-5. アーキテクチャ

[Client]
   │ GET /aBc1De2
   ▼
[CDN / エッジ]（人気リンクはエッジでキャッシュ）
   ▼
[LB] → [リダイレクトサービス（ステートレス、多数）]
              │ ①キャッシュを見る
              ▼
        [Redis クラスタ]  key → long_url（LRU、TTL 24h）
              │ ミス
              ▼
        [KV ストア / DynamoDB or Cassandra]  ← シャードキー = short_key

[作成サービス] → [KGS（事前生成キープール）] → [KV ストア]
                    ↓
              [クリックイベント] → Kafka → 分析基盤（非同期、リダイレクトを遅らせない）

1-6. 深掘り

1-7. まとめの言い方

「読み取りが 100 倍支配的なので、リダイレクトパスを最短にすることに集中しました。 キーは事前生成方式で衝突チェックを排除し、 Redis と CDN の 2 層キャッシュでほとんどのリクエストを DB に到達させません。 分析は非同期化してリダイレクトのレイテンシに影響させない構成です。」

難易度: ★★★（最頻出。必ずマスターすること）

2-1. 要件

機能: ①投稿 ②ホームタイムライン（フォロー中の人の投稿を新しい順） ③フォロー
非機能: DAU 2 億、読み:書き = 100:1、タイムラインの p99 < 200 ms
       投稿は数秒遅れて見えてよい（結果整合で可）

2-2. 見積もり（第 3 章の再掲）

書き込み 4,000 QPS（ピーク 1.2 万）、読み取り 40 万 QPS（ピーク 120 万）
ツイート本文 = 400 GB/日、5 年で 730 TB（レプリカ込み 2.2 PB）
→ **読み取り最適化が全て。シャーディング必須。**

2-3. 核心：ファンアウト戦略

方式 A: Fan-out on Read（Pull 型）

タイムライン取得時に、フォロー中 N 人の最新投稿を取得してマージソート
  読み: 遅い（N=500 なら 500 回のクエリ or 大きな IN 句）
  書き: 速い（自分のテーブルに 1 行入れるだけ）

方式 B: Fan-out on Write（Push 型） ⭐ 基本

投稿時に、全フォロワーのタイムラインキャッシュに ID を配る
  読み: 極めて速い（自分のリストを取るだけ = O(1)）
  書き: 重い（フォロワー 1 億人なら 1 億回の書き込み）

📐 答えはハイブリッド:

通常ユーザー（フォロワー < 10 万）→ Push（書き込み時にファンアウト）
セレブ（フォロワー ≥ 10 万）      → Push しない
タイムライン取得時:
  ① 事前計算済みのタイムラインを Redis から取得（99% はこれ）
  ② フォロー中のセレブの投稿を別途取得（数人分だけなので軽い）
  ③ 2 つをマージして時系列にソート → 返す

🎤 この「ハイブリッド」に自力で辿り着くのが、この問題の合格ラインです。

2-4. データモデル

tweets(tweet_id PK[Snowflake], user_id, content, media_urls, created_at)
   → シャードキー: tweet_id（Snowflake なので時刻順、範囲でも引ける）
   or user_id（ユーザーの全投稿取得が 1 シャードで済む）

follows(follower_id, followee_id, created_at)
   → 2 方向必要: PK(follower_id, followee_id) と 逆引きテーブル/インデックス

timeline_cache: Redis の List or Sorted Set
   key = "timeline:{user_id}"、value = tweet_id のリスト（最新 800 件のみ保持）

📐 タイムラインには tweet_id だけ入れる（本文は入れない）。 理由: ① メモリ節約（8 B × 800 = 6.4 KB/ユーザー） ② 投稿が削除・編集されたときに整合する ③ 本文は別途 multi-get（Redis の MGET で 1 往復）

2-5. アーキテクチャ

【投稿パス】
[Client] → [API GW] → [投稿サービス] → [tweets DB(シャード)]
                            │
                            └→ [Kafka: tweet_created]
                                     ▼
                              [ファンアウトワーカー]
                                 ① フォロワー一覧を取得
                                 ② セレブなら何もしない
                                 ③ 各フォロワーの Redis timeline に LPUSH + LTRIM 800
                                 ④ 非アクティブユーザー（30日ログインなし）はスキップ ← 重要な最適化

【読み取りパス】
[Client] → [API GW] → [タイムラインサービス]
              ① Redis から tweet_id 800 件を取得
              ② フォロー中セレブの最新投稿を取得（別キャッシュ）
              ③ マージ + ソート + ページング
              ④ tweet_id → 本文を Redis MGET（ミス分だけ DB）
              ⑤ ユーザー情報・画像 URL を付与して返す

2-6. 深掘り

2-7. まとめ

「読み:書き = 100:1 なので、書き込み時に読み取りの仕事を済ませる（事前計算） のが基本方針です。 ただしフォロワーが極端に多いアカウントでは書き込みコストが爆発するため、 そこだけ読み取り時マージに切り替えるハイブリッドにしました。 ボトルネックはファンアウトワーカーのスループットで、 Kafka のパーティション数とワーカー数でスケールさせます。」

難易度: ★★★

3-1. 要件

機能: ①1対1チャット ②グループチャット（最大 500 人） ③オンライン状態
     ④既読・配信済み ⑤オフライン中のメッセージ受信 ⑥メッセージ履歴
非機能: 低レイテンシ（p99 < 200 ms）、サーバーACK済みメッセージを定義した障害モデル内で失わない、チャンネル内の順序を保つ
       DAU 5 億、1 人 40 メッセージ/日

3-2. 見積もり

メッセージ数: 5億 × 40 = 200 億/日 = 20万 QPS（ピーク 60 万 QPS）
サイズ: 200 B/件 → 4 TB/日 → 5 年で 7.3 PB（テキストのみ）
同時接続: DAU の 20% が同時接続 = 1 億接続
  → 1 台 10 万接続なら **1,000 台の接続サーバー**が必要

3-3. 通信方式

📐 WebSocket（双方向・低遅延が必要なので確定）

• モバイルはバックグラウンド時に プッシュ通知（APNs / FCM） へフォールバック。

3-4. アーキテクチャ

[Client] ←WebSocket→ [接続サーバー #1..#1000]
                            │
              ┌─────────────┼──────────────┐
              ▼             ▼              ▼
       [セッションレジストリ] [メッセージサービス] [Kafka]
        Redis:                    │              │
        user_id → server_id       ▼              ▼
                            [メッセージDB]   [プッシュ通知]
                             Cassandra      [既読/配信状態]

メッセージ送信の流れ:

① A が接続サーバー S1 へ送信
② メッセージサービスがチャンネル単位のsequence（必要ならSnowflakeは識別子として別管理）を採番し、Cassandra に永続化
③ A に ACK（「サーバーに届いた」チェックマーク 1 つ）
④ レジストリで B の接続先（S7）を検索
⑤ S7 経由で B へ配信 → B から ACK（チェックマーク 2 つ = 配信済み）
⑥ B がメッセージを開いたら既読 ACK（チェックマーク青 = 既読）
⑦ B がオフラインなら → プッシュ通知 + 未配信キューに保持

3-5. データモデル（Cassandra）

CREATE TABLE messages (
  channel_id  uuid,          -- パーティションキー（1対1なら2人のIDから決定的に生成）
  message_id  bigint,        -- Snowflake（時刻順）
  sender_id   uuid,
  content     text,
  created_at  timestamp,
  PRIMARY KEY ((channel_id), message_id)
) WITH CLUSTERING ORDER BY (message_id DESC);
-- → 「あるチャンネルの最新 N 件」が 1 パーティションへの 1 シークで取れる

CREATE TABLE user_channels (user_id, last_read_message_id, channel_id, PRIMARY KEY(user_id, channel_id));

⚠️ パーティションが大きくなりすぎる問題: 何年も続くチャンネルは巨大化する → 時間バケットを複合キーに入れる: PRIMARY KEY ((channel_id, year_month), message_id)

3-6. 深掘り

3-7. まとめ

「接続の保持（ステートフル）とメッセージ処理（ステートレス）を分離するのが設計の中心です。 接続サーバーは 1,000 台規模になるため、ユーザー → サーバーのマッピングを Redis に持ち、 配信は Pub/Sub で中継します。永続化は Cassandra で、 channel_id をパーティションキー、Snowflake をクラスタリングキーにすることで 『最新 N 件の取得』を単一シークで実現します。」

難易度: ★★★★

4-1. 要件

機能: ①動画アップロード ②視聴（ストリーミング） ③検索 ④推薦（今回は軽く）
非機能: 再生開始 < 2 秒、バッファリングを最小化、DAU 10 億、
       アップロード 500 時間/分（YouTube 相当）

4-2. 見積もり

アップロード: 500 時間/分 = 8.3 時間/秒
  1 時間の動画 = 元ファイル 5 GB → 保存量 = 8.3 × 5 GB = 41 GB/秒 = 3.6 PB/日
  トランスコード後の全解像度合計で元の 1.5 倍 → 5.4 PB/日
視聴: 10 億人 × 30 分/日 × 平均 3 Mbps
  = 10^9 × 1800 秒 × 3 Mbps / 86400 秒 ≒ 62 Tbps（！）
  → **オリジンでは絶対に不可能。CDN が設計の中心**

📐 この計算で「CDN が全て」という結論に自力で到達することが評価されます。

4-3. アップロードとトランスコードのパイプライン

[Client]
  │ ① 署名付き URL を取得
  ▼
[オブジェクトストレージ（生ファイル）]  ← マルチパートで直接アップロード
  │ ② イベント通知
  ▼
[Kafka: video_uploaded]
  ▼
[トランスコードパイプライン（DAG ワークフロー）]
   ├ 検査（コーデック、破損、著作権 = コンテンツ ID）
   ├ 分割（動画を 10 秒チャンクに分けて並列処理）★ ここが速度の鍵
   ├ 並列トランスコード（240p/360p/480p/720p/1080p/4K × 複数コーデック）
   ├ サムネイル生成、字幕生成（音声認識）
   ├ セグメント化（HLS/DASH: 2〜6 秒セグメント + マニフェスト）
   └ 結合・検証
  ▼
[オブジェクトストレージ（配信用）] → [CDN へプリウォーム（人気が予想されるものだけ）]
  ▼
[メタデータ DB を "published" に更新] → 検索インデックス更新

📐 並列化が鍵: 1 時間の動画を直列にトランスコードすると数時間かかる。 10 秒チャンクに分割 → 数百ノードで並列 → 結合 で数分に短縮します。 ⚠️ チャンク境界を キーフレーム (GOP) 境界に合わせないと繋ぎ目が壊れます。

4-4. 配信（ABR ストリーミング）

[Player] → マニフェスト（.m3u8 / .mpd）を取得
         → 帯域を推定 → 適切なビットレートのセグメントを順次取得
         → 帯域が落ちたら次のセグメントから低画質へ切替（途切れない）

[Player] → [CDN エッジ]（99% がここでヒット）
              │ ミス
              ▼
        [リージョナルキャッシュ（シールド）]
              │ ミス
              ▼
        [オリジン（オブジェクトストレージ）]

📐 CDN のコンテンツ配置戦略:

• 人気動画（上位 1%）: 全エッジにプッシュ配置（プリポジション）
• 中位: リージョナルキャッシュに保持、アクセスでエッジへ昇格
• ロングテール: オリジンからプル。キャッシュミスを許容 🔬 Netflix の Open Connect は、ISP の建物内にサーバーを置き、 深夜の空き帯域で人気コンテンツを事前配信します。

4-5. データモデル

videos(video_id PK, user_id, title, description, duration, status,
       created_at, thumbnail_url, manifest_url)          → RDB or Spanner
video_renditions(video_id, resolution, bitrate, codec, storage_path)
view_counts(video_id, count)                             → Redis + 定期永続化
watch_history(user_id, video_id, position, watched_at)   → Cassandra
comments(video_id, comment_id, ...)                      → Cassandra

4-6. 深掘り

4-7. まとめ

「視聴帯域が数十 Tbps に達するため、設計の中心は CDN による配信です。 オリジンへのリクエストは 1% 未満に抑える必要があります。 アップロード側は、動画をチャンクに分割して並列トランスコードすることで 処理時間を線形に短縮します。 全体を非同期パイプラインにし、各段階を独立にスケール・リトライできる構成にしました。」

難易度: ★★★★

5-1. 要件

機能: ①ファイルのアップロード/ダウンロード ②複数デバイス間の同期
     ③共有と権限 ④バージョン履歴 ⑤オフライン編集後の同期
非機能: 帯域の効率（差分のみ転送）、競合の解決、大きなファイル（数 GB）対応

5-2. 核心：チャンク化と重複排除

ファイル → 可変長チャンク（平均 4 MB、Rabin fingerprint による境界決定）に分割
        → 各チャンクの SHA-256 を計算
        → サーバーに「このハッシュ持ってる？」と問い合わせ
        → 持っていないチャンクだけアップロード

📐 可変長チャンクが重要な理由:

固定長（4MB ごと）だと、ファイルの先頭に 1 バイト挿入しただけで
  全チャンクの境界がずれ、全チャンクが「新しいチャンク」になってしまう
可変長（内容によって境界を決める）なら、変更箇所の周辺チャンクだけが変わる

効果: 同じファイルを 100 人が持っていても保存は 1 つ。 1 GB のファイルの一部を編集しても数 MB の転送で済む。

5-3. データモデル

files(file_id PK, owner_id, parent_folder_id, name, size, current_version_id, updated_at)
versions(version_id PK, file_id, chunk_list[], created_at, created_by, size)
chunks(chunk_hash PK, storage_path, ref_count, size)   ← 重複排除の要
permissions(file_id, principal_id, role)               ← owner/editor/viewer
device_sync_state(device_id, user_id, last_sync_cursor)

📐 バージョン = チャンクハッシュのリスト。これにより 「バージョン間の差分」も「重複排除」も同じ仕組みで実現できます。

5-4. アーキテクチャ

[Client（デスクトップアプリ）]
   ├ ファイル監視（inotify / FSEvents）
   ├ チャンカー（分割 + ハッシュ）
   ├ ローカル DB（SQLite: ファイル状態、同期状態）
   └ 同期エンジン
        │
        ├─① メタデータ API →[メタデータサービス]→[メタデータ DB]
        │                                              │
        ├─② チャンクの有無を問い合わせ →[チャンクサービス]
        │
        ├─③ 未保有チャンクを直接アップロード →[オブジェクトストレージ]
        │
        └─④ 変更通知の購読 ←[通知サービス（WebSocket/ロングポーリング）]
                                    ▲
                              [変更ログ（Kafka）]

同期の流れ:

【アップロード側】
 ローカル変更を検知 → チャンク化 → 未保有チャンクのみアップロード
 → メタデータをコミット（新バージョン作成）→ 変更ログに記録

【ダウンロード側】
 変更通知を受信（or 定期ポーリング）
 → 自分の last_sync_cursor 以降の変更差分を取得
 → 未保有チャンクのみダウンロード → ローカルに再構成

📐 変更をカーソル（単調増加のシーケンス番号）で管理するのが要点。 「前回どこまで同期したか」だけを覚えていれば、確実に差分同期できます。

5-5. 深掘り

5-6. まとめ

「設計の中心は コンテンツアドレス指定のチャンク化です。 可変長チャンクとハッシュによる重複排除で、ストレージと帯域を大幅に削減できます。 同期はカーソルベースの差分取得にすることで、 オフライン後の再接続でも確実に整合します。 競合は自動解決を諦めて両方を保存する方針が、ユーザーのデータを失わない最も安全な選択です。」

難易度: ★★★★

6-1. 要件

機能: ①ドライバーの位置更新 ②近くのドライバー検索 ③マッチング ④乗車中の追跡 ⑤料金計算
非機能: マッチングは 5 秒以内、位置更新は 100 万台 × 4 秒ごと、
       一度に 2 人の乗客を同じドライバーに割り当ててはいけない（強い一貫性が必要な箇所）

6-2. 見積もり

位置更新: 100 万ドライバー / 4 秒 = 25 万 QPS（書き込み！）
  → 永続 DB には書けない。**インメモリ + 非同期永続化**
乗車リクエスト: 1 日 2,000 万件 = 200 QPS（ピーク 1,000 QPS）
  → マッチングの QPS は低い。問題は位置更新の書き込み量

📐 この問題の本質: 「読み取りが重い」他の問題と違い、 書き込み（位置更新）が支配的である点。ここに気づけるかが評価点です。

6-3. アーキテクチャ

[ドライバーアプリ] ─4秒ごと─► [位置更新サービス（多数、ステートレス）]
                                      │
                                      ├─► [Redis GEO / インメモリグリッド]（現在位置）
                                      │      key = geo:{city_id} → 全ドライバーの位置
                                      └─► [Kafka] → [位置履歴（Cassandra/S3）] 非同期

[乗客アプリ] ─乗車要求─► [マッチングサービス]
                             ① 乗客位置から H3/Geohash セルを算出
                             ② 自セル + 隣接セルのドライバーを取得（50〜200 人）
                             ③ 利用可能・車種・評価でフィルタ
                             ④ ETA を計算（道路距離、経路サービス）
                             ⑤ 短い有効期限で複数候補へオファーし、条件付き更新で最初の承諾だけを確定
                             ⑥ 承諾 → **配車を確定（ここだけ強い一貫性）**

6-4. 一貫性が必要な箇所を切り分ける（この問題の核心）

【結果整合で十分】ドライバーの位置（数秒古くても実害なし）
【強い一貫性が必須】配車の確定（1 ドライバー = 1 乗車）

実装:
  ドライバーの状態を単一の権威ある場所（RDB の 1 行 or 分散ロック）で管理し、
  条件付き更新で確定する:
    UPDATE drivers SET status='assigned', trip_id=?
     WHERE driver_id=? AND status='available';    -- 更新行数 0 なら他に取られた

🎤 「システム全体で一貫性レベルを分ける」 と言えるのが L5 レベルの答え方です。

6-5. データモデル

drivers(driver_id PK, status, current_trip_id, vehicle_type, rating, updated_at)  -- RDB
driver_locations: Redis GEO（永続化しない）
trips(trip_id PK, rider_id, driver_id, status, start_loc, end_loc,
      requested_at, accepted_at, completed_at, fare)   -- RDB、city でシャード
trip_locations(trip_id, timestamp, lat, lng)           -- Cassandra（走行履歴）

6-6. 深掘り

6-7. まとめ

「この問題では書き込み（位置更新 25 万 QPS）が支配的なので、 位置情報はインメモリのジオインデックスに保持し、履歴は非同期で永続化します。 一方、配車の確定だけは二重割当が許されないため、 ドライバーの状態を単一の権威に置いて条件付き更新で確定します。 一貫性レベルを機能ごとに分けることが、この設計の要点です。」

難易度: ★★★★

7-1. 要件

機能: ①シードURLから開始 ②HTMLを取得・解析 ③リンクを抽出して巡回 ④コンテンツを保存
非機能: 月 10 億ページ、robots.txt 遵守、礼儀正しさ（同一ドメインへの負荷制限）、
       重複排除、無限ループの回避、拡張性

7-2. 見積もり

10 億ページ/月 = 10^9 / (30 × 10^5) ≒ 400 ページ/秒
1 ページ 500 KB（HTML + リソース）→ 500 TB/月（HTML のみなら 100 KB で 100 TB/月）
帯域: 400 × 500 KB = 200 MB/s = 1.6 Gbps

7-3. アーキテクチャ

[シード URL]
     ▼
┌──────────────────────────────────────────────┐
│ URL フロンティア（優先度付きキュー群）          │
│  ├ 優先度キュー（PageRank、更新頻度で決定）     │
│  └ ドメイン別キュー（同一ホストへのレート制限）  │ ★ 礼儀の要
└──────────────────────────────────────────────┘
     ▼
[DNS 解決（キャッシュ必須）]
     ▼
[ダウンローダ（数千の並行接続、非同期 I/O）]
     ├ robots.txt チェック（キャッシュ）
     └ タイムアウト、サイズ上限、リダイレクト上限
     ▼
[コンテンツ重複判定]  ← ドキュメントのハッシュ / SimHash（近似重複）
     ▼
[パーサ] HTML 解析 → 本文抽出、リンク抽出、正規化
     ▼
[URL フィルタ] robots、拡張子、ブラックリスト、URL 正規化
     ▼
[URL 重複判定]  ← Bloom フィルタ（訪問済み）
     ▼
[URL フロンティアへ戻す]  +  [コンテンツを保存（S3/HDFS）→ インデックス構築へ]

7-4. 核心的な設計要素

7-5. 深掘り

7-6. まとめ

「クローラの本質は 『URL フロンティアの管理』 です。 優先度と礼儀正しさという 2 つの制約を同時に満たすため、 優先度キューとホスト別キューの二層構造にします。 URL の重複排除は 10 億件規模なので Bloom フィルタを使い、 ホストのハッシュでシャーディングすることで、 各ノードが独立にレート制限を管理できる構成にします。」

難易度: ★★★

8-1. 要件

機能: 入力中のプレフィックスに対し、人気のクエリ上位 5〜10 件を返す
非機能: p99 < 100 ms（**キー入力ごとに呼ばれるので極めて厳しい**）、
       1 日 100 億クエリ、リアルタイム性は数時間遅れでも可

8-2. 見積もり

検索クエリ 100 億/日。1 クエリで平均 20 文字入力 → デバウンスして 4 回リクエスト
→ 400 億リクエスト/日 = 40 万 QPS（ピーク 120 万 QPS）
→ **完全にキャッシュ/メモリで応答する必要がある**

8-3. データ構造：Trie（トライ木）

        (root)
        /    \
      s        t
     /|\        \
    y c  ...     o
   /   \          \
  s     h          k
 (system:5000)   (tokyo:9000)

各ノードに「そのプレフィックスで始まる上位 K 件」を事前計算して保持する
→ 検索は O(プレフィックス長) で、その後のソートが不要

📐 最重要の最適化: 各ノードに Top-K をキャッシュする。 これがないと、そのノード以下の全部分木を走査してソートする必要があり、間に合いません。

8-4. アーキテクチャ

【オフライン（数時間ごと）】
[検索ログ] → [Kafka] → [集計ジョブ（Spark/Flink）]
                          ・クエリの出現回数を集計（時間減衰つき）
                          ・NG ワードのフィルタ
                          ▼
                    [Trie の構築]
                          ▼
                    [シリアライズして配布]
                          ▼
【オンライン】
[Client] → [CDN/エッジキャッシュ] → [サジェストサービス（Trie をメモリに保持）]
             ↑ 人気プレフィックスはここで返る（大半）

📐 Trie は各サービスノードのメモリに丸ごと載せる（数 GB）。 ネットワークを介さないので p99 が守れます。更新はプロセスの再起動 or アトミックな差し替え（ダブルバッファ）。

8-5. 深掘り

8-6. まとめ

「キー入力ごとに呼ばれるためレイテンシ要件が極端に厳しく、 オンラインでの計算を一切しない設計にします。 オフラインで Trie を構築し、各ノードに Top-K を事前計算して埋め込み、 サービスノードのメモリに丸ごと載せます。 リアルタイム性は数時間遅れで許容し、 トレンドだけ小さな差分 Trie で補う 2 層構成にします。」

難易度: ★★★

9-1. 要件

機能: ①複数チャネル（iOS Push / Android Push / SMS / メール / アプリ内）
     ②テンプレート ③ユーザーの設定（オプトアウト） ④配信状況の追跡
     ⑤スケジュール配信・一斉配信
非機能: 1 日 10 億通知、重要な通知は失わない、重複配信を避ける、
       サードパーティ（APNs/FCM/SendGrid）の障害に耐える

9-2. アーキテクチャ

[各サービス] ──通知イベント──► [通知 API]
                                   │ ① 検証・重複排除（冪等キー）
                                   ▼
                            [Kafka: notifications]
                                   ▼
                          [通知ワーカー（プランナー）]
                             ② ユーザー設定を確認（オプトアウト、時間帯、頻度上限）
                             ③ テンプレートをレンダリング（多言語対応）
                             ④ 送信先チャネルとデバイストークンを決定
                                   ▼
                     ┌─────────────┼─────────────┐
                     ▼             ▼             ▼
              [iOS キュー]   [Android キュー]  [メールキュー]  ← チャネルごとに分離
                     ▼             ▼             ▼
              [APNs 送信]    [FCM 送信]      [SES/SendGrid]
                     └─────────────┼─────────────┘
                                   ▼
                          [配信結果イベント] → 分析・リトライ・無効トークン削除

📐 チャネルごとにキューを分ける理由（バルクヘッド）: メールプロバイダが遅くなっても、プッシュ通知は影響を受けない。

9-3. データモデル

notification_templates(template_id, channel, locale, subject, body)
user_preferences(user_id, channel, category, enabled, quiet_hours_start/end, timezone)
device_tokens(user_id, device_id, platform, token, updated_at, is_valid)
notification_log(notification_id, user_id, channel, status, sent_at, delivered_at, error)
   → Cassandra（大量・時系列・検索は user_id 単位）

9-4. 深掘り

9-5. まとめ

「通知システムの要点は チャネルごとの分離とレート制御です。 チャネルごとにキューとワーカーを分けることで、あるプロバイダの障害が 他チャネルに波及しないようにします。 一斉配信はセグメント分割 + レート制限で段階的に行い、 ユーザー設定と頻度上限をプランナー段階で必ず適用します。」

難易度: ★★☆（第 24 章の知識をそのまま使う）

10-1. 要件

機能: ユーザー/API キー/IP 単位で「N リクエスト / 時間窓」を強制する
     複数のルール（グローバル、エンドポイント別、プラン別）
非機能: 追加レイテンシ < 5 ms、レート制限サービス自体が落ちても本体は動く、
       10 万 QPS のチェック

10-2. 設計

[Client] → [API Gateway]
              │ ① ルールを取得（ローカルキャッシュ、設定は Config サービスから配信）
              │ ② カウントを確認・更新
              ▼
        【二層方式】
        ローカルカウンタ（プロセス内、トークンバケット）
              │ 100 ms ごとに同期
              ▼
        [Redis クラスタ]（グローバルカウンタ、Lua で原子的に）

📐 二層方式が実務の答え:

• ローカルだけ → 台数分だけ超過する
• 中央だけ → レイテンシと Redis への負荷が高い
• 二層 → 各ノードにクォータを配分し、超えそうになったら中央に問い合わせる （わずかな超過を許容する代わりに、レイテンシとコストを劇的に下げる）

10-3. 深掘り

難易度: ★★★★★（正確性が最優先の問題）

11-1. 要件

機能: ①支払いの受付 ②決済代行への連携 ③返金 ④台帳の記録 ⑤精算
非機能: **絶対に二重請求しない**、絶対に金額を失わない、監査可能、
       整合性 > 可用性、PCI DSS 準拠

📐 他の問題と根本的に違う点: ここでは 可用性より正確性が優先されます。 「とりあえず結果整合で」は不正解です。

11-2. 核心的な設計原則

① 複式簿記（Double-Entry Bookkeeping）

すべての取引を「借方」と「貸方」の対で記録し、合計が必ずゼロになるようにする

取引 tx_001（ユーザーが 1000 円支払う）:
  ledger_entries:
    (tx_001, account=user_wallet,     amount=-1000)
    (tx_001, account=merchant_payable, amount=+1000)
  → SUM(amount) = 0 が常に成立（これが検算になる）

📐 お金は「更新」しない。「追記」する。 残高は「エントリの合計」として導出します。 これにより監査可能性と、不整合の検出可能性が得られます。

② 冪等性キー（第 9・18 章）

POST /payments  Idempotency-Key: <client-uuid>
→ 一意制約付きテーブルに記録し、既存なら保存済みレスポンスを返す
→ **ネットワークタイムアウト時のリトライで二重請求が起きない**

③ 状態機械

[created] → [authorized] → [captured] → [settled]
    │            │              └→ [refunded]
    └→ [failed]  └→ [voided]

・遷移は必ず条件付き更新: UPDATE ... WHERE status = '想定の現在状態'
・不可逆な遷移は元に戻さない（返金は「取り消し」ではなく新しい取引）

④ Saga（第 18 章）: 外部決済ゲートウェイとの連携は 2PC が使えないので、 状態機械 + 補償トランザクション（返金）で整合を取ります。

11-3. アーキテクチャ

[Client] → [決済 API]
              ① 冪等性キーの確認
              ② 取引レコードを created で作成（自 DB のトランザクション）
              ▼
        [決済オーケストレーター]
              ③ 決済代行（Stripe/Adyen）へ authorize
              ④ 結果を記録（authorized / failed）
              ⑤ capture（即時 or 後日）
              ▼
        [台帳サービス（append-only）]
              ⑥ 複式簿記のエントリを記録
              ▼
        [イベント発行（Outbox）] → 注文サービス、通知、分析

【非同期】
[Webhook 受信] ← 決済代行からの状態変更通知（**必ず署名検証 + 冪等処理**）
[照合バッチ]   ← 毎日、自社台帳と決済代行の明細を突合（reconciliation）

📐 照合（reconciliation）は必須です。 どれだけ設計しても、外部システムとの間には必ず不一致が発生します。 「毎日突合し、差分を検出してアラートする」 仕組みがないシステムは本番で使えません。 🎤 面接でこれに言及できると、金融ドメインの理解として非常に高く評価されます。

11-4. データモデル

payments(payment_id PK, idempotency_key UNIQUE, user_id, amount, currency,
         status, provider, provider_ref, created_at, updated_at, version)
ledger_entries(entry_id PK, transaction_id, account_id, amount, currency,
               created_at)   -- **UPDATE も DELETE もしない（追記専用）**
   制約: 同一 transaction_id の amount 合計 = 0
webhook_events(event_id PK[provider の ID], payload, processed_at)  -- 重複排除

11-5. 深掘り

11-6. まとめ

「決済システムでは可用性より正確性を優先します。 設計の柱は 3 つです。① 冪等性キーによる二重請求の防止、 ② 追記専用の複式簿記台帳による監査可能性と検算、 ③ 明示的な状態機械による曖昧な状態の排除です。 さらに、外部システムとの不一致は必ず発生するため、 日次の照合バッチを運用の一部として最初から組み込みます。」

難易度: ★★★★

12-1. 要件

機能: ①ジョブの登録（cron 式 or 1 回限り） ②時刻に実行 ③リトライ ④実行履歴
非機能: 100 万ジョブ、秒精度、**重複実行を避ける**、
       ワーカー障害時も実行される（at-least-once）

12-2. 設計の核心

【素朴な設計の問題】
  全ジョブを 1 秒ごとにスキャンする → 100 万件のスキャンが毎秒。無理

【解1: 時間バケット（タイムホイール）】
  ジョブを「実行予定時刻の分」でバケット化して保存
    jobs_by_minute: (execute_minute) → [job_id, ...]
  → 毎分、次の 1 分のバケットだけを読む（数千件）
  → メモリ上のタイムホイール（階層型）で秒精度の発火

【解2: 優先度キュー / ソート済みインデックス】
  Redis Sorted Set（score = 実行時刻の UNIX 秒）
    ZRANGEBYSCORE jobs 0 <now> LIMIT 0 100  → 実行すべきものだけ取得
  → シンプルで実用的。100 万件でも O(log N + M)

12-3. アーキテクチャ

[API] → [ジョブ DB（永続、真実の情報源）]
             │ 次の N 分のジョブを先読み
             ▼
      [スケジューラ（リーダー選出: Raft/etcd で 1 台がアクティブ）]
             │ 実行時刻になったら
             ▼
        [実行キュー（Kafka / SQS）]
             ▼
      [ワーカー（多数、ステートレス）]
             ① メッセージを取得（可視性タイムアウト付き）
             ② **実行状態をclaim**: (job_id, scheduled_time) を一意にし、queued/running/succeeded/failed と lease_until、attempt、owner_epoch を保存
                → lease切れのrunningは回収し、同じ実行を無期限に捨てない
             ③ 実行 → 結果を記録。副作用はジョブ側で冪等にし、fencing tokenを検証する
             ④ 失敗ならリトライ（指数バックオフ）→ 上限超えで DLQ
             ▼
      [次回実行時刻を計算してスケジュールに戻す（cron の場合）]

12-4. 深掘り

難易度: ★★★

13-1. 要件

機能: get / set / delete / TTL、クラスタ構成
非機能: p99 < 1 ms、10 TB のデータ、100 万 QPS、ノード追加削除に耐える

13-2. 設計

【データ配置】コンシステントハッシュ + 仮想ノード（第 16 章）
  ノード追加時の移動は K/N のみ。クライアント側でルーティング（プロキシレス）
  or 専用プロキシ（twemproxy, Envoy）を経由

【単一ノードの構造】
  ハッシュテーブル（キー → 値）
  + LRU 連結リスト（追い出し順）
  + スラブアロケータ（メモリ断片化の防止：サイズクラス別にチャンクを管理）
  + イベントループ（epoll/kqueue）で数万接続を少数スレッドで処理

【高可用性】
  各シャードに 1 プライマリ + N レプリカ（非同期複製）
  クライアントは読みをレプリカへ分散可（結果整合を許容する場合）

13-3. 深掘り

難易度: ★★★★

14-1. 要件

機能: ①メトリクス収集 ②時系列の保存 ③クエリと集計 ④アラート ⑤ダッシュボード
非機能: 1000 万時系列、10 秒間隔（= 100 万点/秒の書き込み）、
       1 年保持、クエリ p99 < 1 秒

14-2. 見積もり

1000 万時系列 × 6 点/分 = 6000 万点/分 = 100 万点/秒
1 点 = (timestamp 8B + value 8B) = 16 B → 圧縮前 16 MB/s = 1.4 TB/日
→ **圧縮が必須**。Gorilla 圧縮で 1 点あたり ~1.4 B（約 10 倍）→ 140 GB/日

14-3. 時系列データの圧縮（Facebook の Gorilla 方式）

タイムスタンプ: デルタ・オブ・デルタ符号化
  10:00:00, 10:00:10, 10:00:20, 10:00:30 → 間隔が一定なら差分の差分が 0
  → ほぼ 1 ビットで表現できる

値: XOR 符号化
  連続する値は似ている → 前の値と XOR すると先頭と末尾に 0 が並ぶ
  → 有意なビットだけを記録

結果: 1 点あたり平均 1.37 バイト（元の 16 B から 12 倍圧縮）

🎤 この仕組みを説明できると、時系列 DB の理解として高評価です。

14-4. アーキテクチャ

【収集】
 Pull 型（Prometheus）: サーバーが各ターゲットの /metrics を定期取得
   ✅ ターゲットの死活が分かる、設定が中央集約
   ❌ NAT 越え・短命なジョブに弱い（Push Gateway で補う）
 Push 型（StatsD/OTLP）: クライアントが送る
   ✅ 短命なジョブ・サーバーレスに対応
   ❌ 送信元の暴走で受け側が死ぬ（レート制限が必要）

【保存】
  直近（数時間）: メモリ上の write-ahead + 可変長ブロック
  中期: ローカル SSD の TSDB（時間ブロック単位、インデックス付き）
  長期: オブジェクトストレージ（Thanos/Cortex/Mimir 方式）+ ダウンサンプリング

【クエリ】
  ラベルの転置インデックス（label=value → 時系列 ID のポスティングリスト）
  → 集合演算で対象時系列を絞る → 該当ブロックを読む → 集計

14-5. 深掘り

難易度: ★★★★

15-1. 要件

機能: ①広告のターゲティングと配信 ②インプレッション/クリックの記録 ③リアルタイム集計
     ④予算管理（**予算超過で配信を止める**） ⑤課金
非機能: 広告選択 p99 < 50 ms、1 日 1000 億イベント、
       課金に使うので**集計は正確でなければならない**、不正クリックの検出

15-2. 見積もり

イベント 1000 億/日 = 100 万 QPS
1 イベント 200 B → 20 TB/日
→ 生イベントの保存は安いストレージ、集計はストリーム処理

15-3. 配信パス（低レイテンシが命）

[広告リクエスト] → [広告サーバー]
    ① ターゲティング（ユーザー属性・文脈でマッチする候補を取得）… 数万件
    ② フィルタ（予算切れ、フリークエンシー上限、ブランドセーフティ）
    ③ 予測（CTR 予測モデル）… 数千件 → 上位数十件
    ④ オークション（eCPM = bid × pCTR で順位付け、セカンドプライス）
    ⑤ 配信 + インプレッションログ
  すべて 50 ms 以内 → **候補生成は事前計算されたインデックスから、モデルは軽量**

15-4. 集計パス（正確性が命）

[クリックイベント]
   │ クライアント → エッジ（軽量な受け口。書くだけ）
   ▼
[Kafka]（パーティションキー = ad_id or campaign_id）
   ├──► 【リアルタイム経路】Flink/ストリーム集計
   │        1 分ウィンドウで集計 → Redis/OLAP へ → ダッシュボード（暫定値）
   │        予算消化の監視 → 閾値超過で配信停止シグナル
   │
   └──► 【バッチ経路】S3 に生ログ保存 → 日次バッチで正確に再集計
            → 課金はこちらの数値を使う（**リアルタイムは目安、課金は確定値**）

📐 これは Lambda アーキテクチャの正当な使用例です。 「速報値」と「確定値」で求められる性質が本質的に違うため、2 経路が正当化されます。

15-5. 深掘り

難易度: ★★★★（在庫の一貫性が主題）

16-1. 要件

機能: ①イベント/座席の検索 ②座席の仮押さえ ③決済 ④確定
非機能: **同じ座席を 2 人に売らない（絶対）**、
       人気公演の発売開始時に 100 万人が同時アクセス、
       仮押さえは 10 分で自動解放

📐 この問題の本質: 「読み取りは大量・結果整合で良い」が 「在庫の確定だけは厳密な一貫性が必要」という、性質の異なる 2 つが同居すること。

16-2. 設計

【閲覧（大量・結果整合）】
[Client] → [CDN] → [イベント情報 API] → [キャッシュ] → [DB レプリカ]
  座席の空き状況は「数秒古くてよい」→ キャッシュして大量アクセスを捌く
  ※ ただし「空いてると思ったら埋まっていた」体験を減らす工夫は必要

【仮押さえ（厳密）】
[Client] → [予約サービス] → [予約 DB（RDB のトランザクション）]
   BEGIN;
     SELECT status, held_by, hold_token, hold_expires_at FROM seats WHERE event_id=? AND seat_id=? FOR UPDATE;
     -- または条件付き更新（こちらが軽い）
     UPDATE seats SET status='held', held_by=?, hold_token=?, hold_expires_at=now()+interval '10 min'
      WHERE event_id=? AND seat_id=? AND (status='available'
                           OR (status='held' AND hold_expires_at < now()));
     -- 更新行数 0 → 他の人に取られた（409 を返す）
   COMMIT;

【確定】決済成功 → `status='sold'` に更新。ただし `event_id`、`seat_id`、`held_by`、`hold_token`、期限、現在状態を条件に含める。
古い決済通知は更新行数 0 として無視・照合する（Saga: 決済失敗なら hold を解放）
【期限切れ】バックグラウンドジョブ or 参照時の遅延評価で 'available' に戻す

16-3. 発売開始の殺到（サンダリングハード）への対策

【仮想待合室（Virtual Waiting Room）】★ 有力な選択肢
  ① 発売前にアクセスした全員をキューに入れる（トークンを発行）
  ② 一定レート（例: 1000 人/分）でのみ本システムへ入場を許可
  ③ 待機中は「あなたは 12,345 番目です」と表示（体験も改善する）
  → バックエンドへの流入を制御できる。ただしキュー、レート制限、在庫の条件付き更新、Bot対策、容量増強を組み合わせる

【その他】
  ・座席マップは静的化して CDN へ（在庫状態だけ別途軽量 API で取得）
  ・書き込みパスを極限まで軽くする（決済は仮押さえの後）
  ・Bot 対策（CAPTCHA、レート制限、購入枚数制限）

16-4. 深掘り

16-5. まとめ

「このシステムの本質は、閲覧（大量・結果整合可）と在庫確保（少量・厳密）の分離です。 閲覧は CDN とキャッシュで捌き、在庫確保だけを RDB のトランザクションで守ります。 在庫確保の QPS は座席数に上限があるため、実は大した量にはなりません。 発売開始の殺到に対しては、仮想待合室で入場レートそのものを制御し、 バックエンドの処理能力、キューの滞留時間、SLOを基準に流入を制御し、能力を超えないようにします。」

難易度: ★★★（Google / OpenAI 等で最頻出）

17-1. 要件

機能要件:
  ・社内ドキュメント（1,000 万件、平均 10 KB）をアップロード・自動インデックス
  ・ユーザーの自然文の質問に対し、関連文書を検索し、根拠のある回答をストリーミング生成
  ・ドキュメント単位のアクセス権（ACL）制御
  ・ドキュメント更新/削除が 1 分以内に検索へ反映
非機能要件:
  ・検索 + 回答生成のレイテンシ: TTFT（最初のトークン）< 300 ms、全体完了 p99 < 2 秒
  ・検索 QPS: 500 QPS（ピーク 1,500 QPS）
  ・ハルシネーションの最小化（根拠のない回答をしない、引用リンクを付与）

17-2. 見積もり

データ量:
  ・ドキュメント 1,000 万件 × 10 KB = 100 GB（テキスト）
  ・チャンキング: 500 トークン（約 2 KB）/ チャンク（オーバーラップ 10%）→ 5,000 万チャンク
  ・ベクトルストレージ: 5,000 万 × 1,536 次元 × 4 B (float32) = 300 GB
  ・HNSW インデックス RAM: ベクトル 300 GB + グラフエッジ 150 GB = 450 GB
    → 64 GB RAM ノード × 8 台のベクター DB クラスタ（IVF-PQ なら 1 台 40 GB に圧縮可能）
計算リソース:
  ・クエリ Embedding: ピーク 1,500 QPS × 10 ms は、Little の法則では平均同時実行数約 15 を表す。
    GPU台数は、モデル、バッチサイズ、実測throughput、p95/p99制約、冗長性から決める
  ・LLM 回答生成: キャッシュヒット率を仮定するだけでなく、入力/出力トークン、同時ストリーム数、モデルthroughputから容量を見積もる

17-3. API

POST /v1/documents
  Request:  {doc_id, title, content, acl_groups: ["eng", "hr"], metadata: {created_at, dept}}
  Response: 202 Accepted {task_id}

POST /v1/chat/completions
  Request:  {query: "育児休業の手続き方法は？", conversation_id, stream: true}
  Response: Server-Sent Events (SSE)
            data: {"token": "育児", "citations": []}
            ...
            data: {"token": "", "citations": [{"doc_id": "hr-102", "title": "育休ガイド.pdf"}]}

17-4. アーキテクチャ

【インジェスチョン（文書登録）パイプライン】
[Document Upload] → [Kafka] → [Chunking Service] (500 tokens / 10% overlap)
                                      │
                 ┌────────────────────┴────────────────────┐
                 ▼                                         ▼
   [Embedding Worker (GPU)]                   [Elasticsearch (BM25)]
                 │                                         │
                 ▼                                         ▼
   [Vector DB (HNSW / Milvus)]                  [Metadata DB (PostgreSQL)]
   (ベクトル + ACL ビットセット)                      (文書本文 + ACL 定義)

【クエリ（質問・生成）パイプライン】
[Client] ──(SSE)──► [API Gateway]
                           │
                           ▼
                  [認証・テナント/ACLコンテキスト確定]
                           │
                           ▼
                  [Semantic Cache (Redis)] ──(権限・モデル・コーパス版を含むキー)──► 安全な場合だけ回答返却
                           │ ミス
                           ▼
                  [Query Rewriter / HyDE] (検索用クエリの最適化)
                           │
            ┌──────────────┴──────────────┐
            ▼                             ▼
    [Embedding 推論]             [BM25 キーワード検索]
            │                             │
            ▼                             ▼
    [Vector DB (HNSW)]            [Elasticsearch]
    (ACL フィルタ適用)            (ACL フィルタ適用)
            └──────────────┬──────────────┘
                           ▼
                  [RRF ランク統合] (上位 50 件)
                           │
                           ▼
                  [Cross-Encoder Reranker] (上位 5 件を厳選)
                           │
                           ▼
                  [Prompt Assembler] (システム指示 + 厳選チャンク + 質問)
                           │
                           ▼
                  [LLM 推論エンジン] ──(Streaming)──► [Client]

17-5. 深掘り

17-6. まとめ

「検索品質と精度のために BM25 とベクトル検索を組み合わせ、RRF とリランカーを導入しました。 認証後のテナント・権限コンテキストを検索、キャッシュ、プロンプト生成の全段で検証し、 文書更新・削除、プロンプトインジェクション、引用の正しさを評価します。権限漏洩を完全に防ぐとは断定せず、監査と負荷試験で確認します。」

難易度: ★★★（Google / Meta で最頻出）

18-1. 要件

機能要件:
  ・ユーザーごとにパーソナライズされた動画フィードを推薦
  ・ユーザーの直近のリアクション（視聴完了、いいね、スキップ）が 1 秒以内に次回の推薦に反映される
非機能要件:
  ・規模: DAU 2 億人、総動画数 10 億本
  ・フィード取得レイテンシ: p99 < 50 ms
  ・スループット: ピーク 25 万 QPS
  ・コールドスタート問題（新規ユーザー・新規動画）の解決

18-2. 見積もり

QPS:
  ・2 億人 × 50 回/日 ÷ 10^5 ≒ 100,000 QPS（平均）、ピーク 250,000 QPS
ストレージ:
  ・動画埋め込み: 10 億本 × 128 次元 × 4 B = 512 GB → ScaNN インデックスで 16 ノードに分散
  ・オンライン特徴量: 2 億人 × 5 KB = 1 TB → Redis / Bigtable クラスタ
特徴量アクセス:
  ・25 万 QPS × 1,000 候補 = 2.5 億 lookup/s → バッチ Multi-Get とローカルキャッシュで処理

18-3. 3 段階推薦パイプライン

[Client] ──(GET /v1/feed)──► [Recommendation Gateway]
                                    │
    ┌───────────────────────────────┴───────────────────────────────┐
    ▼ ① Candidate Generation (Retrieval) [~15 ms]                  │
    ・ユーザー ID → オンライン特徴量ストア (Redis) から直近視聴 5 件を取得 │
    ・User Tower モデル (GPU) でユーザーベクトル u を計算            │
    ・ScaNN / HNSW クラスタで ANN 探索: 10 億本 → 1,000 本抽出       │
    └───────────────────────────────┬───────────────────────────────┘
                                    ▼
    ┌───────────────────────────────────────────────────────────────┐
    ▼ ② Heavy Ranking (Scoring) [~25 ms]                            │
    ・1,000 候補の特徴量（動画静的特徴 + ユーザーリアルタイム特徴）を │
      Feature Store から Multi-Get で一括取得                       │
    ・DLRM / Transformer ランキングモデル（GPU）で各動画の CTR と    │
      視聴時間を予測スコアリング                                    │
    └───────────────────────────────┬───────────────────────────────┘
                                    ▼
    ┌───────────────────────────────────────────────────────────────┐
    ▼ ③ Re-ranking & Business Rules [~5 ms]                         │
    ・作者・カテゴリの重複排除 (MMR)                                 │
    ・Exploration Slot (5%): 新規動画・新規カテゴリの探索            │
    ・広告挿入・ネガティブフィードバック（ブロック・報告済み）の除外 │
    └───────────────────────────────┬───────────────────────────────┘
                                    ▼
                          上位 20 本の動画リストを返却（トータル 45 ms）

18-4. データモデルと特徴量ストア

【Feature Store の二重構造】
・オフライン (BigQuery / Dataflow):
    過去 1 年の全イベントログから、動画ごとの 7 日間平均視聴時間、CTR を集計。
    毎日夜間にバッチモデル学習を実行。
・オンライン (Bigtable / Redis):
    user:{id}:recent_actions → [ {video_id, action, timestamp} ] (TTL 24h)
    video:{id}:stats         → {views_1h, likes_1h, shares_1h} (Flink で 1 分集計)

18-5. 深掘り

18-6. まとめ

「10 億本から 50 ms でパーソナライズ推薦を行うため、Two-Tower による ANN 候補抽出（1,000 件）、DLRM による精密ランキング（100 件）、多様性制御の Re-ranking（20 件）という 3 段階パイプラインを採用しました。 Flink と Redis によるリアルタイム特徴量ストアで直近のアクションを即座に反映し、 位置バイアスの補正と探索枠（Exploration）によりコールドスタートとエコーチェンバーを打破する構成です。」

難易度: ★★★（最新インフラ・差別化問題）

19-1. 要件

機能要件:
  ・自然文プロンプトを受け取り、LLM による回答をストリーミング生成
  ・マルチターン対話（会話履歴のコンテキスト維持）
  ・優先度付きキューイングとトークン単位のレート制限
非機能要件:
  ・モデル: 70B パラメータ（FP16 で 140 GB、INT8 量子化で 70 GB）
  ・スループット: ピーク 2,000 QPS（同時アクティブ対話 20,000 セッション）
  ・レイテンシ: TTFT（Time To First Token）< 200 ms、生成速度 > 30 tokens/秒/ユーザー
  ・GPU メモリ利用効率の最大化

19-2. 見積もり

モデルメモリ:
  ・70B (INT8): 重みだけで概算 70 GB。実際には KV Cache、ランタイム、ワークスペース、断片化の余裕が必要で、80 GB GPU 1 枚に安全に収まるとは限らない
KV Cache メモリ:
  ・1 セッション（プロンプト 2,000 + 生成 1,000 = 3,000 トークン）:
    KV bytes = 2 × 80層 × KVヘッド数 × head_dim × 3000 × 2B
    例: GQA（KVヘッド8、head_dim 128）なら約 0.98 GB（10進）。MHA（8192次元）なら約 7.86 GB。
    使うモデルのKVヘッド数を必ず確認する
  ・1 GPU ノード（80 GB H100 × 2 = 160 GB）:
    モデル 70 GB + バッファ 20 GB → 残り 70 GB を KV Cache に使用
    → ノードあたり同時リクエスト数は、残りVRAM、KVサイズ、出力長、バッチング、TTFT/TPOT目標を実測して決める
クラスタ規模:
  ・同時 20,000 セッション ÷ 50 セッション/ノード = 400 GPU ノード（計 800 基の H100）

19-3. アーキテクチャ（Prefill / Decode 分離 + PagedAttention）

[Client] ──(HTTP/3 / SSE)──► [Global Load Balancer (Envoy)]
                                    │
                                    ▼
                       [Distributed LLM Router]
                       (トークンレート制限 / セッションルーティング)
                                    │
        ┌───────────────────────────┴───────────────────────────┐
        ▼ 【Prefill クラスタ (Compute-bound)】                   │
        ・プロンプト全体（2,000 トークン）を一括並列処理 (TTFT < 150ms)   │
        ・初期 KV Cache を生成                                  │
        └───────────────────────────┬───────────────────────────┘
                                    │ RDMA (400 Gbps ネットワーク)
                                    ▼
        ┌───────────────────────────────────────────────────────┐
        ▼ 【Decode クラスタ (Memory Bandwidth-bound)】           │
        ・Continuous Batching: 毎ステップで新規/完了を差し替え   │
        ・PagedAttention (vLLM): 不連続なブロック単位で KV Cache 管理│
        ・Prefix Caching: 共通システムプロンプトの KV を再利用    │
        ・1 トークン生成ごとに即座に Gateway 経由で SSE ストリーム │
        └───────────────────────────────────────────────────────┘

19-4. 核心技術

19-5. 深掘り

19-6. まとめ

「70B LLM の大規模推論基盤として、GPU 計算律速な Prefill と VRAM 帯域律速な Decode をクラスタレベルで分離し、RDMA で KV Cache を転送するアーキテクチャを設計しました。 PagedAttention と Continuous Batching により GPU メモリ利用率とスループットを極限まで高め、 Prefix Caching と投機的デコーディングを組み合わせて TTFT 200 ms 以下と 30 tokens/秒以上の高速生成を両立させています。」

19-7. 追加課題：業務ツールを操作する AI エージェント

要件例: ユーザーの依頼から社内検索、チケット照会、下書き作成を行う。送信・削除・権限変更は 明示的な承認が必要。複数ツールの一部がタイムアウトしても、重複操作や越権を起こさず再開できること。

設計で必ず触れる論点:

深掘り質問: 「決済 API がタイムアウトした後、ユーザーが再送したら二重請求されないか」 に対し、idempotency_key、状態照会、事後条件、期限付きリース、監査トレースを組み合わせて説明します。

演習問題の総まとめ：頻出パターン早見表