難
ソーシャルグラフ(最短経路)を設計せよ
課題
ソーシャルネットワークで、あるユーザーを検索して『自分から目的の人物までの最短のつながり(友達の友達の…)』を表示する。LinkedInの『〇次のつながり』のような機能。高可用が必須。最大の制約は『グラフ全体が1台のマシンに収まらない』こと。これをどう分散させ、その上で最短経路を計算するかが課題です。
制約・前提
- ユーザーは100M(1億)人
- 1ユーザー平均50人の友達
- 友達関係(エッジ)は5B(50億)件
- friend search は1B(10億)/月
- グラフは1台のマシンに収まらない(必ず分散が必要)
- エッジは無重み(全ての友達関係は等価)
- 平均400 search req/s(ピークはもっと高い)、高可用が必須
主要数値
概算（back-of-the-envelope）の出発点。
| ユーザー数 | 100M (1億) |
|---|---|
| 平均友達数 | 50人/user |
| エッジ(友達関係) | 5B (50億) |
| 平均search req/s | 400 req/s |
| 最短経路アルゴリズム | BFS (無重みのため) |
| メモリ1MB連続read | 約250マイクロ秒 |
主要数値の可視化
グラフの規模感（対数軸・件数）
規模
検索 400 req/s ユーザー1億 × 友達50で計5BのエッジをメモリにのせBFSで最短経路を解く。read/write よりグラフ規模が支配的。
まず自分で設計を考えてから、1ステップずつ答え合わせをしましょう。
Step 1: 要件・ユースケース（まだ伏せられています）
考えてみよう（面接官の追加質問）
- AさんとBさんの最短経路を求めるとき、双方向BFSは片方向BFSに比べて探索ノード数をどれくらい減らせるか?
- person_idでのshardingだと、仲の良い人同士が別サーバーに散る。データの局所性を上げる分割方法はあるか?
- 『6次の隔たり』のように経路が深くなりすぎる場合、何ホップで打ち切る? その判断基準は?
- 友達追加/削除が頻繁に起きる。Person ServerとMemory Cacheの整合性をどう保つ?
- Lookup Service自体がボトルネック/単一障害点にならないために、どう冗長化・分散する?