システム設計面接 第2巻 | 第2章. 近くの友達

Tags:

「近くの友達(Nearby friends)」というモバイルアプリ機能を支える、スケールしやすいバックエンドシステムを設計してみる。

Facebookの「近くの友達」機能リリース

1段階: 問題理解と設計範囲の確定

  • 「近くにいる」とは、直線距離で5マイル(mile)以内にいる場合を意味する。
    • この値は設定可能である。
  • ユーザーの移動履歴を保存する。
    • 機械学習(machine learning)など、さまざまな用途に使えるだろう。
  • ユーザーが10分以上非アクティブ状態なら、近くの友達リストから消える。
  • プライバシーデータ保護法は考慮しない。
    • 複雑なので除外する。

機能要件

  • ユーザーはモバイルアプリで近くの友達を確認できなければならない。
    • その友達までの距離、その情報が最後に更新された時刻(timestamp)を表示する。
  • この友達リストは数秒ごとに更新されなければならない。

非機能要件

  • 低遅延(low latency)
    • 近くの友達の位置変化に時間がかかりすぎてはいけない。
  • 信頼性
    • 全体的に安定しているべきだが、時には少量のデータ損失は許容できる。
  • 結果整合性
    • 位置データの保存に強い整合性を支援する必要はない。
    • レプリカのデータが元データと同じになるまで数秒程度かかってもよい。

概略的な規模推定

  • 「近くの友達」は5マイル半径以内の友達と定義する。
  • 友達の位置情報は30秒周期。
    • 人はそれほど速く歩かないため、30秒で十分である。
  • 1日あたり近くの友達検索機能を使うユーザーを1億人と仮定。
  • 同時接続ユーザー数は10%と仮定。
    • 10% * 1億 = 1,000万人。
  • 平均的な1ユーザーが4,000人の友達を持つと仮定。
  • この機能は1ページあたり20人の近くの友達を表示する。
    • リクエストがあれば、さらに多くの友達を表示する。

2段階: 概略設計案の提示と合意

他の章とは異なり、位置情報をすべての友達へ送る必要があるため、サーバーとクライアント間でHTTPプロトコルを使用できないことを踏まえると、まず概略設計案を理解しなければ、どのようなAPIを作るべきか分かりにくい。そのため、概略設計案から見ていく。

概略設計案

共用バックエンド

  • すべてのアクティブユーザーの位置変化履歴を受信する。
  • ユーザー位置が変わるたびに、アクティブ状態の友達へ変更履歴を伝える。
  • 2人のユーザーの距離が遠い場合には変更履歴を送信する。

問題は、大規模に適用しにくい点である。

  • アクティブ状態の同時接続ユーザーが約1,000万人で、位置情報を30秒ごとに更新すると、1秒あたり約334,000回の位置情報更新になる。
    • TPS: 10,000,000トランザクション / 30秒 = 333,333.333 TPS(約334,000回)。
  • 平均ユーザー1人が400人の友達を持ち、そのうち10%が近隣でアクティブ状態だと仮定すると、1,400万件の位置情報更新リクエストになる。
    • 1秒あたり334,000回 * 400人 * 10% = 1,400万。
  • この膨大な量の更新履歴をユーザー端末へ送らなければならない。

設計案

概略設計案

  • ロードバランサー
    • WebSocketおよびHTTPサーバーの前段に配置。
    • 負荷を均等に分散するため、トラフィックをサーバー群に配分する役割。
  • RESTful APIサーバー
    • 友達の追加/削除やユーザー情報の更新など、付加的な作業を処理。
  • WebSocketサーバー
    • 友達の位置情報変更をリアルタイムに状態維持するサーバークラスター。
      • 各クライアントは1つのWebSocket接続を継続的に維持する。
      • 位置変更履歴はこの接続で送信する。
  • Redis位置情報キャッシュ
    • アクティブ状態ユーザーの最新位置情報をキャッシュするために使用。
    • TTLを指定し、時間が経つと位置情報キャッシュを削除する。
    • キャッシュ情報が更新されるたびにTTLも更新する。
  • ユーザーデータベース
    • ユーザーデータおよびユーザーの友達関係情報も保存。
    • RDB、NoSQLのどちらでも使用可能。
  • 位置移動履歴データベース
    • ユーザーの位置変更履歴を保管。
  • Redis Pub/Subサーバー
    • 超軽量メッセージバスとしてRedis Pub/Subを使用。

周期的な位置更新

  1. クライアントが位置変更の事実をロードバランサーへ送信する。
  2. ロードバランサーはその位置変更履歴をWebSocketサーバーへ送信する。
  3. WebSocketサーバーは該当イベントを位置移動データベースに保存する。
  4. WebSocketサーバーはキャッシュに保存し、TTLも更新する。
  5. WebSocketサーバーはRedis Pub/Subサーバーの該当ユーザーチャンネルへ位置を発行する。3から5は並列で実行する。
  6. Redis Pub/Subがすべての購読者(オンラインの友達)へブロードキャストする。
  7. 新しい位置を送ったユーザーとメッセージを受け取ったユーザーの間の距離を再計算する。
  8. 7で計算した距離が検索半径を超えなければ各クライアントへ情報を送信し、超えれば送信しない。

API設計

  1. サーバーAPI - 周期的な位置更新。
  2. クライアントAPI - クライアントが更新された友達位置を受信するために使用するAPI。
  3. サーバーAPI - WebSocket初期化API。
  4. クライアントAPI - 新しい友達購読API。
  5. クライアントAPI - 購読解除API。

データモデル

位置情報キャッシュ

  • キー: ユーザーID。
  • 値: {位置、経度、時刻}。

現在情報だけを保存する。
RedisはアクティブユーザーをTTL付きで保存できるため適している。

位置移動履歴データベース

  • カラム: ユーザーID、位置、経度、時刻。

大容量処理が求められるほど、シャーディングが必要なデータベースが必要になる。

3段階: 詳細設計

重要コンポーネント別のスケーラビリティ

APIサーバー

  • クラスターをCPU、I/O使用率に応じて自動的に増やす方法はさまざまである。

WebSocketサーバー

  • 使用率に応じて規模を自動的に増やすことは難しくない。
  • 自動で拡張するにはロードバランサーで対応できる。

クライアント初期化

  1. 位置情報キャッシュを更新する。
  2. すべての友達情報を取得する。
  3. アクティブなすべての友達の位置情報を一度に取得する。
  4. 非アクティブなユーザーはすでにTTLによって存在しないはずである。
  5. 受け取った友達位置それぞれに対してWebSocket接続を行う。
  6. WebSocketサーバーは各友達のRedis Pub/Subチャンネルを購読する。
  7. ユーザーの現在位置をRedis Pub/Subサーバーの専用チャンネルを通じてすべての友達へ送信する。

ユーザーデータベース

  • 保存されるデータ
    • ユーザーID、ユーザー名、プロフィール画像URLなど。
    • 友達関係データ。
  • 大容量向けにはユーザーIDでシャーディングされたデータベースが必要。
  • 規模が大きければ、実際にはユーザーおよび友達データを管理するチームが別途必要になる。

位置情報キャッシュ

  • 大容量処理を行うには、ユーザーIDを基準に複数サーバーへシャーディングすれば負荷を分散できる。
  • 可用性を高めるには、待機ノードを複製し、主ノードに障害が起きた場合に待機ノードを主ノードへ昇格させることで障害時間を短縮する。

Redis Pub/Subサーバー

  • Redis Pub/Subを選んだ理由は、チャンネルを作るコストが非常に低いためである。
  • Redis Pub/SubのボトルネックはメモリではなくCPU使用量である。
  • 予想されるメモリ使用量は約200GB程度で、100GBを搭載できるサーバーを使えばよい。
  • 位置情報更新は1秒あたり1,400万件 / サーバー1台で処理可能な購読者数は100,000人 = 約140台のサーバーを想定。
  • 大規模に対応するには、分散Redis Pub/Subクラスターが必要である。

分散Redis Pub/Subサーバークラスター

  • メッセージを発行するユーザーIDを基準にPub/Subサーバーをシャーディングすればよい。
    • すべてのチャンネルは互いに独立している。
  • 運用ではサービス探索(service discovery)コンポーネントを導入してこの問題を解決できる。
    • etcd、ZooKeeperなどがある。
  • 方法として一貫性ハッシュ(consistent hash)のハッシュリングを参照する。

友達の追加/削除

  • 友達の追加/削除時にコールバックを該当アプリに登録しておくことができる。
  • このコールバックが呼び出されると、WebSocketサーバーへ友達のPub/Subチャンネルを購読/購読解除するようメッセージを送る。

友達が多いユーザー

  • 友達5,000人までのみ処理し、方向を持つフォロワーモデルのような一方向関係は議論から除外する。
  • 数千人の友達を購読するために必要なPub/Sub購読関係は、クラスター内の多くのWebSocketサーバーに分散される。
  • 負荷は各ソケットサーバーが分担して処理するため、ホットスポット問題は発生しないだろう。

近くの任意ユーザー

  • ジオハッシュに基づいて構築されたPub/Subチャンネルプールを置く。
    • 詳細は省略。

Redis Pub/Sub以外の代替案

  • Erlangを代替として使用できる。
    • 詳細は省略。

4段階: まとめ

  • ユーザーの位置情報変更履歴をその友達へ効率よく伝えるシステムを設計した。
  • WebSocket、Redis、Redis Pub/Subがこの設計案の主要コンポーネントである。
  • 小規模から規模が大きくなるにつれて必要になる解決策も見た。