システムデザイン完全ガイド ④｜システムの部品箱

ブラウザキャッシュ
    ↓
CDN / エッジキャッシュ            ← 静的コンテンツ、地理的に近い
    ↓
ロードバランサ / リバースプロキシキャッシュ
    ↓
アプリのローカルメモリ（プロセス内）  ← 最速だがノードごとに別物
    ↓
分散キャッシュ（Redis / Memcached） ← 共有できる。ネットワーク 1 往復
    ↓
データベースのバッファプール        ← DB が自前で持つページキャッシュ
    ↓
OS のページキャッシュ
    ↓
ディスク

def get_user(user_id):
    key = f"user:{user_id}"
    v = cache.get(key)
    if v is not None:
        return v                      # ヒット
    v = db.query("SELECT ... WHERE id=?", user_id)   # ミス
    cache.set(key, v, ttl=300 + random.randint(0, 60))  # ← ジッタを入れる
    return v

def update_user(user_id, data):
    db.update(...)
    cache.delete(f"user:{user_id}")   # ← 更新ではなく「削除」する

人気キーの TTL が切れた瞬間、1 万個の同時リクエストが全部 DB に殺到 → DB が死ぬ

if now - delta * beta * log(random()) >= expiry:  # 期限前に確率的に再計算
    refresh()

存在しない ID を大量に問い合わせる → 毎回キャッシュミス → 毎回 DB に行く（攻撃にも使われる）

Redis クラスタが落ちる / 全キーの TTL が同時に切れる → 全リクエストが DB へ

ユーザー（東京）→ 東京 PoP（キャッシュヒット → 5 ms で返却）
                    │ ミス
                    ▼
                 シールド／リージョナルキャッシュ
                    │ ミス
                    ▼
                 オリジンサーバー（米国, 120 ms）

【同期】ユーザー登録 API
  DB 保存(20ms) → 確認メール送信(800ms) → 画像生成(1500ms) → レスポンス
  = 2.3 秒。しかもメール送信が失敗したら登録も失敗する

【非同期】
  DB 保存(20ms) → キューに積む(2ms) → レスポンス（22ms！）
  ワーカーが後からメール送信・画像生成

Topic: "orders"
 ├ Partition 0: [msg0][msg1][msg2][msg3] →  ← 追記のみのログ
 ├ Partition 1: [msg0][msg1][msg2] →
 └ Partition 2: [msg0][msg1][msg2][msg3][msg4] →

各パーティションは複数ブローカーにレプリケート（leader + follower）
コンシューマグループ内では、1 パーティション = 1 コンシューマ

acks=0   : 送りっぱなし。最速・最も危険
acks=1   : リーダーが書けば OK。リーダー障害で失う可能性
acks=all : ISR 全員が書いたら OK。min.insync.replicas=2 と併用が定番

at-most-once : 処理前にオフセットをコミット（失敗すると失われる）
at-least-once: 処理後にオフセットをコミット（重複しうる）← 基本

SELECT * FROM posts WHERE content LIKE '%システム設計%';

【元データ】
doc1: "分散システムの設計"
doc2: "システム設計の面接"
doc3: "分散データベース"

【転置インデックス】（単語 → その語を含む文書リスト）
"分散"     → [doc1, doc3]
"システム" → [doc1, doc2]
"設計"     → [doc1, doc2]
"面接"     → [doc2]
"データベース" → [doc3]

検索「分散 AND 設計」→ [doc1,doc3] ∩ [doc1,doc2] = [doc1]

原文 → ① 文字正規化（全角半角、大文字小文字、Unicode 正規化）
     → ② トークン化（英語は空白、日本語は形態素解析 or N-gram）
     → ③ ストップワード除去（"the", "の"）
     → ④ ステミング/正規化（running → run、送り仮名の統一）
     → ⑤ 同義語展開（PC = パソコン）
     → 転置インデックスへ

Index（テーブル相当）
 └ Shard（Lucene インデックス 1 つ = 独立した検索単位）
     ├ Primary shard
     └ Replica shard（読み取り分散 + 冗長化）

テキスト "犬が公園を走る" ──[Embedding モデル]──► [0.12, -0.85, 0.44, ..., 0.03] (768〜1536次元)
テキスト "子犬が外で遊ぶ" ──[Embedding モデル]──► [0.15, -0.81, 0.40, ..., 0.05]
  → 高次元空間での距離（コサイン類似度・内積）が非常に近い！

┌─────────────────────────────────────────────────────────────┐
│                    ANN アルゴリズムの比較                   │
├──────────────────┬──────────────────┬───────────────────────┤
│ HNSW             │ IVF-PQ           │ ScaNN (Google)        │
├──────────────────┼──────────────────┼───────────────────────┤
│ グラフベース     │ クラスタ + 積量子化│ クラスタ + 異方性量子化│
│ 高精度・超高速   │ メモリ 90% 削減  │ 高速・高再現率        │
│ メモリ消費 大    │ 精度はやや低下   │ Google 検索/YouTube   │
└──────────────────┴──────────────────┴───────────────────────┘

❌ Pre-filtering（先に SQL 等で絞り込んでから ANN）
   → 候補が 1 万件に減った状態でグラフ探索すると、
     グラフが途切れて ANN が辿り着けない（孤立ノード問題）

❌ Post-filtering（ANN で上位 100 件取ってからメタデータで絞る）
   → 上位 100 件の中に条件合致が 1 件もなく、検索結果が 0 件になる

✅ Single-Stage / Iterative Filtered Search（グラフ探索中にメタデータを評価）
   → HNSW の探索ステップごとに「メタデータ条件を満たすか」を
     ビットマップ等で高速チェックしながら巡回

① クライアント → アプリ:「upload.jpg を上げたい（10 MB, image/jpeg）」
② アプリ: 権限チェック → S3 の署名付き PUT URL を発行（有効期限 15 分）
③ クライアント → S3 に直接 PUT   ← アプリサーバーを経由しない
④ S3 のイベント通知 → Lambda/キュー → サムネイル生成・DB のステータス更新

アップロードセッションを DB に記録: upload_id, 総サイズ, 完了チャンクのビットマップ
→ 中断後は「どこから再開すればいいか」をクライアントに返せる

非公開ファイル: 署名付き GET URL（有効期限付き）→ CDN 経由
公開ファイル:   CDN に長期キャッシュ + コンテンツハッシュ付きファイル名

アップロード → トランスコード（複数解像度・ビットレート）
   1080p/5Mbps, 720p/2.5Mbps, 480p/1Mbps, 360p/600kbps
→ セグメント化（HLS/DASH: 2〜10 秒ごとの .ts / .m4s ファイル + マニフェスト）
→ CDN へ配置
→ プレイヤーが帯域を測定し、セグメント単位で品質を切替（ABR: Adaptive Bitrate）

key = "user:42:2026-08-22T10:00"  → INCR、TTL 60 秒。上限を超えたら拒否

Redis の Sorted Set にタイムスタンプを全部記録
ZREMRANGEBYSCORE（古いものを削除）→ ZCARD（件数）→ 上限内なら ZADD

現在のウィンドウのカウント + 前のウィンドウのカウント × (はみ出し割合)
例: 10:01:15 時点 → count(10:01) + count(10:00) × (45/60)

バケットに毎秒 r 個のトークンを補充（上限 b 個）
リクエスト時に 1 個消費。無ければ拒否（or 待つ）

┌─────────┐
│ ●●●●●   │ ← 毎秒 r 個補充、最大 b 個まで貯まる
└────┬────┘
     ▼ リクエストが 1 個消費

リクエストをキューに入れ、一定速度で処理する

[LB] → [APIサーバー × 50 台] → 共有の Redis でカウント

API キー / ユーザー ID  ← 認証済みなら最良
IP アドレス            ← 未認証時。ただし NAT 配下の企業ユーザーを巻き込む
IP + エンドポイント     ← ログイン試行など、危険な操作は厳しく
テナント / 組織         ← B2B SaaS

HTTP/1.1 429 Too Many Requests
Retry-After: 30
RateLimit-Limit: 100
RateLimit-Remaining: 0
RateLimit-Reset: 1755855600

 1 bit    41 bits            10 bits       12 bits
┌──┬────────────────────┬──────────┬────────────┐
│0 │ タイムスタンプ(ms)  │ ノードID  │ シーケンス  │  = 64 bit
└──┴────────────────────┴──────────┴────────────┘
  ↑符号ビット(通常0)    ↑1024ノード ↑同一ms内で4096個

DB の主キー（InnoDB）    → Snowflake / UUIDv7 / ULID（単調増加が必須）
公開 URL の ID          → 推測不可能な ID（ランダム or 暗号化した連番）
短縮 URL                → Base62 の連番 or ハッシュ先頭 7 文字 + 衝突時に再試行
分散トレース ID         → UUID v4 / 128 bit ランダムで十分
冪等性キー              → クライアント生成の UUID v4

アプリノードが DB から「1000 個分の範囲」をまとめて確保する
  UPDATE id_segments SET max_id = max_id + 1000 WHERE biz='order' RETURNING max_id;
  → ノードはメモリ内で 1000 個を配る（DB アクセスは 1000 回に 1 回）
  → 半分使ったら非同期で次の範囲を先読み確保（バッファ枯渇を防ぐ）

m ビットの配列と k 個のハッシュ関数
追加: h1(x), h2(x), h3(x) のビットを 1 にする
検査: 全部 1 なら「たぶんある」、1 つでも 0 なら「絶対にない」

     0 1 0 1 1 0 0 1 0 1 0 0
        ↑   ↑     ↑
      h1(x) h2(x) h3(x)

仕組み: ハッシュ値の先頭の 0 の連続数を見る
  「先頭に 0 が 10 個続く値が観測された」→ 要素数は 2^10 ≒ 1024 くらいだろう
  これを多数のバケットで平均（調和平均）して精度を上げる

d 個のハッシュ関数 × w 個のカウンタの 2 次元配列
追加: 各行の hash_i(x) 番目のカウンタを +1
問合: 各行の値の最小値を返す（衝突による過大評価を最小値で抑える）

SELECT * FROM drivers
WHERE SQRT(POW(lat-?,2) + POW(lng-?,2)) < 0.05;   -- 全行スキャン。100 万台で数秒

緯度経度を交互にビット分割し、Base32 文字列にエンコードする
  "xn774c"  ← 東京駅付近

文字数と精度（緯度で幅が変わる概算）:
  4 文字 → 約 20 km 四方
  5 文字 → 約 5 km
  6 文字 → 約 1.2 km
  7 文字 → 約 150 m
  8 文字 → 約 38 m

前方一致 = 近い！  → 通常の文字列インデックス（B-Tree）でそのまま検索できる
  SELECT * FROM shops WHERE geohash LIKE 'xn774%';

領域を再帰的に 4 分割し、1 ノードあたりの点が閾値を超えたら分割する
→ 密度に応じて適応的（都心は細かく、地方は粗く）

CREATE INDEX ON shops USING GIST (location);
SELECT * FROM shops
WHERE ST_DWithin(location, ST_MakePoint(?,?)::geography, 1000)  -- 1km 以内
ORDER BY location <-> ST_MakePoint(?,?) LIMIT 10;               -- KNN 検索

GEOADD drivers 139.767 35.681 "driver:42"
GEOSEARCH drivers FROMLONLAT 139.77 35.68 BYRADIUS 3 km ASC COUNT 10

【ドライバーの位置更新】4 秒ごと × 100 万台 = 25 万 QPS
  → 永続 DB には書かない。Redis (GEO) or メモリ上のグリッドに保持
  → 履歴が必要なら Kafka → オブジェクトストレージへ非同期に流す

【近傍検索】
  ① 乗客の位置から H3/Geohash セルを算出
  ② 自セル + 隣接セルのドライバーを取得（数十〜数百人）
  ③ 直線距離でフィルタ → 実際の道路距離/ETA を計算（ここが重い）
  ④ スコアリング（距離・評価・車種）してマッチング

【スケール】
  地理でシャーディング（都市単位）→ 都市間のトラフィックは独立
  ホットスポット（渋谷駅）はセルをさらに細分化