FacebookのようなSNSでは、「友達」「いいね」「コメント」「投稿者」「チェックイン先」といった関係を、画面を開くたびに高速でたどる必要があります。しかも、表示内容はユーザーごとの公開範囲や関係性によって変わるため、完成済みのページをあらかじめ作っておく方法では対応できません。
この問題に対してFacebookが構築したのが、ソーシャルグラフ専用の分散データストア TAO です。2013年にUSENIX ATCで発表された論文「TAO: Facebook’s Distributed Data Store for the Social Graph」では、TAOがどのような割り切りによって、毎秒10億回規模の読み取りを処理したのかが説明されています。
結論から言うと、TAOの強さは高機能なグラフデータベースを目指さず、Facebookで頻出する少数の操作に機能を絞ったことにあります。
TAOが解決したかった問題
TAO以前のFacebookでは、ソーシャルグラフをMySQLに保存し、PHPから問い合わせ、結果をmemcacheにキャッシュしていました。一般的な「キャッシュにあれば使い、なければDBから読む」構成です。
しかし、友達一覧やコメント一覧のような「辺のリスト」を扱うと、単純なキーバリュー型キャッシュには無理が出ます。1件のコメントが追加されただけでも一覧全体を読み直す必要があり、複数のアプリケーションサーバーが同じデータを同時に更新すると、キャッシュの整合性管理も複雑になります。
さらに、MySQLの非同期レプリケーションを使う環境では、書き込み直後に別地域のレプリカを読むと、まだ古い値が返る可能性があります。TAOは、これらの制御を各クライアントのPHPコードから切り離し、グラフ構造を理解する専用サービスに集約しました。
データモデルは「オブジェクト」と「関連」の2種類
TAOのデータモデルは非常に単純です。
- Object（オブジェクト）：ユーザー、投稿、コメント、場所などのノード
- Association（関連）：友達、投稿者、いいね、コメントの所属先などの有向エッジ
たとえば「AliceがゴールデンゲートブリッジにBobとチェックインし、Cathyがコメントし、Davidがそのコメントにいいねした」という出来事は、ユーザー・場所・チェックイン・コメントをオブジェクトとして持ち、それらを「友達」「投稿者」「タグ付け」「コメント」「いいね」といった関連で接続します。
関連は、始点ID・関連タイプ・終点IDで識別され、時刻フィールドを持ちます。この時刻を使って「最新のコメント50件」のような問い合わせを効率よく処理します。
TAOは任意の複雑なグラフ探索を実行するシステムではありません。主なAPIは、オブジェクトの取得・更新と、関連の追加・削除・件数取得・範囲取得です。用途を限定したからこそ、キャッシュやシャーディングを徹底的に最適化できました。
MySQLを捨てず、その前段に巨大なグラフ対応キャッシュを置く
TAOの永続ストレージはMySQLです。Facebookはデータを多数の論理シャードに分割し、オブジェクトIDの中にシャードIDを埋め込みました。関連データは始点オブジェクトと同じシャードに保存するため、特定オブジェクトから伸びる関連一覧は原則として1台のDBで処理できます。
その前段に、TAO独自のキャッシュ層を配置します。キャッシュは単なる値の保存場所ではなく、オブジェクト、関連一覧、関連件数を理解し、完全に同じ問い合わせが過去になくても、保持している情報から答えを組み立てられます。
キャッシュはLRU方式で入れ替えられますが、データ型ごとにメモリ領域を分け、アクセスの多い型が他の重要データを追い出さないようにしています。また、極端に人気のあるオブジェクトはシャードを複製したり、クライアント側にも小さなキャッシュを持たせたりして、ホットスポットを分散します。
LeaderとFollowerで読み取りを水平分散する
各地域のキャッシュは、1つのLeader層と複数のFollower層に分かれます。
- Follower：通常の読み取りを担当し、キャッシュミスや書き込みをLeaderへ転送
- Leader：DBとの通信を担当し、同じシャードへの書き込みを直列化
クライアントは最寄りのFollowerにアクセスするため、Followerを増やせば読み取り性能を伸ばせます。LeaderはDBへの重複問い合わせを抑え、キャッシュミスが集中してDBに大量アクセスが発生する「thundering herd」も防ぎます。
世界規模では「読み取りは近く、書き込みはマスターへ」
データセンター間が数千キロ離れると、すべての読み取りをマスター地域へ送る設計では遅延が大きくなります。TAOは、地域ごとにソーシャルグラフ全体のDBコピーとキャッシュを持ち、読み取りのキャッシュミスは地域内のレプリカDBで処理します。
一方、書き込みは、そのシャードのマスターDBがある地域へ転送します。更新内容はMySQLのレプリケーションストリームとともに他地域へ伝わり、キャッシュの無効化や再取得が行われます。
この構成により、読み取り遅延は地域間ネットワークの往復時間に左右されません。ただし、レプリケーションが完了するまで他地域では古いデータが見える可能性があります。
強い整合性より、可用性と速度を選ぶ
TAOは 結果整合性 を採用しています。更新後、最終的にはすべてのコピーが同じ状態になりますが、常に最新値が返るとは限りません。
ただし通常時は、書き込みを実行したFollowerのキャッシュを同期的に更新するため、同じキャッシュ層を使い続ければ、書き込み直後の読み取りで新しい値を確認できる「read-after-write consistency」を多くの場合で実現します。
認証など古いデータが危険な処理では、読み取りをマスター地域へ転送する「critical read」も用意されています。すべてを強整合にするのではなく、必要な処理だけコストを払う設計です。
論文で示された本番規模と性能
論文執筆時点のTAOは、数千台のマシンと数ペタバイトのデータを扱い、毎秒10億回の読み取りと数百万回の書き込みを処理していました。
| 指標 | 論文での値 |
|---|---|
| リクエスト構成 | 読み取り99.8%、書き込み0.2% |
| 読み取りキャッシュヒット率 | 96.4% |
| キャッシュヒット時の中央値 | 主な読み取りで約1.0〜1.3ms |
| キャッシュミス時の中央値 | 約5.0〜8.2ms |
| 90日間の問い合わせ失敗率 | 4.9×10^-6 |
| 地域間レプリケーション遅延 | 85%が1秒未満、99%が3秒未満 |
特に重要なのは、Facebookの負荷が圧倒的に読み取り中心だった点です。汎用性や書き込みの強い整合性を犠牲にしてでも、読み取りの局所性とキャッシュ効率を最大化する判断には、実際のワークロード分析という根拠がありました。
TAOから学べる設計上のポイント
1. 汎用性を削ると、規模を伸ばしやすくなる
TAOは、複雑なグラフクエリや分散トランザクションを提供しません。その代わり、実際に頻出する操作を固定し、キャッシュ、ルーティング、障害処理を最適化しました。
2. データモデルを理解するキャッシュは強い
単純なキーバリューキャッシュでは、関連一覧の差分更新や逆向きエッジの管理が難しくなります。TAOはキャッシュ自体がグラフの意味を理解することで、制御を中央集約しました。
3. 整合性は一律ではなく、処理ごとに選ぶ
ニュースフィードの「いいね」が数秒遅れることと、認証情報が古いことは、同じ問題ではありません。TAOは通常処理を結果整合にし、重要な読み取りだけマスターに送ります。
4. アーキテクチャは実測した負荷に合わせる
TAOの設計は、読み取りが99.8%を占めるFacebookの負荷に特化しています。書き込み中心のサービスや、残高・在庫のように強整合性が不可欠なシステムへ、そのまま適用すべき設計ではありません。
まとめ
TAOは「万能なグラフデータベース」ではなく、巨大なソーシャルグラフを低遅延で配信するための専用システムです。
MySQLを信頼できる永続ストレージとして残し、その前段にグラフ構造を理解する多層キャッシュを置く。読み取りを各地域で完結させ、書き込みはマスターへ集約する。強い整合性は必要な場所だけに限定する。この一連の割り切りによって、Facebookは非常に大きな読み取り負荷を現実的なコストで処理しました。
この論文の本質は、「最高性能の技術を選ぶこと」ではなく、実際の負荷と許容できる不整合を測り、不要な機能を削ってシステム全体を設計することにあります。
参考論文
Nathan Bronson et al., “TAO: Facebook’s Distributed Data Store for the Social Graph,” USENIX Annual Technical Conference, 2013.
本記事の数値と構成は2013年の論文発表時点の内容です。現在のMetaの内部システム構成を示すものではありません。
