論文メモ TAO: Facebook's Distributed Data Store for the Social Graph

February 4, 2021

TAOは、Facebookで開発されたソーシャルグラフのためのマルチリージョンの分散システムで、秒間で10億件の読み込みと数百万件の書き込みの性能を誇る。 Facebookは、もともと、ソーシャルグラフをMySQLに保存し、memcacheをキャッシュにつかい、PHPで問いあわせるシステムを構成していた。 TAOは、そのシステムの現状を引きつぎ、MySQLをストレージに採用している。

TAOでは、ソーシャルグラフのノードをobject, 辺をassociationとよぶ。 objectは、64ビットの整数値のidで一意に特定できる。 associationは、値のほかに32ビットで時間をあらわすtimeをもつ。 objectとassociationには連想配列でデータをもたせることができる。 以下のid1, id2はオブジェクトのIDであり、otype, atypeはobjectやassociationがあらわすソーシャルグラフ上の意味にあたる。

Object: (id) -> (otype, (key -> value)*)
Assoc.: (id1, atype, id2) -> (time, (key -> value)*)

TAOは、associationのクエリAPIを提供する。 ユーザは、例えば、id1, atypeでassociationの件数をかぞえたり、associationを検索できたりする。 ソーシャルグラフの多くのデータは古く、一方で、クエリの対象になるデータは新しいものが多い。 この時間の局所性を活かすために、内部では、idatypeが同じassociationは時間順に並べて管理される。 この配列はassociation listとよばれ、次の構造をとる。

Association List: (id1, atype) -> [a_new ... a_old]

TAOは、永続層とキャッシュ層をもつ。 永続層にシャーディングをもちいたMySQLがある。 キャッシュ層にはLeader, Followerの2種類のキャッシュサーバがある。 また、TAOは複数のデータセンタ上に展開されており、データセンタのまとまりをregionといい、regionはMasterとSlaveで区別される。 以下の図は、TAOの全体像をしめす。 tao

objectを格納するシャードはobject idで、assiciationはid1できまる。 これらのIDは、保存先のシャードを特定するID shard_idをふくむ。

複数のキャッシュサーバのまとまりをtierという。 全てのキャッシュサーバが互いに通信するとホットスポットができるため、キャッシュ層は、一つのleader tierと複数のfollower tierに分割されている。 leader tierは、永続層への読み込み、書き込みを担当する。 followerは読み込みミスや書き込みリクエストをleaderに送る。 followerは、ほかのtierに問いあわせなくても、どんなリクエストであっても応答できる。 クライアントは、follower tierと通信し、leaderには直接リクエストを送らない。

各シャードはひとつのleaderに対応づけられ、書き込みは対応するleaderからしか送られない。 leaderがobjectを更新すると、キャッシュを無効にするメッセージ(invalidation message)をfollwerに送る。 メッセージにはバージョン番号がふくまれており、followerは、番号からメッセージの新しさを調べ、古いものを無視する。 更新によって、followerにキャッシュされた大量のassociationが無効になることがある。 そのため、leaderは、refillメッセージをfollowerにおくり、association listを再キャッシュするようfollowerに伝える。

巨大なソーシャルグラフのホスティングするために、TAOは複数のデータセンタをまたいで展開されている。 複数のデータセンタのまとまりをregionとよばれ、少数のregionが存在する。 各regionは、ソーシャルグラフ全体の複製をホスティングしている。 ネットワークのレイテンシを抑えるために、masterのregionとslaveのregionのmaster/slave構成をとり、どんな読み込みリクエストも単一のregion内で完結される。 masterとslaveにあるfollowerはどちらも同じ動きをするが、slaveのleaderは、read missが生じても、ローカルのfollowerに古いデータを返す。 データの新しさを犠牲にすることで、master regionへのリクエストにかかる時間を省いている。 slaveのleaderは書き込みリクエストをmasterのleaderに伝達する。 前述のinvalidationやrefillメッセージは、MySQLのレプリケーションストリームにふくまれ、トランザクションが複製された直後に伝達される。

論文をこちらからダウンロードできます。 また、図はすべて論文から引用されています。